Queremos descomponer la matriz de coeficientes $A$ en una matriz triangular superior $U$ y una matriz triangular inferior $L$ de forma que
$$A=LU$$No todas las matrices admiten factorización $LU.$ Si A es invertible, admite descomposición $LU$ si y solo si todos sus menores principales son distintos de cero.
La factorización $LU$ no es única. Por ejemplo:
- Método de Crout: los elementos de la diagonal de $U$ son unos.
- Método de Doolittle: los elementos de la diagonal de $L$ son unos.
- Método de Cholesky (matrices simétricas definidas positivas): los elementos de la diagonal son iguales en $L$ y $U.$ Es decir, $u_{ii}=l_{ii}$
Usaremos el método de Doolittle. En este caso:
- $U$ es la matriz triangular superior que se obtiene al triangularizar $A$ como en Gauss.
- Los elementos de la matriz $L$ (por debajo de la diagonal principal) son los factores que usamos en las operaciones por filas en Gauss.
Consideramos el sistema de ecuaciones lineales $A\mathbf{x}=\mathbf{b}$ donde la matriz $A$ admite la factorización $LU.$ Para resolver el sistema, hay que
- Descomponer $A=LU$. Como $A\mathbf{x}=\mathbf{b}$ se transforma en $LU\mathbf{x}=\mathbf{b},$ si a $U\mathbf{x}$ le llamamos $\mathbf{y}$ podemos escribirla como $L\mathbf{y}=\mathbf{b}.$
- Resolver $L\mathbf{y}=\mathbf{b}$ por sustitución progresiva.
- Resolver $U\mathbf{x}=\mathbf{y}$ por sustitución regresiva.
Ejercicio¶
Sea el sistema $A\mathbf{x}=\mathbf{b}$ donde
$$ A=\left(\begin{array}{crc} 1 & 1 & 3\\ 3 & 0 & 1\\ 1 & -2 & 1 \end{array}\right) \quad \mathbf{b}=\left(\begin{array}{c} -2\\ -1\\ -3 \end{array}\right) $$Calcular $\mathbf{x}$ utilizando la factorización $LU$.
Los pasos son
- Factorización: $A=LU$
- Sustitución progresiva: $Ax=b \Longrightarrow LUx=b \Longrightarrow Ly = b$. Resolvemos $Ly=b$.
- Sustitución regresiva: Resolvemos $Ux=y$.
Factorización A=LU¶
En el primer paso hacemos ceros por debajo del elemento $a_{11}$ sumando la primera fila multiplicada por un real.
$$ \begin{array}{c} f_{1}\\ f_{2}\\ f_{3} \end{array} \left(\begin{array}{rrr} \mathbf{1} & 1 & 3\\ 3 & 0 & 1\\ 1 & -2 & 1 \end{array}\right) \quad \begin{array}{lclcrr} f_{1} & \rightarrow & f_{1} & & & \\ f_{2} & \rightarrow & f_{2} & - & \color{red}{\fbox{3/1}} & f_{1}\\ f_{3} & \rightarrow & f_{3} & - & \color{blue}{\fbox{1/1}} & f_{1} \end{array} $$Los multiplicadores, que aparecen en recuadros, son los elementos con los que construímos la matriz $L$. Los insertamos en la matriz, en lugar de los ceros creados. La matriz transformada es
$$ \left(\begin{array}{rrr} 1 & 1 & 3\\ \color{red}{\fbox{3}} & \mathbf{-3}& -8\\ \color{blue}{\fbox{1}} & -3 & -2 \end{array}\right)\quad\begin{array}{lclcrr} f_{1} & \rightarrow & f_{1}\\ f_{2} & \rightarrow & f_{2}\\ f_{3} & \rightarrow & f_{3} & - & \color{ForestGreen}{\fbox{$(-3)/(-3)$}} & f_{2} \end{array} $$Repetimos el proceso creando ceros por debajo de $a'_{22}$ y llegamos a la matriz que almacena simultáneamente $L$ y $U$.
$$ \left(\begin{array}{rrr} 1 & 1 & 3\\ \color{red}{\fbox{3}} & -3 & -8\\ \color{blue}{\fbox{1}} & \color{ForestGreen}{\fbox{1}} & 6 \end{array}\right) $$Y las matrices $L$ y $U$ son:
$$ L=\left(\begin{array}{rrr} 1 & 0 & 0\\ \color{red}{\fbox{3}} & 1 & 0\\ \color{blue}{\fbox{1}} & \color{lime}{\color{ForestGreen}{\fbox{1}}} & 1 \end{array}\right)\quad U=\left(\begin{array}{rrr} 1 & 1 & 3\\ 0 & -3 & -8\\ 0 & 0 & 6 \end{array}\right) \qquad \mathbf{b}=\left(\begin{array}{c} -2\\ -1\\ -3 \end{array}\right) $$Sustitución progresiva Ly = b¶
De la primera ecuación $$ y_1 = -2$$ De la segunda $$ y_2 = -1 -3 y_1 = -1-3(-2) = 5$$ Y de la tercera $$ y_3 = -3-y_1-y_2=-3-(-2)-5=-6$$ Es decir $$ y_1 = -2 \quad y_2 = 5 \quad y_3 = -6$$
Sustitución regresiva Ux = y¶
De la tercera ecuación $$ x_3 = -1$$ De la segunda $$ x_2 = \frac{5 +8 x_3}{-3} = \frac{5 +8 (-1)}{-3} = 1$$ Y de la primera $$ x_1 = -2-x_2-3x_3=-2-1-3(-1)=0$$ Es decir $$ x_1 = 0 \quad x_2 = 1 \quad x_3 = -1$$
Otras consideraciones¶
Diferencias entre Gauss y factorización LU¶
El método de factorización $LU$ es, esencialmente, el método de Gauss. La matriz $U$ es la misma matriz triangular que obtenemos por Gauss. ¿En qué son distintos entonces?
- En Gauss, incluímos a $\mathbf{b}$ en las transformaciones por fila, en factorización $LU$ no.
- En $LU$ es la matriz $L$ la que almacena las transformaciones que estamos haciendo a $\mathbf{b}$ (calculamos $\mathbf{y}$ en $L\mathbf{y}=\mathbf{b}$) para luego aplicárselas y obtener $\mathbf{y}$, que sería el vector $\mathbf{b}$ transformado con las operaciones por filas de Gauss.
Entonces, si hacemos lo mismo que con Gauss ¿por qué no trabajar directamente con la matriz aumentada? ¿Por qué hacerlo en dos pasos?
El método de factorización $LU$ tiene sentido (comparado con Gauss) si tenemos una serie de sistemas que hemos de resolver secuencialmente y donde la solución de uno determina el término independiente del siguiente $\mathbf{b}$. Por ejemplo
$$ 1.\quad A\mathbf{x}_1=\mathbf{x}_0,\quad A\mathbf{x}_2=\mathbf{x}_1, \quad A\mathbf{x}_3=\mathbf{x}_2,\dots\\ 2.\quad L\mathbf{y}_1=\mathbf{x}_0,\quad L\mathbf{y}_2=\mathbf{x}_1, \quad L\mathbf{y}_3=\mathbf{x}_2,\dots\\ 3.\quad U\mathbf{x}_1=\mathbf{y}_1,\quad U\mathbf{x}_2=\mathbf{y}_2, \quad U\mathbf{x}_3=\mathbf{y}_y,\dots\\ $$En este caso, con Gauss tendríamos que triangularizar una vez para cada sistema, cambiando el término independiente, mientras que con el método $LU$ haríamos sólo una vez el paso 1 y repetiríamos para cada sistema los pasos 2 y 3.
Factorización LU con matrices elementales¶
La secuencia de operaciones sobre las filas que se usa para transformar la matriz $A$ en un matriz triangular superior equivalente es
$f_2\longleftarrow f_2-(3)f_1$ $$ \left( \begin{array}{rrr} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 1 & -2 & 1 \\ \end{array} \right) $$ $ f_3\longleftarrow f_3-(1)f_1 $ $$ \left( \begin{array}{ccc} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 0 & -3 & -2 \\ \end{array} \right) $$ $ f_3\longleftarrow f_3-(1)f_2 $ $$ \left( \begin{array}{rrr} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 0 & 0 & 6 \\ \end{array} \right) $$
Estas transformaciones se consiguen con una serie de multiplicación de matrices por la izquierda que se corresponden con las matrices elementales
$$ f_2\longleftarrow f_2-(3)f_1 $$.
$$ \left( \begin{array}{rrr} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 1 & 3 \\ 3 & 0 & 1 \\ 1 & -2 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 1 & -2 & 1 \\ \end{array} \right) $$.
$$ f_3\longleftarrow f_3-(1)f_1 $$.
$$ \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{ccc} 1 & 1 & 3 \\ 3 & 0 & 1 \\ 1 & -2 & 1 \\ \end{array} \right) = \left( \begin{array}{ccc} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 0 & -3 & -2 \\ \end{array} \right) $$.
$$ f_3\longleftarrow f_3-(1)f_2 $$.
$$ \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 1 & 3 \\ 3 & 0 & 1 \\ 1 & -2 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 0 & 0 & 6 \\ \end{array} \right) $$Cada matriz elemental $G_1$, $G_2$ y $G_3$ se corresponde con una operación pof fila
$$G_3G_2G_1A=U$$Y, por lo tanto
$$A=(G_3G_2G_1)^{-1}U=G_1^{-1}G_2^{-1}G_3^{-1}U$$Si llamamos
$$L=G_1^{-1}G_2^{-1}G_3^{-1}$$${\color{white}.}$ $$A=\text{LU}$$
donde $L$ es una matriz triangular inferior. Calculemos esta matriz $L$
$$ G_1^{-1}= \left( \begin{array}{rrr} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)^{-1} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) $$.
$$ G_2^{-1}= \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{array} \right)^{-1} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ \end{array} \right) $$.
$$ G_3^{-1}=\left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \\ \end{array} \right)^{-1} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ \end{array} \right) $$Y entonces
$$ G_1^{-1}G_2^{-1}= \left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 1 & 0 & 1 \\ \end{array} \right) $$.
$$ G_1^{-1}G_2^{-1}G_3^{-1}= \left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 1 & 1 & 1 \\ \end{array} \right) $$Y ya tenemos $A$ factorizada como $LU$
$$ A =\left( \begin{array}{ccc} 1 & 1 & 3 \\ 3 & 0 & 1 \\ 1 & -2 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 1 & 1 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 1 & 3 \\ 0 & -3 & -8 \\ 0 & 0 & 6 \\ \end{array} \right) = LU $$