Metodo di Gauss-Seidel

In analisi numerica il metodo di Gauss-Seidel è un metodo iterativo di risoluzione di un sistema matriciale della forma Ax=b, dove $A$ indica la matrice dei coefficienti e $b$ il vettore dei termini noti. Questo metodo risulta simile al metodo di Jacobi. Per la risoluzione, si procede prima alla scomposizione della matrice iniziale nella somma di tre matrici:

• D matrice diagonale;
• -L matrice triangolare inferiore;
• -U matrice triangolare superiore.

La matrice iniziale risulta quindi essere:

$A = D - L - U$

E il sistema da risolvere è:

$\left(D-L-U\right)x = b$

$\left(D-L\right)x = Ux+b$

$\left(D-L\right)x^{(k+1)} = Ux^{(k)}+b$

$x^{(k+1)} = \left(D-L\right)^{-1} U \cdot x^{(k)} + (D-L)^{-1}\cdot b$

Ponendo $M_{GS}$ come la matrice di convergenza del metodo di Gauss-Seidel.

$M_{GS} = \left(D-L\right)^{-1} U$

La soluzione risulta quindi:

$x^{(k+1)} = M_{GS}\cdot x^{(k)}+\left(D-L\right)^{-1}\cdot b$

Convergenza

Affinché il metodo converga verso la soluzione esatta si deve verificare che l'errore $E$ diminuisca ad ogni iterazione:

$\lim_{m \to \infty} E^{m} = \lim_{m \to \infty} M_{GS}^{m} =0$

Questo si verifica se il raggio spettrale della matrice di convergenza risulta essere strettamente minore di 1. Una condizione sufficiente affinché ciò accada è che la matrice dei coefficienti sia a diagonale dominante in senso stretto (il che tra l'altro ne implica la non singolarità):

$\forall i: \left | a_{ii} \right | > \sum_{j \ne i} {\left | a_{ij} \right |}.$

il tutto si può riassumere dicendo che se $B = M^{1} * N$ dove $M$ è la matrice triangolare bassa ricavata da $A$ ed $N=M-A$ allora nel caso compaia nella matrice $A$ un parametro per il quale occorra trovare il campo di esistenza tale per cui la matrice converge, basta studiare gli autovalori della matrice $B$ e porre l'autovalore più grosso (in modulo) minore di 1.

è molto comodo inoltre ricavare la matrice $M^{-1}$ dalla matrice $A$ con la matrice di Fugazza:

$M^{-1}=$ $\begin{bmatrix} \frac{1}{a_{11}} & 0 & 0 \\ -\frac{a_{21}}{a_{22}a_{11}} & \frac{1}{a_{22}} & 0 \\ \frac {det\begin{bmatrix} a_{21} & a_{22} \\ a_{31} & a_{32}\end{bmatrix} }{a_{11}a_{22}a_{33}} & -\frac{a_{32}}{a_{33}a_{22}} & \frac{1}{a_{33}} \end{bmatrix}$

moltiplicando questa matrice per la $N =$ $\begin{bmatrix} 0 & -a_{12} & -a_{13} \\ 0 & 0 & -a_{23} \\ 0 & 0& 0 \end{bmatrix}$ si ottiene la matrice $B$ il cui raggio spettrale deve essere minore di 1

Per risolvere il sistema lineare si utilizza quindi una successione di $x^{(k)}$ che converge verso la soluzione $x$ del sistema lineare. Indicando $a_{ij}=[A]_{ij}$ e $b_i=[b]_i$, la successione è costruita come segue:

$x^{(k)}_i = \frac{b_i - \sum\limits_{j<i} a_{ij} x^{(k)}_j - \sum\limits_{j> i} a_{ij} x^{(k-1)}_j}{a_{ii}}$

Voci correlate

• Metodo di Jacobi
• Successive Over Relaxation

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica