Busca monografías, tesis y trabajos de investigación

Buscar en Internet 

       Revistas   Cursos   Biografías

rss feeds RSS / /

Descomposición LU y método de Gauss-Seidel

Resumen: A lo largo de las páginas de este trabajo se presenta un marco teórico que introduce a cada tema, al tiempo que se muestran en total cuatro ejercicios resueltos con explicaciones detalladas sobre cada proceso realizado.

Publicación enviada por Jaime Montoya




 


INTRODUCCIÓN
En el presente documento se explican detalladamente dos importantes temas:
1. Descomposición LU.
2. Método de Gauss-Seidel.

Se trata de dos importantes herramientas que sirven para encontrar soluciones de sistemas de ecuaciones.

A lo largo de las páginas de este trabajo se presenta un marco teórico que introduce a cada tema, al tiempo que se muestran en total cuatro ejercicios resueltos con explicaciones detalladas sobre cada proceso realizado.

Además de las explicaciones, se muestran continuamente imágenes y matrices que permiten comprender con toda claridad cada uno de los procesos que se van siguiendo en el análisis de cada paso realizado.

Las explicaciones son detalladas y tienen el fin de permitir al lector comprender cada tema aun cuando sea primera vez que lo estudie.

Normalmente estos temas tienen procesos largos y por ello son ideales para programar por computadora y no solamente para hacerlos sobre el papel. Programar estos temas permite incluso obtener una mejor comprensión de la teoría aquí presentada.

OBJETIVOS
OBJETIVO GENERAL:
· Comprender las diferentes formas de solucionar sistemas de ecuaciones lineales por medio de los métodos de descomposición LU y Gauss-Seidel.

OBJETIVOS ESPECÍFICOS:

· Proporcionar al estudiante una idea clara y comprensible de los métodos de descomposición LU y Gauss-Seidel.
· Mostrar cómo aplicar los métodos mencionados para facilitar la solución de sistemas de ecuaciones, y poder así programar dichos métodos en la computadora.

DESCOMPOSICIÓN LU


Su nombre se deriva de las palabras inglesas “Lower" y “Upper”, que en español se traducen como “Inferior” y “Superior”. Estudiando el proceso que se sigue en la descomposición LU es posible comprender el por qué de este nombre, analizando cómo una matriz original se descompone en dos matrices triangulares, una superior y otra inferior.

La descomposición LU involucra solo operaciones sobre los coeficientes de la matriz [A], proporcionando un medio eficiente para calcular la matriz inversa o resolver sistemas de álgebra lineal.

Primeramente se debe obtener la matriz [L] y la matriz [U].

[L] es una matriz diagonal inferior con números 1 sobre la diagonal. [U] es una matriz diagonal superior en la que sobre la diagonal no necesariamente tiene que haber números 1.

El primer paso es descomponer o transformar [A] en [L] y [U], es decir obtener la matriz triangular inferior [L] y la matriz triangular superior [U].

PASOS PARA ENCONTRAR LA MATRIZ TRIANGULAR SUPERIOR (MATRIZ [U])

1. Hacer cero todos los valores abajo del pivote sin convertir este en 1.
2. Para lograr lo anterior se requiere obtener un factor el cual es necesario para convertir a cero los valores abajo del pivote.
3. Dicho factor es igual al número que se desea convertir en cero entre el número pivote.
4. Este factor multiplicado por -1 se multiplica luego por el pivote y a ese resultado se le suma el valor que se encuentra en la posición a cambiar (el valor en la posición que se convertirá en cero). Esto es:

- factor * pivote + posición a cambiar


PASOS PARA ENCONTRAR LA MATRIZ TRIANGULAR INFERIOR (MATRIZ [L])
Para encontrar la matriz triangular inferior se busca hacer ceros los valores de arriba de cada pivote, así como también convertir en 1 cada pivote. Se utiliza el mismo concepto de “factor” explicado anteriormente y se ubican todos los “factores” debajo de la diagonal según corresponda en cada uno.

Esquemáticamente se busca lo siguiente:

Debido a que [A] = [L][U], al encontrar [L] y [U] a partir de [A] no se altera en nada la ecuación y se tiene lo siguiente:



Por lo tanto, si Ax = b, entonces LUx = b, de manera que Ax = LUx = b.

PASOS PARA RESOLVER UN SISTEMA DE ECUACIONES POR EL MÉTODO DE DESCOMPOSICIÓN LU
1. Obtener la matriz triangular inferior L y la matriz triangular superior U.
2. Resolver Ly = b (para encontrar y).
3. El resultado del paso anterior se guarda en una matriz nueva de nombre “y”.
4. Realizar Ux = y (para encontrar x).
5. El resultado del paso anterior se almacena en una matriz nueva llamada “x”, la cual brinda los valores correspondientes a las incógnitas de la ecuación.

