7: Método de descomposición LU para resolver ecuaciones lineales simultáneas

Objetivos de aprendizaje

Después de completar con éxito esta sección, deberías poder

1. resolver un conjunto de ecuaciones lineales simultáneas usando el método de descomposición LU
2. descomponer una matriz no singular en forma LU.
3. resolver un conjunto de ecuaciones lineales simultáneas usando el método de descomposición LU
4. descomponer una matriz no singular en forma LU.
5. encontrar la inversa de una matriz usando el método de descomposición LU.
6. justificar por qué usar el método de descomposición LU es más eficiente que la eliminación gaussiana en algunos casos.

Escucho sobre la descomposición de LU utilizada como método para resolver un conjunto de ecuaciones lineales simultáneas. ¿Qué es?

Ya se estudiaron dos métodos numéricos para encontrar la solución a ecuaciones lineales simultáneas: la eliminación ingenua de Gauss y la eliminación gaussiana con pivotamiento parcial. Entonces, ¿por qué necesitamos aprender otro método? Para apreciar por qué la descomposición de LU podría ser una mejor opción que las técnicas de eliminación de Gauss en algunos casos, discutamos primero de qué se trata la descomposición de LU.

Para una matriz no singular\(\left\lbrack A \right\rbrack\) en la que uno pueda llevar a cabo con éxito los pasos de eliminación hacia adelante de eliminación ingenua de Gauss, siempre se puede escribir como

\[\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack \nonumber \]

donde

\[\left\lbrack L \right\rbrack = \text{Lower triangular matrix} \nonumber \]

\[\left\lbrack U \right\rbrack = \text{Upper triangular matrix} \nonumber \]

Entonces, si uno está resolviendo un conjunto de ecuaciones

\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack, \nonumber \]

entonces

\[\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\ \text{as }\left( \lbrack A\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack \right) \nonumber \]

Multiplicando ambas partes por\(\left\lbrack L \right\rbrack^{- 1}\),

\[\left\lbrack L \right\rbrack^{- 1}\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack \nonumber \]

\[\left\lbrack I \right\rbrack \left\lbrack U \right\rbrack \left\lbrack X \right\rbrack = \left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack\ \text{as }\left( \left\lbrack L \right\rbrack^{- 1}\left\lbrack L \right\rbrack = \lbrack I\rbrack \right) \nonumber \]

\[\left\lbrack U \right\rbrack \left\lbrack X \right\rbrack = \left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack\ \text{as }\left( \left\lbrack I \right\rbrack\ \left\lbrack U \right\rbrack = \lbrack U\rbrack \right) \nonumber \]

Let

\[\left\lbrack L \right\rbrack^{- 1}\left\lbrack C \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]

entonces

\[\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\ \ \ (1) \nonumber \]

y

\[\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack\ \ \ (2) \nonumber \]

Entonces podemos resolver la Ecuación (1) primero para\(\lbrack Z\rbrack\) usando la sustitución directa y luego usar la Ecuación (2) para calcular el vector de solución\(\left\lbrack X \right\rbrack\) por sustitución inversa.

¿Cómo descompongo una matriz no singular [A], es decir, ¿cómo encuentro [A] = [L] [U]?

Si los pasos de eliminación hacia adelante de los métodos de eliminación de Gauss ingenuos se pueden aplicar en una matriz no singular, entonces se\(\left\lbrack A \right\rbrack\) puede descomponer en LU como

\[\begin{split} \lbrack A\rbrack &= \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 & 0 & \ldots & 0 \\ {l}_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \cdots & \vdots \\ {l}_{n1} & {l}_{n2} & \cdots & 1 \\ \end{bmatrix}\ \ \begin{bmatrix} u_{11} & u_{12} & \ldots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & \cdots & u_{nn} \\ \end{bmatrix} \end{split} \nonumber \]

Los elementos de la\(\left\lbrack U \right\rbrack\) matriz son exactamente los mismos que la matriz de coeficientes que se obtiene al final de los pasos de eliminación hacia adelante en la eliminación de Gauss ingenuos.

