Metodi Numerici per Sistemi Lineari

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.