Métodos Iterativos para
solucionar sistemas lineales.
Método iterativo de Jacobi.
Consideremos
el siguiente sistema de ecuaciones.
a11 |
a12 |
a13 |
|
x1 |
|
b1 |
a21 |
a22 |
a23 |
|
x2 |
= |
b2 |
a31 |
a32 |
a33 |
|
x3 |
|
b3 |
Vamos a
representar cada una de las variables en términos de ellas mismas.
b1 - a12x2 -
a13x3
x1 = ------------------
a11
b2 – a21x1 –
a23x3
x2 = ------------------
a22
b3 – a31x1 –
a32x2
x3 = ------------------
a22
Lo cual nos sugiere el siguiente esquema iterativo de solución.
b1 - a12x2(t) -
a13x3(t)
x1(t+1) = ----------------------
a11
b2 – a21x1(t)
– a23x3(t)
x2(t+1) = ----------------------
a22
b1 – a31x1(t)
– a32x2(t)
x3(t+1) = ----------------------
a33
En general podemos escribir como
b1 – Si=1, i !=k, n akixi(t)
xk(t+1)
= ----------------------
akk
Algoritmo iterativo
de Gauss-Seidel.
El cambio que debemos hacer respecto al de Jacobi, es que las variables nuevas son utilizadas una vez que se realiza el cálculo de ellas así, para un sistema de tres ecuaciones tendremos:
b1 - a12x2(t) -
a13x3(t)
x1(t+1) = ----------------------
a11
b2 – a21x1(t+1)
– a23x3(t)
x2(t+1) = ------------------------
a22
b1 – a31x1(t+1)
– a32x2(t+1)
x3(t+1) = --------------------------
a33
Ejemplo.
Resolver el siguiente sistema de ecuaciones
utilizando el método de Jacobi y comparar con el método de Gauss-Seidel.
4 |
-1 |
1 |
|
x1 |
|
7 |
4 |
-8 |
1 |
|
x2 |
= |
-21 |
-2 |
1 |
5 |
|
x3 |
|
15 |
Las primeras 20 iteraciones del algoritmo de Jacobi son :
k |
x(1) |
x(2) |
x(3) |
1 |
1.0000 |
2.0000 |
2.0000 |
2 |
1.7500 |
3.3750 |
3.0000 |
3 |
1.8438 |
3.8750 |
3.0250 |
4 |
1.9625 |
3.9250 |
2.9625 |
5 |
1.9906 |
3.9766 |
3.0000 |
6 |
1.9941 |
3.9953 |
3.0009 |
7 |
1.9986 |
3.9972 |
2.9986 |
8 |
1.9996 |
3.9991 |
3.0000 |
9 |
1.9998 |
3.9998 |
3.0000 |
10 |
1.9999 |
3.9999 |
2.9999 |
11 |
2.0000 |
4.0000 |
3.0000 |
12 |
2.0000 |
4.0000 |
3.0000 |
13 |
2.0000 |
4.0000 |
3.0000 |
14 |
2.0000 |
4.0000 |
3.0000 |
15 |
2.0000 |
4.0000 |
3.0000 |
16 |
2.0000 |
4.0000 |
3.0000 |
17 |
2.0000 |
4.0000 |
3.0000 |
18 |
2.0000 |
4.0000 |
3.0000 |
19 |
2.0000 |
4.0000 |
3.0000 |
20 |
2.0000 |
4.0000 |
3.0000 |
La solución utilizando Gauss-Seidel es :
k |
x(0) |
x(1) |
x(3) |
1 |
1.0000 |
2.0000 |
2.0000 |
2 |
1.7500 |
3.7500 |
2.9500 |
3 |
1.9500 |
3.9688 |
2.9863 |
4 |
1.9956 |
3.9961 |
2.9990 |
5 |
1.9993 |
3.9995 |
2.9998 |
6 |
1.9999 |
3.9999 |
3.0000 |
7 |
2.0000 |
4.0000 |
3.0000 |
8 |
2.0000 |
4.0000 |
3.0000 |
9 |
2.0000 |
4.0000 |
3.0000 |
10 |
2.0000 |
4.0000 |
3.0000 |
11 |
2.0000 |
4.0000 |
3.0000 |
12 |
2.0000 |
4.0000 |
3.0000 |
13 |
2.0000 |
4.0000 |
3.0000 |
14 |
2.0000 |
4.0000 |
3.0000 |
15 |
2.0000 |
4.0000 |
3.0000 |
16 |
2.0000 |
4.0000 |
3.0000 |
17 |
2.0000 |
4.0000 |
3.0000 |
18 |
2.0000 |
4.0000 |
3.0000 |
19 |
2.0000 |
4.0000 |
3.0000 |
20 |
2.0000 |
4.0000 |
3.0000 |
Note que Gauss-Seidel requiere de 7 iteraciones mientras Jacobi de 11, para convergir.