Método de Jacobi

En análisis numérico el método de Jacobi es un método iterativo, usado para resolver sistemas de ecuaciones lineales del tipo ${\displaystyle A\mathbf {x} =\mathbf {b} }$. El algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi. El método de Jacobi consiste en usar fórmulas como iteración de punto fijo.

Descripción

La base del método consiste en construir una sucesión convergente definida iterativamente. El límite de esta sucesión es precisamente la solución del sistema. A efectos prácticos si el algoritmo se detiene después de un número finito de pasos se llega a una aproximación al valor de x de la solución del sistema.

La sucesión se construye descomponiendo la matriz del sistema ${\displaystyle {\mathit {A}}}$ en la forma siguiente:

${\displaystyle {\mathit {A}}={\mathit {D}}+{\mathit {R}}}$

donde ${\displaystyle {\mathit {D}}}$, es una matriz diagonal y ${\displaystyle {\mathit {R}}}$, es la suma de una matriz triangular inferior ${\displaystyle {\mathit {L}}}$ y una matriz triangular superior ${\displaystyle {\mathit {U}}}$, luego ${\displaystyle {\mathit {R}}={\mathit {L}}+{\mathit {U}}}$. Partiendo de ${\displaystyle A\mathbf {x} =\mathbf {b} }$, podemos reescribir dicha ecuación como:

${\displaystyle {\mathit {D}}\mathbf {x} +{\mathit {R}}\mathbf {x} =\mathbf {b} }$

Luego,

${\displaystyle \mathbf {x} ={\mathit {D}}^{-1}\left(\mathbf {b} -{\mathit {R}}\mathbf {x} \right)}$

Si a_ii ≠ 0 para cada i. Por la regla iterativa, la definición del Método de Jacobi puede ser expresado de la forma:

${\displaystyle \mathbf {x} ^{\left(k+1\right)}={\mathit {D}}^{-1}\left(\mathbf {b} -{\mathit {R}}\mathbf {x} ^{(k)}\right)}$

donde ${\displaystyle k}$ es el contador de iteración, Finalmente tenemos:

${\displaystyle x_{i}^{\left(k+1\right)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum \limits _{j\neq i}{a_{ij}x_{j}^{\left(k\right)}}\right),i=1,2,3,...}$

Cabe destacar que al calcular x_i^(k+1) se necesitan todos los elementos en x^(k), excepto el que tenga el mismo i. Por eso, al contrario que en el método Gauss-Seidel, no se puede sobreescribir x_i^(k) con x_i^(k+1), ya que su valor será necesario para el resto de los cálculos. Esta es la diferencia más significativa entre los métodos de Jacobi y Gauss-Seidel. La cantidad mínima de almacenamiento es de dos vectores de dimensión n, y será necesario realizar un copiado explícito.

Convergencia

El método de Jacobi siempre converge si la matriz A es estrictamente diagonal dominante y puede converger incluso si esta condición no se satisface.

Para verificar la convergencia del método se calcula el radio espectral (ρ):

${\displaystyle \rho (D^{-1}R)<1.}$

es la condición necesaria y suficiente para la convergencia, siendo R = L + U . No es necesario que los elementos de la diagonal en la matriz sean mayores (en magnitud) que los otros elementos (la matriz es diagonalmente dominante), pero en el caso de serlo, la matriz converge.

Algoritmo

El método de Jacobi se puede escribir en forma de algoritmo de la siguiente manera:

Algoritmo Método de Jacobi

función Jacobi (${\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}^{(k-1)}}$ fin para ${\displaystyle x_{i}^{(k)}={{\left({b_{i}-\sigma }\right)} \over {a_{ii}}}}$ fin para comprobar si se alcanza convergencia fin para

Ejemplo

Un sistema lineal de la forma ${\displaystyle Ax=b}$ con una estimación inicial${\displaystyle x^{(0)}}$ está dado por

${\displaystyle A={\begin{bmatrix}2&1\\5&7\\\end{bmatrix}},\ b={\begin{bmatrix}11\\13\\\end{bmatrix}}\quad {\text{y}}\quad x^{(0)}={\begin{bmatrix}1\\1\\\end{bmatrix}}.}$

Usamos la ecuación ${\displaystyle x^{(k+1)}=D^{-1}(b-Rx^{(k)})}$, descrita anteriormente, para estimar ${\displaystyle x}$. Primero, reescribimos la ecuación de una manera más conveniente ${\displaystyle D^{-1}(b-Rx^{(k)})=Tx^{(k)}+C}$, donde ${\displaystyle T=-D^{-1}R}$ y ${\displaystyle C=D^{-1}b}$. vea que ${\displaystyle R=L+U}$ donde ${\displaystyle L}$ y ${\displaystyle U}$ son las partes inferior y superior de ${\displaystyle A}$. de los valores conocidos.

${\displaystyle D^{-1}={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}},\ L={\begin{bmatrix}0&0\\5&0\\\end{bmatrix}}\quad {\text{y}}\quad U={\begin{bmatrix}0&1\\0&0\\\end{bmatrix}}.}$

determinamos ${\displaystyle T=-D^{-1}(L+U)}$ como

${\displaystyle T={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}\left\{{\begin{bmatrix}0&0\\-5&0\\\end{bmatrix}}+{\begin{bmatrix}0&-1\\0&0\\\end{bmatrix}}\right\}={\begin{bmatrix}0&-0.5\\-0.714&0\\\end{bmatrix}}.}$

C es encontrada como

${\displaystyle C={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}5.5\\1.857\\\end{bmatrix}}.}$

con T y C calculadas, estimaremos ${\displaystyle x}$ como ${\displaystyle x^{(1)}=Tx^{(0)}+C}$:

${\displaystyle x^{(1)}={\begin{bmatrix}0&-0.5\\-0.714&0\\\end{bmatrix}}{\begin{bmatrix}1\\1\\\end{bmatrix}}+{\begin{bmatrix}5.5\\1.857\\\end{bmatrix}}={\begin{bmatrix}5.0\\1.143\\\end{bmatrix}}.}$

siguientes iteraciones.

${\displaystyle x^{(2)}={\begin{bmatrix}0&-0.5\\-0.714&0\\\end{bmatrix}}{\begin{bmatrix}5.0\\1.143\\\end{bmatrix}}+{\begin{bmatrix}5.5\\1.857\\\end{bmatrix}}={\begin{bmatrix}4.929\\-1.713\\\end{bmatrix}}.}$

este proceso se repetirá hasta que converja (i.e., hasta que ${\displaystyle \|Ax^{(n)}-b\|}$ sea pequeño). la solución después de 25 iteraciones es:

${\displaystyle x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.}$

Véase también

• Método de Gauss-Seidel

Enlaces externos

• Acceleration of the Jacobi iterative method
• Jacobi Method from www.math-linux.com
• Weisstein, Eric W. «Jacobi Method». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Module for Jacobi and Gauss–Seidel Iteration
• Numerical matrix inversion

• Datos: Q1481893