¿Por qué el método de Jacobi está definido de esta manera?

Question

Estoy leyendo unos apuntes de clase, y el método de Jacobi se deriva (aproximadamente) así:

Dejemos que $A=D-L-U$ donde D es la componente diagonal de A, L es el negativo de la componente triangular inferior de A y U es el negativo de la componente triangular superior de A. Entonces

$Ax=b \rightarrow (D-L-U)x=b \rightarrow Dx-Lx-Ux=b \rightarrow Dx=(L-U)x+b$

Así, el método de Jacobi se define como

Elija $x_0$ y luego resolver $Dx_{k+1}=(L+U)x_k +b$ .

Mi pregunta es: ¿Por qué se define así? ¿Podríamos igualmente tener $Ux_{k+1}=(L+D)x_k +b$ donde definimos A como $A=U-D-L$ ? Entiendo que es importante que $det(D) \neq 0$ . ¿Es esto más probable en una matriz diagonal? ¿No podríamos alterar el método en función de la matriz A que tengamos? Si por ejemplo $det(D)=0$ pero observamos que $det(U) \neq 0$ ¿podríamos entonces modificar nuestro método?

Answer 1

Es fácil perder de vista la intuición sencilla y clara que hay detrás del método de Jacobi cuando se expresa utilizando la notación matricial. La idea es la siguiente. Supongamos que queremos resolver el sistema lineal

\begin{align} a_{11} x_1 + \cdots + a_{1n} x_n &= b_1 \\ & \vdots \\ a_{n1} x_1 + \cdots + a_{nn} x_n &= b_n, \end{align} y supongamos que nuestra mejor estimación actual para la solución es $$ x^k = \begin{bmatrix} x_1^k \\ \vdots \\ x_n^k \end{bmatrix}. $$ Una idea muy sencilla es resolver la primera ecuación para $x_1$ y utilizar nuestra estimación más reciente para los otros componentes de $x$ así: $$ x_1^{k+1} = -\frac{a_{12}}{a_{11}} x_2^k - \cdots - \frac{a_{1n}}{a_{11}} x_n^k. $$ Calculamos $x_2^{k+1},\ldots, x_n^{k+1}$ de forma similar (y podemos calcularlos todos en paralelo). Eso es todo el método de Jacobi. También puedes ver cómo una estrategia similar conduce al método de Gauss-Seidel.

Answer 2

El método de Jacobi forma parte de una clase más amplia de métodos de "división de matrices". Permítanme explicar...

Métodos de división

Supongamos que podemos escribir $A$ como una diferencia de matrices $A=M-N$ tal que $M$ es no singular. Nos referimos a $M$ y $N$ como dividir de la matriz $A$ . Se deduce que para cualquier $x$ Satisfaciendo a $Ax=b$ , $$ x=M^{-1}b+M^{-1}Nx. $$ Esto sugiere definir el llamado método de división $$ x_{k+1}=M^{-1}b+M^{-1}Nx_{k}. $$

En general, queremos elegir la división tal que

• $M$ es fácil de invertir (computacionalmente) y
• el radio espectral de $M^{-1}N$ es estrictamente menor que uno.

Esta última es una condición necesaria y suficiente para garantizar la convergencia del método. De hecho, cuanto menor sea el radio espectral, más rápido se espera que converja el método.

Método Jacobi

Una opción de división es el método de Jacobi, en el que tomamos $M=D$ y $N=L+U$ como sugieres en tu post. Esta elección está motivada por el hecho de que cuando $M$ es invertible, su inversa es trivial de calcular. Tenemos el siguiente resultado para el método de Jacobi:

Teorema . Si $A$ es estrictamente diagonalmente dominante ( $|a_{ii}|>\sum_{j\neq i}|a_{ij}|$ ), el método de Jacobi converge.

Prueba . $$ \rho(D^{-1}\left(L+U\right)) \leq \left\Vert D^{-1}(L+U)\right\Vert _{\infty} =\max_{i}\frac{\sum_{_{j\neq i}}\left|a_{ij}\right|}{\left|a_{ii}\right|} <1. $$

Otras divisiones

• Método de Gauss-Seidel: $M=D-L$ y $N=U$ .
• Relajación excesiva sucesiva (SOR): $M=D/\omega-L$ y $N=(1-1/\omega)D-U$ donde $\omega>1$ .

Nota: : observe que Gauss-Seidel no es más que un caso especial de SOR (tome $\omega = 1$ ).