Per sistemi lineari A\mathbf{x} = \mathbf{b} di grandi dimensioni i metodi diretti (eliminazione di Gauss, decomposizione LU) possono essere troppo costosi. I metodi iterativi producono una successione \mathbf{x}^{(k)} \to \mathbf{x}^*.
Metodo di Jacobi
Si decompone A = D + L + U con D diagonale, L triangolare inferiore stretta, U triangolare superiore stretta. L’iterazione è: \mathbf{x}^{(k+1)} = D^{-1}(\mathbf{b} - (L+U)\mathbf{x}^{(k)})
Componente per componente: x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j \neq i} a_{ij}x_j^{(k)}\right).
Tutte le componenti di \mathbf{x}^{(k)} vengono usate contemporaneamente, il che permette la parallelizzazione.
Metodo di Gauss-Seidel
Come Jacobi, ma usa subito le componenti appena calcolate: x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j < i} a_{ij}x_j^{(k+1)} - \sum_{j > i} a_{ij}x_j^{(k)}\right)
Converge tipicamente in metà delle iterazioni rispetto a Jacobi.
Convergenza: entrambi i metodi convergono se A è a diagonale dominante stretta per righe, o se A è simmetrica definita positiva (Gauss-Seidel).
Condizionamento
Il numero di condizionamento \kappa(A) = \|A\|\cdot\|A^{-1}\| misura la sensibilità della soluzione alle perturbazioni dei dati: \frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \leq \kappa(A)\,\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|}
Per \kappa(A) \gg 1 (sistema mal condizionato) piccoli errori numerici nei dati producono grandi errori nella soluzione. La fattorizzazione LU con pivoting parziale migliora la stabilità numerica.