Métodos iterativos para Resolver Ax = b – Método de Jacobi

Quizás el método iterativo más simple para resolver Ax = b es el Método de Jacobi. Tenga en cuenta que la simplicidad de este método es tanto buena como mala: buena, porque es relativamente fácil de entender y, por lo tanto, es un buen primer gusto de los métodos iterativos; mala, porque no se usa típicamente en la práctica (aunque su utilidad potencial se ha reconsiderado con la llegada de la computación paralela). Aún así, es un buen punto de partida para aprender sobre métodos iterativos más útiles, pero más complicados.

Dada una aproximación actual

x(k) = (x1(k), x2(k), x3(k), …, xn(k))

para x, la estrategia del Método de Jacobi es usar la primera ecuación y los valores actuales de x2(k), x3(k), …, xn(k) para encontrar un nuevo valor x1(k+1), y de manera similar para encontrar un nuevo valor xi(k) utilizando la i-ésima ecuación y los valores antiguos de las otras variables. Es decir, dadas las actuales valores de x(k) = (x1(k) x2(k), …, xn(k)), encontrar nuevos valores mediante la resolución de

x(k+1) = (x1(k+1), x2(k+1), …, xn(k+1))

en

Este sistema también puede ser escrito como

Para ser claros, el subíndice i significa que xi(k) es el i ésimo elemento del vector

x(k) = (x1(k) x2(k), …, xi(k), …, xn(k) ),

y el superíndice k corresponde a la iteración particular (no la kth poder de xi ).

Si escribimos D, L y U para la diagonal, la triangular inferior estricta y la triangular superior estricta y las partes de A, respectivamente,

entonces el método de Jacobi se puede escribir en notación matricial-vectorial como

Ejemplo 1

Vamos a aplicar el método de Jacobi al sistema

.

En cada paso, dada la actual valores de x1(k) x2(k), x3(k), podemos resolver para x1(k+1), x2(k+1) y x3(k+1) en

.

Entonces, si nuestra conjetura inicial x(0) = (x1 (0), x2(0), x3 (0)) es el vector cero 0 = (0,0,0), una conjetura inicial común a menos que tengamos alguna información adicional que nos lleve a elegir otra, entonces encontramos x(1) = (x1(1), x2 (1), x3(1)) resolviendo

Así que x(1) = (x1(1), x2 (1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Repetimos este proceso para encontrar una secuencia de aproximaciones cada vez mejores x(0), x(1), x(2), … . Mostramos los resultados en la siguiente tabla, con todos los valores redondeados a 3 decimales.

Estamos interesados en el error e en cada iteración entre la verdadera solución x y la aproximación x(k): e(k) = x − x(k) . Obviamente, generalmente no conocemos la solución verdadera x. Sin embargo, para comprender mejor el comportamiento de un método iterativo, es esclarecedor usar el método para resolver un sistema Ax = b para el cual conocemos la solución verdadera y analizamos la rapidez con la que las aproximaciones convergen a la solución verdadera. Para este ejemplo, la solución verdadera es x = (1, 2, -1).

La norma de un vector|| x / / nos dice qué tan grande es el vector como un todo (a diferencia de lo grande que es cada elemento del vector). La norma vectorial más utilizada en álgebra lineal es la norma l2:

Por ejemplo, si x = (1, 2, -1), entonces

En este módulo, siempre usaremos la norma l2 (incluso para las normas de matriz en tutoriales posteriores), de modo que | / / / siempre signifique|| ||2.

Para nuestros propósitos, observamos que|| x / / será pequeño exactamente cuando cada uno de los elementos x1, x2,…, xn en x = (x1, x2, …, xn ) es pequeño. En la siguiente tabla, la norma del error se hace progresivamente más pequeña a medida que el error en cada uno de los tres elementos x1, x2, x3 se hace más pequeño, o en otras palabras, a medida que las aproximaciones se vuelven progresivamente mejores.