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 wikitesto]

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 wikitesto]

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 wikitesto]

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 wikitesto]

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.

Inoltre, 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, la convergenza del metodo avviene più velocemente e quindi si eseguono meno iterazioni che portano questo metodo ad essere più efficiente di quello di Jacobi (che utilizza soltanto le componenti del vecchio vettore x_i^{(k)}).

Voci correlate[modifica | modifica wikitesto]

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