Laboratorio di calcolo numerico e informatica

Informatica

Fabiola

2016

2

Indice

1 Concetti introduttivi 7

1.1 Il teorema di Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Teoremi del valore medio e dei valori estremi . . . . . . . . . . . . . . . . . . . . 7

1.3 Errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Brevi richiami sull'aritmetica dell'elaboratore . . . . . . . . . . . . . . . . . . . . 9

1.5 Approssimazioni semplici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Rassegna di metodi semplici 11

2.1 Regola di Horner e moltiplicazione nidicata . . . . . . . . . . . . . . . . . . . . 11

2.2 Approssimazioni alle dierenze della derivata . . . . . . . . . . . . . . . . . . . . 11

3 Ricerca delle radici di un'equazione 13

3.1 Il metodo di bisezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1.1 Errore e convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 La Regula falsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Il metodo di Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.3.1 Un criterio di arresto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3.2 La formula dell'errore di Newton . . . . . . . . . . . . . . . . . . . . . . 17

3.4 Il metodo della secante (Newton discretizzato) . . . . . . . . . . . . . . . . . . . 18

3.5 Iterazione del punto sso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Stocastica sperimentale 21

4.0.1 Algoritmi di generazione . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.1 Tecnica di congruenza lineare (Lehmer, 1951) . . . . . . . . . . . . . . . . . . . 23

4.2 Generatori Tausworthe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3 Algoritmo di Mersenne Twister . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.4 Generatore Minimal Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.5 Altre distribuzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.5.1 Distribuzione esponenziale . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.5.2 Algoritmo di Box Muller (gaussiana) . . . . . . . . . . . . . . . . . . . . 25

4.6 Metodo Montecarlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

π

4.6.1 Determinazione del valore di . . . . . . . . . . . . . . . . . . . . . . . . 26

4.6.2 Integrazione numerica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5 Integrazione numerica 29

5.1 Interpolazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2 Il metodo dei trapezi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.3 Il metodo dei rettangoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3

4 INDICE

5.4 Il metodo di Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.5 Regole di Quadratura Composte . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.5.1 Il metodo Midpoint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.6 Formule di quadratura Gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.6.1 Formule di Gauss-Legendre . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.7 Integrale di funzioni discontinue . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6 Equazioni Dierenziali Ordinarie 41

6.1 Algoritmo di Eulero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.2 Algoritmo di Eulero perfezionato . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.3 Algoritmo di Eulero-Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.4 Metodi Predictor-Corrector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.5 Metodi di Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.5.1 Adaptive stepsize control . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

7 Il caos deterministico 47

7.1 L'equazione logistica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

7.1.1 L'equazione di Malthus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

7.1.2 L'equazione di Verhulst . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

7.2 La mappa logistica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7.2.1 Il numero di Feigenbaum . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

7.3 Insiemi caotici e frattali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

7.3.1 Caratteristiche dei frattali . . . . . . . . . . . . . . . . . . . . . . . . . . 57

7.3.2 La curva di Koch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

7.3.3 Il metodo del box-counting . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.3.4 Sierpinski gasket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.4 Esempi di frattali reali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

8 Automi cellulari 65

8.0.1 Denizione formale di AC . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.1 Regole di transizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

8.1.1 Automa 1-D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

8.2 Nomenclatura di Wolfram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

8.3 Regole totalistiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8.4 Regole multi-step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.5 Regole di transizione probabilistiche . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.5.1 Simulazione di incendi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.6 Il "Game of Life" di John Conway . . . . . . . . . . . . . . . . . . . . . . . . . . 74

9 Automi Cellulari e 75

− −

0 D 1 D

−

0 D

9.1 Automi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

9.1.1 Entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

9.1.2 Congettura di Ulam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

−

1 D

9.2 Automi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

9.2.1 Regole di transizione e kernel di convoluzione . . . . . . . . . . . . . . . 78

5

INDICE

10 Automi Cellulari probabilistici: percolazione e SOC 81

−

2 D