La matriz triangular inferior\(\left\lbrack L \right\rbrack\) tiene\(1\) en sus entradas diagonales. Los elementos distintos de cero en los elementos no diagonales en\(\left\lbrack L \right\rbrack\) son multiplicadores que hicieron que las entradas correspondientes fueran cero en la matriz triangular superior\(\left\lbrack U\right\rbrack\) durante la eliminación hacia adelante.

Veamos esto usando el mismo ejemplo que se usó en la eliminación gaussiana ingenua.

Ejemplo\(\PageIndex{1}\)

Encuentra la descomposición LU de la matriz

\[\left\lbrack A \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix} \nonumber \]

Solución

\[\begin{split} \left\lbrack A \right\rbrack &= \left\lbrack L \right\rbrack \left\lbrack U \right\rbrack\\ &= \begin{bmatrix} 1 & 0 & 0 \\ {l}_{21} & 1 & 0 \\ {l}_{31} & {l}_{32} & 1 \\ \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \end{split} \nonumber \]

La\(\left\lbrack U \right\rbrack\) matriz es la misma que se encontró al final de la eliminación hacia adelante del método de eliminación de Gauss ingenuo, es decir

\[\left\lbrack U \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix} \nonumber \]

Para encontrar\({l}_{21}\) y\({l}_{31}\), encontrar el multiplicador que se utilizó para hacer cero\(a_{31}\) los elementos\(a_{21}\) y en el primer paso de la eliminación hacia adelante del método de eliminación ingenua de Gauss. Fue

\[\begin{split} {l}_{21} &= \frac{64}{25}\\ &= 2.56 \end{split} \nonumber \]

\[\begin{split} {l}_{31} &= \frac{144}{25}\\ &= 5.76 \end{split} \nonumber \]

Para encontrar\({l}_{32}\), ¿qué multiplicador se utilizó para hacer\(a_{32}\) el elemento cero? Recuerde\(a_{32}\) elemento se hizo cero en el segundo paso de la eliminación hacia adelante. La\(\left\lbrack A \right\rbrack\) matriz al inicio del segundo paso de la eliminación hacia adelante fue

\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & - 16.8 & - 4.76 \\ \end{bmatrix} \nonumber \]

Entonces

\[\begin{split} {l}_{32} &= \frac{- 16.8}{- 4.8}\\ &= 3.5 \end{split} \nonumber \]

De ahí

\[\left\lbrack L \right\rbrack = \begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix} \nonumber \]

Confirmar\(\left\lbrack L \right\rbrack \left\lbrack U \right\rbrack = \left\lbrack A \right\rbrack\).

\[\begin{split} \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack &= \begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\\ &= \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix} \end{split} \nonumber \]

Ejemplo\(\PageIndex{2}\)

Utilice el método de descomposición LU para resolver las siguientes ecuaciones lineales simultáneas.

\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ 177.2 \\ 279.2 \\ \end{bmatrix} \nonumber \]

Solución

Recordemos que

\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]

y si

\[\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack \nonumber \]

luego primero resolviendo

\[\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]

y luego

\[\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]

da el vector de solución\(\left\lbrack X \right\rbrack\).

Ahora en el ejemplo anterior, mostramos

\[\begin{split} \left\lbrack A \right\rbrack &= \left\lbrack L \right\rbrack \left\lbrack U \right\rbrack\\ &=\begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix} \end{split} \nonumber \]

Primera solución

\[\left\lbrack L \right\rbrack\ \left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]

\[\begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ 177.2 \\ 279.2 \\ \end{bmatrix} \nonumber \]

para dar

\[z_{1} = 106.8 \nonumber \]

\[2.56z_{1} + z_{2} = 177.2 \nonumber \]

\[5.76z_{1} + 3.5z_{2} + z_{3} = 279.2 \nonumber \]

La sustitución hacia delante a partir de la primera ecuación da

\[z_{1} = 106.8 \nonumber \]

\[\begin{split} z_{2} &= 177.2 - 2.56z_{1}\\ &= 177.2 - 2.56 \times 106.8\\ &= - 96.208 \end{split} \nonumber \]

\[\begin{split} z_{3} &= 279.2 - 5.76z_{1} - 3.5z_{2}\\ &= 279.2 - 5.76 \times 106.8 - 3.5 \times \left( - 96.208 \right)\\ &= 0.76 \end{split} \nonumber \]

De ahí

