2.10: Factorización LU

Una\(LU\) factorización de una matriz implica escribir la matriz dada como el producto de una matriz triangular inferior\(L\) que tiene la diagonal principal constituida enteramente por unas, y una matriz triangular superior\(U\) en el orden indicado. Esta es la versión que aquí se discute pero a veces es el caso de que el\(L\) tenga números distintos a 1 por debajo de la diagonal principal. Sigue siendo un concepto útil. El\(L\) va con “inferior” y el\(U\) con “superior”.

Resulta que muchas matrices se pueden escribir de esta manera y cuando esto es posible, la gente se entusiasma con las formas ingeniosas de resolver el sistema de ecuaciones,\(AX=B\). Es por esta razón que se quiere estudiar la\(LU\) factorización. Permite trabajar únicamente con matrices triangulares. Resulta que se necesitan alrededor de la mitad de operaciones para obtener una\(LU\) factorización que para encontrar la forma de escalón reducido de fila.

Primero hay que señalar que no todas las matrices tienen una\(LU\) factorización y por lo tanto enfatizaremos las técnicas para lograrlo más que las pruebas formales.

Ejemplo\(\PageIndex{1}\): A Matrix with NO \(LU\) factorization

¿Se puede escribir\(\left[ \begin{array}{rr} 0 & 1 \\ 1 & 0 \end{array} \right]\) en el formulario\(LU\) como se acaba de describir?

Solución

Para hacerlo necesitarías\[\left[ \begin{array}{rr} 1 & 0 \\ x & 1 \end{array} \right] \left[ \begin{array}{rr} a & b \\ 0 & c \end{array} \right] = \ \left[ \begin{array}{cc} a & b \\ xa & xb+c \end{array} \right] =\left[ \begin{array}{rr} 0 & 1 \\ 1 & 0 \end{array} \right] .\nonumber \]

Por lo tanto,\(b=1\) y\(a=0.\) también, desde las filas inferiores, lo\(xa=1\) que no puede suceder y tener\(a=0.\) Por lo tanto, no se puede escribir esta matriz en la forma\(% LU.\) No tiene\(LU\) factorización. Esto es lo que queremos decir anteriormente al decir que el método carece de generalidad.

Sin embargo, el método suele ser extremadamente útil, y describiremos a continuación uno de los muchos métodos utilizados para producir una\(LU\) factorización cuando sea posible.

Encontrar una\(LU\) factorización por inspección

¿Qué matrices tienen una\(LU\) factorización? Resulta que son aquellos cuya forma fila-escalón se puede lograr sin cambiar de filas. En otras palabras, matrices que solo implican el uso de operaciones de fila de tipo 2 o 3 para obtener la forma fila-escalón.

Ejemplo\(\PageIndex{2}\): An \(LU\) factorization

Encuentra una\(LU\) factorización de\(A=\left[ \begin{array}{cccc} 1 & 2 & 0 & 2 \\ 1 & 3 & 2 & 1 \\ 2 & 3 & 4 & 0 \end{array} \right] .\)

Solución

Una forma de encontrar la\(LU\) factorización es simplemente buscarla directamente. Necesitas

\[\left[ \begin{array}{cccc} 1 & 2 & 0 & 2 \\ 1 & 3 & 2 & 1 \\ 2 & 3 & 4 & 0 \end{array} \right] =\left[ \begin{array}{ccc} 1 & 0 & 0 \\ x & 1 & 0 \\ y & z & 1 \end{array} \right] \left[ \begin{array}{cccc} a & d & h & j \\ 0 & b & e & i \\ 0 & 0 & c & f \end{array} \right] .\nonumber \]

