Appunti Calcolo numerico

UNIVERSITÀ DEGLI STUDI DI BERGAMO

Dipartimento di Ingegneria e Scienze Applicate

Metodi numerici

·

Fattorizzazione LU Metodi iterativi

·

Gradiente coniugato Metodo di Newton

·

Interpolazione e quadratura Metodi di Eulero

Corso Calcolo numerico

Docente prof.ssa Nicoletta Franchina

Appunti a cura di Cristiano Rollo

Anno accademico 2020/2021

Indice

Notazione 6

I L’eliminazione gaussiana e la fattorizzazione LU 8

1 Il problema dei sistemi lineari e la formula di Cramer 9

1.1 Posizione del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 La formula di Cramer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Il costo computazionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 I sistemi triangolari e i metodi di sostituzione 11

2.1 La matrice triangolare inferiore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 La matrice triangolare superiore . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Esercizio: l’algoritmo della sostituzione in avanti . . . . . . . . . . . . . . . . . 13

3 La fattorizzazione LU e il metodo di eliminazione gaussiana 14

3.1 Il teorema di fattorizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Il metodo di eliminazione gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Esempio: la fattorizzazione di una matrice di Hilbert . . . . . . . . . . . . . . . 16

4 Il pivoting e la matrice di permutazione 17

4.1 Il caso di arresto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.2 Il pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.3 La matrice di permutazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

II L’algoritmo di Cholesky e l’algoritmo di Thomas 20

5 Le condizioni di fattorizzabilità e l’algoritmo di Cholesky 21

5.1 Le condizioni sufficienti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.2 Le matrici simmetriche definite positive . . . . . . . . . . . . . . . . . . . . . . . 21

5.3 L’algoritmo di Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

6 L’algoritmo di Thomas e le matrici sparse 23

6.1 La matrice tridiagonale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.2 L’algoritmo di Thomas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.3 Le matrici sparse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.4 Il fenomeno del fill-in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

III Il numero di condizionamento 26

7 La propagazione degli errori di arrotondamento 27

7.1 Il modello dell’errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1

Indice 2

7.2 Perché la domanda non è oziosa . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

8 Il numero di condizionamento e le norme di matrice 28

8.1 La norma di matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

8.2 Il teorema di propagazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

8.3 Il pivoting come rimedio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

IV I metodi di Jacobi, Gauss–Seidel e SOR 30

9 I metodi iterativi: consistenza e convergenza 31

9.1 L’impostazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

9.2 La legge di aggiornamento lineare . . . . . . . . . . . . . . . . . . . . . . . . . . 31

9.3 La consistenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

10 Lo splitting della matrice e il raggio spettrale 33

10.1 La propagazione dell’errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

10.2 Il raggio spettrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

10.3 Lo splitting della matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

11 I metodi di Jacobi, Gauss–Seidel e SOR 35

11.1 Il metodo di Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

11.2 Il metodo di Gauss–Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

11.3 Il metodo SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

11.4 I risultati di convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

V Il metodo di Richardson e il metodo del gradiente 38

12 Il metodo di Richardson e il parametro ottimale 39

12.1 Il residuo e la legge di aggiornamento . . . . . . . . . . . . . . . . . . . . . . . . 39

12.2 La condizione di convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

12.3 Il parametro ottimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

13 Il funzionale dell’energia e il metodo del gradiente 42

13.1 Il funzionale dell’energia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

13.2 Il metodo del gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

13.3 Il passo ottimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

14 La convergenza del metodo del gradiente 44

14.1 Il teorema di convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

14.2 L’interpretazione geometrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

VI Il metodo del gradiente coniugato 46

15 Le direzioni coniugate e l’algoritmo del gradiente coniugato 47

15.1 L’ottimalità rispetto a una direzione . . . . . . . . . . . . . . . . . . . . . . . . . 47

15.2 Le direzioni coniugate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

15.3 La costruzione delle direzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

15.4 L’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Indice 3

15.5 La terminazione finita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

16 Il confronto fra i metodi di discesa 50

16.1 I tre fattori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

16.2 Che cosa la stima non dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

VII Il precondizionamento 52

17 Il gradiente precondizionato e i precondizionatori 53

17.1 Il tentativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

17.2 Il prezzo di ogni iterazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

17.3 Le due richieste, e la loro contrapposizione . . . . . . . . . . . . . . . . . . . . . 54

17.4 I tre precondizionatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

18 I criteri d’arresto 56