\[\begin{split} \left\lbrack Z \right\rbrack &= \begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 106.8 \\ - 96.208 \\ 0.76 \\ \end{bmatrix} \end{split} \nonumber \]

Esta matriz es la misma que la del lado derecho obtenida al final de los pasos de eliminación hacia adelante del método de eliminación de Gauss ingenuo. ¿Es esto una coincidencia?

Ahora soluciona

\[\left\lbrack U \right\rbrack \left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]

\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ - 96.208 \\ 0.76 \\ \end{bmatrix} \nonumber \]

\[25a_{1} + 5a_{2} + a_{3} = 106.8 \nonumber \]

\[- 4.8a_{2} - 1.56a_{3} = - 96.208 \nonumber \]

\[0.7a_{3} = 0.76 \nonumber \]

A partir de la tercera ecuación

\[0.7a_{3} = 0.76 \nonumber \]

\[\begin{split} a_{3} &= \frac{0.76}{0.7}\\ &= 1.0857\end{split} \nonumber \]

Sustituyendo el valor de\(a_{3}\) en la segunda ecuación,

\[- 4.8a_{2} - 1.56a_{3} = - 96.208 \nonumber \]

\[\begin{split} a_{2} &= \frac{- 96.208 + 1.56a_{3}}{- 4.8}\\ &= \frac{- 96.208 + 1.56 \times 1.0857}{- 4.8}\\ &= 19.691 \end{split} \nonumber \]

Sustituyendo el valor de\(a_{2}\) y\(a_{3}\) en la primera ecuación,

\[25a_{1} + 5a_{2} + a_{3} = 106.8 \nonumber \]

\[\begin{split} a_{1} &= \frac{106.8 - 5a_{2} - a_{3}}{25}\\ &= \frac{106.8 - 5 \times 19.691 - 1.0857}{25}\\ &= 0.29048 \end{split} \nonumber \]

Por lo tanto, el vector de solución es

\[\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.29048 \\ 19.691 \\ 1.0857 \\ \end{bmatrix} \nonumber \]

¿Cómo encuentro la inversa de una matriz cuadrada usando descomposición LU?

Una matriz\(\left\lbrack B \right\rbrack\) es la inversa de\(\left\lbrack A \right\rbrack\) si

\[\left\lbrack A \right\rbrack\left\lbrack B \right\rbrack = \left\lbrack I \right\rbrack = \left\lbrack B \right\rbrack\left\lbrack A \right\rbrack \nonumber \]

¿Cómo podemos usar la descomposición de LU para encontrar la inversa de la matriz? Supongamos que la primera columna de\(\left\lbrack B \right\rbrack\) (la inversa de\(\left\lbrack A \right\rbrack\)) es

\[\lbrack b_{11}\ b_{12}\ldots\ \ldots b_{n1}\rbrack^{T} \nonumber \]

Luego de la definición anterior de una inversa y la definición de multiplicación matricial

\[\left\lbrack A \right\rbrack\begin{bmatrix} b_{11} \\ b_{21} \\ \vdots \\ b_{n1} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} \nonumber \]

De igual manera, la segunda columna de\(\left\lbrack B \right\rbrack\) viene dada por

\[\left\lbrack A \right\rbrack\begin{bmatrix} b_{12} \\ b_{22} \\ \vdots \\ b_{n2} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \\ \end{bmatrix} \nonumber \]

De igual manera, todas las columnas de se\(\left\lbrack B \right\rbrack\) pueden encontrar resolviendo\(n\) diferentes conjuntos de ecuaciones siendo la columna del lado derecho las\(n\) columnas de la matriz de identidad.

Ejemplo\(\PageIndex{3}\)

Utilice la descomposición de LU para encontrar la inversa de

\[\left\lbrack A \right\rbrack = \begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix} \nonumber \]

Solución

Sabiendo que

\[\begin{split} \left\lbrack A \right\rbrack &= \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\\ &= \begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix} \end{split} \nonumber \]

Podemos resolver para la primera columna de\(\lbrack B\rbrack = \left\lbrack A \right\rbrack^{- 1}\) resolviendo para

\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix} \nonumber \]

Primera solución

\[\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack, \nonumber \]

es decir

\[\begin{bmatrix} 1 & 0 & 0 \\ 2.56 & 1 & 0 \\ 5.76 & 3.5 & 1 \\ \end{bmatrix}\begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix} \nonumber \]

