Mtodo de Gauss-SeidelIng. Marvin Hernndez II Semestre 2008Instituto Tecnolgico de Costa RicaCM 3201 Mtodos Numricos
NDICEIntroduccinDescripcin del Criterio de ConvergenciaErroresEjemplo 1Ejemplo 2Ejemplo 3 Ejemplo 4Bibliografa
IntroduccinEste mtodo se basa en la aproximacin iterativa propuesta por Seidel en 1874 en la Academia de Ciencias de Munich, para la aplicacin al problema del flujo de potencia.
La ecuacin anterior es el corazn del algoritmo iterativo. La iteracin comienza con una estimacin de las magnitudes y ngulos de todas las barras del sistema, y se van recalculando las tensiones utilizando los mejores valores disponibles. Esto es, para calcular la tensin Vk se utilizan los V1...k-1 ya actualizados, y los Vk...n del paso anterior. El mtodo tiene una convergencia extremadamente lenta pero segura (excepto para problemas mal condicionados, o sin convergencia posible).
El mtodo de Gauss-Seidel pertenece a la familia de los mtodos iterativos utilizados para obtener la o las races de una funcin cualquiera, especialmente en forma de matrices de n ecuaciones [A]{X}={B}
Si los elementos de la diagonal de la matriz que se est solucionando no son todos cero la 1era se resuelve para x1, la 2da para x2 y la tercera para x3, y la ensima para xn para obtener:
X1= ( b1 a12x2 a13x3 ) / a11
X2 = ( b2 a21x1 a23x3 ) / a22
X3 = ( b3 a31x1 a32x2 ) / a33 . . . Xn = ( bn an1x1 - - ann-1xn-1 ) / ann
TeoremaConsiderar un sistema de n ecuaciones con n incgnitas, es decir, se tiene una matriz de coeficientes A cuadrada. Si el valor absoluto del elemento de la diagonal de cada rengln de A es ms grande que la suma de los valores absolutos de los otros elementos de tal rengln entonces el sistema tiene una solucin nica. El mtodo iterativo de Gauss-Seidel converger a la solucin sin importar los valores iniciales.
Este criterio no solo se aplica a las ecuaciones lineales que se resuelven con el mtodo de Gauss-Seidel sino tambin para el mtodo iterativo del punto fijo y el mtodo de Jacobi . Por tanto, al aplicar este criterio sobre las ecuaciones de Gauss-Seidel y evaluando con respecto a cada una de las incgnitas, obtenemos la expresin siguiente:
El valor absoluto de las pendientes en la ecuacin, debe ser menor que la unidad para asegurar la convergencia.
Es decir, el elemento diagonal debe ser mayor que el elemento fuera de la diagonal para cada regln de ecuaciones. La generalizacin del criterio anterior para un sistema de n ecuaciones es:
Criterio de Convergencia
Ejemplos de convergenciaIteraciones utilizando las siguientes ecuaciones sin ordenar
Acomodadas
Convergencia Seidel
X1X2
0.000.00
9.000.00
9.0014.38
20.7714.38
20.774.43
12.624.43
12.6211.32
18.2611.32
18.266.55
14.366.55
14.369.85
17.069.85
17.067.56
15.197.56
15.199.15
16.489.15
16.488.05
15.598.05
15.598.81
Convergencia Jacobi
X1X2
0.000.00
9.0022.00
27.0014.38
20.77-0.85
8.314.43
12.6214.97
21.2511.32
18.264.02
12.296.55
14.3611.60
18.499.85
17.066.35
14.207.56
15.199.99
17.179.15
16.487.47
15.118.05
Acomodadas
X2
X1
X2
Convergencia Seidel
Sin acomodar
X2
X1
X2
Convergencia Jacobi
Divergencia Seidel
X1X2
0.000.00
26.000.00
26.0020.78
1.4420.78
1.44-9.23
36.91-9.23
36.9134.12
-14.3234.12
-14.32-28.50
59.68-28.50
59.6861.95
-47.2161.95
-47.21-68.70
107.19-68.70
107.19120.01
-115.83120.01
-115.83-152.57
Divergencia Jacobi
X1X2
0.000.00
26.00-11.00
39.0020.78
1.4436.67
-17.33-9.23
36.91-32.19
64.0434.12
-14.3267.27
-53.50-28.50
59.68-76.39
X2
X1
X2
Divergencia Seidel
X2
X1
X2
Divergencia Jacobi
Iteraciones utilizando previamente el criterio de diagonal dominanteEjemplos de convergencia
Acomodadas
Convergencia Seidel
X1X2
0.000.00
9.000.00
9.0014.38
20.7714.38
20.774.43
12.624.43
12.6211.32
18.2611.32
18.266.55
14.366.55
14.369.85
17.069.85
17.067.56
15.197.56
15.199.15
16.489.15
16.488.05
15.598.05
15.598.81
Convergencia Jacobi
X1X2
0.000.00
9.0022.00
27.0014.38
20.77-0.85
8.314.43
12.6214.97
21.2511.32
18.264.02
12.296.55
14.3611.60
18.499.85
17.066.35
14.207.56
15.199.99
17.179.15
16.487.47
15.118.05
Acomodadas
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
X2
X1
X2
Convergencia Seidel
Sin acomodar
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
X2
X1
X2
Convergencia Jacobi
Divergencia Seidel
X1X2
0.000.00
26.000.00
26.0020.78
1.4420.78
1.44-9.23
36.91-9.23
36.9134.12
-14.3234.12
-14.32-28.50
59.68-28.50
59.6861.95
-47.2161.95
-47.21-68.70
107.19-68.70
107.19120.01
-115.83120.01
-115.83-152.57
Divergencia Jacobi
X1X2
0.000.00
26.00-11.00
39.0020.78
1.4436.67
-17.33-9.23
36.91-32.19
64.0434.12
-14.3267.27
-53.50-28.50
59.68-76.39
0
0
0
0
0
0
0
0
0
0
0
X2
X1
X2
Divergencia Seidel
0
0
0
0
0
0
0
0
0
0
X2
X1
X2
Divergencia Jacobi
En Resumen
El mtodo de Gauss-Seidel est basado en el concepto de punto fijo, es decir ( xi = gi (x), i = 1.. n), para resolver sistemas de ecuaciones lineales.
Para garantizar la convergencia se debe de cumplir que el sistema tenga una diagonal dominante, es decir que se cumpla la desigualdad dada abajo; si se cambia el orden de las ecuaciones puede haber divergencia.
En Resumen
Adems, se destaca que para mejorar la convergencia, se usan tcnicas como:
Utilizacin de los clculos previos asumiendo una mejor aproximacin que el vector de condiciones iniciales. ( Gauss-Seidel ).
Un factor de ponderacin para reducir el error residual ( Relajacin )
Errores de Gauss- SeidelVentajas?Espacio: convenientes para matrices cuadradasTiempo: menor nmero de operaciones
Desventajas?Velocidad: convergencia lentaConvergencia: no siempre se obtiene la solucin en un nmero finito de pasos
Anlisis de error
EJEMPLO #1Resolver el siguiente sistema de ecuacin por el mtodo Gauss-Seidel utilizando un E= 0.001.
0.1 X1 + 7.0 X2 - 0.3 X3 = -19.303.0 X1 - 0.1 X2 - 0.2 X3 = 7.850.3 X1 - 0.2 X2 - 10.0 X3 = 71.40
SOLUCIN:
Primero ordenamos las ecuaciones, de modo que en la diagonal principal estn los coeficientes mayores para asegurar la convergencia.
3.0 X1 - 0.1 X2 - 0.2 X3 = 7.850.1 X1 + 7.0 X2 - 0.3 X3 = -19.300.3 X1 - 0.2 X2 - 10.0 X3 = 71.40
Despejamos cada una de las variables sobre la diagonal:
Suponemos los valores iniciales X2 = 0 y X3 = 0 y calculamos X1
Este valor junto con el de X3 se puede utilizar para obtener X2
La primera iteracin se completa sustituyendo los valores de X1 y X2 calculados obteniendo:
En la segunda iteracin, se repite el mismo procedimiento:
Comparando los valores calculados entre la primera y la segunda iteracin
Como podemos observar, no se cumple la condicin
Entonces tomamos los valores calculados en la ltima iteracin y se toman como supuestos para la siguiente iteracin. Se repite entonces el proceso:
Comparando de nuevo los valores obtenidos
Como se observa todava no se cumple la condicin
As que hacemos otra iteracin
Comparando los valores obtenidos
Dado que se cumple la condicin, el resultado es:
X1 = 3.0 X2 = -2.5 X3 = 7.0
EJEMPLO #2Usar el mtodo de Gauss-Seidel para aproximar la solucin del sistema:
(1)
(2)
(3)
hasta que:
SolucinPrimero despejamos las incgnitas x1, x2 y x3 de las ecuaciones 1, 2 y 3. As tenemos:
Estas son nuestro juego de frmulas iterativas. Comenzamos iteraciones, sustituyendo x1=x2=0 en la 1ra ecuacin, para calcular el 1er valor de x1:
Ahora, sustituimos x1=2.66667 y x3=0 en la segunda ecuacin, para obtener x2 :
Ahora sustituimos x1=2.66667 y x2=-2.82381 en la tercera ecuacin, para obtener x3:
As, tenemos nuestra primera aproximacin a la solucin del sistema: x1=2.66667, x2=-2.82381, x3=7.1051
Puesto que todava no podemos calcular ningn error aproximado, repetimos el proceso pero ahora con los ltimos datos obtenidos para las incgnitas:
Sustituyendo x2=-2.82381 y x3=7.1051 en la ecuacin 1 obtenemos x1=3.6626. Sustituyendo x1=3.6626 y x3=7.1051 en la ecuacin 2 obtenemos x2=-3.24404, finalmente, sustituyendo x1=3.6626 y x2=-3.24404 en la ecuacin 3 obtenemos x3=7.06106.
As, tenemos la 2da lista de valores de aproximacin a la solucin del sistema:
Ahora si podemos calcular los errores absolutos para las incgnitas. Tenemos:
Puesto que no se ha logrado el objetivo, se repite el mismo proceso con los ltimos valores obtenidos de cada una de las incgnitas. Note que aunque el error aproximado ya cumple con ser menor al 1%, esto se debe de cumplir para los tres errores aproximados!Por lo tanto repetimos el mismo proceso. Omitiendo los pasos intermedios, obtenemos:
Y en este caso tenemos los siguientes errores aproximados:
Vemos que ahora s se ha cumplido el objetivo para cada uno de los errores aproximados. Por lo tanto, concluimos que la solucin aproximada es:
X1=3.62724, X2=-3.24102, X3=7.06250
BibliografaSteven Chapra, Raymond Canale. Mtodos numricos para ingenieros, cuarta edicin, 2003. pp 301-313, 320-321, 344-346.The Jacobi Method, marzo 2004. (disponible en http:/www.netlib2.cs.utk.edu/linalg/html_templates/node12.html)The Gauss_Seidel Method, marzo 2004. (disponible en http:/www.netlib2.cs.utk.edu/linalg/html_templates/node14.html)The Successive Overrelaxation Method, marzo 2004. (disponible en http:/www.netlib2.cs.utk.edu/linalg/html_templates/node15.html)