Descomposición LU; ¿conmutan las matrices de permutación?

Question

Tengo una tarea para mi clase de Métodos Numéricos de escribir una función que encuentre la PA=LU para una matriz A dada y que devuelva P, L y U.

Olvídate de los problemas de codificación por un momento; hay un problema matemático importante que estoy teniendo y que mi profesor parece incapaz de abordar, y después de buscar durante horas (tal vez ineficientemente) no pude encontrar ninguna explicación al respecto. ¿Cómo podemos separar las matrices de permutación de las matrices de eliminación de filas?

Básicamente la idea, si lo entiendo bien, es que realicemos una serie de transformaciones sobre una matriz $A$ aplicando sucesivas matrices triangulares inferiores que eliminan elementos individuales, así $L_nL_{n-1}...L_2L_1A = U$ . A mi entender, esto es útil desde el punto de vista computacional porque las matrices atómicas triangulares inferiores pueden invertirse cambiando el signo del elemento no diagonal, de modo que $A = L_1^{-1}L_2^{-1}...U$ .

Todo eso está muy bien (suponiendo que esté en lo cierto), pero la introducción de matrices de pivote entre cada $L_j$ parece hacer que el problema sea intratable. En todas las contabilidades que he visto se produce alguna brujería que se parece a esta: $$L_nP_nL_{n-1}...P_3L_2P_2L_1P_1A = U \Rightarrow P_nP_{n-1}...P_2P_1L_nL_{n-1}...L_2L_1A = U$$

Y nadie se molesta en explicar cómo sucede esto o, de hecho, ni siquiera lo declara explícitamente.

Si es posible, me gustaría saber
a) ¿Es aceptable desde el punto de vista operativo?

b) ¿Qué propiedades de estas respectivas clases de matrices hacen que este tipo de conmutación sea legal?

c) ¿Es correcta mi comprensión del método y sus ventajas?

Answer 1

No, en general las matrices de permutación no conmutan.

Parece que está utilizando el Algoritmo Doolittle Así que voy a suponer que, efectivamente, lo eres.

Dejemos que $U_i$ sea el $i$ :ª etapa en su descomposición LU de $A$ Así que $$\begin{align} U_0 &= A \\ U_1 &= L_1P_1U_0 \\ \vdots \\ U_n &= L_nP_nU_{n-1} \end{align}$$

Esto se corresponde con la forma en que se haría la descomposición LU a mano; se obtiene el elemento más grande como elemento principal de la fila en la que se está (es decir, se multiplica con $P_k$ ), entonces se elimina esa columna en las filas siguientes (es decir, se multiplica con $L_k$ ).

Como usted señala, el $L_i$ serán matrices atómicas triangulares inferiores, estando todos los elementos no nulos en la columna $i$ . La inversa de $L_i$ se puede construir negando todos los elementos no diagonales, ver Wikipedia .

La matriz de permutación $P_j$ será una matriz de permutación de fila $j$ con una fila $k \geq j$ si se multiplica por la izquierda de la matriz que se quiere transformar. La inversa de $P_j$ es $P_j$ mismo (ya que $P_j$ fila de interruptores $j$ con la fila $k$ , puede deshacerlo haciendo lo mismo).

Considere el producto $P_jL_i$ para $i < j$ . $P_j$ cambiará dos filas de $L_i$ , fila $j$ y $k \geq j > i$ . Cambiamos los elementos en $L_i$ de la siguiente manera: $$\begin{align} L_{j,i} &\leftrightarrow L_{k,i} \\ L_{j,j} &\leftrightarrow L_{k,j} \end{align}$$ Dejemos que $L_k'$ sea la matriz producida al cambiar sólo los elementos no diagonales (el primer cambio anterior). Obsérvese que sigue siendo una matriz atómica triangular inferior. Entonces podemos producir $P_jL_i$ simplemente cambiando columna $j$ con columna $k$ en $L_k'$ , que se multiplica por $P_j$ en el a la derecha . Aquí es importante que $i < j, k$ , por lo que la columna $i$ en $L_i'$ ¡no se cambia! En otras palabras: $$P_j L_i = L_i' P_j$$

Por lo tanto, puede a partir de su ecuación $$L_nP_nL_{n-1}...P_3L_2P_2L_1P_1A = U$$ producir $$L_n^S L_{n-1}^S \cdots L_1^S P_n P_{n-1} \cdots P_1A = U$$ que puede transformarse en (nótese que $L_i^S$ sigue siendo triangular inferior atómico): $$PA = LU$$ tomando $$P = P_nP_{n-1} \cdots P_1$$ y $$L = (L_n^S L_{n-1}^S \cdots L_1^S)^{-1}.$$

Aquí, $L_i^S$ es la matriz hecha tomando $L_i$ y aplicando todos los $P_j$ (a la izquierda) para $j > i$ en el elementos no diagonales .