Entonces multiplicando estos se obtiene\[ \ \left[ \begin{array}{cccc} a & d & h & j \\ xa & xd+b & xh+e & xj+i \\ ya & yd+zb & yh+ze+c & yj+iz+f \end{array} \right]\nonumber \] y así ya se puede decir a qué equivalen las diversas cantidades. Desde la primera columna, necesitas\(a=1,x=1,y=2.\) Ahora ve a la segunda columna. Lo necesitas\(d=2,xd+b=3\)\(b=1,yd+zb=3\) así\(z=-1.\) De la tercera columna,\(h=0,e=2,c=6.\) Ahora de la cuarta columna,\(j=2,i=-1,f=-5.\) Por lo tanto, una\(LU\) factorización es\[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 2 & -1 & 1 \end{array} \right] \left[ \begin{array}{rrrr} 1 & 2 & 0 & 2 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 6 & -5 \end{array} \right] \nonumber .\] Puedes comprobar si lo hiciste bien simplemente multiplicando estos dos.

\(LU\)Factorización, Método Multiplicador

Recuerda que para que una matriz\(A\) se escriba en la forma\(A=LU\), debes poder reducirla a su forma fila-escalón sin intercambiar filas. El siguiente método da un proceso para calcular la\(LU\) factorización de dicha matriz\(A\).

Ejemplo\(\PageIndex{3}\): \(LU\) factorization

Encuentre una\(LU\) factorización para\[\left[ \begin{array}{rrr} 1 & 2 & 3 \\ 2 & 3 & 1 \\ -2 & 3 & -2 \end{array} \right]\nonumber \]

Solución

Escribe la matriz como el siguiente producto. \[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 2 & 3 & 1 \\ -2 & 3 & -2 \end{array} \right]\nonumber \]

En la matriz de la derecha, comience con la fila izquierda y ponga a cero las entradas debajo de la parte superior usando la operación de fila que implica agregar un múltiplo de una fila a otra fila. Esto lo haces y además actualizas la matriz de la izquierda para que el producto quede sin cambios. Aquí está el primer paso. Toma\(-2\) tiempos la fila superior y agrega a la segunda. Después toma\(2\) tiempos la fila superior y agrega a la segunda en la matriz de la izquierda. \[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & -1 & -5 \\ -2 & 3 & -2 \end{array} \right]\nonumber \]El siguiente paso es tomar\(2\) veces la fila superior y agregar a la parte inferior en la matriz de la derecha. Para asegurarse de que el producto no se modifica, coloca un\(% -2\) en la parte inferior izquierda en la matriz de la izquierda. De esta manera el siguiente paso rinde\[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -2 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & -1 & -5 \\ 0 & 7 & 4 \end{array} \right]\nonumber \] Siguiente toma\(7\) veces la fila del medio a la derecha y agrega a la fila inferior. Actualizando la matriz de la izquierda de manera similar a lo que se hizo antes,\[\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -2 & -7 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & -1 & -5 \\ 0 & 0 & -31 \end{array} \right]\nonumber \] En este punto, detente. Ya terminaste.

El método que se acaba de describir se llama el método multiplicador.

Resolver sistemas mediante\(LU\) factorización

Una razón por la que la gente se preocupa por la\(LU\) factorización es que permite la rápida solución de sistemas de ecuaciones. Aquí hay un ejemplo.

Ejemplo\(\PageIndex{4}\): \(LU\) factorization to Solve Equations

Supongamos que quieres encontrar las soluciones para\[\left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 4 & 3 & 1 & 1 \\ 1 & 2 & 3 & 0 \end{array} \right] \left[ \begin{array}{c} x \\ y \\ z \\ w \end{array} \right] =\left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right] .\nonumber \]

Solución

Por supuesto, una forma es escribir la matriz aumentada y moler. Sin embargo, esto implica más operaciones de fila que el cálculo de la\(LU\) factorización y resulta que la\(LU\) factorización puede dar la solución rápidamente. Aquí está cómo. A continuación se presenta una\(LU\) factorización para la matriz. \[\left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 4 & 3 & 1 & 1 \\ 1 & 2 & 3 & 0 \end{array} \right] \ = \ \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 0 & -5 & -11 & -7 \\ 0 & 0 & 0 & -2 \end{array} \right] .\nonumber\]