para dar

\[z_{1} = 1 \nonumber \]

\[2.56z_{1} + z_{2} = 0 \nonumber \]

\[5.76z_{1} + 3.5z_{2} + z_{3} = 0 \nonumber \]

La sustitución hacia delante a partir de la primera ecuación da

\[z_{1} = 1 \nonumber \]

\[\begin{split} z_{2} &= 0 - 2.56z_{1}\\ &= 0 - 2.56\left( 1 \right)\\ &= - 2.56 \end{split} \nonumber \]

\[\begin{split} z_{3} &= 0 - 5.76z_{1} - 3.5z_{2}\\ &= 0 - 5.76\left( 1 \right) - 3.5\left( - 2.56 \right)\\ &= 3.2 \end{split} \nonumber \]

De ahí

\[\begin{split} \left\lbrack Z \right\rbrack &= \begin{bmatrix} z_{1} \\ z_{2} \\ z_{3} \\ \end{bmatrix}\\ &= \begin{bmatrix} 1 \\ - 2.56 \\ 3.2 \\ \end{bmatrix} \end{split} \nonumber \]

Ahora soluciona

\[\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack \nonumber \]

es decir

\[\begin{bmatrix} 25 & 5 & 1 \\ 0 & - 4.8 & - 1.56 \\ 0 & 0 & 0.7 \\ \end{bmatrix}\begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ - 2.56 \\ 3.2 \\ \end{bmatrix} \nonumber \]

\[25b_{11} + 5b_{21} + b_{31} = 1 \nonumber \]

\[- 4.8b_{21} - 1.56b_{31} = - 2.56 \nonumber \]

\[0.7b_{31} = 3.2 \nonumber \]

La sustitución hacia atrás a partir de la tercera ecuación da

\[\begin{split} b_{31} &= \frac{3.2}{0.7}\\ &= 4.571 \end{split} \nonumber \]

\[\begin{split} b_{21} &= \frac{- 2.56 + 1.56b_{31}}{- 4.8}\\ &= \frac{- 2.56 + 1.56(4.571)}{- 4.8}\\ &= - 0.9524 \end{split} \nonumber \]

\[\begin{split} b_{11} &= \frac{1 - 5b_{21} - b_{31}}{25}\\ &= \frac{1 - 5( - 0.9524) - 4.571}{25}\\ &= 0.04762 \end{split} \nonumber \]

De ahí que la primera columna de la inversa de\(\left\lbrack A \right\rbrack\) es

\[\begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ \end{bmatrix} = \begin{bmatrix} 0.04762 \\ - 0.9524 \\ 4.571 \\ \end{bmatrix} \nonumber \]

Del mismo modo, resolviendo

\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} b_{12} \\ b_{22} \\ b_{32} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ \end{bmatrix}\ \text{gives }\begin{bmatrix} b_{12} \\ b_{22} \\ b_{32} \\ \end{bmatrix} = \begin{bmatrix} - 0.08333 \\ 1.417 \\ - 5.000 \\ \end{bmatrix} \nonumber \]

y resolviendo

\[\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} b_{13} \\ b_{23} \\ b_{33} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ \end{bmatrix}\ \text{gives }\begin{bmatrix} b_{13} \\ b_{23} \\ b_{33} \\ \end{bmatrix} = \begin{bmatrix} 0.03571 \\ - 0.4643 \\ 1.429 \\ \end{bmatrix} \nonumber \]

De ahí

\[\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} 0.04762 & - 0.08333 & 0.03571 \\ - 0.9524 & 1.417 & - 0.4643 \\ 4.571 & - 5.000 & 1.429 \\ \end{bmatrix} \nonumber \]

¿Se puede confirmar lo siguiente para el ejemplo anterior?

\[\left\lbrack A \right\rbrack\ \left\lbrack A \right\rbrack^{- 1} = \left\lbrack I \right\rbrack = \left\lbrack A \right\rbrack^{- 1}\left\lbrack A \right\rbrack \nonumber \]

La descomposición de LU parece más complicada que la eliminación gaussiana. ¿Utilizamos la descomposición de LU porque es computacionalmente más eficiente que la eliminación gaussiana para resolver un conjunto de n ecuaciones dadas por\(\mathbf{[A][X]=[C]}\)?

