Métodos numéricos

UNIVERSIDAD NACIONAL DE ASUNCIÓN
FACULTAD POLITÉCNICA

Ingeniería en Informática

Métodos Numéricos

“Métodos Iterativos para la solución de sistemas de ecuaciones lineales”

Método de Richardson
Método de Jacobi
Método de Gauss-Seidel

• Rubén López
• Roberto Bañuelos

San Lorenzo – Paraguay

Métodos iterativos para resolver sitemas lineales
Introducción
Los métodosestudiados anteriormente para la resolución de sistemas de ecuaciones lineales se conocen con el nombre de métodos directos: se ejecutan a través de un número finito de pasos y dan lugar a una solución que sería exacta si no fuese por los errores de redondeo.
Un método indirecto da lugar a una sucesión de vectores que idealmente converge a la solución. El cálculo se detiene cuando se cuenta con unasolución aproximada con cierto grado de precisión especificado de antemano o después de cierto número de iteraciones. Los métodos indirectos son casi siempre iterativos: para obtener la sucesión mencionada se utiliza repetidamente un proceso sencillo.
En estas técnicas se necesita disponer de una aproximación inicial de la solución y no se espera que proporcionen la solución exacta, aun cuando todaslas operaciones se realizaran usando aritmética exacta. En muchos casos, sin embargo, son más efectivas que los métodos directos, ya que pueden requerir mucho menos esfuerzo computacional, y los errores de redondeo se reducen. Esto es especialmente cierto cuando la matriz es dispersa, esto es, cuando tienen un alto porcentaje de elementos nulos, ya que no es necesario almacenar cada elemento dela matriz.
Una desventaja de los métodos iterativos es que no convergen hacia la solución en todas las ocasiones. Puede demostrarse que la convergencia solo está garantizada si la matriz de coeficientes es diagonal dominante. Le elección inicial del vector de soluciones no tiene ninguna influencia en la convergencia, si el procedimiento converge para un vector inicial, también lo hará paracualquier otro vector inicial. La elección del vector inicial solo afecta el número de iteraciones necesarias que se requieren para la convergencia.
Conceptos básicos
En general, en todos los procesos iterativos para resolver el sistema Ax = b se recurre a una cierta matriz Q, llamada matriz descomposición, escogida de tal forma que el problema original adopte la forma equivalente:
Qx = (Q-A)x + b(1)
La ecuación (1) sugiere un proceso iterativo que se concreta al escribir:

(2)
El vector inicial x(0) puede ser arbitrario, aunque si se dispone de un buen candidato como solución éste es el que se debe emplear. La aproximación inicial que se adopta, a no ser que se disponga de una mejor, es la idénticamente nula x1 = x3 = x2 = … = xn = 0 . A partir de la ecuación (2) se puede calcularuna sucesión de vectores x(1), x(2), ... , x(n).

Nuestro objetivo es escoger una matriz Q de manera que:
• se pueda calcular fácilmente la sucesión [x(k)].
• la sucesión [x(k)] converja rápidamente a la solución.
Como en todo método iterativo, deberemos especificar un criterio de convergencia y un número máximo de iteraciones M, para asegurar que el proceso se detiene si no se alcanza laconvergencia. Algunos criterios de convergencia son los siguientes:
1. El módulo del vector diferencia, partido por el módulo del vector x, deberá ser menor que la convergencia deseada:

2. La diferencia relativa del mayor elemento en valor absoluto del vector x(k), deberá ser diez veces menor que , donde

3. El método más sencillo consiste en que la norma ∞ del vector diferencia entrela aproximación actual y la anterior debe ser menor que :
║ x(k) - x(k -1)║∞ <
Convergencia y Radio Espectral
A partir de un sistema lineal Ax = b puede obtenerse un sistema equivalente de la forma x = Tx + c, despejando cada xi de la ecuación i. La sucesión de vectores que aproximan la solución se generan calculando
x(k) = T(k-1)x + c
Esta sucesion converge a la solución de x = Tx +...