Vamos\(UX=Y\) y consideremos\(LY=B\) dónde en este caso,\(B=\left[ 1,2,3\right] ^{T}\). Así\[ \ \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right] \left[ \begin{array}{c} y_{1} \\ y_{2} \\ y_{3} \end{array} \right] =\left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right]\nonumber \] que lo que rinde muy rápidamente que\(Y=\left[ \begin{array}{r} 1 \\ -2 \\ 2 \end{array} \right] \ .\)

Ahora puedes encontrar\(X\) resolviendo\(UX=Y\). Así, en este caso,\[\left[ \begin{array}{rrrr} 1 & 2 & 3 & 2 \\ 0 & -5 & -11 & -7 \\ 0 & 0 & 0 & -2 \end{array} \right] \left[ \begin{array}{c} x \\ y \\ z \\ w \end{array} \right] =\left[ \begin{array}{r} 1 \\ -2 \\ 2 \end{array} \right]\nonumber \] que rinde\[X=\left[ \begin{array}{c} - \frac{3}{5}+\frac{7}{5}t \\ \frac{9}{5}-\frac{11}{5}t \\ t \\ -1 \end{array} \right] ,\enspace t\in \mathbb{R}\text{.}\nonumber \]

Justificación del Método Multiplicador

¿Por qué funciona el método multiplicador para encontrar la\(LU\) factorización? Supongamos que\(A\) es una matriz que tiene la propiedad de que la forma fila-escalón se\(A\) puede lograr sin cambiar de filas. Así, cada fila que se reemplaza usando esta operación de fila para obtener la forma fila-escalón puede ser modificada usando una fila que está por encima de ella.

Lema\(\PageIndex{1}\): Multiplier Method and Triangular Matrices

Dejar\(L\) ser una matriz triangular inferior (superior) la\(m\times m\) cual tiene unas abajo de la diagonal principal. Entonces\(L^{-1}\) también es una matriz triangular inferior (superior) la cual tiene unas abajo de la diagonal principal. En el caso que\(L\) sea de la forma\[L=\left[ \begin{array}{cccc} 1 & & & \\ a_{1} & 1 & & \\ \vdots & & \ddots & \\ a_{n} & & & 1 \end{array} \right] \label{4nove1h}\] donde todas las entradas son cero excepto la columna izquierda y la diagonal principal, también es el caso que\(L^{-1}\) se obtiene de simplemente multiplicando cada entrada\(L\) por debajo de la diagonal principal en \(L\)con\(-1\). Lo mismo es cierto si la columna única distinta de cero está en otra posición.

Prueba

Considere la configuración habitual para encontrar la inversa\(\left[ \begin{array}{cc} L & I \end{array} \right] .\) Luego, cada operación de fila realizada para reducir\(L\) a la forma de escalón reducido de fila da como resultado cambiar solo las entradas\(I\) debajo de la diagonal principal. En el caso especial de\(L\) dado en\(\eqref{4nove1h}\) o la única columna distinta de cero está en otra posición, la multiplicación por\(-1\) como se describe en el lema claramente da como resultado\(L^{-1}\).