EJEMPLO 1 DE DESCOMPOSICIÓN LU

PROBLEMA: Encontrar los valores de x1, x2 y x3 para el siguiente sistema de ecuaciones:

NOTA: Recuérdese que si la matriz es 2x2 se hará 1 iteración; si es 3x3, 2 iteraciones; si es 4x4, 3 iteraciones; y así sucesivamente.

SOLUCIÓN:


ITERACIÓN 1
factor 1 = (a21 / a11) = 5 / 4 = 1.25
factor 2 = (a31 / a11) = 1 / 4 = 0.25

Encontrando [U]
fila 2 = - (factor 1) * (fila 1) + (fila 2)
fila 3 = - (factor 2) * (fila 1) + (fila 3)

a11 = a11
a12 = a12
a13 = a13
a21 = - (1.25) * (4) + (5) = 0
a22 = - (1.25) * (- 2) + (1) = 3.5
a23 = - (1.25) + (- 1) + (- 1) = 0.25
a31 = - (0.25) * (4) + (1) = 0
a32 = - (0.25) * (- 2) + (2) = 2.5
a33 = - (0.25) * (- 1) + (- 1) = - 0.75



Encontrando [L]


ITERACIÓN 2
factor 3 = (u32 / u22) = 2.5 / 3.5 = 0.7142857143

Encontrando [U]
fila 3 = - (factor 3) * (fila 2) + (fila 3)

a31 = - (2.5 / 3.5) * (0) + (0) = 0
a32 = - (2.5 / 3.5) * (3.5) + (2.5) = 0
a33 = - (2.5 / 3.5) * (0.25) + (- 0.75) = - 0.9285714286



Encontrando [L]


Ahora ya se tiene la matriz [U] y la matriz [L]. El siguiente paso es resolver
Ly = b para encontrar la matriz y. En pocas palabras es como que se pidiera resolver el siguiente sistema de ecuaciones, encontrando los valores de y1, y2 y y3:

Al resolver el sistema anterior, se obtienen los siguientes valores para y1, y2 y y3:

El último paso es resolver Ux = y para encontrar la matriz x. En otras palabras es como que se pidiera resolver el siguiente sistema de ecuaciones, encontrando los valores de x1, x2 y x3:

La solución del sistema es:

Este es finalmente el valor de x1, x2 y x3; es decir, la respuesta del ejercicio utilizando la descomposición LU.

EJEMPLO 2 DE DESCOMPOSICIÓN LU
PROBLEMA: Encontrar los valores de x1, x2 y x3 para el siguiente sistema de ecuaciones:

SOLUCIÓN:


ITERACIÓN 1
factor 1 = (a21 / a11) = 5/11 = 0.4545454545
factor 2 = (a31 / a11) = 4/11 = 0.3636363636


Encontrando [U]

fila 2 = - (factor 1) * (fila 1) + (fila 2)
fila 3 = - (factor 2) * (fila 1) + (fila 3)

a11 = a11
a12 = a12
a13 = a13
a21 = - (0.4545454545) * (11) + (5) = 0
a22 = - (0.4545454545) * (- 3) + (- 2) = - 0.6363636365
a23 = - (0.4545454545) + (- 2) + (- 8) = - 7.0909090919
a31 = - (0.3636363636) * (11) + (4) = 0
a32 = - (0.3636363636) * (- 3) + (- 7) = - 5.909090909
a33 = - (0.3636363636) * (- 2) + (2) = 2.7272727272



Encontrando [L]


ITERACIÓN 2
factor 3 = (u32/u22) = - 5.909090909 / - 0.6363636365 = 9.285714284

Encontrando [U]
fila 3 = - (factor 3) * (fila 2) + (fila 3)

a31 = - (9.285714284) * (0) + (0) = 0
a32 = - (9.285714284) * (- 0.6363636365) + (- 5.909090909) = 0
a33 = - (9.285714284) * (- 7.0909090919) + (2.7272727272) = 68.57142857



Encontrando [L]


Ahora ya se tiene la matriz [U] y la matriz [L]. El siguiente paso es resolver
Ly = b para encontrar la matriz y. En pocas palabras es como que se pidiera resolver el siguiente sistema de ecuaciones, encontrando los valores de y1, y2 y y3:

Al resolver el sistema anterior, se obtienen los siguientes valores para y1, y2 y y3:

El último paso es resolver Ux = y para encontrar la matriz x. En otras palabras es como que se pidiera resolver el siguiente sistema de ecuaciones, encontrando los valores de x1, x2 y x3:

La solución del sistema es:

Este es finalmente el valor de x1, x2 y x3; es decir, la respuesta del ejercicio utilizando la descomposición LU.

MÉTODO DE GAUSS-SEIDEL
El método de Gauss-Seidel es un método iterativo y por lo mismo resulta ser bastante eficiente. Se comienza planteando el sistema de ecuaciones con el que se va a trabajar:

