Metodo di Gauss-Seidel

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.