Método de Gauss-Seidel

En análisis numérico el método de Gauss-Seidel es un método iterativo utilizado para resolver sistemas de ecuaciones lineales. El método se llama así en honor a los matemáticos alemanes Carl Friedrich Gauss y Philipp Ludwig von Seidel y es similar al método de Jacobi.

Aunque este método puede aplicarse a cualquier sistema de ecuaciones lineales que produzca una matriz (cuadrada, naturalmente pues para que exista solución única, el sistema debe tener tantas ecuaciones como incógnitas) de coeficientes con los elementos de su diagonal no-nulos, la convergencia del método solo se garantiza si la matriz es diagonalmente dominante o si es simétrica y, a la vez, definida positiva.

Descripción

Es un método iterativo, lo que significa que se parte de una aproximación inicial y se repite el proceso hasta llegar a una solución con un margen de error tan pequeño como se quiera. Buscamos la solución a un sistema de ecuaciones lineales, en notación matricial:

${\displaystyle Ax=b,\,}$

donde:

${\displaystyle A={\begin{pmatrix}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{pmatrix}},\qquad x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}},\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{pmatrix}}.}$

El método de iteración Gauss-Seidel se computa, para la iteración ${\displaystyle (k+1)\,}$:

${\displaystyle x^{(k+1)}=Mx^{(k)}+c.\,}$

donde

${\displaystyle A=N-P\,}$

definimos

${\displaystyle M=N^{-1}P\,}$

y

${\displaystyle c=N^{-1}b\,}$,

donde los coeficientes de la matriz N se definen como ${\displaystyle n_{ij}=a_{ij}\,}$ si ${\displaystyle i{\leq }j}$, ${\displaystyle n_{ij}=0\,}$ si ${\displaystyle i>j\,}$, esto es, la matriz N es triangular superior.

Considerando el sistema ${\displaystyle Ax=b,\,}$ con la condición de que ${\displaystyle a_{ii}{\neq }0,i=1,...,n\,}$. Entonces podemos escribir la fórmula de iteración del método

${\displaystyle x_{i}^{(k+1)}={\frac {-\sum _{1{\leq }j{\leq }i-1}a_{ij}x_{j}^{(k+1)}-\sum _{i+1{\leq }j{\leq }n}a_{ij}x_{j}^{(k)}+b_{i}}{a_{ii}}},i=1,...,n\,}$(*)

La diferencia entre este método y el de Jacobi es que, en este último, las mejoras a las aproximaciones no se utilizan hasta completar las iteraciones.

Convergencia

Teorema: Suponga una matriz ${\displaystyle A\in R(n,n)}$ es una matriz no singular que cumple la condición de ${\displaystyle |a_{\mu \mu }|>\sum _{1{\leq }\nu {\leq }n,\nu {\neq }\mu }|a_{\mu \nu }|\,}$ o ${\displaystyle \sum _{1{\leq }\nu {\leq }n,\nu {\neq }\mu }|a_{\nu \mu }|,1{\leq }\mu {\leq }n\,}$. Entonces el método de Gauss-Seidel converge a una solución del sistema de ecuaciones, y la convergencia es por lo menos tan rápida como la convergencia del método de Jacobi.

Para ver los casos en que converge el método primero mostraremos que se puede escribir de la siguiente forma:

${\displaystyle x^{(k+1)}=Mx^{(k)}+c,k=1,2,3...\,}$ (**)

(el término ${\displaystyle x^{(k)}\,}$ es la aproximación obtenida después de la k-ésima iteración) este modo de escribir la iteración es la forma general de un método iterativo estacionario.

Primeramente debemos demostrar que el problema lineal ${\displaystyle Ax=b}$ que queremos resolver se puede representar en la forma (**), por este motivo debemos tratar de escribir la matriz A como la suma de una matriz triangular inferior, una diagonal y una triangular superior A=(L+D+U), D=diag(${\displaystyle a_{ii}\,}$). Haciendo los despejes necesarios escribimos el método de esta forma

${\displaystyle x^{(k+1)}={-(L+D)}^{-1}{U}x^{(k)}+{(L+D)}^{-1}b\,}$

por lo tanto M=-(L+D)^-1 U y c=(L+D)^-1b

Ahora podemos ver que la relación entre los errores, el cual se puede calcular al substraer x=Bx+c de (**)

${\displaystyle x^{(k+1)}-x=M(x^{(k)}-x)=...=M^{(k+1)}(x^{(0)}-x).\,}$

Supongamos ahora que ${\displaystyle \lambda _{i}\,}$, i= 1, ..., n, son los valores propios que corresponden a los vectores propios ${\displaystyle u_{i}}$, i= 1,..., n, los cuales son linealmente independientes, entonces podemos escribir el error inicial

${\displaystyle x^{(0)}-x=\alpha _{1}u_{1}+...+\alpha _{n}u_{n}\,}$

${\displaystyle x^{(k)}-x=\alpha _{1}\lambda _{1}^{k}u_{1}+...+\alpha _{n}\lambda _{n}^{k}u_{n}\,}$(***)

Por lo tanto la iteración converge si y sólo si ${\displaystyle |\lambda _{i}|<1,\forall \ i=1,\ldots ,n}$. De este hecho se desprende el siguiente teorema:

Teorema: Una condición suficiente y necesaria para que un método iterativo estacionario ${\displaystyle x^{(k+1)}=Mx^{(k)}+c\,}$ converja para una aproximación arbitraria ${\displaystyle x^{(0)}}$ es que ${\displaystyle \rho (M)=\max _{1{\leq }i{\leq }n}|\lambda _{i}|<1\,}$ donde ρ(M) es el radio espectral de M.

Algoritmo

El método de Gauss-Seidel se puede escribir en forma de algoritmo de la siguiente manera:

Algoritmo Método de Gauss-Seidel

función Gauss-Seidel (${\displaystyle A}$, ${\displaystyle x^{0}}$) //${\displaystyle x^{0}}$ es una aproximación inicial a la solución// para ${\displaystyle k\gets 1}$ hasta convergencia hacer para ${\displaystyle i\gets 1}$ hasta ${\displaystyle n\,}$ hacer ${\displaystyle \sigma \gets 0}$ para ${\displaystyle j\gets 1}$ hasta ${\displaystyle n\,}$ hacer si ${\displaystyle j\neq i\,}$ entonces ${\displaystyle \sigma =\sigma +a_{ij}x_{j}}$ fin para ${\displaystyle x_{i}={{\left({b_{i}-\sigma }\right)} \over {a_{ii}}}}$ fin para comprobar si se alcanza convergencia fin para

Véase también

• Método de Jacobi
• Método de Sobre-Relajación Sucesiva (SOR)

Enlaces externos

• Gauss-Seidel from www.math-linux.com Archivado el 5 de marzo de 2013 en Wayback Machine.
• Módulo para la iteración de Gauss-Seidel
• Weisstein, Eric W. «Gauss-Seidel». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Gauss-Seidel