Calcolo numerico

Calcolo Numerico

Bimbati Alan, Dainese Andrea

Contents

1 Fattorizzazioni 2

1.1 Fattorizzazione LR . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Fattorizzazione QR . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Tabella Complessitá 3

2.1 Algoritmo di Thomas . . . . . . . . . . . . . . . . . . . . . . 3

3 Matrice di Vandermonde 4

4 Interpolazione 4

4.1 Polinomio di Lagrange . . . . . . . . . . . . . . . . . . . . . . 4

5 Estrapolazione 5

5.1 Polinomi di Chebyshev . . . . . . . . . . . . . . . . . . . . . . 5

5.1.1 Nodi di Chebyshev . . . . . . . . . . . . . . . . . . . . 5

5.2 Polinomio di Newton . . . . . . . . . . . . . . . . . . . . . . . 5

5.3 Interpolazione di Birkoff Hermite . . . . . . . . . . . . . . . . 5

6 Metodo dei Grafi 6

7 Metodi di convergenza 6

7.1 Metodo di Iacobi . . . . . . . . . . . . . . . . . . . . . . . . . 6

7.2 Metodo di Gauss - Seidel . . . . . . . . . . . . . . . . . . . . 6

7.3 SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

7.4 Convergenza Globale di Newton . . . . . . . . . . . . . . . . . 7

7.5 Altre considerazioni . . . . . . . . . . . . . . . . . . . . . . . 7

8 Info Generali 7

9 Codici Utili 9

1

1 Fattorizzazioni

1.1 Fattorizzazione LR

La fattorizzazione é valida solo su matrici quadrate, l’output sono una ma-

trice triangolare inferiore (L) e matrice triangolare superiore (R) che molti-

plicate tra loro resituiscono A.

É fattorizzabile se tutti i minori principali di A sono non nulli, ec-

cetto l’ultimo o A é non singolare, infatti basta che gli elementi in

diagonale, ad ogni passo di fattorizzazione siano non nulli eccetto l’ultimo

perché la matrice sia fattorizzabile.

3

n

Complessitá: 6

Condizioni sufficienti:

• matrice strettamente diagonale dominante

• matrice non singolare dominante

• matrice simmetrica definita positiva

Con pivoting:

• Pro: l’algoritmo é stabile in senso forte

• Contro:non mantiene la struttura della matrice e non conviene se la

la matrice é diagonale dominante o definita positiva

Risoluzione del sistema

−1

x = R y

−1

y = L P b

y=sollower(L,b(P));

x=solupper(R,y);

1.2 Cholesky

É fattorizzabile solo se la matrice é simmetrica definita positiva (solo se

A=LL’). 3

n

Complessitá: 6

Stabile in senso forte

1.3 Givens

Le trasformazioni di Givens mantengono invariata la norma euclidea.

Esse sono utili per ottenere la fattorizzazione QR di matrici sparse.

2

1.4 Fattorizzazione QR

Questa fattorizzazione vale anche per matrici non quadrate ma é stabile

in senso debole.

Complessitá: 3

n

• )

Matrice quadrata: O(4 3

Risoluzione del sistema

T

y = Q b

x = Ry

y=Q’b;

x=solupper(R,y);

2 Tabella Comp