18.1 Il criterio sul residuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

18.2 Il criterio sull’incremento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

VIII Il metodo di Newton e il metodo delle secanti 58

19 La ricerca delle radici e il metodo della corda 59

19.1 Posizione del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

19.2 Le due proprietà con cui si classificano i metodi . . . . . . . . . . . . . . . . . . 60

19.3 Il metodo della corda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

20 Il metodo di Newton e il metodo di Newton modificato 61

20.1 Il metodo di Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

20.2 Il metodo di Newton modificato . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

21 Il metodo delle secanti e il controllo dell’errore 63

21.1 Quando la funzione è data per punti . . . . . . . . . . . . . . . . . . . . . . . . . 63

21.2 Il controllo dell’errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

IX Le iterazioni di punto fisso 66

22 Il problema dei punti fissi e la sua convergenza 67

22.1 Posizione del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

22.2 Due esempi che si comportano in modo opposto . . . . . . . . . . . . . . . . . . 68

22.3 La condizione di convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

22.4 L’ordine di convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

23 Il metodo di Newton come iterazione di punto fisso 70

23.1 Il legame fra radici e punti fissi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

23.2 Newton come iterazione di punto fisso . . . . . . . . . . . . . . . . . . . . . . . 70

23.3 La dimostrazione dell’ordine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

23.4 Una precisazione sulla linearità . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Indice 4

X Il metodo di Newton per i sistemi non lineari 72

24 I sistemi di equazioni non lineari e la matrice jacobiana 73

24.1 Posizione del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

24.2 Il metodo di Newton per i sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . 73

24.3 Ordine e costo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Newton

25 L’inexact e il metodo di Newton–Krylov 75

p

25.1 Aggiornare lo jacobiano ogni passi . . . . . . . . . . . . . . . . . . . . . . . . . 75

Newton

25.2 L’inexact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

25.3 Il metodo di Newton–Krylov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

25.4 I due criteri d’arresto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

XI L’interpolazione di Lagrange 79

26 L’approssimazione di funzioni e il polinomio di Lagrange 80

26.1 Le due situazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

26.2 Il polinomio interpolatore di Lagrange . . . . . . . . . . . . . . . . . . . . . . . 81

26.3 Che il polinomio interpoli davvero . . . . . . . . . . . . . . . . . . . . . . . . . . 82

26.4 L’unicità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

27 L’errore di interpolazione e il fenomeno di Runge 83

27.1 La stima dell’errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

27.2 La funzione di Runge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

28 L’interpolazione composita e i nodi di Chebyshev 85

28.1 L’interpolazione lagrangiana composita . . . . . . . . . . . . . . . . . . . . . . . 85

28.2 L’interpolazione sui nodi di Chebyshev . . . . . . . . . . . . . . . . . . . . . . . 86

XII L’interpolazione trigonometrica e i minimi quadrati 88

29 L’interpolatore trigonometrico e la trasformata di Fourier 89

29.1 La base trigonometrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

29.2 I coefficienti e la trasformata di Fourier . . . . . . . . . . . . . . . . . . . . . . . 89

29.3 Il problema dell’aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

29.4 Il limite comune delle tecniche interpolatorie . . . . . . . . . . . . . . . . . . . . 90

30 Il metodo dei minimi quadrati e la retta di regressione 92

30.1 Il metodo dei minimi quadrati . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

30.2 La retta di regressione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

XIII Le formule di quadratura interpolatorie 94

31 Le formule di quadratura e il grado di esattezza 95

31.1 Le formule di quadratura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

31.2 Le due grandezze che misurano una formula . . . . . . . . . . . . . . . . . . . . 95

31.3 Le formule di quadratura interpolatorie . . . . . . . . . . . . . . . . . . . . . . . 96

31.4 Il grado di esattezza di una formula interpolatoria . . . . . . . . . . . . . . . . . 96

Indice 5

32 Il punto medio, i trapezi e la formula di Simpson 97

32.1 La formula del punto medio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

32.2 La formula dei trapezi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

32.3 La formula di Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

32.4 Il caso generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

33 La quadratura gaussiana sui nodi di Legendre 101

33.1 Il limite delle formule a passo costante . . . . . . . . . . . . . . . . . . . . . . . 101

33.2 La quadratura gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

XIV I metodi di Eulero e di Crank–Nicolson 103

34 Il problema di Cauchy e l’approssimazione delle derivate 104

34.1 Il problema di Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