Para una matriz cuadrada\(\lbrack A\rbrack\) de\(n \times n\) tamaño, el tiempo computacional [^1]\(CT|_{DE}\) para descomponer la\(\lbrack A\rbrack\) matriz a\(\lbrack L\rbrack\lbrack U\rbrack\) formar viene dado por

\[CT|_{DE} = T\left( \frac{8n^{3}}{3} + 4n^{2} - \frac{20n}{3} \right), \nonumber \]

donde

\[T = \text{clock cycle time}^{2} \nonumber \]

El tiempo computacional\(CT|_{FS}\) para resolver por sustitución directa\(\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\) viene dado por

\[CT|_{FS} = T\left( 4n^{2} - 4n \right) \nonumber \]

El tiempo computacional\(CT|_{BS}\) para resolver por retrosustitución\(\left\lbrack U \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack Z \right\rbrack\) viene dado por

\[CT|_{BS} = T\left( 4n^{2} + 12n \right) \nonumber \]

Entonces, el tiempo computacional total para resolver un conjunto de ecuaciones por descomposición de LU es

\[\begin{split} {CT|}_{LU} &= {CT|}_{DE} + {CT|}_{FS} + {CT|}_{BS}\\ &= T\left( \frac{8n^{3}}{3} + 4n^{2} - \frac{20n}{3} \right) + T\left( 4n^{2} - 4n \right) + T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{8n^{3}}{3} + 12n^{2} + \frac{4n}{3} \right) \end{split} \nonumber \]

Ahora veamos el tiempo computacional que lleva la eliminación gaussiana. El tiempo computacional\(CT|_{FE}\) para la parte de eliminación hacia adelante,

\[{CT|}_{FE} = T\left( \frac{8n^{3}}{3} + 8n^{2} - \frac{32n}{3} \right), \nonumber \]

y el tiempo computacional\(CT|_{BS}\) para la parte de sustitución posterior es

\[{CT|}_{BS} = T\left( 4n^{2} + 12n \right) \nonumber \]

Entonces, el tiempo computacional total\(CT|_{GE}\) para resolver un conjunto de ecuaciones por Eliminación Gaussiana es

\[\begin{split} {CT|}_{GE} &= {CT|}_{FE} + {CT|}_{BS}\\ &= T\left( \frac{8n^{3}}{3} + 8n^{2} - \frac{32n}{3} \right) + T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{8n^{3}}{3} + 12n^{2} + \frac{4n}{3} \right) \end{split} \nonumber \]

El tiempo computacional para la eliminación gaussiana y la descomposición de LU es idéntico.

¡Esto me ha confundido aún más! ¿Por qué debería aprender el método de descomposición LU cuando toma el mismo tiempo computacional que la eliminación gaussiana, y eso también cuando los dos métodos están estrechamente relacionados? ¡Por favor, convencerme de que la descomposición de LU tiene su lugar en la resolución

Ahora tenemos el conocimiento para convencerte de que el método de descomposición LU tiene su lugar en la solución de ecuaciones lineales simultáneas. Veamos un ejemplo donde el método de descomposición de LU es computacionalmente más eficiente que la eliminación gaussiana. Recuerde que al tratar de encontrar la inversa de la matriz\(\lbrack A\rbrack\) en el Capítulo 04.01, el problema se reduce a resolver\(n\) conjuntos de ecuaciones con las\(n\) columnas de la matriz de identidad como el vector RHS. Para los cálculos de cada columna de la inversa de la\(\lbrack A\rbrack\) matriz, la\(\lbrack A\rbrack\) matriz de coeficientes en el conjunto de ecuaciones\(\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\) no cambia. Entonces, si usamos el método de descomposición LU, la\(\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) descomposición necesita hacerse solo una vez, la sustitución hacia adelante (Ecuación 1)\(n\) veces, y la sustitución posterior (Ecuación 2)\(n\) veces.

Por lo tanto, el tiempo computacional total\(CT|_{inverse\ {LU}}\) requerido para encontrar la inversa de una matriz usando descomposición de LU es

