Calcolo numerico

Calcolo numerico

Bimbati Alan, Dainese Andrea

Contents

• Fattorizzazioni
• Tabella Complessità
• Matrice di Vandermonde
• Interpolazione
• Estrapolazione
• Metodo dei Grafi
• Metodi di convergenza
• Info Generali
• Codici Utili

Fattorizzazioni

1.1 Fattorizzazione LR

La fattorizzazione è valida solo su matrici quadrate, l’output sono una matrice triangolare inferiore (L) e una matrice triangolare superiore (R) che moltiplicate tra loro restituiscono A. È fattorizzabile se tutti i minori principali di A sono non nulli, eccetto l’ultimo, o A è non singolare. Infatti, basta che gli elementi in diagonale, a ogni passo di fattorizzazione, siano non nulli eccetto l’ultimo perché la matrice sia fattorizzabile.

Complessità: 3n

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 matrice è diagonale dominante o definita positiva

Risoluzione del sistema:
x = R-1 y
y = L-1 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’).

Complessità: 3n

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.

1.4 Fattorizzazione QR

Questa fattorizzazione vale anche per matrici non quadrate ma è stabile in senso debole.

Complessità: 3n

• Matrice quadrata: O(4/3)

Risoluzione del sistema:
Ty = Q b
x = R-1 y
y = Q’ b;
x = solupper(R, y);

Tabella Complessità

2.1 Algoritmo di Thomas

Descrizione e dettagli dell'algoritmo di Thomas.

Matrice di Vandermonde

Descrizione e dettagli sulla matrice di Vandermonde.

Interpolazione

4.1 Polinomio di Lagrange

Descrizione e dettagli sul polinomio di Lagrange.

Estrapolazione

5.1 Polinomi di Chebyshev

5.1.1 Nodi di Chebyshev

Descrizione e dettagli sui nodi di Chebyshev.

5.2 Polinomio di Newton

Descrizione e dettagli sul polinomio di Newton.

5.3 Interpolazione di Birkoff Hermite

Descrizione e dettagli sull'interpolazione di Birkoff Hermite.

Metodo dei Grafi

Descrizione generale del metodo dei grafi.

Metodi di convergenza

7.1 Metodo di Iacobi

Descrizione e dettagli sul metodo di Iacobi.

7.2 Metodo di Gauss-Seidel

Descrizione e dettagli sul metodo di Gauss-Seidel.

7.3 SOR

Dettagli sul metodo SOR (Successive Over-Relaxation).

7.4 Convergenza Globale di Newton

Descrizione e dettagli sulla convergenza globale di Newton.

7.5 Altre considerazioni

Ulteriori considerazioni sui metodi di convergenza.

Info Generali

Informazioni generali sull'argomento trattato.

Codici Utili

Esempi di codici utili per l'applicazione dei metodi descritti.