Método jacobi

En álgebra lineal numérica, el Método Jacobi (a.k.a. the Método de iteración Jacobi) es un algoritmo iterativo para determinar las soluciones de un sistema estrictamente diagonal dominante de ecuaciones lineales. Cada elemento diagonal se resuelve, y un valor aproximado está conectado. El proceso es entonces iterado hasta que converge. Este algoritmo es una versión desmontada del método de transformación Jacobi de la diagonalización matriz. El método es nombrado por Carl Gustav Jacob Jacobi.

Descripción

Vamos. ${\displaystyle A\mathbf {x} =\mathbf {b}$ ser un sistema cuadrado n ecuaciones lineales, donde:$${\displaystyle A={\begin{bmatrix}a_{11} limita_{12} "A_{1n}\a_{21} 'a_{2n}\vdots &\vdots &\ddots &\vdots \\a_{n1} limita_{n2} limit\cdots ' {nnnn}\end{bmatrix},\qquad \mathbf {x} ={bmatrix}x_{1} \\x_{n}\end{bmatrix}}\qquad \mathbf {b} = {\begin{bmatrix}b_{1}\b_{2}\\\\\vdots {\fn}}$$

Cuando ${\displaystyle A}$ y ${\displaystyle \mathbf}$ son conocidos, y ${\displaystyle \mathbf {x}$ es desconocido, podemos utilizar el método Jacobi para aproximarse ${\displaystyle \mathbf {x}$. El vector ${\displaystyle \mathbf {x} {}}}$ denota nuestra suposición inicial para ${\displaystyle \mathbf {x}$ (a menudo ${\displaystyle \mathbf {x} _{i}}=0}$ para ${\displaystyle i=1,2,...,n}$). We denote ${\displaystyle \mathbf {x} {\cH00}}$ como k-t aproximación o iteración de ${\displaystyle \mathbf {x}$, y ${\displaystyle \mathbf {x} {(k+1)}$ es el siguiente (o k+1) iteración de ${\displaystyle \mathbf {x}$.

Fórmula basada en la matriz

Entonces... A se puede descomponer en un componente diagonal D, una parte triangular inferior L y una parte triangular superior U:$${\displaystyle A=D+L+U\qquad {where}\qquad D={\begin{bmatrix}a_{11} >\0\0\0\cdots >\vdots &\ddots >\vdots \\vdots \\0 concdots ################################################################################################################################################################################################################################################################ {2n}\\vdots > 'ddots >\cdots > 'vdots &\ddots &\vdots \ 'vdots \\a_{n1} limita_{n2} limit\cdots > {bmatrix}}}$$La solución se obtiene por vía iterativa

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

Fórmula basada en elementos

La fórmula basada en elementos para cada fila ${\displaystyle i}$ es así:$${\displaystyle x_{i}{(k+1)}={\frac {1}{a_{ii}\left(b_{i}-\sum ¿Por qué?$$La computación de ${\displaystyle x_{i}{(k+1)}$ requiere cada elemento en ${\displaystyle \mathbf {x} {\cH00}}$ excepto ella misma. A diferencia del método Gauss–Seidel, no podemos sobreescribir ${\displaystyle x_{i} {\cH00}}$ con ${\displaystyle x_{i}{(k+1)}$, ya que ese valor será necesario por el resto de la computación. La cantidad mínima de almacenamiento es dos vectores de tamaño n.

Algoritmo

Entrada: inicial x(0) a la solución, matriz (diagonal dominante) A, vector de lado derecho b, criterio de convergencia
Producto: solución cuando se alcanza la convergenciaComentarios: pseudocódigo basado en la fórmula basada en elementos arriba

k = 0mientras convergencia no alcanzada do para i:= 1 paso hasta n do σ = 0 para j:= 1 paso hasta n do si j ل i entonces σ = σ + aij xj()k) final final xi()k+1) =bi − σ) aii finalaumento kfinal

Convergencia

La condición de convergencia estándar (para cualquier método iterativo) es cuando el radio espectral de la matriz de iteración es menor que 1:

${\displaystyle \rho (D^{-1}(L+U) se realizó 1.}$

Una condición suficiente (pero no necesaria) para que el método converja es que la matriz A sea estricta o irreductiblemente diagonalmente dominante. La dominancia diagonal de fila estricta significa que para cada fila, el valor absoluto del término diagonal es mayor que la suma de los valores absolutos de otros términos:

${\displaystyle \left WordPressa_{ii}\right WordPress\sum _{j\neq i}{\left habita_{ij}\right sobre la vida}$

El método de Jacobi a veces converge incluso si estas condiciones no se cumplen.

Tenga en cuenta que el método Jacobi no converge para cada matriz simétrica positiva-definida. Por ejemplo, $${\displaystyle A={\begin{pmatrix}29 tendrían 2 resultados1\2 afectados6 tendrían 1\1}\fnMicroc {1}}\end{pmatrix}\quad \Rightarrow \quad D^{-1}(L+U)={\begin{pmatrix}0 tarde{\frac {2}{29}} {\frac {1}{29}}\{\frac {1}{3}} {0} {0} {0}{6}}}}}\5 simultáneamente5 {0\end{pmatrix}\quad}}\quad \Rightarrow \quad \rho (D^{-1}(L+U)\approx 1.0661\,.}$$

Ejemplos

Pregunta de ejemplo

Sistema lineal de la forma ${\displaystyle Ax=b$ con estimación inicial ${\displaystyle x^{(0)}$ es dado por

${\displaystyle A={\begin{bmatrix}2 ventaja1\5 implica7\\\end{bmatrix}\,\ b={\begin{bmatrix}11\13\\end{bmatrix}\quad {\text{y}\4\\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif}}}$

Usamos la ecuación ${\displaystyle x^{(k+1)}=D^{-1}(b-(L+U)x^{(k)}}$, descrita anteriormente, para estimar ${\displaystyle x}$. Primero, reescribimos la ecuación en una forma más conveniente ${\displaystyle D^{-1}(b-(L+U)x^{(k)}=Tx^{(k)}+C}$, donde ${\displaystyle T=-D^{-1}(L+U)}$ y ${\displaystyle C=D^{-1}b}$. De los valores conocidos $${\displaystyle ¿Qué? L={\begin{bmatrix}0 tarde0\5 diez0\\end{bmatrix}\quad {\text{and}\quad U={\begin{bmatrix}0 tarde1\0\0\end{bmatrix}}$$determinamos ${\displaystyle T=-D^{-1}(L+U)}$ como $${\displaystyle T={\begin{bmatrix}1/2 limit0\0}\0 {\0}\end{bmatrix}\left\{\begin{bmatrix}0}0\5 {0\end{bmatrix}}+{\begin{bmatrix}01/2\0}\0}\0}\0 {0}\begin\b}\begin\begin\m}\m}\m}\m}\m}\m}\m}\b}\m}\m}\m}\m\m}\m\m\m\cH0{0}\cH0}\m\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\b}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0}\cH0$$Además, ${\displaystyle C}$ se encuentra como $${\displaystyle C={\begin{bmatrix}1/2 limit0\0 diez1/7\\\end{bmatrix}{\begin{bmatrix}11\13\\\\\end{bmatrix}={\begin{bmatrix}11/2\13/7\\\\\\\end{bmatrix}}}$$Con ${\displaystyle T}$ y ${\displaystyle C}$ calculada, estimamos ${\displaystyle x}$ como ${\displaystyle x^{(1)}=Tx^{(0)}+C}$: $${\fnK} {\fn}\fnK}\fn}\fn}\fn}\m\fn} {\fncip}\bmatrix} {\bn\cH0}\fn}\fn\fnK}\c\c\cH0\cH0}\cH0\cH0\cH0\cH0\cH0\cH0}\cH0\cH0\cH0}\cH0\cH0\cH0\cH0\cH0\cH0\cH0\cH0\cH0\cH0\cH00}\cH0}\\\\\cH0\cH0\cH00}\cH0\cH0}\cH00\cH0\cH00\cH00\cH0}\\\cH00}\cH0\cH0\cH00}\cH0\cH0\cH0}\cH0\cH0 {\begin{bmatrix}5\1.143\\\end{bmatrix}}}$$El próximo rendimiento de la iteración $${\fnK} {\fnK}\fnK}\f}\\fnK}\fnK}}\m\cH30}}}\m\cH0\\\8/7\\\\\\\\\d\cH0}\m\cH0}\cH00\cH00\cH00\cH00\cH0}\cH00\cH00\cH0}\cH0}\cH0}\cH00\cH0\cH00}\cH0\cH00\cH00\cH00\cH00\cH0}\cH0}\cH00\cH0}\cH00\cH00\cH00\cH0}\cH00\cH00}\cH00\cH00\cH00\cH00\cH00}\cH00\cH0}\cH00\cH0}\cH0\cH0}\cH0}\cH00\cH {\begin{bmatrix}4.929\\-1.714\\\end{bmatrix}}}$$Este proceso se repite hasta la convergencia (es decir, hasta ${\displaystyle {\fn]}-b\fnción}$ es pequeño). La solución después de 25 iteraciones es

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

