Il metodo di Gauss-Seidel è un metodo iterativo per sistemi lineari A\vec{x} = \vec{b} che, a differenza del metodo di Jacobi, usa immediatamente i valori aggiornati appena calcolati. Converge tipicamente circa il doppio più veloce di Jacobi sulle stesse classi di matrici.
Vedi anche: Metodo di Jacobi (Iterativo), Metodi Numerici per Sistemi Lineari, Gradiente Coniugato.
Schema di Iterazione
Con la decomposizione A = D + L + U:
\vec{x}^{(k+1)} = -(D + L)^{-1} U\, \vec{x}^{(k)} + (D + L)^{-1}\vec{b}
Componente per componente (aggiornamento sequenziale):
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)
La differenza con Jacobi: i termini j < i usano già i valori aggiornati x_j^{(k+1)} calcolati nel passo corrente.
Convergenza
Il metodo converge se \rho(B_{GS}) < 1 dove B_{GS} = -(D+L)^{-1}U.
Condizioni sufficienti:
- A a dominanza diagonale stretta per righe.
- A simmetrica e definita positiva — in questo caso Gauss-Seidel converge sempre (a differenza di Jacobi che non è garantito).
Teorema di Stein-Rosenberg: se A è a dominanza diagonale stretta, \rho(B_{GS}) < \rho(B_J) < 1 (Gauss-Seidel converge più velocemente di Jacobi).
Metodo SOR (Successive Over-Relaxation)
Il metodo SOR accelera la convergenza introducendo un parametro di rilassamento \omega \in (0, 2):
x_i^{(k+1)} = (1-\omega) x_i^{(k)} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{j<i} a_{ij} x_j^{(k+1)} - \sum_{j>i} a_{ij} x_j^{(k)}\right)
- \omega = 1: Gauss-Seidel standard.
- \omega \in (1, 2): over-relaxation (accelera la convergenza se \omega è scelto ottimalmente).
- \omega \in (0, 1): under-relaxation (stabilizza sistemi difficili).
Per matrici tridiagonali simmetriche definite positive, il \omega ottimale è:
\omega_{\text{opt}} = \frac{2}{1 + \sqrt{1 - \rho(B_J)^2}}
Applicazioni ingegneristiche
- Analisi strutturale: Gauss-Seidel con SOR era il metodo standard prima dell’avvento dei solvitori di Krylov; ancora usato come smoothing nei metodi multigriglie (multigrid).
- Rendering 3D (radiosity): il metodo di progressiva raffinazione per il calcolo dell’illuminazione globale è strutturalmente identico a Gauss-Seidel applicato al sistema delle equazioni di scambio radiativo.
- Simulazione termica: la soluzione stazionaria delle equazioni di diffusione del calore su griglia cartesiana usa schemi iterativi di tipo Gauss-Seidel con SOR per la loro semplicità implementativa.