Metodo di Gauss-Seidel

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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 x0, si costruisce quindi una successione di vettori per iterazione (come per Jacobi)

xk+1=L-1(Uxk+b)

Come sistema lineare[modifica | modifica sorgente]

Come per il metodo di Jacobi, la ricorsione 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 xk+1 viene immediatamente sostituita per il calcolo delle successive

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


\begin{cases}
 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{cases}

con il metodo di Gauss-Seidel si utilizza la ricorsione


\begin{cases}
 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{cases}

Convergenza[modifica | modifica sorgente]

Come per il metodo di Jacobi, la successione converge indipendentemente dalla scelta di x0 se e solo se la matrice B=M-1N=L-1U 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 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. Indicando A=(a_{ij})_{ij} e b=(b_i)_i, la successione è costruita come segue:

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

Aspetto computazionale[modifica | modifica sorgente]

A differenza del metodo di Jacobi, il metodo di Gauss-Seidel richiede di tenere in memoria un solo vettore (n), a patto che i calcoli non vengano svolti in parallelo.

Voci correlate[modifica | modifica sorgente]

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