Iteracion y convergencia de sistemas de ecuaciones

Iteracion y convergencia de sistemas de ecuaciones

Conceptos básicos

En general, en todos los procesos iterativos para resolver el sistema Ax=b se recurre a una cierta matriz Q, llamada matriz descomposición, escogida de tal forma que el problema original adopte la forma equivalente:

Qx = (Q-A)x+b (62)

La ecuación (62) sugiere un proceso iterativo que se concreta al escribir:

(63)

El vector inicial x(0) puede ser arbitrario, aunque si se dispone de un buen candidato como solución éste es el que se debe emplear. La aproximación inicial que se adopta, a no ser que se disponga de una mejor, es la idénticamente nula . A partir de la ecuación (63) se puede calcular una sucesión de vectores x(1), x(2), .... Nuestro objetivo es escoger una matriz Q de manera que:

• se pueda calcular fácilmente la sucesión [x(k)].

• la sucesión [x(k)] converja rápidamente a la solución.

Como en todo método iterativo, deberemos especificar un criterio de convergencia y un número máximo de iteraciones M, para asegurar que el proceso se detiene si no se alcanza la convergencia. En este caso, puesto que x es un vector, emplearemos dos criterios de convergencia que se deberán satisfacer simultáneamente:

1.

El módulo del vector diferencia, , partido por el módulo del vector x, deberá ser menor que la convergencia deseada:

2.

La diferencia relativa del mayor elemento en valor absoluto del vector x(k), , deberá ser diez veces menor que :

Método de Richardson

El método de Richardson toma como matriz Q la matriz identidad (I). En este caso la ecuación (63) queda en la forma:

Ix(k) = (I-A)x(k-1)+b = x(k-1)+r(k-1) (64)

en donde r(k-1) es el vector residual definido mediante r(k-1)=b-Ax(k-1).

La matriz identidad es aquella matriz diagonal cuyos elementos no nulos son 1, es decir:

y cumple que

IA = A

para cualquier valor de A; es decir, es el elemento neutro del producto matricial. De acuerdo con esto, la ecuación (64) se puede escribir como:

x(k) = x(k-1) - Ax(k-1) + b = x(k-1) + r(k-1)

en donde un elemento cualquiera del vector r(k-1) vendrá dado por la expresión:

En la figura (13) se muestra un algoritmo para ejecutar la iteración de Richardson. Este método recibe también el nombre de método de relajación o método de los residuos.

Figure: Implementación del algoritmo iterativo de Richardson.

Método de Jacobi

En la iteración de Jacobi, se escoge una matriz Q que es diagonal y cuyos elementos diagonales son los mismos que los de la matriz A. La matriz Q toma la forma:

y la ecuación general (63) se puede escribir como

Qx(k) = (Q-A)x(k-1) + b (65)

Si denominamos R a la matriz A-Q:

...