Metodo di Gauss-Seidel

Template:F In analisi numerica il metodo di Gauss-Seidel è un metodo iterativo, simile al metodo di Jacobi, per la risoluzione di un sistema lineare, scritto nella forma matriciale $Ax=b.$

Algoritmo

Come per il metodo di Jacobi, la matrice $A$ viene scritta come differenza di due matrici: $A=M-N.$ Nel metodo di Gauss-Seidel si prendono $M=L,$ matrice triangolare inferiore, e $N=-U,$ matrice triangolare superiore con diagonale nulla.

Preso un qualunque vettore $x_0,$ si costruisce quindi una successione di vettori per iterazione (come per il metodo di Jacobi)

$x_{k+1}=L^{-1}(U{x}_k+b).$

Come sistema lineare

Come per il metodo di Jacobi, la ricorrenza si può ottenere riscrivendo il sistema di equazioni lineari in modo da isolare una variabile per ogni riga. In questo caso, tuttavia, ogni nuova componente di $x_{k+1}$ viene immediatamente sostituita per il calcolo delle successive

Ad esempio, se con il metodo di Jacobi in un sistema 3x3 si utilizza la ricorrenza

$\{\begin{array}{c}{x}_{k+1}=-\frac{a_{1,2}}{a_{1,1}}{y}_k-\frac{a_{1,3}}{a_{1,1}}{z}_k+\frac{b_1}{a_{1,1}}\\ y_{k+1}=-\frac{a_{2,1}}{a_{2,2}}{x}_k-\frac{a_{2,3}}{a_{2,2}}{z}_k+\frac{b_2}{a_{2,2}}\\ z_{k+1}=-\frac{a_{3,1}}{a_{3,3}}{x}_k-\frac{a_{3,2}}{a_{3,3}}{y}_k+\frac{b_3}{a_{3,3}}\end{array}$

con il metodo di Gauss-Seidel si utilizza la ricorrenza

$\{\begin{array}{c}{x}_{k+1}=-\frac{a_{1,2}}{a_{1,1}}{y}_k-\frac{a_{1,3}}{a_{1,1}}{z}_k+\frac{b_1}{a_{1,1}}\\ y_{k+1}=-\frac{a_{2,1}}{a_{2,2}}{x}_{k+1}-\frac{a_{2,3}}{a_{2,2}}{z}_k+\frac{b_2}{a_{2,2}}\\ z_{k+1}=-\frac{a_{3,1}}{a_{3,3}}{x}_{k+1}-\frac{a_{3,2}}{a_{3,3}}{y}_{k+1}+\frac{b_3}{a_{3,3}}\end{array}$

Convergenza

Come per il metodo di Jacobi, la successione converge indipendentemente dalla scelta di $x_0$ se e solo se la matrice $B=M^{-1}N=L^{-1}U$ ha tutti autovalori con valore assoluto minore di 1.

Una condizione sufficiente perché questo avvenga è che $A$ sia una matrice a diagonale dominante per righe o per colonne in senso stretto. (Questa condizione implica la non singolarità di $A,$ quindi l'unicità della soluzione.)

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

$x_i^{(k+1)}=\frac{b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)}}{a_{ii}}.$

Aspetti computazionali

A differenza del metodo di Jacobi, il metodo di Gauss-Seidel richiede di tenere in memoria un solo vettore, purché i calcoli non vengano svolti in parallelo.

Considerando il fatto che per calcolare la componente $i$-esima $x_i^{(k+1)}$ del nuovo vettore della successione si utilizzano le $j<i$ componenti $x_j^{(k+1)}$ già calcolate, si osserva che una iterazione del metodo di Gauss-Seidel equivale a due iterazioni del metodo di Jacobi (che utilizza soltanto le componenti del vecchio vettore $x_i^{(k)}$), quindi nel metodo di Gauss-Seidel si eseguano meno iterazioni e, quindi, converge più velocemente. Tuttavia la complessità computazionale non varia ed entrambi i due metodi hanno una complessità di $O(n^2)$ iterazioni.

Voci correlate

• Metodo di Jacobi
• Successive Over Relaxation

Collegamenti esterni

• Template:Collegamenti esterni