Ejemplo de pregunta 2

Supongamos que tenemos el siguiente sistema lineal:

${\fnMicrosoft Sans Serif} {\cH00}\4\cH00}\cH009}\cH009}\c_}\cH3_\4}\cH0_\4} {3_\4}\cH00}\2x_{2}+10x_{3} {4} {3\c\c\cH0}}\c\c\cH0\c\cH0\cH0\c\cH00}\c\cH0\c\cH0\cH00}\cH0\c\cH00}\c\cH0\c\c\cH00}\cH00}\c\c\c\c\cH00}\cH3\cH00}\cH00}\cH00}\cH004\cH00\c\cH00}\cH00}\cH00}\cH00\cH004\cH00}\c\cH00}\c\cH00}$

Si elegimos (0, 0, 0, 0) como la aproximación inicial, entonces la primera solución aproximada es dada por $${\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif}\cH0} {\fnMicrosoft Sans Serif}*}\fnMicrosoft Sans Serif}*}*}*}*}*}*}*$$Utilizando las aproximaciones obtenidas, el procedimiento iterativo se repite hasta que se haya alcanzado la precisión deseada. Las siguientes son las soluciones aproximadas después de cinco iteraciones.

${\displaystyle x_{1}}$	${\displaystyle x_{2}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$
0.6	2.27272	-1.1	1.875
1.04727	1.7159	-0.80522	0.88522
0,9263	2.05330	-1.0493	1.13088
1.01519	1.95369	-0.9681	0.97384
0.98899	2.0114	-1.0102	1.02135

La solución exacta del sistema es (1, 2, −1, 1).

Ejemplo de Python

importación numposo como npITERATION_LIMIT = 1000# inicializar la matrizA = np.array[[[10., -1., 2., 0.] [-1., 11., -1., 3.] [2., -1., 10., -1.] [0,0, 3., -1., 8.]]# inicializar el vector RHSb = np.array([2]6., 25., -11., 15.])# prints the systemimpresión()"System:")para i dentro rango()A.forma[0]] fila = [f"{}A[i, j]}*x{}j + 1}" para j dentro rango()A.forma[1]] impresión()f'{}" + ".Únase()fila)} = {}b[i]}')impresión()x = np.ceros()b)para it_count dentro rango()ITERATION_LIMIT): si it_count ! 0: impresión()f"Iteración {}it_count}: {}x}") x_new = np.ceros()x) para i dentro rango()A.forma[0]] s1 = np.#()A[i, :i] x[:i]) s2 = np.#()A[i, i + 1:] x[i + 1:) x_new[i] = ()b[i] - s1 - s2) / A[i, i] si x_new[i] == x_new[i-1]: descanso si np.allclose()x, x_new, atol=1e-10, rtol=0.): descanso x = x_newimpresión()"Solución: ")impresión()x)error = np.#()A, x) - bimpresión()"Error:")impresión()error)

Método de Jacobi ponderado

La iteración jacobi ponderada utiliza un parámetro ${\displaystyle \omega }$ para calcular la iteración como

${\displaystyle \mathbf {x} {(k+1)}=\omega D^{-1}(\mathbf {b} -(L+U)\mathbf {x} ^{(k)})+\left(1-\omega \right)\mathbf {x} ^{(k)}$

con ${\displaystyle \omega =2/3}$ ser la opción habitual. De la relación ${\displaystyle L+U=A-D}$, esto también puede expresarse

${\displaystyle \mathbf {x} {(k+1)}=\omega D^{-1}\mathbf {b} +\left(I-\omega D^{-1}A\right)\mathbf {x} ^{(k)}$.

Convergencia en el caso definido positivo simétrico

En caso de que la matriz del sistema ${\displaystyle A}$ es de tipo simétrico positivo-definido uno puede mostrar convergencia.

Vamos. ${\displaystyle C=C_{\omega ♪=I-\omega D^{-1}A}$ ser la matriz de iteración. Entonces, la convergencia está garantizada para

${\displaystyle \rho (C_{\omega }) \Longleftrightarrow \quad 0 observado\omega <{\frac {2}{\lambda _{\text{max}}(D^{-1}A)}}\,}$

Donde ${\displaystyle \lambda _{max}}$ es el valor máximo.

El radio espectral se puede minimizar para una elección particular ${\displaystyle \omega =\omega _{\text{opt}}$ como sigue: $${\displaystyle \min _{\omega }\rho (C_{\omega })=\rho (C_{\omega _{\text{opt}}})=1-{\frac {2}{\kappa (D^{-1}A)+1}\quad {\text{for}\quad \omega _{\text{opt}={\frac {2}{\lambda _{\text{min}}(D^{-1}A)+\lambda _{\text{max}}(D^{-1}A)}}\,}$$Donde ${\displaystyle \kappa }$ es el número de la condición de matriz.