Metodo 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 0 iterativos. En ellos se comienza con x = (x1 , x2 , ..., x0 ), unaaproximaci´n o n 0 inicial de la soluci´n. A partir de x 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→∞

Generalmentelos 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. ´ En cada iteraci´n del m´todo de Gauss-Seidel, hayn 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 x1 = 1
1 xi

b1 − (a12 x0 + a13 x0 + · · · + a1n x0 ) n 3 2 , a11 = x0 , i = 2, ..., n. i

En la segunda subiteraci´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
2 xi

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 coordenadas x1 , x2 , ..., xn−1 no se modifican. El c´lculo de xn se a a 1

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

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

partiendo de x0 = (1, 2, 3, 4). x1 = 1 x1 x2 2 x2 x3 3 x3 x4 4 x4

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



 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).

Una vez que se ha hecho una iteraci´n completa (n subiteraciones), se utiliza o el ultimo x obtenido como aproximaci´ninicial 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 3.0000 3.0000 3.0000 3.0000 3.0000 3.0000 3.00003.0000

−1.0114 −0.9997 −0.9997 −0.9997 −0.9997 −1.0000 −1.0000 −1.0000 −1.0000 −1.0000 −1.0000 −1.0000

2.0025 2.0025 2.0002 2.0002 2.0002 2.0002 2.0000 2.0000 2.0000 2.0000 2.0000 2.0000

1.9991 1.9991 1.9991 1.9998 1.9998 1.9998 1.9998 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 dexk 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 converge, entonces otra detenci´n del proceso, e o no deseada pero posible, est´ determinada cuando el n´ mero de iteraciones a u realizadas es igual a un n´ mero m´ximo de iteraciones previsto. u a El siguiente ejemplo no es convergente, ni siquiera empezando de...