De la ecuación 1 despejar x1, de la ecuación 2 despejar x2, …, de la ecuación n despejar xn. Esto da el siguiente conjunto de ecuaciones:

Este último conjunto de ecuaciones son las que forman las fórmulas iterativas con las que se va a estar trabajando. Para comenzar el proceso iterativo, se le da el valor de cero a las variables x2,…, xn; esto dará un primer valor para x1. Más precisamente, se tiene que:

Enseguida, se sustituye este valor de x1 en la ecuación 2, y las variables x3,…, xn siguen teniendo el valor de cero. Esto da el siguiente valor para x2:

Estos últimos valores de x1 y x2, se sustituyen en la ecuación 3, mientras que x4,…, xn siguen teniendo el valor de cero; y así sucesivamente hasta llegar a la última ecuación. Todo este paso arrojará una lista de primeros valores para las incógnitas, la cual conforma el primer paso en el proceso iterativo. Para una mejor comprensión esto se simbolizará de esta forma:

Se vuelve a repetir 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, lo cual se simbolizará así:

En este momento se pueden calcular los errores aproximados relativos, respecto a cada una de las incógnitas. La lista de errores se presenta a continuación:

El proceso se vuelve a repetir hasta que:

donde se debe prefijar convenientemente.

EJEMPLO 1 DEL MÉTODO DE GAUSS-SEIDEL
PROBLEMA: Usar el método de Gauss-Seidel para aproximar la solución del sistema:

hasta que:


SOLUCIÓN:
Primero se despejan las incógnitas x1, x2 y x3 de las ecuaciones 1, 2 y 3 respectivamente. Se tiene:

Estas últimas son el juego de fórmulas iterativas que se estará utilizando.

Puesto que todavía no se puede calcular ningún error aproximado, se repite el proceso pero ahora con los últimos datos obtenidos para las incógnitas:



Es así como se tiene la segunda lista de valores de aproximación a la solución del sistema:

Ahora se pueden calcular los errores absolutos para cada una de las incógnitas:

Puesto que no se ha logrado el objetivo, se debe repetir el mismo proceso con los últimos valores obtenidos de cada una de las incógnitas. Nótese que aunque el error aproximado ya cumple con ser menor al 1%, esto se debe cumplir para los tres errores aproximados. Por lo tanto se repite el mismo proceso. Omitiendo los pasos intermedios, se obtiene:

En este caso se tienen los siguientes errores aproximados:

Se puede observar que ahora se ha cumplido el objetivo para cada uno de los errores aproximados. Por lo tanto, se concluye que la solución aproximada es:

Importante observación respecto al método de Gauss-Seidel: Es lógico preguntarse si siempre el método de Gauss-Seidel converge a la solución del sistema de ecuaciones y también es lógico esperar que la respuesta es NO.

Un resultado de Análisis numérico da una condición suficiente para la convergencia del método.

Teorema: El método de Gauss-Seidel converge a la solución del sistema si se cumple la condición de que la matriz de coeficientes del sistema sea una matriz diagonalmente dominante, es decir, si se cumple la siguiente condición:

La condición de ser una matriz diagonalmente dominante simplemente significa que los elementos de la diagonal son mayores (en valor absoluto) que la suma de los valores absolutos de los demás elementos del mismo renglón. Nótese que en el ejemplo anterior, la matriz sí es diagonalmente dominante y por lo tanto, el método de Gauss-Seidel sí converge a la solución del sistema.

Sin embargo, la condición de la matriz diagonalmente dominante, solamente es una condición suficiente pero no necesaria, es decir, existen sistemas de ecuaciones que no cumplen con la condición y que sí convergen a la solución y también existen sistemas de ecuaciones que no cumplen con la condición y que no convergen a la solución.

Finalmente, obsérvese que aunque un sistema no cumpla con la condición de ser diagonalmente dominante, es posible a veces, lograr que sí se cumpla con esta condición mediante un intercambio de renglones, como se verá en el siguiente ejemplo:

EJEMPLO 2 DEL MÉTODO DE GAUSS-SEIDEL
PROBLEMA: Usar el método de Gauss-Seidel para aproximar la solución del sistema:


SOLUCIÓN:
En este caso se puede observar que el sistema no es diagonalmente dominante, lo cual se comprueba con los siguientes cálculos:

Primera fila:
|a11| > (|a12| + |a13|)
5 > (1.4 + 2.7)
5 > 4.1; es cierto.
La condición se cumple para la primera fila.

Segunda fila:
|a22| > (|a21| + |a23|)
2.5 > (0.7 + 15)
2.5 > 15.7; no es cierto.
La condición no se cumple para la segunda fila.

|a33| > (|a31| + |a32|)
4.4 > (3.3 + 11)
4.4 > 14.3; no es cierto.
La condición no se cumple para la tercera fila.

