Descomposición LU
En análisis numérico y álgebra lineal , la descomposición o factorización inferior-superior ( LU ) factoriza una matriz como el producto de una matriz triangular inferior y una matriz triangular superior. El producto a veces también incluye una matriz de permutación . La descomposición LU puede verse como la forma matricial de la eliminación gaussiana . Las computadoras generalmente resuelven sistemas cuadrados de ecuaciones lineales usando la descomposición LU, y también es un paso clave al invertir una matriz o calcular el determinantede una matriz. La descomposición LU fue introducida por el matemático polaco Tadeusz Banachiewicz en 1938. [1]
Sea A una matriz cuadrada. Una factorización LU se refiere a la factorización de A , con ordenaciones o permutaciones de filas y / o columnas adecuadas, en dos factores: una matriz triangular inferior L y una matriz triangular superior U :
En la matriz triangular inferior todos los elementos por encima de la diagonal son cero, en la matriz triangular superior, todos los elementos por debajo de la diagonal son cero. Por ejemplo, para una matriz A de 3 × 3 , su descomposición LU se ve así:
Sin una ordenación adecuada o permutaciones en la matriz, es posible que la factorización no se materialice. Por ejemplo, es fácil verificar (expandiendo la multiplicación de matrices) que . Si , entonces al menos uno de y tiene que ser cero, lo que implica que L o U es singular . Esto es imposible si A no es singular (invertible). Este es un problema de procedimiento. Puede eliminarse simplemente reordenando las filas de A para que el primer elemento de la matriz permutada sea distinto de cero. El mismo problema en los siguientes pasos de factorización se puede eliminar de la misma manera; consulte el procedimiento básico a continuación.
Resulta que una permutación adecuada en filas (o columnas) es suficiente para la factorización LU. La factorización LU con pivote parcial (LUP) se refiere a menudo a la factorización LU con permutaciones de fila únicamente:
donde L y U son de nuevo inferior y superior matrices triangulares, y P es una matriz de permutación , que, multiplicados izquierda cuando a A , reordena las filas de A . Resulta que todas las matrices cuadradas se pueden factorizar de esta forma, [2] y la factorización es numéricamente estable en la práctica. [3] Esto hace que la descomposición LUP sea una técnica útil en la práctica.