10.1 Percolazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

10.2 Modello di Sand Pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

10.3 SOC in altri sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

10.3.1 Fenomeni sismici (movimenti delle placche) . . . . . . . . . . . . . . . . . 84

10.3.2 Forest re (incendi) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

10.3.3 Rumor Mill (diusione di un pettegolezzo) . . . . . . . . . . . . . . . . . 86

11 Automi Cellulari Dissipativi 87

11.0.1 AC asincrono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

11.0.2 AC aperto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6 INDICE

Capitolo 1

Concetti introduttivi

1.1 Il teorema di Taylor

Il risultato più importante nella computazione numerica è il Teorema di Taylor.

Teorema di Taylor con resto f (x) n + 1 [a, b]

Sia una funzione avente derivate continue su

∈

n> 0 x, x [a, b]

per qualche e siano . Allora

0 f (x) = p (x) + R (x)

n n

con k

n (x−x ) (k)

P 0 f (x )

p (x) = 0

n k=0 k!

e x

1 R n n+1

−

R (x) = (x t) f (t) dt

n n! x 0

∃ξ ∈ (x, x )

Inoltre, t.c.

x 0 n

(x−x ) (n+1)

0

R (x) = f (ξ )

n x

(n+1)!

x

Di solito il punto iniziale è scelto pari a 0. Il tipo di problema da arontare è costruire

0

approssimazioni semplici per calcoli complessi e conoscerne la precisione.

1.2 Teoremi del valore medio e dei valori estremi

Teorema del valor medio ∃ξ ∈

f [a, b] (a, b) [a, b]

Data continua in e dierenziabile su , tale

che f (b)−f (a)

0

f (ξ) = b−a

Se riscriviamo la formula precedente come 0

− −

f (x ) f (x ) = f (ξ)(x x )

1 2 1 2

notiamo che questa ci permette di sostituire la dierenza di due valori della funzione con la

1

dierenza dei valori dei corrispondenti argomenti. Analogo è il teorema dei valori intermedi.

1 Ad esempio, possiamo determinare che , dal momento che la derivata del coseno

|cosx − | ≤ |x − |

cosx x

1 2 1 2

è il seno che, in modulo, è maggiorato da .

1 7

8 CAPITOLO 1. CONCETTI INTRODUTTIVI

Teorema dei valori intermedi ∈ C([a, ∀ ≤ ≤ ∃ ∈

f b]), W f (a) W f (b) c [a, b]

Data t.c.

f (c) = W

t.c. . Questo teorema ci fornisce un metodo per la ricerca degli zeri di una funzione

metodo di bisezione

( ) ed è quello che ci dice che una funzione continua è quella il cui graco

può essere disegnato senza staccare la penna dal foglio. Un risultato attinente è il Teorema dei

valori estremi.

Teorema dei valori estremi ∈ C([a, ∃ ∈ ≤ ∀ ∈

f b]) m [a, b] f (m) f (x) x [a, b]

Data t.c.

∃ ∈ ≥ ∀ ∈

M [a, b] f (M ) f (x) x [a, b] f

e t.c. . Se inoltre è derivabile, assume il suo valore

massimo e minimo in un punto critico.

Teorema della media integrale ∈ C([a,

f, g b]) g

Siano e supponiamo che non cambi segno

∃ξ ∈

[a, b] [a, b]

in . Allora t.c. b b

R R

g(t)f (t)dt = f (ξ) g(t)dt

a a

Teorema della media discreta ∈ C([a,

f b])

Sia e si consideri la somma

n

P

S = a f (x )

k k

k=1

∈

x [a, b]

dove ogni punto e i coecienti vericano

k n

P

≥ a = 1

a 0; k

k k=1

∃η ∈ [a, b] f (η) = S

Allora t.c. , cioè n

P a f (x )

f (η) = k k

k=1

1.3 Errore

A A

Se è una quantità che vogliamo calcolare ed una sua approssimazione, allora l'errore è

h

dato dalla dierenza dei due valori −

