Sistemas de ecuaciones linealesMtodos iterativos

Resolucin de sistemas de ecuaciones lineales El objetivo de este apartado es examinar los aspectos numricos que se presentan al resolver

sistemas de ecuaciones lineales de la forma:

Se trata de un sistema de n ecuaciones con n incgnitas, x1, x2, ..., xn. Los elementos aij y bi sonnmeros reales fijados. El sistema de ecuaciones se puede escribir, empleando una muy tilrepresentacin matricial, como:

Entonces podemos denotar estas matrices por A, x y b de forma que la ecuacin se reducesimplemente a:

Ax=B

Los mtodos de resolucin de sistemas de ecuaciones se puedendividir en dos grandes grupos: Los Mtodos exactos o algoritmos finitos que permiten obtener la solucin

del sistema de manera directa.

Los Mtodos aproximados que utilizan algoritmos iterativos e infinitos y quecalculan las solucin del sistema por aproximaciones sucesivas. Al contrariode lo que pueda parecer, en muchas ocasiones los mtodos aproximadospermiten obtener un grado de exactitud superior al que se puede obtenerempleando los denominados mtodos exactos, debido fundamentalmente alos errores de truncamiento que se producen en el proceso.

En los mtodos exactos se encuentran el mtodo de Gauss y unamodificacin de ste denominado mtodo de Gauss-Jordan. Y entrelos mtodos aproximados nos centraremos en el estudio de losmtodos de Jacobi y Gauss-Seidel.

Mtodos iterativos

Un mtodo iterativo es un mtodo que progresivamente vacalculando aproximaciones a la solucin de un problema. EnMatemticas, en un mtodo iterativo se repite un mismo proceso demejora sobre una solucin aproximada: se espera que lo obtenido seauna solucin ms aproximada que la inicial. El proceso se repite sobreesta nueva solucin hasta que el resultado ms reciente satisfagaciertos requisitos. A diferencia de los mtodos directos, en los cualesse debe terminar el proceso para tener la respuesta, en los mtodositerativos se puede suspender el proceso al termino de una iteraciny se obtiene una aproximacin a la solucin.

Ventajas y Desventajas

Un elemento en contra que tienen los mtodos iterativos sobre los mtodos directos es que calculan aproximaciones a la solucin.

Los mtodos iterativos se usan cuando no se conoce un mtodo para obtener la solucin en forma exacta.

Tambin se utilizan cuando el mtodo para determinar la solucin exacta requiere mucho tiempo de clculo, cuando una respuesta aproximada es adecuada, y cuando el nmero de iteraciones es relativamente reducido

Un mtodo iterativo consta de los siguientes pasos.

1. inicia con una solucin aproximada (Semilla),

2. ejecuta una serie de clculos para obtener o construir una mejor aproximacin partiendo de la aproximacin semilla. La frmula que permite construir la aproximacin usando otra se conoce como ecuacin de recurrencia.

3. se repite el paso anterior pero usando como semilla la aproximacin obtenida

El mtodo de Gauss-Seidel

Es un refinamiento del mtodo de Jacobi que generalmente (pero no siempre)converge ms rpido. El ltimo valor de cada variable es sustituido en cadapaso en el proceso iterativo. El mtodo de Gauss-Seidel, es un mtodoiterativo y por lo mismo, resulta ser un mtodo bastante eficiente. Acontinuacin se presenta un sistema de ecuaciones:

De la ecuacin 1 se despeja x1, de la ecuacin 2 se despeja x2,, de la ecuacin n se despeja xn.Resolviendo lo anterior se obtiene el siguiente conjunto de ecuaciones:

Este ltimo conjunto de ecuaciones son las que forman las frmulas iterativas. Para comenzar elproceso iterativo, le se le asigna el valor de cero a las variables x2,, xn, esto dar un primer valor parax1. entonces se tiene que :

Luego se sustituye este valor de x1, en la ecuacin 2 y las variables x3,, xn, siguen teniendo el valor 0,por lo cual se puede obtener el valor de x2,

Los valores de x1,x2 se reemplazan en la ecuacin 3, mientras x4,, xn permanecen con el valor 0. Assucesivamente hasta llegar a la ltima ecuacin.

Todo este paso, darn una lista de primeros valores para las incgnitas, la cual conforma el primer paso en el proceso iterativo. Digamos que se tiene:

Se repite el proceso, pero ahora sustituyendo estos ltimos datos en vez de ceros como al inicio, se obtendr una segunda lista de valores para cada una de las incgnitas. Por lo tanto ahora se tiene:

En este momento, se puede calcular los errores aproximados relativos, respecto a cada una de las incgnitas. As, se tiene la lista de errores como sigue:

El proceso sigue hasta: , donde

es una cota suficiente prefijado s

Criterio de Convergencia para el mtodo de Gauss-Seidel El mtodo de Gauss-Seidel surgio como una modificacin del mtodo de Jacobi que acelera la convergencia de

ste.

El mtodo de Gauss-Seidel recorta sustancialmente el nmero de iteraciones a realizar para obtener una cierta precisin en la solucin. Evidentemente los criterios de convergencia son similares a los de Jacobi.

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, deben ser menor que la unidad para asegurar laconvergencia.

Es decir, el elemento diagonal debe ser mayor que el elemento fuera de la diagonal para cada regln deecuaciones. La generalizacin del criterio anterior para un sistema de n ecuaciones es:

122

21 a

a1

11

12 a

a

2122 aa 1211 aa

n

ij

jjiii aa

1,

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 siguiente, si se cambi el orden de las ecuaciones esta puede divergir.

n

iji

ija

iia

1