DESCOMPOSICIÓN
LU
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descomposición LU
• Introducción
• Explicación General
• Eliminación de Gauss
• Matriz Inversa
• Error y condicionamiento
• Ejemplo
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Introducción
El Método de descomposición LU se
utiliza para resolver sistemas de
ecuaciones algebraicas lineales de la
forma: [A] {X} = {B} cuando se tienen
ecuaciones con los mismos
coeficientes A pero con diferentes
constantes del lado derecho
(diferentes B).
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descomposición LU
• Introducción
• Explicación General
• Eliminación de Gauss
• Matriz Inversa
• Error y condicionamiento
• Ejemplo
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Explicación General
• Ecuación original
[A] {X} = {B}
• Ecuación reordenada
[A] {X} - {B} = 0
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Método
• Ecuación expresada en forma de sistema
triangular
u11 u12 u13
0 u22 u23
0 0 u33
x1
x2
x3
d1
= d2
d3
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Método
• Mediante una matriz diagonal inferior
con números uno en la diagonal
L =
1 0 0
0 1 0
0
0
1
• Se realiza la siguiente simplificación
[L]{[U] {X}-{D}} = [A] {X}-{B}
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Método
• Si la ecuación anterior se satisface se
obtiene:
[L][U] = [A]
[L]{D} = {B}
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Pasos
•
•
Descomposición LU: A se factoriza en
matrices triangulares inferior L y
superior U.
Sustitución: L y U se usan para
determinar una solución X para un lado
derecho B. Primero se genera un vector
intermedio D mediante la sustitución
hacia delante. Después el resultado se
sustituye en la ecuación para obtener
mediante sustitución hacia atrás el valor
de X.
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descomposición LU
• Introducción
• Explicación General
• Eliminación de Gauss
• Matriz Inversa
• Error y condicionamiento
• Ejemplo
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
•
A se descompone de forma directa en L
y U.
– U : resultado directo de la eliminación
hacia delante.
a11 a12 a13
U = 0 a`22 a`23
0 0 a``33
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
•
L se obtiene de un proceso de
eliminación mediante un sistema de tres
ecuaciones:
a11 a12 a13
x1
a21 a22 a23
a31 a32 a33
x2
x3
b1
=
b2
b3
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
Paso 1: Multiplicar el reglón uno por
F21=a21 / a11 y restar el resultado al
segundo reglón para eliminar a21
a21-a11*a21 = 0
a11
a22-a12*a21 = a`22
a11
a23-a13*a21 = a`23
a11
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
Paso 2: Multiplicar el reglón uno por
F31 = a31 / a11 y restar el resultado al
renglón tres
a31- 0*a31 = 0
a11
a32-a12*a31 = a`32
a11
a33-a13*a31 = a`33
a11
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
Paso 3: multiplicar el segundo renglón
modificado por F32 = a´32 / a´22 y restar
este resultado al tercer renglón.
0 - 0*a`32 = 0
a´32 - a`22*a`32 = 0
a`22
a`22
a´33 - a`23*a`32 = a``32
a`22
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
•
Se almacenan los factores F21, F31 y F32
en los ceros que fueron creados
mediante la eliminación anterior.
a11 a12 a13
U = 0 a`22 a`23
0 0 a``33
L =
1 0 0
f21 1 0
f31 f32 1
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Eliminación de Gauss usando
descomposición LU
•
•
•
Después de descomponer la matriz, se
puede generar una solución para un
vector particular B.
Primero se realiza un paso de sustitución
hacia delante para encontrar D. El lado
derecho queda sin alterar.
En el segundo paso se realiza la
sustitución hacia atrás, para obtener X.
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descomposición LU
• Introducción
• Explicación General
• Eliminación de Gauss
• Matriz Inversa
• Error y condicionamiento
• Ejemplo
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Matriz Inversa
• Si una matriz [A] es cuadrada,
existe otra matriz [A] ‫־‬¹,
conocida como la inversa de [A],
de lo que se cumple que:
[A][A] ‫־‬¹ = [A] ‫־‬¹[A] = [I]
[I] es la Matriz identidad
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Matriz Inversa
Ya que el algoritmo de descomposición LU es
ideal para evaluar los vectores unitarios
requeridos en el cálculo de la inversa.
a11 a12 a13
1 0 0
1 0 0
a21 a22 a23
a31 a32 a33
0 1 0
0 0 1
0 1 0
0 0 1
A ‫־‬¹
Matriz inversa por Gauss-Jordan
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Matriz Inversa
d se resuelve como un sistema de
ecuaciones normales de 3 incógnitas:
1 0 0
f21 1 0
f31 f32 1
d1
d2 =
d3
1
0
0
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Matriz Inversa
x se resuelve como un sistema de
ecuaciones normales de 3 incógnitas
a11 a12 a13
0 a`22 a`23
0 0 a``33
x1
x2
x3
t
=
D
La xt va a ser la primera columna de
la inversa de [A]
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Matriz Inversa
El procedimiento se repite para obtener
los otros términos de la matriz inversa
pero el sistema de ecuaciones se iguala a
las siguientes vectores unitarios
Para la
segunda
columna
0
1
0
Para la
tercera
columna
0
0
1
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descomposición LU
• Introducción
• Explicación General
• Eliminación de Gauss
• Matriz Inversa
• Error y condicionamiento
• Ejemplo
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
ERROR Y
CONDICIONAMIENTO
Existen 3 métodos para determinar si los
sistemas están mal condicionados:
• Escalar la matriz de coeficientes [A], de
tal manera que el elemento más grande
en cada renglón sea 1.Se invierte la
matriz escalada, y si existen elementos
[A]‫ ־‬¹ que sean varios órdenes de
magnitud mayores que uno, es posible
que el sistema esté mal condicionado.
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
ERROR Y
CONDICIONAMIENTO
•
Multiplicar la inversa por la matriz de
coeficientes original y estimar si el
resultado es lo suficientemente cercano
a la matriz identidad. Si no es así, esto
indica que el sistema esta mal
condicionado.
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
ERROR Y
CONDICIONAMIENTO
•
Invertir la matriz inversa y estimar si el
resultado está lo suficientemente
cercano a la matriz de coeficientes
original. Si no es así, esto de nueva
cuenta indica que esta mal
condicionado.
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descomposición LU
• Introducción
• Explicación General
• Eliminación de Gauss
• Matriz Inversa
• Error y condicionamiento
• Ejemplo
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
EJEMPLO
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
EJEMPLO
1