\[\begin{split} {CT|}_{inverse\ {LU}} &= 1 \times {CT|}_{DE} + n \times {CT|}_{FS} + n \times {CT|}_{BS}\\ &= 1 \times T\left( \frac{8n^{3}}{3} + 4n^{2} - \frac{20n}{3} \right) + n \times T\left( 4n^{2} - 4n \right) + n \times T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{32n^{3}}{3} + 12n^{2} - \frac{20n}{3} \right) \end{split} \nonumber \]

En comparación, si se utilizó el método de eliminación gaussiana para encontrar la inversa de una matriz, la eliminación hacia adelante así como la sustitución posterior tendrán que hacerse n veces. El tiempo computacional total\({CT|}_{inverse\ {GE}}\) requerido para encontrar la inversa de una matriz mediante el uso de la eliminación gaussiana entonces es

\[\begin{split} {CT|}_{inverse\ {GE}} &= n \times {CT|}_{FE} + n \times {CT|}_{BS}\\ &= n \times T\left( \frac{8n^{3}}{3} + 8n^{2} - \frac{32n}{3} \right) + n \times T\left( 4n^{2} + 12n \right)\\ &= T\left( \frac{8n^{4}}{3} + 12n^{3} + \frac{4n^{2}}{3} \right) \end{split} \nonumber \]

Claramente para grandes\(n\), al\({CT|}_{inverse\ {GE}} >>{CT|}_{inverse\ {LU}}\) igual\({CT|}_{inverse\ {GE}}\) que los términos dominantes de\(n^{4}\) y\({CT|}_{inverse\ {LU}}\) tiene los términos dominantes de\(n^{3}\). Para grandes valores de\(n\), El método de eliminación gaussiana tomaría más tiempo computacional (aproximadamente\(n/4\) veces, probarlo) que el método de descomposición de LU. Los valores típicos de la relación del tiempo computacional para diferentes valores de\(n\) se dan en la Tabla 1.

Cuadro 1. Comparar tiempos computacionales de hallazgo inverso de una matriz usando descomposición de LU y eliminación gaussiana.

\(n\)	\(10\)	\(100\)	\(1000\)	\(10000\)
\ (n\) ">\({CT|}_{inverse\ {GE}}/{CT|}_{inverse\ {LU}}\)	\ (10\) ">\(3.28\)	\ (100\) ">\(25.83\)	\ (1000\) ">\(250.8\)	\ (10000\) ">\(2501\)

¿Estás convencido ahora de que la descomposición de LU tiene su lugar en la resolución de sistemas de ecuaciones cuando tenemos que resolver múltiples vectores del lado derecho mientras la matriz de coeficientes permanece sin cambios?

El tiempo se calcula calculando primero por separado el número de sumas, restas, multiplicaciones y divisiones en un procedimiento como la sustitución inversa, etc. Luego asumimos 4 ciclos de reloj cada uno para una operación de suma, resta o multiplicación, y 16 ciclos de reloj para una operación de división como es el caso para un chip AMD® -K7 típico.
http://www.isi.edu/~draper/papers/mwscas07_kwon.pdf

Método de descomposición de LU para resolver ecuaciones lineales simultáneas

Quiz 1

El método de\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) descomposición es computacionalmente más eficiente que la eliminación de Gauss ingenua para resolver

(A). un solo conjunto de ecuaciones lineales simultáneas.

(B). múltiples conjuntos de ecuaciones lineales simultáneas con diferentes matrices de coeficientes y los mismos vectores del lado derecho.

(C). múltiples conjuntos de ecuaciones lineales simultáneas con la misma matriz de coeficientes y diferentes vectores del lado derecho.

(D). menos de diez ecuaciones lineales simultáneas.

Quiz 2

La matriz triangular inferior\(\left\lbrack L \right\rbrack\) en la\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) descomposición de la matriz dada a continuación

\[\begin{bmatrix} 25 & 5 & 4 \\ 10 & 8 & 16 \\ 8 & 12 & 22 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \mathcal{l}_{21} & 1 & 0 \\ \mathcal{l}_{31} & \mathcal{l}_{32} & 1 \\ \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \nonumber \]es

(A)\(\begin{bmatrix} 1 & 0 & 0 \\ 0.40000 & 1 & 0 \\ 0.32000 & 1.7333 & 1 \\ \end{bmatrix}\)

