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:

la ecuación (65) se puede reescribir como:

Qx(k) = -Rx(k-1) + b

El producto de la matriz Q por el vector columna x(k) será un vector columna. De modo análogo, el producto de la matriz R por el vector columna x(k-1) será también un vector columna. La expresión anterior, que es una ecuación vectorial, se puede expresar por necuaciones escalares (una para cada componente del vector). De este modo, podemos escribir, para un elemento i cualquiera y teniendo en cuenta que se trata de un producto matriz-vector:

Si tenemos en cuenta que en la matriz Q todos los elementos fuera de la diagonal son cero, en el primer miembro el único término no nulo del sumatorio es el que contiene el elemento

...