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,^[1] 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.^[2] Una publicació no va ser lliurada abans de 1874 per Seidel.^[3]

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

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

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

Amb més detall, escriu A, x i b en els seus components:${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 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:

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

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

${\displaystyle 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.}$ ^[6]

Referències

1. Sauer, Timothy. Numerical Analysis (en anglès). 2a edició. Pearson Education, Inc., 2006, p. 109. ISBN 978-0-321-78367-7. 
2. Gauss 1903; direct link.
3. Seidel, Ludwig (en alemany) Abhandlungen der Mathematisch-Physikalischen Klasse der Königlich Bayerischen Akademie der Wissenschaften, 11, 3, 1874, pàg. 81–108.
4. «Gauss–Seidel method» (en anglès). https://www.geeksforgeeks.org,+02-08-2019.+[Consulta: 3 desembre 2022].
5. Golub & Van Loan 1996, p. 511
6. Golub & Van Loan 1996