NOMBRE: MARLON REYES BRITO

Factorización LU

En el álgebra lineal, la factorización o descomposición LU (del inglés Lower-

Upper) es una forma de factorización de una matriz como el producto de una
matriz triangular inferior y una superior. Debido a la inestabilidad de este
método, por ejemplo si un elemento de la diagonal es cero, es necesario
premultiplicar la matriz por una matriz de permutación. Método llamado
factorización PA = LU o LU con pivote.

Esta descomposición se usa en el análisis numérico para resolver sistemas de

ecuaciones (más eficientemente) o encontrar las matrices inversas.

Definiciones

Sea A una matriz no singular (si lo fuera, entonces la descomposición podría

no ser única)

Donde L y U son matrices inferiores y superiores triangulares.

Para matrices , esto es:

Por otro lado la descomposición PLU tiene esta forma:

Lm − 1Pm − 1...L2P2L1P1A = U

Con Lm − 1...L1 matrices triangulares inferiores, Pm − 1 ...P1 matrices de

permutación y U una matriz triangular superior.

Para determinar L:

L = (L'm − 1 *... * L'2 * L'1) − 1

y cada L'k está dado por:

L'k =
Esto se debe a que L'k es igual a Lk, pero con los elementos de la subdiagonal
permutados.

Otra forma de ver éste tipo de factorización es: A = PTLU Recordando que las
matrices de permutación matriz permutación son invertibles y su inversa es su
traspuesta

Unicidad

Las matrices L y U son únicas, si la matriz no es singular. En caso contrario

pueden no ser únicas.

Demostración:

Dada la matriz A ∈ Rmxn

A = L1U1 y A = L2U2

Recordemos que L1,U1,L2,U2 son invertibles por tener el determinante distinto

de cero entonces:

L1U1 = L2U2

Entonces es una matriz triangular inferior, con unos en la diagonal y

es triangular superior, con unos en la diagonal (recordando que el
producto matricial de triangulares superiores/inferiores es triangular
superior/inferior). La única matriz que cumple estas dos propiedades es la
identidad. Por lo tanto:

Con lo cual:

L1 = L2 y U1 = U2

Algoritmos

La factorización LU es básicamente una forma modificada de la eliminación

Gaussiana. Transformamos la matriz A en una triangular superior U anulando
los elementos debajo de la diagonal.

E1 * E2 *... * En * A = U
Donde E1,E2,...,En son matrices elementales, que representan los distintos
pasos de la eliminación. Luego recordando que la inversa de una matriz
elemental, es otra matriz elemental:

Llamamos L a una matriz triangular inferior.

Aplicaciones

Resolviendo sistemas de álgebra lineal

Dada la ecuación matricial

Ax = LUx = b

Queremos la solución para un determinando A y b. Los pasos son los

siguientes:

1. Primero, resolvemos Ly = b para y

2. Segundo, resolvemos Ux = y para x.

Nótese que ya tenemos las matrices L y U. La ventaja de este método es que

es computacionalmente eficiente, porque podemos elegir el vector b que nos
parezca y no tenemos que volver a hacer la eliminación de Gauss cada vez.

Factorización L-U con pi votación:

Al utilizar la técnica de triangulación de Gauss para obtener la descomposición

L-U de una matriz A podemos encontrarnos con el mismo problema de
encontrar un coeficiente en la diagonal que sea 0 o un mal condicionamiento.
Podemos entonces utilizar la misma técnica de pi votación : buscar el siguiente
elemento en la columna que sea distinto de 0 o, mejor aún, el de mayor valor
absoluto.

Pero una vez obtenida la descomposición L-U, si queremos aplicarla a resolver

un sistema de ecuaciones, tendremos que tener en cuenta la “historia” o
registro de las pi votaciones efectuadas para aplicar al vector de términos
independientes.

Esto se realiza mediante la matriz de permutación P, que consiste en efectuar

sobre la matriz identidad, las mismas permutaciones de filas que se vayan
efectuando sobre la matriz que se está triangulando por Gauss.

Al mismo tiempo se efectúan las mismas permutaciones sobre los elementos

subdiagonal de la matriz L.

Así, si tenemos, por ejemplo, el sistema:

AX=B

y L y U son las matrices obtenidas de la matriz A como descomposición L-U

por triangulación de Gauss con pi votaciones recogidas en la matriz de
permutación P, es fácil comprobar que :

LU=PA (LU) X=P (AX)=PB=NUEVOB

Por tanto los procesos de sustitución descendente y ascendente los aplicamos

a : LD=NUEVOB UX=D

Matriz Inversa

Las matrices L y U pueden ser usadas para calcular la matriz inversa mediante:

A − 1 = U − 1L − 1

Algunas implementaciones que invierten matrices usan este método.

Determinante de una matriz

Las matrices L y U pueden ser usadas para calcular el determinante de la

matriz A muy eficientemente porque det(A) = det(L)det(U) y los determinantes
de matrices triangulares son simplemente el producto de los elementos de sus
diagonales. En particular, si L es una matriz triangular en cuya diagonal todos
los elementos son uno, entonces:

La misma aproximación al problema puede ser usada para factorizaciones LUP

en las que aparece matrices de permutación, pues el determinante de una
matriz de permutación P es (−1)S, donde S es el número de permutaciones de
filas en la descomposición.

Introducción a MATLAB

¿Cómo Empezar?

Entrando Matrices Simples

MATLAB trabaja esencialmente con matrices numéricas rectangulares. La
manera más fácil de entrar matrices pequeñas es enumerando los elementos
de ésta de tal manera que:

 los elementos estén separados por blancos ó comas.

 los elementos estén cerrados entre corchetes, [ ].
 muestre el final de cada fila con ; (punto y coma).

Ejemplo:

A = [ 1 2 3; 4 5 6; 7 8 9 ]

resultaría en la matriz

A=

123
456
789

MATLAB guarda esta matriz para utilizarla luego bajo el nombre de A.

Si la matriz a entrar es muy grande se puede utilizar el siguiente formato:

A = [1 2 3
456
7 8 9]

El comando load y la función fread pueden leer matrices generadas en

sesiones anteriores ó generadas por otros programas.

Elementos de matrices

Los elementos de una matriz pueden ser cualquier expresión de MATLAB.

Ejemplo:

x = [-1.3,sqrt(3),(1+2+3) *4/5]

resultaría en

x=

-1.3000 1.7321 4.8000

Nos podemos referir a elementos individuales de la matriz con índices entre

paréntesis.

Ejemplo: En el ejemplo anterior

x(5) = abs(x(1))
resultaría en

x=

-1.3000 1.7321 4.8000 0 1.3000

Para añadir otra fila a la matriz A de arriba podemos hacer lo siguiente:

r = [10 11 12];

A = [A; r]

y resultaría en

A=
123
456
789
10 11 12

Instrucciones de MATLAB y Variables

Si omites el nombre de la variable y el signo "=", MATLAB automáticamente

crea la variable ans para guardar el resultado. También distingue las letras
mayúsculas de las minúsculas. Todos los nombres de funciones deben ser en
letras minúsculas.

Obteniendo Información del Espacio de Trabajo

Los ejemplos que hemos dado se han guardado en variables que están en el
espacio de trabajo de MATLAB. Para listar las variables en el espacio de
trabajo se utiliza el comando who. Para ver información adicional acerca de
estas variables se utiliza el comando whos.

Variables Permanentes

Las variables permanentes son aquellas con significado especial, y que no se

pueden eliminar. Estas son por ejemplo las variables ans y eps.

La variable eps es una tolerancia para determinar cosas como singularidad y

rango. Su valor inicial es la distancia de 1.0 al próximo número de punto
flotante mayor. En otras palabras, eps es el número positivo más pequeño tal
que .

Ayuda

Para obtener ayuda ó información de MATLAB utilice el comando help.

Saliendo y Guardando el Espacio de Trabajo

Para salir de MATLAB se escribe quit ó exit. Al terminar una sesión de
MATLAB, las variables en el espacio de trabajo se borran. Si deseas guardar tu
espacio de trabajo escribes save. save guarda todas las variables en un
archivo llamado [Link].

Se puede utilizar save y load con otros nombres de archivos, ó para guardar
solo variables seleccionadas

Ejemplo:

save temp X Y Z

Este ejemplo guarda las variables X, Y, Z en el archivo [Link]. Usando el

comando load temp las obtienes nuevamente del archivo [Link]. load y
save también pueden importar y exportar información de archivos ASCII.

Expresiones Numéricas y Aritméticas

Puedes construir expresiones con los operadores usuales de aritmética y

reglas de precedencia:

+ suma
- resta
* multiplicación
/ división a la derecha (división usual)
\ división a la izquierda
^ exponenciación

Algunas funciones matemáticas elementales de MATLAB son abs, sqrt, log y

sin. Puedes añadir funciones fácilmente con los archivos-M.

La función intrínseca pi devuelve el número . La función Inf equivale a "infinito".

Matrices y Números Complejos

MATLAB también permite números complejos, indicados por las variables

especiales i y j, en todas sus operaciones y funciones.

Funciones

Las funciones que utiliza MATLAB son intrínsecas al procesador de éste. Otras
funciones están disponibles en la librería externa de archivos-M. Además de
éstas funciones todo usuario también puede crear otras funciones. Puedes
combinar las funciones de acuerdo a tu necesidad.
Factorizar una matriz consiste en descomponerla en dos matrices cuyo
producto es la matriz original. 

Factorización LU

En este método se descompone la matriz A en dos matrices L (low) y U (up). A

= LU

La factorización es útil para la resolución de sistemas de ecuaciones.  

Sea el sistema de ecuaciones representado por AX = C. Sustituyendo A por

LU, nos queda LUX = C. 

Calculando el producto UX = Y, y sustituyendo en LUX = C nos queda LY = C.

De aquí podemos calcular el valor de Y y entonces sustituyéndolo en UX = Y
podemos calcular X. 

Toda matriz cuadrada, cuyos menores principales son todos no nulos, puede
descomponerse en la forma A = LU.

Ejemplo: Factorización LU de la matriz  

 1    0    2   -1

 3    1    1    0
-1    1   -6    2
 0   -1    1    1

Complementamos la matriz con la matriz identidad por la izquierda:

 1   0   0   0    1    0    2   -1

 0   1   0   0    3    1    1    0
 0   0   1   0   -1    1   -6    2
 0   0   0   1    0   -1    1    1

Empezaremos haciendo ceros en la cuarta columna, para ello sumamos la

primera fila y la tercera:

 1   0   0   0    1    0    2   -1

 0   1   0   0    3    1    1    0
 1   0   1   0    0    1   -4    1
 0   0   0   1    0   -1    1    1

Ahora multiplicamos la primera fila por 3 y se la restamos a la segunda.

 1   0   0   0    1    0    2   -1

-3   1   0   0    0    1   -5    3
 1   0   1   0    0    1   -4    1
 0   0   0   1    0   -1    1    1
Ahora hacemos lo mismo con la sexta columna. Operamos igual que antes
pero sin hacer las operaciones en la primera columna (que es la que hemos
utilizado antes). Sumando la segunda fila a la cuarta queda:

 1   0   0   0    1    0    2   -1

-3   1   0   0    0    1   -5    3
 1   0   1   0    0    1   -4    1
 0   1   0   1    0    0   -4    4

Restando la segunda fila a la tercera (sin tocar la primera columna):

 1   0   0   0    1    0    2   -1

-3   1   0   0    0    1   -5    3
 1  -1   1   0    0    0    1   -2
 0   1   0   1    0    0   -4    4

Sólo nos queda convertir el -4 en cero. Hacemos lo mismo pero sin hacer las
operaciones en la primera y segunda columna. Multiplicando la tercera fila por
4 y sumándola a la cuarta queda:

 1   0   0   0    1    0    2   -1

-3   1   0   0    0    1   -5    3
 1  -1   1   0    0    0    1   -2
 0   1   4   1    0    0    0   -4

Para obtener la matriz L se cambia el signo a los elementos del triángulo

inferior.

 1   0   0   0    1    0    2   -1

 3   1   0   0    0    1   -5    3
-1   1   1   0    0    0    1   -2
 0  -1  -4   1    0    0    0   -4