Álgebra lineal numérica · Definición

Métodos de Jacobi y Gauss-Seidel

métodos numéricosálgebra lineal numérica

Antes de empezar necesitas conocer

Cuando un sistema tiene muchas incógnitas, resolverlo por eliminación directa puede resultar costoso. Estos métodos ofrecen una alternativa basada en iteraciones sucesivas.

Definición

Los métodos de Jacobi y Gauss-Seidel son procedimientos iterativos que aproximan la solución de un sistema lineal \(A\mathbf{x}=\mathbf{b}\) mediante la actualización repetida de sus componentes.

\[x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\neq i}a_{ij}x_j^{(k)}\right)\]

Jacobi usa en cada paso solo los valores de la iteración anterior, mientras que Gauss-Seidel incorpora de inmediato las componentes ya actualizadas. Si \(A\) es estrictamente diagonal dominante, ambos métodos convergen para cualquier vector inicial.

Consideremos el sistema \(4x+y=9\), \(x+3y=7\). Partiendo de \((0,0)\), Jacobi da \(x^{(1)}=9/4\), \(y^{(1)}=7/3\), y Gauss-Seidel usa de inmediato el nuevo \(x\) para calcular \(y\), acelerando la convergencia.

Un error típico es aplicar estos métodos a matrices sin dominancia diagonal y esperar convergencia; en ese caso las iteraciones pueden divergir. Conviene verificar la condición antes de iterar.

Para pensar

¿Es la dominancia diagonal estricta necesaria para que Jacobi converja? Justifica.

No: es suficiente, pero hay matrices sin dominancia estricta donde Jacobi converge, así que no es condición necesaria.

Ejercicios 10

  1. ¿Qué método actualiza las componentes usando los valores ya calculados en la misma iteración?
  2. ¿Qué propiedad de la matriz garantiza la convergencia de ambos métodos?
  3. En la fórmula de actualización, ¿por qué se divide entre \(a_{ii}\)?
  4. ¿Cuál es el vector inicial habitual en estos métodos cuando no se conoce una estimación?
  5. ¿Qué tipo de sistema es el que se resuelve con estos métodos?
  6. Para \(4x+y=9\), \(x+3y=7\), ¿cuál es \(x^{(1)}\) con Jacobi desde \((0,0)\)?
  7. Para \(4x+y=9\), \(x+3y=7\), con Gauss-Seidel desde \((0,0)\), ¿cuál es \(y^{(1)}\)?
  8. Si \(a_{22}=0\) en un sistema 2x2, ¿qué ocurre al aplicar la fórmula de actualización de la segunda incógnita?
  9. ¿Cuál de estas afirmaciones sobre la comparación de ambos métodos es correcta?
  10. Dado \(A=\begin{pmatrix}2&1\\1&2\end{pmatrix}\) y \(\mathbf{b}=(3,3)\), ¿cuál es \(x^{(2)}\) con Jacobi desde \((0,0)\)?

Referencias

  • Richard L. Burden, J. Douglas Faires, Annette M. Burden, Numerical Analysis, 10th edition, Cengage Learning, 2016.
  • Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, 1st edition, SIAM, 1997.