M´etodos Iterativos para Resolver Sistemas Lineales Departamento de Matem´aticas, CCIR/ITESM 17 de julio de 2009
´Indice 3.1. Introducci´ on . . . . . . . . . . . . . . . 3.2. Objetivos . . . . . . . . . . . . . . . . 3.3. Generalidades . . . . . . . . . . . . . . 3.4. M´etodo Iterativo: Un ejemplo . . . . . 3.5. Ventajas y Desventajas . . . . . . . . . 3.6. M´etodo Iterativo General . . . . . . . 3.7. Metodo de Jacobi: Idea . . . . . . . . 3.8. Convergencia y convergencia en Jacobi 3.9. Matriz Diagonalmente Dominante . . 3.10. Orden conveniente para Jacobi . . . . 3.11. El M´etodo de Gauss-Seidel: Idea . . . 3.12. M´etodo de Gauss-Seidel: Ejemplos . . 3.13. Costo computacional . . . . . . . . . .
3.1.
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
1 1 2 2 2 3 3 5 5 5 6 6 7
Introducci´ on
En esta lectura veremos procedimientos iterativos para resolver un sistema de ecuaciones lineales. El primero de ellos conocido como el procedimiento de Jacobi basado en la idea de punto fijo y un segundo procedimiento conocido como m´etodo de Gauss-Seidel el cual es una modificaci´on simple del procedimiento de Jacobi. Introduciremos el concepto de matriz diagonalmente dominante el cual se relaciona con la garant´ıa de convergencia en la aplicaci´on de los m´etodos vistos. Veremos que en algunos casos es posible replantear el sistema para garantizar la convergencia. Asimismo se comentar´ a en qu´e situaciones los m´etodos iterativos son m´ as convenientes a los m´etodos directos.
3.2.
Objetivos
Ser´ a importante que usted Entienda los conceptos: • m´etodo iterativo, • ecuaci´on de recurrencia, • convergencia, • matriz diagonalmente dominante En t´erminos cualitativos • Entienda la diferencia entre un m´etodo directo y uno iterativo.
• Entienda la conveniencia de usar un m´etodo iterativo y uno directo. Entienda y mecanice los procedimientos de • M´etodo de Jacobi, y • M´etodo de Gauss-Seidel.
3.3.
Generalidades
Un m´etodo iterativo es un m´etodo que progresivamente va calculando aproximaciones a la soluci´ on de un problema. En Matem´ aticas, en un m´etodo iterativo se repite un mismo proceso de mejora sobre una soluci´on aproximada: se espera que lo obtenido sea una soluci´ on m´ as aproximada que la inicial. El proceso se repite sobre esta nueva soluci´ on hasta que el resultado m´ as reciente satisfaga ciertos requisitos. A diferencia de los m´etodos directos, en los cuales se debe terminar el proceso para tener la respuesta, en los m´etodos iterativos se puede suspender el proceso al termino de una iteraci´on y se obtiene una aproximaci´on a la soluci´ on.
3.4.
M´ etodo Iterativo: Un ejemplo
Considere el problema de encontrar una ra´ız a una ecuaci´on cuadr´ atica, por ejemplo: f (x) = x2 − x − 2 = 0 Un m´etodo directo para resolverlo es aplicar la f´ ormula general q −(−1) ± (−1)2 − 4(1)(−2) = −1, 2 x= 2(1) Un m´etodo iterativo es el m´etodo de Newton que consiste en usar la f´ ormula de mejora: xi+1 = xi −
f (xi ) xi 2 − xi − 2 = x − i f ′ (xi ) 2 xi − 1
Si tomamos como primera aproximaci´on x0 = 3 (para i = 0), tendremos x1 = x0 −
x0 2 − x0 − 2 32 − 3 − 2 =3− ≈ 2.2 2 x0 − 1 2·3−1
Si ahora tomamos como aproximaci´on x1 = 2.2 y aplicamos de nuevo la f´ ormula tendremos: x2 = x1 −
2.22 − 2.2 − 2 x1 2 − x1 − 2 = 2.2 − ≈ 2.011 2 x1 − 1 2 · 2.2 − 1
Si ahora tomamos como aproximaci´on x2 = 2.011 y aplicamos de nuevo la f´ ormula tendremos: x3 = x2 −
2.0112 − 2.011 − 2 x2 2 − x2 − 2 = 2.011 − ≈ 2.00004 2 x2 − 1 2 · 2.011 − 1
Etceter´a.
3.5.
Ventajas y Desventajas
Un elemento en contra que tienen los m´etodos iterativos sobre los m´etodos directos es que calculan aproximaciones a la soluci´ on. Los m´etodos iterativos se usan cuando no se conoce un m´etodo para obtener la soluci´on en forma exacta. Tambi´en se utilizan cuando el m´etodo para determinar la soluci´ on exacta requiere mucho tiempo de c´alculo, cuando una respuesta aproximada es adecuada, y cuando el n´ umero de iteraciones es relativamente reducido. 2
3.6.
M´ etodo Iterativo General
Un m´etodo iterativo consta de los siguientes pasos. 1. inicia con una soluci´ on aproximada (Semilla), 2. ejecuta una serie de c´alculos para obtener o construir una mejor aproximaci´on partiendo de la aproxion maci´ on semilla. La f´ ormula que permite construir la aproximaci´on usando otra se conoce como ecuaci´ de recurrencia. 3. se repite el paso anterior pero usando como semilla la aproximaci´on obtenida.
3.7.
Metodo de Jacobi: Idea
El m´etodo Jacobi es el m´etodo iterativo para resolver sistemas de ecuaciones lineales m´ as simple y se aplica s´olo a sistemas cuadrados, es decir a sistemas con tantas inc´ognitas como ecuaciones. 1. Primero se determina la ecuaci´on de recurrencia. Para ello se ordenan las ecuaciones y las inc´ognitas. De la ecuaci´on i se despeja la inc´ognita i. En notaci´ on matricial se escribirse como: x = c + Bx
(1)
donde x es el vector de inc´ognitas. 2. Se toma una aproximaci´on para las soluciones y a ´esta se le designa por xo 3. Se itera en el ciclo que cambia la aproximaci´on xi+1 = c + Bxi
(2)
Ejemplo 3.1 Partiendo de (x = 1, y = 2) aplique dos iteraciones del m´etodo de Jacobi para resolver el sistema:
5x + 2y = 1 x − 4y = 0
Soluci´ on Debemos primeramente despejar de la ecuaci´on la inc´ognita correspondiente. x = 0.20 + 0.00 x − 0.40 y y = 0.00 + 0.25 x + 0.00 y Escrito en la notaci´ on vectorial quedar´ıa: x 0.00 −0.40 0.20 x + = y 0.25 0.00 0.00 y Aplicamos la primera iteraci´on partiendo de x0 = 1.00 y y0 = 2.00: x1 = 0.20 + 0.00 (1.00) − 0.40 (2.00) = −0.60 y1 = 0.00 + 0.25 (1.00) + 0.00 (2.00) = 0.25
3
(3)
Aplicamos la segunda iteraci´on partiendo de x1 = −0.60 y y1 = 0.25: x2 = 0.20 + 0.00 (−0.60) − 0.40 (0.25) = 0.10 y2 = 0.00 + 0.25 (−0.60) + 0.00 (0.25) = −0.15 Aplicamos la siguiente iteraci´on partiendo de x2 = 0.10 y y1 = −0.15: x3 = 0.20 + 0.00 (0.10) − 0.40 (−0.15) = 0.26 y3 = 0.00 + 0.25 (0.10) + 0.00 (−0.15) = 0.025 Aplicamos la siguiente iteraci´on partiendo de x3 = 0.26 y y3 = 0.025: x4 = 0.20 + 0.00 (0.26) − 0.40 (0.025) = 0.190 y4 = 0.00 + 0.25 (0.26) + 0.00 (0.025) = 0.065 Aplicamos la siguiente iteraci´on partiendo de x4 = 0.190 y y4 = 0.065: x5 = 0.20 + 0.00 (0.19) − 0.40 (0.065) = 0.174 y5 = 0.00 + 0.25 (0.19) + 0.00 (0.065) = 0.0475 Aplicamos la siguiente iteraci´on partiendo de x5 = 0.174 y y5 = 0.0475: x6 = 0.20 + 0.00 (0.174) − 0.40 (0.0475) = 0.181 y6 = 0.00 + 0.25 (0.174) + 0.00 (0.0475) = 0.0435 Si uno dispone de una hoja de c´alculo como EXCEL es f´ acil realizar los c´alculos anteriores:
i 0 1 2 3 4 5 6
xi 1.000 -0.600 0.100 0.260 0.190 0.174 0.181
yi 2.000 0.250 -0.150 0.025 0.065 0.047 0.043
xi+1 -0.600 0.100 0.260 0.190 0.174 0.181 0.182
yi+1 0.250 -0.150 0.025 0.065 0.047 0.043 0.045
Di 1.750 0.700 0.175 0.070 0.017 0.007 0.001
donde Di = m´ ax (|xi − xi+1 |, |yi − yi+1 |) Este Di es utilizado como criterio de paro en las iteraciones: Cuando Di es menos que cierto valor dado (digamos 0.001) uno ya no realiza la siguiente iteraci´on. Si se grafica las aproximaciones obtenidas en el plano x − y se obtendr´ a algo como:
4
3.8.
Convergencia y convergencia en Jacobi
Uno de los principales problemas de los m´etodos iterativos es la garant´ıa de que el m´etodo va a converger, es decir, va a producir una sucesi´on de aproximaciones cada vez efectivamente m´ as pr´oximas a la soluci´ on. En el caso del m´etodo de Jacobi no existe una condici´on exacta para la convergencia. Lo mejor es una condici´on que garantiza la convergencia, pero en caso de no cumplirse puede o no haberla es la siguiente: Si la matriz de coeficientes original del sistema de ecuaciones es diagonalmente dominante, el m´etodo de Jacobi seguro converge.
3.9.
Matriz Diagonalmente Dominante
Una matriz se dice matriz diagonalmente dominante, si en cada uno de los renglones, el valor absoluto del elemento de la diagonal principal es mayor que la suma de los valores abslutos de los elementos restantes del mismo rengl´ on. A veces la matriz de un sistema de ecuaciones no es diagonalmente dominante pero cuando se cambian el orden de las ecuaciones y las inc´ognitas el nuevo sistema puede tener matriz de coeficientes diagonalmente dominante. Ejemplo 3.2 Son matrices diagonalmente dominantes: 4 1 1 −6 1 2 4 1 0 , 2 8 −3 , 1 3 3 8 3 2 9 3 2 −9 Ejemplo 3.3 No son matrices diagonalmente dominantes: 4 1 3 4 1 1 4 4 8 1 , 2 8 −7 , 2 3 8 3 −10 2 3 −10 20
3.10.
Orden conveniente para Jacobi
En ciertas ocasiones al aplicar Jacobi la matriz no es diagonalmente dominante y por tanto no existir´ a garant´ıa de convergencia. Sin embargo, en algunos casos ser´ a posible reordenar las inc´ognitas en otra manera de forma que la nueva matriz de coeficientes sea diagonalmente dominante. Esto se puede detectar revisando todos los posibles ordenamientos de las inc´ognitas y ver c´ omo es la matriz resultante. Claro que esto conlleva un bueno n´ umero de pruebas pues el n´ umero posible de ordenamientos en n variables es (n − 1)! pero cuando n es reducido es sencillo. Veamos algunos ejemplos. Ejemplo 3.4 Indique cu´ al es el orden conveniente para aplicar Jacobi al sistema: 3 x + 12 y − z = −2 3 12 −1 11 x − 4 y + 3 z = −3 → 11 −4 3 −3 x − 2 y − 12 z = −2 −3 −2 −12 Soluci´ on Con el orden y → x → z el sistema y su matriz de coeficientes quedan: 12 y + 3 x − z = −2 12 3 −1 − 4 y + 11 x + 3 z = −3 → −4 11 3 − 2 y − 3 x − 12 z = −2 −2 −3 −12 la matriz de coeficientes es diagonalmente dominante 5
3.11.
El M´ etodo de Gauss-Seidel: Idea
El m´etodo de Gauss-Seidel es muy semejante al m´etodo de Jacobi. Mientras que en el de Jacobi se utiliza el valor de las inc´ognitas para determinar una nueva aproximaci´on, en el de Gauss-Seidel se va utilizando los valores de las inc´ognitas recien calculados en la misma iteraci´on, y no en la siguiente. Por ejemplo, en el m´etodo de Jacobi se obtiene en el primer c´alculo xi+1 , pero este valor de x no se utiliza sino hasta la siguiente iteraci´on. En el m´etodo de Gauss-Seidel en lugar de eso se utiliza de xi+1 en lugar de xi en forma inmediata para calcular el valor de yi+1 de igual manera procede con las siguientes variables; siempre se utilizan las variables recien calculadas.
3.12.
M´ etodo de Gauss-Seidel: Ejemplos
Ejemplo 3.5 Partiendo de (x = 1, y = 2) aplique dos iteraciones del m´etodo de Gauss-Seidel para resolver el sistema: 5x + 2y = 1 x − 4y = 0 Soluci´ on Debemos primeramente despejar de la ecuaci´on la inc´ognita correspondiente. x = 0.20 + 0.00 x − 0.40 y y = 0.00 + 0.25 x + 0.00 y Aplicamos la primera iteraci´on partiendo de x0 = 1.00 y y0 = 2.00: x1 = 0.20 + 0.00 (+1.000) − 0.40 (2.00) = −0.600 y1 = 0.00 + 0.25 (−0.600) + 0.00 (2.00) = −0.15 Aplicamos la segunda iteraci´on partiendo de x1 = −0.600 y y1 = −0.15: x2 = 0.20 + 0.00 (−0.600) − 0.40 (−0.15) = 0.26 y2 = 0.00 + 0.25 (0.26) + 0.00 (−0.15) = 0.065 Aplicamos la tercera iteraci´on partiendo de x2 = 0.26 y y2 = 0.065: x2 = 0.20 + 0.00 (0.26) − 0.40 (0.065) = 0.174 y2 = 0.00 + 0.25 (0.174) + 0.00 (0.174) = 0.0435 Ejemplo 3.6 Partiendo de (x = 1, y = 2, z = 0) aplique dos iteraciones del m´etodo de Gauss-Seidel para resolver el sistema: 10 x + 0 y − z = −1 4 x + 12 y − 4 z = 8 4 x + 4 y + 10 z = 4 Soluci´ on Debemos primeramente despejar de la ecuaci´on la inc´ognita correspondiente. x = −0.10 + 0.00 x + 0.00 y + 0.10 z y = 0.66 − 0.33 x + 0.00 y + 0.33 z z = 0.40 − 0.40 x − 0.40 y + 0.00 z 6
Aplicamos la primera iteraci´on partiendo de x0 = 1.00, y0 = 2.00, y z = 0.00: x1 = −0.10 + 0.00(1.00) + 0.00 (2.00) + 0.10 (0.00) = −0.1 y1 = 0.66 − 0.33(−0.10) + 0.00 (2.00) + 0.33 (0.00) = 0.70 z1 = 0.40 − 0.40(−0.10) − 0.40 (0.70) + 0.00 (0.00) = 0.16 Aplicamos la segunda iteraci´on partiendo de x1 = −0.10 y y1 = 0.70 y z1 = 0.16: x1 = −0.10 + 0.00(−0.10) + 0.00 (0.70) + 0.10 (0.16) = −0.084 y1 = 0.66 − 0.33(−0.084) + 0.00 (0.70) + 0.33 (0.16) = 0.748 z1 = 0.40 − 0.40(−0.084) − 0.40 (0.748) + 0.00 (0.16) = 0.134 Aplicamos la tercera iteraci´on partiendo de x1 = −0.084 y y1 = 0.748 y z1 = 0.134: x1 = −0.10 + 0.00(−0.084) + 0.00 (0.748) + 0.10 (0.134) = −0.086 y1 = 0.66 − 0.33(−0.086) + 0.00 (0.748) + 0.33 (0.134) = 0.740 z1 = 0.40 − 0.40(−0.086) − 0.40 (0.740) + 0.00 (0.134) = 0.138
3.13.
Costo computacional
Es dif´ıcil estimar el costo computacional de un m´etodo iterativo, pues de antemano se desconoce cu´ antas iteraciones requerira para obtener una respuestas que satisfaga al usuario. Generalmente se procede a calcular el costo computacional por iteraci´ on. En el caso del m´etodo de Jacobi la relaci´on de recurrencia utilizada es: xi+1 = c + B xi No es dif´ıcil estimar el costo computacional que involucra: el producto de la matriz B, n × n por el vector xi toma n × (2n − 1) FLOPs, y la suma de dos vectores en ℜn toma n FLOPs lo cual da un total de 2 n2 FLOPs en cada iteraci´on del m´etodo de Jacobi. Utilizando esta informaci´on podemos concluir que si el algoritmo toma m iteraciones entonces el total de FLOPs ser´ a de: 2 m n2 Por ello es que el m´etodo de Jacobi se prefiere en problemas donde n es grande, cuando se puede garantizar la convergencia y cuando el n´ umero de iteraciones esperado es bajo.
7