errore = A A

h

e l'errore assoluto è dato dal valore assoluto |A − |

errore assoluto = A

h

mentre l'errore relativo si ottiene |A−A |

h

errore relativo = |A|

|A| 6

= 0

assumendo .

L'errore relativo fornisce una misura del numero di cifre correttamente approssimate, quindi

|x−y| =1

|x| −9

10 9

indica che non molte cifre coincidono, mentre un valore dell'ordine di indica che circa

cifre sono corrette. h 0 n

Di solito si indica con un parametro reale che tende a e con un parametro che tende

invece all'innito. 9

1.4. BREVI RICHIAMI SULL'ARITMETICA DELL'ELABORATORE

1.4 Brevi richiami sull'aritmetica dell'elaboratore

La maggior arte dei linguaggi dell'elaboratore usa la cosiddetta aritmetica a virgola mobile

oating point

( ). L'idea di base è la stessa: ogni numero viene rappresentato usando un numero

bit

sso di cifre binarie, dette . Un'implementazione tipica è della forma

t−p

x = σ f β

x x

σ f

dove rappresenta il segno del numero, rappresentato da un singolo bit, è la mantissa o

β 2 t

frazione, è la base del sistema di numerazione (di solito binario, quindi ), è l'esponente

p

traslato, ossia il valore eettivamente memorizzato, la traslazione da eettuare per ottenere

l'esponente eettivo. word 2

Il numero totale di bit usati è di solito 32 bit per una , organizzati con 24 bit per la

frazione, 7 bit per l'esponente e un bit per il segno. Questo impone ovviamente dei limiti al

numero che può essere rappresentato. overow

Eventuali tentativi di memorizzare esponenti più grandi producono un cosiddetto ,

underow 3

mentre più piccoli un .

precisione di macchina

Deniamo (o epsilon di macchina) il più grande numero a virgola

x x +1 1

mobile tale che non può essere distinto da sul computer

0

{x|1

u = max + x = 1 nell aritmetica del computer}

1.5 Approssimazioni semplici

funzione errore

La è denita mediante un integrale

x 2

−t

2 R e dt

erf (x) = √ 0

π

Non è possibile valutare questo integrale mediante i teoremi fondamentali di analisi: non c'è

2

−t

e

una primitiva elementare di . Approssimando la funzione integranda con un polinomio

(usando cioè il teorema di Taylor), si arriva ad un'espressione dell'errore che lo divide in tre

parti distinte:

• C

una costante numerica ;

• un'espressione che dipende dai parametri computazionali del problema;

• un fattore che dipende dalla funzione o dalle sue derivate, valutate in un punto indeter-

minato.

La costante è di solito poco interessante, perchè non si può far nulla per minimizzarla; la

parte che dipende dalla funzione ci interessa relativamente nelle approssimazioni più complesse,

in genere non siamo in grado di computare questo valore e ricorriamo quindi a delle maggiora-

zioni. La parte dell'errore che determina la convergenza, l'accuratezza e quanto velocemente si

raggiungono entrambe è quella dipendente dal parametro, ed è questa parte ad essere sotto il

nostro controllo.

2 Una è la più grande unità di memoria del computer, di solito costituita da due o più , costituiti

word byte

da un certo numero di bit, tipicamente 8.

3 Nel moderno standard IEEE in aggiunta ai numeri ordinari è permesso avere come risultati (innito),

Inf

(non un numero) e sono incluse regole per eseguire operazioni tra i numeri a virgola mobile e questi valori

NaN

speciali. Un tempo se si vericava un overow o una divisione per l'esecuzione del programma terminava.

0

10 CAPITOLO 1. CONCETTI INTRODUTTIVI

Capitolo 2

Rassegna di metodi semplici

2.1 Regola di Horner e moltiplicazione nidicata

Il metodo più eciente per valutare un polinomio è la moltiplicazione nidicata. Se abbiamo

2 n

p (x) = a + a x + a x + ... + a x

n 0 1 2 n

