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, deben tenerse en cuenta algunos casos especiales, por ejemplo, si uno o varios elementos de la diagonal principal de la matriz a factorizar es cero, es necesario premultiplicar la matriz por una o varias matrices elementales de permutación. Existe un segundo método llamado factorización ${\displaystyle PA=LU}$o ${\displaystyle 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 ${\displaystyle A}$ una matriz invertible (si no lo fuera, entonces la descomposición podría no ser única). Tenemos que

${\displaystyle A=LU}$,

donde ${\displaystyle L}$ y ${\displaystyle U}$ son matrices inferiores y superiores triangulares respectivamente.

Para matrices ${\displaystyle 3\times 3}$, esto es${\displaystyle {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{pmatrix}}={\begin{pmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\\\end{pmatrix}}{\begin{pmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{pmatrix}}}$.

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

${\displaystyle L_{m-1}P_{m-1}...L_{2}P_{2}L_{1}P_{1}A=U}$

Con ${\displaystyle L_{m-1}...L_{1}}$ matrices triangulares inferiores, ${\displaystyle P_{m-1}...P_{1}}$ matrices de permutación y ${\displaystyle U}$ una matriz triangular superior.

Para determinar ${\displaystyle L}$ tenemos que

${\displaystyle L=({L'}_{m-1}*...*{L'}_{2}*{L'}_{1})^{-1}}$

y cada ${\displaystyle {L'}_{k}}$ está dado por:

${\displaystyle {L'}_{k}}$ = ${\displaystyle {P}_{m-1}*...*{P}_{k+1}*{L}_{k}*{P^{-1}}_{k+1}*...*{P^{-1}}_{m-1}}$

Esto se debe a que ${\displaystyle {L'}_{k}}$ es igual a ${\displaystyle L_{k}}$, pero con los elementos de la subdiagonal permutados.

Otra forma de ver este tipo de factorización es: ${\displaystyle A=P^{T}LU}$. Recordando que las matrices de permutación. La matriz permutación es invertible y su inversa es su traspuesta

Unidad

Las matrices ${\displaystyle L}$y ${\displaystyle U}$, donde L es una matriz triangular inferior con unos en la diagonal y U es una matriz triangular superior, son únicas, si la matriz no es singular. En caso contrario pueden no ser únicas.

Demostración:

Dada la matriz ${\displaystyle A\in {\mathcal {M}}_{m\times n}(\mathbb {R} )}$, tenemos que ${\displaystyle A=L_{1}U_{1}}$ y ${\displaystyle A=L_{2}U_{2}}$. Recordemos que ${\displaystyle L_{1},U_{1},L_{2},U_{2}}$ son invertibles por tener el determinante distinto de cero entonces:

${\displaystyle L_{1}U_{1}=L_{2}U_{2}}$, y también ${\displaystyle {L_{2}}^{-1}L_{1}=U_{2}{U_{1}}^{-1}}$Entonces ${\displaystyle {L_{2}}^{-1}L_{1}}$ es una matriz triangular inferior, con unos en la diagonal y ${\displaystyle U_{2}{U_{1}}^{-1}}$ es triangular superior (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:

${\displaystyle {L_{2}}^{-1}L_{1}=I}$y ${\displaystyle U_{2}{U_{1}}^{-1}=I}$.

Con lo cual se concluye que ${\displaystyle L_{1}=L_{2}}$ y ${\displaystyle U_{1}=U_{2}}$

Algoritmos

La factorización ${\displaystyle LU}$es básicamente una forma modificada de la eliminación gaussiana. Transformamos la matriz ${\displaystyle A}$ en una matriz triangular superior ${\displaystyle U}$anulando los elementos debajo de la diagonal. Entonces,

${\displaystyle E_{1}*E_{2}*...*E_{n}*A=U}$,

donde ${\displaystyle E_{1},E_{2},...,E_{n}}$ 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 tenemos que

${\displaystyle A=E_{n}^{-1}*...*E_{2}^{-1}*E_{1}^{-1}*U}$.

Llamamos ${\displaystyle L}$a ${\displaystyle E_{n}^{-1}*...*E_{2}^{-1}*E_{1}^{-1}}$ una matriz triangular inferior.

Aplicaciones

Resolviendo sistemas de álgebra lineal

Dada la ecuación matricial ${\displaystyle Ax=LUx=b}$.

Queremos la solución para un determinando ${\displaystyle A}$y ${\displaystyle b}$. Los pasos son los siguientes:

1. Primero, resolvemos ${\displaystyle Ly=b}$ para ${\displaystyle y}$.
2. Segundo, resolvemos ${\displaystyle Ux=y}$ para ${\displaystyle x}$.

Nótese que ya tenemos las matrices ${\displaystyle L}$y ${\displaystyle 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 LU con pivoteo

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 pivotació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 ${\displaystyle LU}$, si queremos aplicarla a resolver un sistema de ecuaciones, tendremos que tener en cuenta la “historia” o registro de las pivotaciones efectuadas para aplicar al vector de términos independientes.

Esto se realiza mediante la matriz de permutación ${\displaystyle 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:

${\displaystyle Ax=b}$

y ${\displaystyle L}$y ${\displaystyle U}$son las matrices obtenidas de la matriz ${\displaystyle A}$como descomposición ${\displaystyle LU}$ por triangulación de Gauss con pivotaciones recogidas en la matriz de permutación ${\displaystyle P}$, es fácil comprobar que

${\displaystyle (LU)x=Pb}$

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

1. Primero, resolvemos ${\displaystyle Ly=Pb}$ para ${\displaystyle y}$
2. Segundo, resolvemos ${\displaystyle Ux=y}$ para ${\displaystyle x}$

Matriz Inversa

Las matrices ${\displaystyle L}$y ${\displaystyle U}$pueden ser usadas para calcular la matriz inversa mediante:

${\displaystyle A^{-1}=U^{-1}L^{-1}P}$.

Algunas implementaciones que invierten matrices usan este método.

Determinante de una matriz

Las matrices ${\displaystyle L}$ y ${\displaystyle U}$ pueden ser usadas para calcular el determinante de la matriz ${\displaystyle A}$ muy eficientemente porque ${\displaystyle 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 ${\displaystyle L}$ es una matriz triangular en cuya diagonal todos los elementos son uno, entonces:${\displaystyle \det(A)=\det(L)\det(U)=\det(U)=\prod _{i=1}^{n}u_{ii}.}$

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 ${\displaystyle P}$es${\displaystyle (-1)^{S}}$, donde ${\displaystyle S}$ es el número de permutaciones de filas en la descomposición.