Para una simple ilustración de la última reclamación,\[\left[ \begin{array}{cccccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & a & 1 & 0 & 0 & 1 \end{array} \right] \rightarrow \left[ \begin{array}{cccccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & -a & 1 \end{array} \right]\nonumber \]

Ahora\(A\) déjese ser una\(m\times n\) matriz, digamos\[A=\left[ \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array} \right]\nonumber \] y asuma\(A\) puede ser fila reducida a una forma triangular superior usando solo la operación de fila 3. Así, en particular,\(a_{11}\neq 0\). Multiplicar a la izquierda por\(E_{1}=\)\[\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ - \frac{a_{21}}{a_{11}} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -\frac{a_{m1}}{a_{11}} & 0 & \cdots & 1 \end{array} \right]\nonumber \] Este es el producto de matrices elementales que hacen modificaciones en la primera columna solamente. Es equivalente a tomar\(-a_{21}/a_{11}\) tiempos la primera fila y sumar a la segunda. Después tomando\(-a_{31}/a_{11}\) tiempos la primera fila y sumando a la tercera y así sucesivamente. Los cocientes en la primera columna de la matriz anterior son los multiplicadores. Así el resultado es de la forma\[E_{1}A=\left[ \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}^{\prime } \\ 0 & a_{22}^{\prime } & \cdots & a_{2n}^{\prime } \\ \vdots & \vdots & & \vdots \\ 0 & a_{m2}^{\prime } & \cdots & a_{mn}^{\prime } \end{array} \right]\nonumber \] Por suposición,\(a_{22}^{\prime }\neq 0\) y así es posible utilizar esta entrada para poner a cero todas las entradas debajo de ella en la matriz de la derecha por multiplicación por una matriz de la forma\(E_{2}=\left[ \begin{array}{cc} 1 & \mathbf{0} \\ \mathbf{0} & E \end{array} \right]\) donde\(E\) se encuentra un \(\left[ m-1\right] \times \left[ m-1\right]\)matriz de la forma\[E=\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ -\frac{a_{32}^{\prime }}{a_{22}^{\prime }} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -\frac{a_{m2}^{\prime }}{a_{22}^{\prime }} & 0 & \cdots & 1 \end{array} \right]\nonumber \] Nuevamente, las entradas en la primera columna por debajo de la 1 son los multiplicadores. Continuando de esta manera, poniendo a cero las entradas por debajo de las entradas diagonales, finalmente conduce a\[E_{m-1}E_{n-2}\cdots E_{1}A=U\nonumber \] donde\(U\) está el triangular superior. Cada uno\(E_{j}\) tiene todos los que bajan la diagonal principal y es triangular inferior. Ahora multiplicar ambos lados por las inversas de la\(E_{j}\) en el orden inverso\(.\) Esto rinde\[A=E_{1}^{-1}E_{2}^{-1}\cdots E_{m-1}^{-1}U\nonumber \] Por Lemma\(\PageIndex{1}\), esto implica que el producto de esos\(E_{j}^{-1}\) es una matriz triangular inferior que tiene todas las abajo de la diagonal principal .

La discusión anterior y el lema dan la justificación del método multiplicador. Las expresiones\[\frac{-a_{21}}{a_{11}},\frac{-a_{31}}{a_{11}},\cdots, \frac{-a_{m1}}{a_{11}}\nonumber \] denotadas respectivamente por\(M_{21},\cdots ,M_{m1}\) para guardar notación que se obtuvieron en la construcción\(E_{1}\) son los multiplicadores. Entonces según el lema, para\(E_{1}^{-1}\) encontrarte simplemente escribe Consideraciones\[\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ -M_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -M_{m1} & 0 & \cdots & 1 \end{array} \right]\nonumber \] similares se aplican al otro\(E_{j}^{-1}.\) Así\(L\) es un producto de la forma\[\left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ -M_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -M_{m1} & 0 & \cdots & 1 \end{array} \right] \cdots \left[ \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & 0 & \ddots & \vdots \\ 0 & \cdots & -M_{m\left[ m-1\right] } & 1 \end{array} \right]\nonumber \] cada factor teniendo como máximo una columna distinta de cero, cuya posición se mueve de izquierda a derecha en escanear el producto anterior de matrices de izquierda a derecha. Se deduce de lo que sabemos sobre el efecto de multiplicar a la izquierda por una matriz elemental que el producto anterior es de la forma\[\left[ \begin{array}{ccccc} 1 & 0 & \cdots & 0 & 0 \\ -M_{21} & 1 & \cdots & 0 & 0 \\ \vdots & -M_{32} & \ddots & \vdots & \vdots \\ -M_{\left[ m-1\right] 1} & \vdots & \cdots & 1 & 0 \\ -M_{m1} & -M_{m2} & \cdots & -M_{m\left[m-1\right]} & 1 \end{array} \right]\nonumber \]

En palabras, comenzando por la columna izquierda y moviéndose hacia la derecha, simplemente inserta, en la posición correspondiente en la matriz de identidad,\(-1\) multiplicado por el multiplicador que se utilizó para eliminar a cero una entrada en esa posición por debajo de la diagonal principal adentro\(A,\) mientras se conserva el diagonal principal que consiste enteramente en unos. Esto es\(L.\)