Metodo de gauss seidel

0.1

M´todo de Gauss-Seidel
e

Los m´todos de Gauss y Cholesky hacen parte de los m´todos directos o
e
e
finitos. Al cabo de un n´ mero finito de operaciones, en ausencia de errores
u
de redondeo, se obtiene x∗ soluci´n del sistema Ax = b.
o
El m´todo de Gauss-Seidel hace parte de los m´todos llamados indirectos o
e
e
0
0
iterativos. En ellos se comienza con x = (x1 , x0 , ..., x0), una aproximaci´n
o
2
n
inicial de la soluci´n. A partir de x0 se construye una nueva aproximaci´n de
o
o
la soluci´n, x1 = (x1 , x1 , ..., x1 ). A partir de x1 se construye x2 (aqu´ el suo
ı
1
2
n
per´
ındice indica la iteraci´n y no indica una potencia). As´ sucesivamente se
o
ı
construye una sucesi´n de vectores {xk }, con el objetivo, no siempre garano
tizado, de que
lim xk= x∗ .
k →∞

Generalmente los m´todos indirectos son una buena opci´n cuando la matriz
e
o
es muy grande y dispersa o rala (sparse ), es decir, cuando el n´ mero de
u
2
elementos no nulos es peque˜ o comparado con n , n´ mero total de elementos
n
u
de A. En estos casos se debe utilizar una estructura de datos adecuada que
permita almacenar unicamente los elementos no nulos.
´
Encada iteraci´n del m´todo de Gauss-Seidel, hay n subiteraciones. En la
o
e
primera subiteraci´n se modifica unicamente x1 . Las dem´s coordenadas x2 ,
o
´
a
x3 , ..., xn no se modifican. El c´lculo de x1 se hace de tal manera que se
a
satisfaga la primera ecuaci´n.
o
b1 − (a12 x0 + a13 x0 + · · · + a1n x0 )
n
3
2
,
a11
= x0 , i = 2, ..., n.
i

x1 =
1
x1
i

En la segundasubiteraci´n se modifica unicamente x2 . Las dem´s coordeo
´
a
nadas x1 , x3 , ..., xn no se modifican. El c´lculo de x2 se hace de tal manera
a
que se satisfaga la segunda ecuaci´n.
o
x2
2
x2
i

b2 − (a21 x1 + a23 x1 + · · · + a2n x1 )
n
3
1
=
,
a22
= x1 , i = 1, 3, ..., n.
i

As´ sucesivamente, en la n-´sima subiteraci´n se modifica unicamente xn .
ı
e
o
´
Las dem´s coordenadasx1 , x2 , ..., xn−1 no se modifican. El c´lculo de xn se
a
a
1

hace de tal manera que se satisfaga la n-´sima ecuaci´n.
e
o
n
n
n
bn − (an1 x1 −1 + an3 x3 −1 + · · · + ann xn−1 )
,
ann
n
= xi −1 , i = 1, 2, ..., n − 1.

xn =
n
xn
i

Ejemplo 0.1. Resolver

10
1

 −2
1


2 −1 0
x1
  x2
20 −2 3  
1 30 0   x3
2
3 20
x4

partiendo de x0 = (1, 2, 3,4).






26
  −15 
=

  53 
47

26 − (2 × 2 + (−1) × 3 + 0 × 4)
= 2.5,
10
= (2.5, 2, 3, 4).
−15 − (1 × 2.5 + (−2) × 3 + 3 × 4)
=
= −1.175,
20
= (2.5, −1.175, 3, 4).
53 − (−2 × 2.5 + 1 × (−1.175) + 0 × 4)
= 1.9725,
=
30
= (2.5, −1.175, 1.9725, 4).
47 − (1 × 2.5 + 2 × (−1.175) + 3 × 1.9725)
= 2.0466,
=
20
= (2.5, −1.175, 1.9725, 2.0466).

x1 =
1
x1x2
2
x2
x3
3
x3
x4
4
x4

Una vez que se ha hecho una iteraci´n completa (n subiteraciones), se utiliza
o
el ultimo x obtenido como aproximaci´n inicial y se vuelve a empezar; se
´
o
calcula x1 de tal manera que se satisfaga la primera ecuaci´n, luego se calcula
o
x2 ... A continuaci´n est´n las iteraciones siguientes para el ejemplo anterior.
o
a
3.0323
3.0323
3.0323
3.0323−1.1750
−1.0114
−1.0114
−1.0114
2

1.9725
1.9725
2.0025
2.0025

2.0466
2.0466
2.0466
1.9991

3.0025
3.0025
3.0025
3.0025

−1.0114
−0.9997
−0.9997
−0.9997

2.0025
2.0025
2.0002
2.0002

1.9991
1.9991
1.9991
1.9998

3.0000
3.0000
3.0000
3.0000

−0.9997
−1.0000
−1.0000
−1.0000

2.0002
2.0002
2.0000
2.0000

1.9998
1.9998
1.9998
2.0000

3.00003.0000
3.0000
3.0000

−1.0000
−1.0000
−1.0000
−1.0000

2.0000
2.0000
2.0000
2.0000

2.0000
2.0000
2.0000
2.0000

Te´ricamente, el m´todo de Gauss-Seidel puede ser un proceso infinito. En
o
e
la pr´ctica el proceso se acaba cuando de xk a xk+n los cambios son muy
a
peque˜ os. Esto quiere decir que el x actual es casi la soluci´n x∗ .
n
o
Como el m´todo no siempre...