Para ello, hay que hacer lo siguiente, empezando por $$L_nP_nL_{n-1}...P_3L_2P_2L_1P_1A = U$$ mover el $P_2$ matriz a la derecha utilizando $P_2L_1 = L_1' P_2$ produciendo: $$L_nP_nL_{n-1}...P_3L_2L_1'P_2P_1A = U$$ y luego hacer lo mismo para la matriz $P_3$ pero esta matriz tiene que moverse a la derecha dos veces, usando $P_3L_2 = L_2'P_3$ y $P_3L_1' = L_1''P_3$ : $$L_nP_nL_{n-1}...L_2'L_1''P_3P_2P_1A = U$$ y así sucesivamente para cada $P_j$ .

Como ejemplo de $P_j L_i = L_i' P_j$ considere $$P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$ $$L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 0 & 1 \end{pmatrix}$$ $$L' = \begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix}$$

$$PL = \begin{pmatrix} 1 & 0 & 0 \\ 3 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix}$$ $$L'P = \begin{pmatrix}1 & 0 & 0 \\ 3 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix}$$

Así que, para resumir: Estas matrices especiales casi de la UE, sólo se necesitan pequeños cambios para intercambiar las matrices. Sin embargo, todas las propiedades importantes de las matrices se conservan al intercambiarlas.

Answer 2

He encontrado una respuesta basada en el álgebra matricial en lugar de los componentes aquí . Aquí está mi intento de reproducirlo con algo más de detalle.

A partir de $$L_3 P_3 L_2 P_2 L_1 P_1 A = U$$ Definir $$\Lambda_1 = P_3 P_2 L_1 P_2^{-1} P_3^{-1}$$ $$\Lambda_2 = P_3 L_2 P_3^{-1}$$ $$\Lambda_3 = L_3$$

Calculando $$\Lambda_3 \Lambda_2 \Lambda_1 P_3 P_2 P_1 = (L_3)(P_3 L_2 P_3^{-1})(P_3 P_2 L_1 P_2^{-1} P_3^{-1}) P_3 P_2 P_1 = L_3 P_3 L_2 P_2 L_1 P_1$$ Podemos cambiar esto en nuestra fórmula inicial para obtener $$\Lambda_3 \Lambda_2 \Lambda_1 P_3 P_2 P_1 A = U$$ Y dejar que $\Lambda = \Lambda_1^{-1} \Lambda_2^{-1} \Lambda_3^{-1}$ y $P = P_3 P_2 P_1$ tenemos $P A = \Lambda U$ .

Ahora queda por demostrar que el $\Lambda_i$ son triangulares inferiores y para responder de frente a tu pregunta sobre los desplazamientos. Observe que el $P_i$ sólo afectan a las filas $i$ y abajo porque el algoritmo de eliminación ha completado su trabajo con las filas de arriba $i$ . Los inversos de la $P_i$ por lo tanto, sólo tendrá que afectar a esas filas para descifrar las cosas. Examinar $\Lambda_1 = P_3 P_2 L_1 P_2^{-1} P_3^{-1}$ vemos que $\Lambda_1$ intercambia alrededor de las filas 2 y siguientes, aplica $L_1$ para añadir los múltiplos de la primera fila a esas filas inferiores, y luego desinstalar las filas. Esto equivale a añadir los múltiplos adecuados de $L_1$ a las filas originales no intercambiadas, lo que sabemos que es una operación descrita por una matriz triangular inferior. Por lo tanto, la matriz $\Lambda_1$ que representa la operación agregada $P_3 P_2 L_1 P_2^{-1} P_3^{-1}$ debe ser triangular inferior.

En resumen, las matrices no conmutan como habías pedido en tu pregunta original, pero podemos cambiar un $L_i$ en un vector relacionado $\Lambda_i$ mediante la multiplicación por la izquierda y por la derecha de algunas matrices de permutación. Como la conmutación falla, nuestra fórmula para $\Lambda$ no es especialmente bonito: $$\Lambda = P_3 P_2 L_1^{-1} P_2^{-1} L_2^{-1} P_3^{-1} L_3^{-1}$$ Sin embargo, podemos obtener una conclusión más clara si volvemos a $$L_3 P_3 L_2 P_2 L_1 P_1 A = U$$ y que $$M = L_3 P_3 L_2 P_2 L_1 P_1$$ para que $M A = U$ . Entonces, porque $P A = \Lambda U$ debemos tener $P = \Lambda M$ o $\Lambda = P M^{-1}$ . Así que podemos calcular $\Lambda$ de nuestro original $M$ simplemente aplicando la composición de nuestras permutaciones a $M^{-1}$ que no es tan bueno como ir al trabajo, pero tampoco está mal.

Answer 3

$\require{color}$

La explicación de @Calle me parece interesante pero me cuesta seguir los argumentos. La explicación de @kuzooroo se ajusta mejor a mi forma de pensar pero los argumentos son demasiado densos. He decidido empezar una nueva respuesta ya que mis argumentos no caben en un espacio para comentarios.

Siguiendo a @Calle: Tenga en cuenta que, dado que cada $P_i$ es una permutación de un ciclo (un intercambio), $P_i^{-1}=P_i$ ya que al hacer un intercambio dos veces la matriz vuelve a tener la misma forma original. Ahora debemos demostrar que $\Lambda$ es una matriz triangular inferior con unos en la diagonal.

