¿Cómo se puede utilizar la factorización de la LU en una matriz no cuadrada?

Question

En mi libro de texto, hay alguna información sobre la factorización de la LU de la matriz cuadrada $A$ pero no sobre la matriz no cuadrada.

¿Cómo se puede utilizar la factorización de la LU para factorizar la matriz no cuadrada?

Answer 1

Voy a ilustrar cómo entender la descomposición LU de un $3 \times 4$ matriz de abajo. El método funciona igual de bien para otros tamaños, ya que la descomposición LU surge naturalmente del estudio de la eliminación gaussiana mediante la multiplicación por matrices elementales.

$$ \begin{array}{ll} A \ = &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 2 & 4 & 0 & 7 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_2-2r_1 \rightarrow r_2} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 0 & 6 & 5 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_3+r_1 \rightarrow r_3} \\ & \\ &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 0 & 6 & 5 \\ 0 & 5 & -1 & 1 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right] = \ U \end{array} $$ Tenemos $U = E_3E_2E_1A$ por lo que $A = E_1^{-1}E_2^{-1}E_3^{-1}U$ y podemos calcular el producto $E_1^{-1}E_2^{-1}E_3^{-1}$ de la siguiente manera: $$ \begin{array}{ll} I \ = &\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right] \ \underrightarrow{r_3-r_1 \rightarrow r_3} \\ & \\ &\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right] \ \underrightarrow{r_2+2r_1 \rightarrow r_2} \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right] = PL \end{array} $$ He insertado un " $P$ " frente a la $L$ ya que la matriz anterior no es triangular inferior. Sin embargo, si vamos un paso más allá y dejamos que $r_2 \leftrightarrow r_3$ entonces obtendremos una matriz triangular inferior: $$ \begin{array}{ll} PL \ = &\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & 0 & 1 \\ \end{array} \right] =L \end{array} $$ Por lo tanto, encontramos que $E_1^{-1}E_2^{-1}E_3^{-1}=PL$ donde $L$ es como la anterior y $P = E_{2 \leftrightarrow 3}$ . Esto significa que $A$ tiene una modificación $LU$ -descomposición. Algunos matemáticos la llaman $PLU$ -descomposición, $$ A = \underbrace{\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right]}_{P} \underbrace{\left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & 0 & 1 \\ \end{array} \right]}_{L}\underbrace{\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right]}_{U} = \underbrace{\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right]}_{PL}\underbrace{\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right]}_{U}. $$ Dado que todas las matrices de permutación satisfacen la condición $P^2=I$ la existencia de un $PLU$ -para $A$ naturalmente sugiere que $PA = LU$ . Por lo tanto, incluso cuando un $LU$ descomposición no está disponible podemos simplemente voltear algunas filas para encontrar un $LU$ -matriz descomponible. Esta es una observación útil porque significa que los hábiles algoritmos desarrollados para $LU$ -se aplican a todas las matrices con un poco más de letra pequeña.

Gran parte de lo escrito anteriormente puede ahorrarse si adoptamos el esquema de notación que se ilustra a continuación. $$ \begin{array}{ll} A \ = &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 2 & 4 & 0 & 7 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_2-2r_1 \rightarrow r_2} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ (2) & 0 & 6 & 5 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_3+r_1 \rightarrow r_3} \\ & \\ &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ (2) & 0 & 6 & 5 \\ (-1) & 5 & -1 & 1 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ (-1) & 5 & -1 & 1 \\ (2) & 0 & 6 & 5 \end{array} \right] = \ U \end{array} $$ Encontramos que si eliminamos las entradas parentéticas de $U$ y uniéndolos a $I$ entonces devuelve la matriz $L$ que encontramos anteriormente: $$ U = \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right] \qquad L=\left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & 0 & 1 \end{array} \right]. $$

Espero que esto ayude.