Metodi per la risoluzione dei sistemi lineari

Due classi di metodi numeri per la risoluzione dei sistemi lineari sono:

1. Metodi diretti (es: Gauss, Gauss-Jordan, fattorizzazione $LU$, fattorizzazione $LL^t$ (Cholesky)
   Si utilizzano su matrici dense, le quali vengono modificate passe dopo passo (fenomeno fill-in);
   di dimensioni $n \leq 10^3$;
   numero di passi finito: $O(n)$.
2. Metodi iterativi (es: Jacobi, Gauss-Seidel)
   Si utilizzano su matrici sparse, che restano invariate poiché il metodo lavora su una opportuna matrice di iterazione.
   di dimensioni $n > 10^3$
   numero di passi (potenzialmente) infinito.

Definizione.

A è sparsa se il numero dei suoi elementi $a_{ij} \neq 0$ è dell'$O(n)$.

Viceversa si dice densa o piena.

Fenomeno del Fill-In.
Abbiamo n matrici intermedie che ci portano da A al risultato.