Mètode de Gauss-Seidel

En àlgebra lineal numèrica, el mètode de Gauss-Seidel, també conegut com a mètode de Liebmann o mètode de desplaçament successiu, és un mètode iteratiu utilitzat per resoldre un sistema d'equacions lineals. Porta el nom dels matemàtics alemanys Carl Friedrich Gauss i Philipp Ludwig von Seidel, i és similar al mètode de Jacobi. Encara que es pot aplicar a qualsevol matriu amb elements diferents de zero a les diagonals, la convergència només està garantida si la matriu és estrictament diagonal dominant, o simètrica i definida positiva. Només es va esmentar en una carta privada de Gauss al seu alumne Christian Ludwig Gerling el 1823. Una publicació no va ser lliurada abans de 1874 per Seidel.

El mètode de Gauss-Seidel és una tècnica iterativa per resoldre un sistema quadrat de n equacions lineals amb x desconegut:$A\mathbf {x} =\mathbf {b} .$Es defineix per la iteració

$L_{*}\mathbf {x} ^{(k+1)}=\mathbf {b} -U\mathbf {x} ^{(k)},$

on $\mathbf {x} ^{(k)}$ és la k- èsima aproximació o iteració de $\mathbf {x} ,\,\mathbf {x} ^{(k+1)}$ és la següent o k + 1 iteració de $\mathbf {x}$, i la matriu A es descompon en un component triangular inferior $L_{*}$, i un component triangular estrictament superior $U$ és a dir, $A=L_{*}+U$.

Amb més detall, escriu A, x i b en els seus components:$A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.$Aleshores, la descomposició de A en la seva component triangular inferior i la seva component triangular estrictament superior ve donada per:

$A=L_{*}+U\qquad {\text{where}}\qquad L_{*}={\begin{bmatrix}a_{11}&0&\cdots &0\\a_{21}&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}}.$

El sistema d'equacions lineals es pot reescriure com:

$L_{*}\mathbf {x} =\mathbf {b} -U\mathbf {x}$

El mètode Gauss-Seidel ara resol el costat esquerre d'aquesta expressió per a x, utilitzant el valor anterior per a x al costat dret. Analíticament, això es pot escriure com:

$\mathbf {x} ^{(k+1)}=L_{*}^{-1}\left(\mathbf {b} -U\mathbf {x} ^{(k)}\right).$

Tanmateix, aprofitant la forma triangular de $L_{*}$, els elements de x ^{(k +1)} es poden calcular seqüencialment mitjançant la substitució directa:

$x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\dots ,n.$