2.5: Descomposición de LU

Ver LU Descomposición en YouTube

Ver Resolviendo lux=b en YouTube

El proceso de eliminación gaussiana también da como resultado la factorización de la matriz\(\text{A}\) para

\[\text{A}=\text{LU},\nonumber \]

donde\(\text{L}\) es una matriz triangular inferior y\(\text{U}\) es una matriz triangular superior. Utilizando la\(\text{A}\) misma matriz que en la última sección, mostramos cómo se realiza esta factorización. Tenemos

\[\left(\begin{array}{rrr}-3&2&-1\\6&-6&7\\3&-4&4\end{array}\right)\to\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\3&-4&4\end{array}\right)=\text{M}_1\text{A},\nonumber \]

donde

\[\text{M}_1\text{A}=\left(\begin{array}{ccc}1&0&0\\2&1&0\\0&0&1\end{array}\right)\left(\begin{array}{rrr}-3&2&-1\\6&-6&7\\3&-4&4\end{array}\right)=\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\3&-4&4\end{array}\right).\nonumber \]

Tenga en cuenta que la matriz\(\text{M}_1\) realiza la eliminación de filas en la segunda fila usando la primera fila. Dos veces se agrega la primera fila a la segunda fila.

El siguiente paso es

\[\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\3&-4&4\end{array}\right)\to\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&-2&3\end{array}\right)=\text{M}_2\text{M}_1\text{A},\nonumber \]

donde

\[\text{M}_2\text{M}_1\text{A}=\left(\begin{array}{rrr}1&0&0\\0&1&0\\1&0&1\end{array}\right)\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\3&-4&4\end{array}\right)=\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&-2&3\end{array}\right).\nonumber \]

Tenga en cuenta que la matriz\(\text{M}_2\) realiza la eliminación de filas en la tercera fila usando la primera fila. Una vez se agrega la primera fila a la tercera fila.

El último paso es

\[\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&-2&3\end{array}\right)\to\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&0&-2\end{array}\right)=\text{M}_3\text{M}_2\text{M}_1\text{A},\nonumber \]

donde

\[\text{M}_3\text{M}_2\text{M}_1\text{A}=\left(\begin{array}{rrr}1&0&0\\0&1&0\\0&-1&1\end{array}\right)\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&-2&3\end{array}\right)=\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&0&-2\end{array}\right).\nonumber \]

Aquí,\(\text{M}_3\) realiza la eliminación de filas en la tercera fila usando la segunda fila. Menos una vez que se agrega la segunda fila a la tercera fila. Ahora tenemos

\[\text{M}_3\text{M}_2\text{M}_1\text{A}=\text{U}\nonumber \]

o

\[\text{A}=\text{M}_1^{-1}\text{M}_2^{-1}\text{M}_3^{-1}\text{U}.\nonumber \]

Las matrices inversas son fáciles de encontrar. La matriz\(\text{M}_1\) multiplica la primera fila por\(2\) y la agrega a la segunda fila. Para invertir esta operación, simplemente necesitamos multiplicar la primera fila por\(−2\) y agregarla a la segunda fila, de modo que

\[\text{M}_1=\left(\begin{array}{ccc}1&0&0\\2&1&0\\0&0&1\end{array}\right),\quad\text{M}_1^{-1}=\left(\begin{array}{rrr}1&0&0\\-2&1&0\\0&0&1\end{array}\right).\nonumber \]

Para verificar eso

\[\text{M}_1\text{M}_1^{-1}=\text{I},\nonumber \]

multiplicamos

\[\left(\begin{array}{ccc}1&0&0\\2&1&0\\0&0&1\end{array}\right)\left(\begin{array}{rrr}1&0&0\\-2&1&0\\0&0&1\end{array}\right)=\left(\begin{array}{rrr}1&0&0\\0&1&0\\0&0&1\end{array}\right).\nonumber \]

Del mismo modo,

\[\text{M}_2=\left(\begin{array}{rrr}1&0&0\\0&1&0\\1&0&1\end{array}\right),\quad\text{M}_2^{-1}=\left(\begin{array}{rrr}1&0&0\\0&1&0\\-1&0&1\end{array}\right),\nonumber \]

y

\[\text{M}_3=\left(\begin{array}{rrr}1&0&0\\0&1&0\\0&-1&1\end{array}\right),\quad\text{M}_3^{-1}=\left(\begin{array}{rrr}1&0&0\\0&1&0\\0&1&1\end{array}\right).\nonumber \]

Por lo tanto,

\[\text{L}=\text{M}_1^{-1}\text{M}_2^{-1}\text{M}_3^{-1}\nonumber \]

está dado por