(B)\(\begin{bmatrix} 25 & 5 & 4 \\ 0 & 6 & 14.400 \\ 0 & 0 & - 4.2400 \\ \end{bmatrix}\)

(C)\(\begin{bmatrix} 1 & 0 & 0 \\ 10 & 1 & 0 \\ 8 & 12 & 0 \\ \end{bmatrix}\)

(D)\(\begin{bmatrix} 1 & 0 & 0 \\ 0.40000 & 1 & 0 \\ 0.32000 & 1.5000 & 1 \\ \end{bmatrix}\)

Quiz 3

La matriz triangular superior\(\left\lbrack U \right\rbrack\) en la\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) descomposición de la matriz dada a continuación

\[\begin{bmatrix} 25 & 5 & 4 \\ 0 & 8 & 16 \\ 0 & 12 & 22 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \mathcal{l}_{21} & 1 & 0 \\ \mathcal{l}_{31} & \mathcal{l}_{32} & 1 \\ \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \nonumber \]

es

(A)\(\begin{bmatrix} 1 & 0 & 0 \\ 0.40000 & 1 & 0 \\ 0.32000 & 1.7333 & 1 \\ \end{bmatrix}\)

(B)\(\begin{bmatrix} 25 & 5 & 4 \\ 0 & 6 & 14.400 \\ 0 & 0 & - 4.2400 \\ \end{bmatrix}\)

(C)\(\begin{bmatrix} 25 & 5 & 4 \\ 0 & 8 & 16 \\ 0 & 0 & - 2 \\ \end{bmatrix}\)

(D)\(\begin{bmatrix} 1 & 0.2000 & 0.16000 \\ 0 & 1 & 2.4000 \\ 0 & 0 & - 4.240 \\ > \end{bmatrix}\)

Quiz 4

Para una matriz dada de\(\times\) 2000 2000\(\left\lbrack A \right\rbrack\), supongamos que se tarda unos 15 segundos en encontrar la inversa de\(\left\lbrack A \right\rbrack\) mediante el uso del método de\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) descomposición, es decir, encontrar el\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) once, y luego hacer la sustitución directa y\(2000\) tiempos de sustitución inversa usando las\(2000\) columnas de la matriz de identidad como vector del lado derecho. El tiempo aproximado, en segundos, que tardará en encontrar lo inverso si se encuentra mediante el uso repetido del método de eliminación Naive Gauss, es decir, haciendo\(2000\) tiempos de eliminación hacia adelante y sustitución hacia atrás usando las\(2000\) columnas de la matriz de identidad como la mano derecha vector lateral es más cercano

(A)\(300\)

(B)\(1500\)

(C)\(7500\)

(D)\(30000\)

Quiz 5

El algoritmo para resolver un conjunto de\(n\) ecuaciones\(\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack\), donde\(\left\lbrack A \right\rbrack = \left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) implica resolver\(\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\) por sustitución directa. El algoritmo a resolver\(\left\lbrack L \right\rbrack\left\lbrack Z \right\rbrack = \left\lbrack C \right\rbrack\) viene dado por

(A)\(z_{1} = c_{1}/l_{11}\)

para\(i\) de 2 a\(n\) hacer

suma = 0

para\(j\) de 1 a\(i\) hacer

suma = suma +\(l_{\text{ij}}*z_{j}\)

terminar hacer

\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)

terminar hacer

(B)\(z_{1} = c_{1}/l_{11}\)

para\(i\) de 2 a\(n\) hacer

suma = 0

para\(j\) de 1 a\((i - 1)\) hacer

suma = suma +\(l_{\text{ij}}*z_{j}\)

terminar hacer

\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)

terminar hacer

(C)\(z_{1} = c_{1}/l_{11}\)

para\(i\) de 2 a\(n\) hacer

para\(j\) de 1 a\((i - 1)\) hacer

suma = suma +\(l_{\text{ij}}*z_{j}\)

terminar hacer

\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)

terminar hacer

(D) para\(i\) de 2 a\(n\) hacer

suma = 0

para\(j\) de 1 a\((i - 1)\) hacer

suma = suma +\(l_{\text{ij}}*z_{j}\)

terminar hacer

\(z_{i} = (c_{i} - \text{sum})/l_{\text{ii}}\)

terminar hacer

Quiz 6