x

allora fattorizziamo le potenze di secondo n−2

p (x) = a + x(a + x(a + ... + a x ))

n 0 1 2 n

n +1 n

In questo modo il calcolo richiede moltiplicazioni ed addizioni, mentre il calcolo della

prima forma richiede la stessa quantità di lavoro ma in più il "costo" della valutazione delle

regola di

n−

potenze esime. La forma algoritmica della moltiplicazione nidicata è nota come

Horner , e può essere facilmente modicata anche per calcolare la derivata prima del polinomio.

2.2 Approssimazioni alle dierenze della derivata

Una delle applicazioni più semplici del teorema di Taylor coinvolge l'uso dei quozienti di dif-

f

ferenze per approssimare la derivata di una funzione nota. Intuitivamente è ovvio dalla

denizione di derivata che f (x+h)−f (x)

0 ≈

f (x) h

Determiniamo l'accuratezza dell'approssimazione mediante un calcolo che coinvolge il teorema

di Taylor 12 00

0 2 1

h f (x)+ h f (ξ )

f (x+h)−f (x) 0 00

0 1

x,h

− −

− = f (x) = h f (ξ )

f (x) x,h

h h 2

per cui f (x+h)−f (x)

0 00

12

− −

f (x) = h f (ξ ) = O(h)

x,h

h h

cioè l'errore è proporzionale al parametro . Se consideriamo gli sviluppi di Taylor

0 00 000

1 16

2 3

h f (x) + h f (ξ )

f (x + h) = f (x) + h f (x) + 1

2

1 00

0 1 2

f (x + h) = f (x) + h f (x) + h f (ξ)

2 11

12 CAPITOLO 2. RASSEGNA DI METODI SEMPLICI

e 0 00 000

1 16

2 3

− − −

f (x h) = f (x) h f (x) + h f (x) h f (ξ )

2

2

Sottraendo la seconda dalla prima si ottiene 0 000 000

1 1

3 3

− −

f (x + h) f (x h) = 2 h f (x) + h f (ξ ) + h f (ξ )

1 2

6 6

0

f (x)

Da quest'ultima è possibile ricavare 000 000

f (x+h)−f (x−h) f (ξ )+f (ξ )

0 16 2

− 1 2

f (x) = h

2h 2

e concludere f (x+h)−f (x−h)

0 000

16 2

−

f (x) = h f (ξ )

x−h

2h

Vediamo che le stime dell'errore sono molto diverse: la prima approssimazione ha un errore che

00 000

f h f

dipende da ed è proporzionale ad mentre la seconda dipende da ed è proporzionale ad

2

h . La seconda stima tenderà ad essere migliore.

Capitolo 3

Ricerca delle radici di un'equazione

α f

Discuteremo alcuni metodi per trovare il punto , denito come uno zero della funzione , cioè

f (α) = 0 y = f (x)

tale che , con generica funzione.

3.1 Il metodo di bisezione f f (a)f (b) < 0

Si basa essenzialmente sulla continuità della : supponiamo di avere . Per il

f

teorema dei valori intermedi ci deve essere un valore nell'intervallo in cui è nulla, cioè deve

α a b c

esistere radice tra e . (Da notare che ci può essere più di una radice nell'intervallo). Sia

denito come (b−a)

c = 2

f (a)f (c)

e consideriamo . Possiamo avere tre casi:

• f (a)f (c) < 0 a c

: una radice si trova tra e ;

• 6

f (a)f (c) = 0 f (a) = 0 α = c

: sappiamo che , dunque ;

• f (a)f (c) > 0

: una radice si trova nell'altra metà dell'intervallo.

3.1.1 Errore e convergenza

[a , b ] = [a, b] f (a)f (b) < 0

Sia l'intervallo iniziale, con , deniamo la radice approssimata come

0 0 −a

(b ) ∈

n−1 n−1

x = c = α [a, b]

. Allora esiste t.c.

n n 2 1 n

|α − | ≤ −

x ( ) (b a)<