L= 4
12
0
l 22
l 32
0

0

l 33
1

U = 0
0
7
1
0
 4

u 23

1 
l22 = -4 – 4 * 7 = -32
l32 = -1 - 12 * 7 = -85
u23 = (9 – 4 * -4) / -32 = -0.78125
l33 = 3 -12 *-4—85 * (-0.78125) = -15.40625
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
EJEMPLO
L=
1

4

12
U=
1

0

0
0
 32
 85
7
1
0


0

 15.40625
0
4


 0.78125


1
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
EJEMPLO
Y ahora se tiene:
1

4

12
0
 32
 85
  y1   51
  

0
y 2  62
  

 15.40625  y 3   8 
0
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
EJEMPLO
Se encuentran los valores de y:
Y1 =  51   51
1
Y2 =
Y3 =
62  4 * (  51 )
  8 . 3125
 32
8  12 * (  51 )  85 * (  8 . 3125 )
 15 . 40625
 5 . 61866
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
EJEMPLO
1

0

0
7
1
0
4
  x1    51 
  

 0.78125 x 2   8.3125
  

  x3   5.61866 
1
Donde:
x3 = 5.61866
x2 = -8.3125 + 0.78125 * 5.61866 = -3.92292
x1 = -51 + 7 * 3.92292 + 4 * 5.61866 = -1.06491
Verónica Miranda, Mariano Avilés, Andrés Navarro, Katherine González
Descargar

DESCOMPOSICIÓN