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 calculo 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.