metodos iterativos sistemas lineales

M´etodos Iterativos para Resolver Sistemas Lineales
Departamento de Matem´aticas, CCIR/ITESM
17 de julio de 2009
´Indice
3.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3.3. Generalidades . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.4. M´etodo Iterativo: Un ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.5. Ventajas y Desventajas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.6. M´etodo Iterativo General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 3
3.7. Metodo de Jacobi: Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.8. Convergencia y convergencia en Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.9. Matriz Diagonalmente Dominante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.10. Orden conveniente para Jacobi . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 5
3.11. El M´etodo de Gauss-Seidel: Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.12. M´etodo de Gauss-Seidel: Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.13. Costo computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.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 procedimien-
to 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 serelaciona con la garant´ıa de conver-
gencia 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 queprogresivamente 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
losm´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 esaplicar la f´ormula general
x =
−(−1) }q(−1)2 − 4(1)(−2)
2(1)
= −1, 2
Un m´etodo iterativo es el m´etodo de Newton que consiste en usar la f´ormula de mejora:
xi+1 = xi −
f(xi)
f′(xi)
= xi −
xi
2 − xi − 2
2 xi − 1
Si tomamos como primera aproximaci´on x0 = 3 (para i = 0), tendremos
x1 = x0 −
x0
2 − x0 − 2
2 x0 − 1
= 3 −
32 − 3 − 2
2 ・ 3 − 1
≈ 2.2
Si ahora tomamos como...