Para resolver problemas de valor límite, se utiliza un método numérico basado en el método de diferencia finita. Esto da como resultado ecuaciones lineales simultáneas con matrices de coeficientes tridiagonales. Estos se resuelven mediante un método de\(\left\lbrack L \right\rbrack\left\lbrack U \right\rbrack\) descomposición especializado.

Elija el conjunto de ecuaciones que resuelva aproximadamente el problema del valor límite

\[\frac{d^{2}y}{dx^{2}} = 6x - 0.5x^{2},\ \ y\left( 0 \right) = 0,\ \ y\left( 12 \right) = 0,\ \ 0 \leq x \leq 12 \nonumber \]

La segunda derivada de la ecuación anterior se aproxima mediante la aproximación exacta de diferencia dividida central de segundo orden según se aprendió en el módulo de diferenciación (Capítulo 02.02). \(h = 4\)Se utiliza un tamaño de paso de, y por lo tanto el valor de y se puede encontrar aproximadamente en equidistantemente colocados 4 nodos entre\(x = 0\) y\(x = 12\).

(A)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.0625 & 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & 0.125 & 0.0625 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 16.0 \\ 16.0 \\ 0 \\ \end{bmatrix}\)

(B)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.0625 & - 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & - 0.125 & 0.0625 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 16.0 \\ 16.0 \\ 0 \\ \end{bmatrix}\)

(C)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0.0625 & - 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & - 0.125 & 0.0625 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 16.0 \\ 16.0 \\ 0 \\ \end{bmatrix}\)

(D)\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0.0625 & 0.125 & 0.0625 & 0 \\ 0 & 0.0625 & 0.125 & 0.0625 \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 16.0 \\ 16.0 \\ \end{bmatrix}\)

Método de descomposición LU para resolver ecuaciones lineales simultáneas ejercicio

Ejercicio 1

Mostrar que la descomposición de LU es computacionalmente una forma más eficiente de encontrar la inversa de una matriz cuadrada que usando la eliminación gaussiana.

Ejercicio 2

Utilice la descomposición de LU para encontrar [L] y [U]

\[4x_{1} + x_{2} - x_{3} = - 2 \nonumber \]\[5x_{1} + x_{2} + 2x_{3} = 4 \nonumber \]\[6x_{1} + x_{2} + x_{3} = 6 \nonumber \]

Ejercicio 3

Encuentra la inversa

\[\lbrack A\rbrack = \begin{bmatrix} 3 & 4 & 1 \\ 2 & - 7 & - 1 \\ 8 & 1 & 5 \\ \end{bmatrix} \nonumber \]

usando descomposición de LU.

Ejercicio 4

Rellene los espacios en blanco para las incógnitas en la descomposición LU de la matriz que se indica a continuación

\[\begin{bmatrix} 25 & 5 & 4 \\ 75 & 7 & 16 \\ 12.5 & 12 & 22 \\ \end{bmatrix} = \begin{bmatrix} \mathcal{l}_{11} & 0 & 0 \\ \mathcal{l}_{21} & \mathcal{l}_{22} & 0 \\ \mathcal{l}_{31} & \mathcal{l}_{32} & \mathcal{l}_{33} \\ \end{bmatrix}\begin{bmatrix} 25 & 5 & 4 \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix} \nonumber \]

Ejercicio 5

Mostrar que la matriz no singular

\[\left\lbrack A \right\rbrack = \begin{bmatrix} 0 & 2 \\ 2 & 0 \\ \end{bmatrix} \nonumber \]

no se puede descomponer en forma LU.

Ejercicio 6

La descomposición de LU de

\[\lbrack A\rbrack = \begin{bmatrix} 4 & 1 & - 1 \\ 5 & 1 & 2 \\ 6 & 1 & 1 \\ \end{bmatrix} \nonumber \]

está dado por

\[\begin{bmatrix} 4 & 1 & - 1 \\ 5 & 1 & 2 \\ 6 & 1 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 1.25 & 1 & 0 \\ 1.5 & 2 & 1 \\ \end{bmatrix}\begin{bmatrix} ?? & ?? & ?? \\ 0 & ?? & ?? \\ 0 & 0 & ?? \\ \end{bmatrix} \nonumber \]

¿Encuentra la matriz triangular superior en la descomposición anterior?