Sistemas de ecuaciones lineales

Vista previa del material en texto

Sistemas de ecuaciones lineales
Métodos iterativos
El método de eliminación gaussiana y sus variantes (pivoteo, factorización LU) son conocidos como métodos directos para resolver un sistema de ecuaciones lineales de la forma AX = b; se ejecutan a través de un número finito de pasos y generan una solución X que sería exacta si no fuera por los errores de redondeo.
Un método iterativo para resolver o aproximar una solución a un sistema de ecuaciones lineales AX = b comienza con una aproximación inicial X0 y se genera una sucesión de vectores Xi que convergen a la solución X.
El proceso de calculo se detiene cuando se cuenta con una solución aproximada con cierto grado de precisión especificado.
Resolución de sistemas de ecuaciones lineales
El objetivo de este apartado es examinar los aspectos numéricos que se presentan al resolver sistemas de ecuaciones lineales de la forma:
 
Se trata de un sistema de n ecuaciones con n incógnitas, x1, x2, ..., xn. Los elementos aij y bi son números reales fijados. El sistema de ecuaciones se puede escribir, empleando una muy útil representación matricial, como: 
Entonces podemos denotar estas matrices por A, x y b de forma que la ecuación se reduce simplemente a:
Ax=B
Los métodos de resolución de sistemas de ecuaciones se pueden dividir en dos grandes grupos:
Los Métodos exactos o algoritmos finitos que permiten obtener la solución del sistema de manera directa.
Los Métodos aproximados que utilizan algoritmos iterativos e infinitos y que calculan las solución del sistema por aproximaciones sucesivas. Al contrario de lo que pueda parecer, en muchas ocasiones los métodos aproximados permiten obtener un grado de exactitud superior al que se puede obtener empleando los denominados métodos exactos, debido fundamentalmente a los errores de truncamiento que se producen en el proceso.
En los métodos exactos se encuentran el método de Gauss y una modificación de éste denominado método de Gauss-Jordan. Y entre los métodos aproximados nos centraremos en el estudio de los métodos de Jacobi y Gauss-Seidel.
Métodos iterativos
Un método iterativo es un método que progresivamente va calculando aproximaciones a la solución de un problema. En Matemáticas, en un método iterativo se repite un mismo proceso de mejora sobre una solución aproximada: se espera que lo obtenido sea una solución más aproximada que la inicial. El proceso se repite sobre esta nueva solución hasta que el resultado más reciente satisfaga ciertos requisitos. A diferencia de los métodos directos, en los cuales se debe terminar el proceso para tener la respuesta, en los métodos iterativos se puede suspender el proceso al termino de una iteración y se obtiene una aproximación a la solución.
Ventajas y Desventajas
Un elemento en contra que tienen los métodos iterativos sobre los métodos directos es que calculan aproximaciones a la solución. 
Los métodos iterativos se usan cuando no se conoce un método para obtener la solución en forma exacta. 
También se utilizan cuando el método para determinar la solución exacta requiere mucho tiempo de cálculo, cuando una respuesta aproximada es adecuada, y cuando el número de iteraciones es relativamente reducido
Un método iterativo consta de los siguientes pasos.
1. inicia con una solución aproximada (Semilla), 
2. ejecuta una serie de cálculos para obtener o construir una mejor aproximación partiendo de la aproximación semilla. La fórmula que permite construir la aproximación usando otra se conoce como ecuación de recurrencia. 
3. se repite el paso anterior pero usando como semilla la aproximación obtenida
METODO DE JACOBI
El método de Jacobi es el método iterativo para resolver sistemas de ecuaciones lineales más simple y se aplica sólo a sistemas cuadrados, es decir a sistemas con tantas incógnitas como ecuaciones
Sea el sistema de ecuaciones lineales:
.
.
.
Donde A es la matriz de los coeficiente, X es el vector de incognitas y b el vector de términos independiente.
En AX = b se puede sustituir a la matriz A por la suma de 2 matrices A = D + R
En donde la matriz D es una matriz cuyos elementos son cero excepto los elementos de la diagonal que corresponden a los elementos de la matriz A y R que es una matriz con ceros en la diagonal y sus restantes elementos coindicen con los respectivos de A.
A partir del sistema de ecuaciones lineales, a despejar a la incognita de ubicada en la diagonal principal de cada una de las ecuaciones que conforman el sistema
El método de Jacobi propone que el vector inicial X0 sea igual a cero. A partir de esta propuesta, el vector solución siguiente , es decir, el elemento independiente entre el coeficiente de la diagonal principal para cada ecuación.
.
Criterio de convergencia
El método de Jacobi es susceptible de los efectos del pivoteo. En consecuencia, su criterio de convergencia lo conforman los criterios de la diagonal pesada, mismo que posee dos condiciones:
1. Condición necesaria: Es condición necesaria que el elemento ubicado en la diagonal principal de cada ecuación sea mayor en valor absoluto que el resto de los elementos de la misma ecuación.
2. Condición suficiente: Es condición suficiente que el elemento ubicado en la diagonal principal de cada ecuación sea mayor en valor absoluto que la suma del resto de los elementos de la misma ecuación.
Algoritmo:
1. Plantear vector solución inicial X0.
2. Establecer tolerancia de error .
3. Verificar convergencia.
4. Calcular próximo vector solución con la fórmula:
El método de Gauss-Seidel
Es un refinamiento del método de Jacobi que generalmente (pero no siempre) converge más rápido. El último valor de cada variable es sustituido en cada paso en el proceso iterativo. El método de Gauss-Seidel, es un método iterativo y por lo mismo, resulta ser un método bastante eficiente. A continuación se presenta un sistema de ecuaciones: 
De la ecuación 1 se despeja x1, de la ecuación 2 se despeja x2,…, de la ecuación n se despeja xn. Resolviendo lo anterior se obtiene el siguiente conjunto de ecuaciones:
Este último conjunto de ecuaciones son las que forman las fórmulas iterativas. Para comenzar el proceso iterativo, le se le asigna el valor de cero a las variables x2,…, xn, esto dará un primer valor para x1. entonces se tiene que :
Luego se sustituye este valor de x1, en la ecuación 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 ecuación 3, mientras x4,…, xn permanecen con el valor 0. Así sucesivamente hasta llegar a la última ecuación.
Todo este paso, darán una lista de primeros valores para las incógnitas, 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 incógnitas. Por lo tanto ahora se tiene:
En este momento, se puede calcular los errores aproximados relativos, respecto a cada una de las incógnitas. Así, se tiene la lista de errores como sigue:
 El proceso sigue hasta:			, donde 
 es una cota suficiente prefijado 
Criterio de Convergencia para el método de Gauss-Seidel
El método de Gauss-Seidel surgio como una modificación del método de Jacobi que acelera la convergencia de éste.
El método de Gauss-Seidel recorta sustancialmente el número de iteraciones a realizar para obtener una cierta precisión en la solución. 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 método de Gauss-Seidel sino también para el método iterativo del punto fijo y el método de jacobi. Por tanto, al aplicar este criterio sobre las ecuaciones de Gauss-Seidel y evaluando con respecto a cada una de las incógnitas, obtenemos la expresiónsiguiente:
 El valor absoluto de las pendientes en la ecuación, deben 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 reglón de ecuaciones. La generalización del criterio anterior para un sistema de n ecuaciones es:
El método 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.
s
Î
1
22
21
<
a
a
1
11
12
<
a
a
21
22
a
a
>
12
11
a
a
>
å
¹
=
>
n
i
j
j
j
i
ii
a
a
1
,
å
¹
=
>
n
i
j
i
ij
a
ii
a
1