\[\text{L}=\left(\begin{array}{rrr}1&0&0\\-2&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\\-1&2&0\\-1&1&1\end{array}\right),\nonumber \]

que es triangular inferior. Observe que los elementos fuera de la diagonal de\(\text{M}_1^{−1}\)\(\text{M}_2^{−1}\), y simplemente\(\text{M}_3^{-1}\) se combinan para formar\(\text{L}\). Sin realmente multiplicar matrices, se podría obtener este resultado considerando cómo una matriz elemental realiza la reducción de filas en otra matriz elemental. Nuestra\(\text{LU}\) descomposición es por lo tanto

\[\left(\begin{array}{rrr}-3&2&-1\\6&-6&7\\3&-4&4\end{array}\right)=\left(\begin{array}{rrr}1&0&0\\-2&1&0\\-1&1&1\end{array}\right)\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&0&-2\end{array}\right).\nonumber \]

Otra característica agradable de la\(\text{LU}\) descomposición es que se puede hacer sobrescribiendo\(\text{A}\), por lo tanto ahorrando memoria si la matriz\(\text{A}\) es muy grande.

La\(\text{LU}\) descomposición es útil cuando uno necesita resolver\(\text{Ax} = \text{b}\) para\(\text{x}\) cuando\(\text{A}\) es fijo y hay muchos diferentes\(\text{b}\), primero determina\(\text{L}\) y\(\text{U}\) usa la eliminación gaussiana. Entonces uno escribe

\[(\text{LU})\text{x}=\text{L}(\text{Ux})=\text{b}.\nonumber \]

Dejamos

\[\text{y}=\text{Ux},\nonumber \]

y primero resolver

\[\text{Ly}=\text{b}\nonumber \]

para\(\text{y}\) por sustitución directa. Luego resolvemos

\[\text{Ux}=\text{y}\nonumber \]

para\(\text{x}\) por sustitución posterior. Si contamos operaciones, podemos demostrar que resolver\((\text{LU})\text{x} = \text{b}\) es un factor de una vez\(n\) más rápido\(\text{L}\) y\(\text{U}\) estamos en la mano que resolviendo\(\text{Ax} = \text{b}\) directamente por eliminación gaussiana.

Ahora ilustramos la solución de\(\text{LUx} = \text{b}\) usar nuestro ejemplo anterior, donde

\[\text{L}=\left(\begin{array}{rrr}1&0&0\\-2&1&0\\-1&1&1\end{array}\right),\quad\text{U}=\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&0&-2\end{array}\right),\quad\text{b}=\left(\begin{array}{r}-1\\-7\\-6\end{array}\right).\nonumber \]

Con\(\text{y} = \text{Ux}\), primero resolvemos\(\text{Ly} = \text{b}\), es decir

\[\left(\begin{array}{rrr}1&0&0\\-2&1&0\\-1&1&1\end{array}\right)\left(\begin{array}{c}y_1\\y_2\\y_3\end{array}\right)=\left(\begin{array}{c}-1\\-7\\-6\end{array}\right).\nonumber \]

Uso de sustitución directa

\[\begin{aligned}y_1&=-1, \\ y_2&=-7+2y_1=-9, \\ y_3&=-6+y_1-y_2=2.\end{aligned} \nonumber \]

Ahora resolvemos\(\text{Ux} = \text{y}\), es decir

\[\left(\begin{array}{rrr}-3&2&-1\\0&-2&5\\0&0&-2\end{array}\right)\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{r}-1\\-9\\2\end{array}\right).\nonumber \]

Usando la sustitución posterior,

\[\begin{aligned}x_3&=-\frac{1}{2}(2)=-1, \\ x_2&=-\frac{1}{2}(-9-5x_3)=2, \\ x_1&=-\frac{1}{3}(-1-2x_2+x_3)=2,\end{aligned} \nonumber \]

y una vez más hemos determinado

\[\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{r}2\\2\\-1\end{array}\right).\nonumber \]

Al realizar la eliminación gaussiana, recordemos que el elemento diagonal que se utiliza durante el procedimiento de eliminación se llama pivote. Para obtener el múltiplo correcto, se utiliza el pivote como divisor a los elementos debajo del pivote. La eliminación gaussiana en esta forma fallará si el pivote es cero. En este caso, se debe realizar un intercambio de filas.

Incluso si el pivote no es idéntico cero, un valor pequeño puede resultar en un cálculo numérico inestable. Para matrices grandes resueltas por una computadora, se puede perder fácilmente toda la precisión en la solución. Para evitar estos errores de redondeo derivados de pequeños pivotes, se realizan intercambios de filas, y la técnica numérica se denomina pivotamiento parcial. Este método de\(\text{LU}\) descomposición con pivotamiento parcial es el que se suele enseñar en un curso de análisis numérico estándar.