34.2 L’approssimazione delle derivate . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

34.3 Eulero e Cauchy: la differenza che governa il capitolo . . . . . . . . . . . . . . . 105

35 I metodi di Eulero in avanti e all’indietro 107

35.1 Il metodo di Eulero in avanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

35.2 Il metodo di Eulero all’indietro . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

35.3 I due algoritmi a confronto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

35.4 Il caso lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

36 L’accuratezza, la consistenza e la zero-stabilità 110

36.1 L’accuratezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

36.2 L’errore di troncamento locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

36.3 La zero-stabilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

36.4 I due errori di un passo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

36.5 Il teorema di equivalenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

37 Il metodo di Crank–Nicolson e l’assoluta stabilità 114

37.1 Il metodo di Crank–Nicolson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

37.2 Che cosa succede a passo finito . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

37.3 L’assoluta stabilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

37.4 Come si sceglie il metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

XV I metodi di Adams 118

38 I metodi di Adams–Bashforth e di Adams–Moulton 119

38.1 L’impostazione integrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

38.2 I metodi di Adams–Bashforth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

38.3 I metodi di Adams–Moulton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Notazione

Le grandezze che ricorrono in più di un capitolo sono raccolte qui con il simbolo adottato nel

testo. I simboli usati in un capitolo solo sono definiti dove compaiono, in legenda attaccata

alla formula. Le matrici sono indicate con la maiuscola corsiva, i vettori con il grassetto —

che rende la sottolineatura degli appunti — e le loro componenti con la minuscola corsiva e

l’indice.

Sistemi lineari ( )

k

A i, j; A

A. Matrice dei coefficienti del sistema; è l’elemento di posto è la matrice

ij

k-esima

trasformata alla passata dell’eliminazione gaussiana.

x. b n

Vettore delle incognite; il vettore dei termini noti; l’ordine del sistema.

=

L, U. A LU:

Fattori della fattorizzazione triangolare inferiore a diagonale unitaria e

L̂, Û inesatta.

triangolare superiore. sono i fattori della fattorizzazione

− − − −

=

D, E, F. A D E F

Decomposizione in diagonale, triangolare inferiore stretta e

triangolare superiore stretta. − 1

∥ ∥ ∥ ∥

( ) ( ) =

K A K A A A

Numero di condizionamento, .

. = =

Autovalori; e sono i due estremi dello spettro.

.

λ λ λ λ λ

n

max min

1

j

Metodi iterativi e di discesa

( ) ( ) ( ) ( ) ( )

k k k k k

− −

x e x x r b

= =

k-esima; Ax

Iterata è l’errore e il residuo.

. ( + ) ( )

k k

1

x f f

= +

B. Bx

Matrice di iterazione della legge ; il suo termine noto.

|

( ) ( ) = ( )|

B B B

Raggio spettrale, max .

.

ρ ρ λ

j j

Passo dei metodi di discesa; il parametro di rilassamento di SOR.

.

α ω

k

( )

k

p Direzione di avanzamento del gradiente coniugato; il coefficiente che la mantiene

. β k

coniugata.

Φ Φ 12 T T T

2

− ∥ ∥

y y y b; z z

( ) = =

Ay Az

Funzionale dell’energia, è la norma dell’energia.

. A

Tolleranza dei criteri d’arresto.

ε.

Equazioni non lineari ( ) =

f f

Radice di , cioè il valore per cui 0.

α. α

Φ, Φ ( ) =

Punto fisso di cioè il valore per cui

β. β β.

( + ) ( )

k k p

1

| − | ≤ | − |

p. x C x

Ordine di convergenza: .

α α

( + ) ( ) ( )

k k k

1 −

= ( )

x x f x

Fattore che nella forma comune distingue corda, Newton e secanti.

γ. γ

m. Molteplicità della radice.

[ ] =

J J f F

Matrice jacobiana, /∂x ; la funzione vettoriale del sistema non lineare.

. ∂

F F ij i j

Approssimazione, quadratura e differenziali

=

x y i n.

Nodi e valori assegnati, 0, . . . ,

, .

i i 6

NOTAZIONE 7

Π Π kh

n; h;

Polinomio interpolatore di grado la sua versione composita su passo le

. φ

n j

funzioni lagrangiane.

h. Passo fra i nodi, sia nell’interpolazione sia nella quadratura.

I, I Integrale esatto e integrale approssimato; i pesi della formula di quadratura.

. α

n i

n

( )

y t u S