$\Lambda_3$ es, por supuesto, un triángulo inferior con 1 en la diagonal. Para demostrar que $\Lambda_2$ es triangular inferior con unos en la diagonal tenemos en cuenta el hecho de que $L_2$ es atómico. Es decir,

\begin{eqnarray*} L_2 = $$\begin{pmatrix} 1 & 0 & \cdots & 0 & \cdots & \cdots &\cdots & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & \cdots &\cdots & \cdots & 0 \\ \vdots & l_{32} & \ddots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots\\ \vdots & \vdots & \cdots & 1 & 0 & \cdots &\cdots& \cdots & \vdots \\ \vdots & l_{i2} & \cdots & 0 & 1 & 0 &\cdots & \cdots & \vdots \\ \vdots & \vdots & \cdots & \vdots & \ddots & \ddots & \ddots & \cdots & \vdots \\ \vdots & l_{k2} & \vdots & \vdots & \vdots & 0 & 1 & 0 & \vdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots & 0 \\ 0 & 0 & \cdots & 0 & \cdots & \cdots &\cdots & 0 & 1 \end{pmatrix}$$ \N - No hay número. \N - Fin.

Supongamos que $P_3$ filas de intercambios $i$ con $k$ . (nótese que ambos $i$ y $k$ son mayores que 2). Tenemos que

\begin{eqnarray*} P_3 L_2 = $$\begin{pmatrix} 1 & 0 & \cdots & 0 & \cdots & \cdots &\cdots & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & \cdots &\cdots & \cdots & 0 \\ \vdots & l_{32} & \ddots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots\\ \vdots & \vdots & \cdots & 1 & 0 & \cdots &\cdots& \cdots & \vdots \\ \vdots & \boxed{l_{k2}} & \vdots & \vdots & \textcolor{green}{0} & 0 & \textcolor{blue}{1} & 0 & \vdots \\ \vdots & \vdots & \cdots & \vdots & \ddots & \ddots & \ddots & \cdots & \vdots \\ \vdots & \boxed{l_{i2}} & \cdots & 0 & \textcolor{green}{1} & 0 & \textcolor{blue}{0} & \cdots & \vdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots & 0 \\ 0 & 0 & \cdots & 0 & \cdots & \cdots &\cdots & 0 & 1 \end{pmatrix}$$ \N - No hay número. \N - Fin.

Finalmente $P_3 L_2 P_3^{-1}= P_3 L_2 P_3$ inetercambios columnas $i$ (verde) con $k$ (azul) en $P_3 L_2$ . El $1$ en la columna $k$ (azul) ocupa el lugar del 0 en la columna $i$ (verde) . Del mismo modo, el $1$ en verde en la fila $k$ toma la posición del azul $0$ en la misma fila.

Es decir

\begin{eqnarray*} P_3 L_2 P_3^{-1} = $$\begin{pmatrix} 1 & 0 & \cdots & 0 & \cdots & \cdots &\cdots & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & \cdots &\cdots & \cdots & 0 \\ \vdots & l_{32} & \ddots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots\\ \vdots & \vdots & \cdots & 1 & 0 & \cdots &\cdots& \cdots & \vdots \\ \vdots & \boxed{l_{k2}} & \vdots & \vdots & \textcolor{green}{1} & 0 & \textcolor{blue}{0} & 0 & \vdots \\ \vdots & \vdots & \cdots & \vdots & \ddots & \ddots & \ddots & \cdots & \vdots \\ \vdots & \boxed{l_{i2}} & \cdots & 0 & \textcolor{green}{0} & 0 & \textcolor{blue}{1} & \cdots & \vdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots & 0 \\ 0 & 0 & \cdots & 0 & \cdots & \cdots &\cdots & 0 & 1 . \end{pmatrix}$$ \N - No hay número. \N - Fin. e

Se trata, de nuevo, de una matriz atómica con las entradas $l_{i2}$ y $l_{k2}$ intercambiados. Del mismo modo, $P_2 L_1 P_2^{-1}$ es atómico y por eso es $\Lambda_1 = P_3 P_2 L_1 P_2^{-1} P_3^{-1}$ ,

En general para

$$\begin{eqnarray*} U= L_{n-1} P_{n-1} L_{n-2} P_{n-2} \cdots P_2 L_1 P_1 A, \end{eqnarray*}$$ definimos

$$\begin{eqnarray*} \Lambda_i = P_{n-1} \cdots P_{i+2} P_{i+1} L_i P_{i+1}^{-1} P_{i+2}^{-1} \cdots P_{n-1}^{-1}. \end{eqnarray*}$$ donde asumimos $P_0=I$ . El mismo procedimiento anterior garantiza que $\Lambda_i$ es atómico y por lo tanto $\Lambda=\prod \Lambda_i$ es triangular inferior con unos en la diagonal.

Por lo tanto, esto completa lo que se necesita para verificar que $PA=LU$ .