Para que el sistema sea diagonalmente dominante, la condición debe cumplirse para todas las filas. Por lo tanto, el sistema anterior no es diagonalmente dominante.

NOTA: Recuérdese que la diagonal principal está compuesta por a11, a22 y a33.

Sin embargo, al hacer el intercambio del renglón 2 por el renglón 3, se tiene el siguiente sistema:

En este caso se puede observar que el sistema sí es diagonalmente dominante, lo cual se comprueba con los siguientes cálculos:
Primera fila:
|a11| > (|a12| + |a13|)
5 > (1.4 + 2.7)
5 > 4.1; es cierto.
La condición se cumple para la primera fila.

Segunda fila:
|a22| > (|a21| + |a23|)
11 > (3.3 + 4.4)
11 > 7.7; es cierto.
La condición se cumple para la segunda fila.

|a33| > (|a31| + |a32|)
15 > (0.7 + 2.5)
15 > 3.2; es cierto.
La condición se cumple para la tercera fila.

Para que el sistema sea diagonalmente dominante, la condición debe cumplirse para todas las filas. En este caso efectivamente la condición se cumple para todas las filas, por lo cual el sistema anterior es diagonalmente dominante. Por lo tanto se procede a despejar x1, x2 y x3 de las ecuaciones 1, 2 y 3 respectivamente:

Se comienza el proceso iterativo sustituyendo los valores de x2 = 0 x3 = 0 en la ecuación 1 para obtener x1:

Ahora se sustituye x1 = -18.84 y x3 = 0 en la ecuación 2 para obtener x2:

Por lo tanto los valores obtenidos en la primera iteración son:

Puesto que sólo se tiene la primera aproximación de la solución del sistema, se debe seguir avanzando en el proceso iterativo. Sustituyendo x2 = -3.152 y x3 = -0.04613 en la ecuación 1, se obtiene x1 = -19.69765; sustituyendo x1 = -19.69765 y x3 = -0.04613 en la ecuación 2, se obtiene x2 = -3.42775; sustituyendo x1 = -19.69765 y x2 = -3.42775 en la ecuación 3, se obtiene x3 = -0.05207. Por lo tanto, la segunda aproximación es:

Ahora se pueden calcular los errores aproximados para cada una de las incógnitas:

Puesto que no se ha cumplido el objetivo, se debe seguir avanzando en el proceso iterativo. Se resumen los resultados de esta manera:

Tercera iteración:

Cuarta iteración:


Así, el objetivo se ha logrado hasta la cuarta iteración y se tiene que los valores aproximados de la solución del sistema son:

CONCLUSIÓN
Luego de haber estudiado a profundidad estos temas o herramientas para resolver sistemas de ecuaciones, se concluye que para resolver estos sistemas de ecuaciones lineales existen diferentes métodos, pero dependerá del gusto de cada persona elegir uno en específico. Sin embargo, muchas veces la elección no será arbitraria, pues cada método tiene sus ventajas y sus desventajas. Algunos métodos son más exactos, otros más fáciles de programar, otros más cortos, etc. Para ser capaces de elegir un método apropiado, lo primero que se necesita es comprender cómo se desarrolla cada uno de estos procesos.

Luego de la elaboración de este reporte, ya se tiene una buena base y el conocimiento de los temas para poder comenzar a programar en la computadora estos procesos. Como se mencionó en la introducción, los dos métodos estudiados en este trabajo son ideales para programarlos por computadora, pues son iterativos y muy largos. Trabajar esto en papel podría resultar extremadamente largo y tedioso. Por ello son métodos ideales para trabajarlos en computadora.

El aprendizaje adquirido en esta investigación ha sido de gran valor y seguramente servirá de la misma manera a aquellos quienes posteriormente lean estas explicaciones y lo expuesto en este reporte.

BIBLIOGRAFÍA
1. C. Chapra, S.; P. Canale, R. Métodos Numéricos para Ingenieros. (3ª ed.). McGrawHill.
2. Factorización LU. Wikipedia. Extraído el 22 Enero, 2007, de http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_LU
3. MÉTOTO DE GAUSS-SEIDEL. Universidad Autónoma de Ciudad Juárez (UACJ). Extraído el 22 Enero, 2007, de http://docentes.uacj.mx/gtapia/AN/Unidad3/Seidel/SEIDEL.htm

AUTOR
Jaime Montoya
jaimemontoya@jaimemontoya.com
www.jaimemontoya.com
Santa Ana, 30 de noviembre de 2007
El Salvador



Valora este artículo 5   4   3   2   1

Comparte  Enviar a facebook Facebook   Enviar a menéame Menéame   Digg   Añadir a del.icio.us Delicious   Enviar a Technorati Technorati   Enviar a Twitter Twitter
Artículos Destacados