Descomposición LU de matrices

Question

Aunque sé cómo se hace la descomposición LU, dadas las siguientes dos matrices:

$\begin{pmatrix} 0 & 2 & 3\\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$ y $ \begin{pmatrix} 1 & 2 & 1 \\ -2 & -1 & 1 \\ -2 & -1 & 1 \end{pmatrix}$

Me gustaría escribirlos como PAQ = LU mientras que P y Q son matrices de permutación y la descomposición se realiza con pivote completo . ¿Cómo se puede hacer esto?

Answer 1

Dada:

$A = \begin{pmatrix} 0 & 2 & 3\\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$

Utilizando el pivote completo para la descomposición, escribe $A$ como $PAQ = LU$ donde $P$ y $Q$ son ambas matrices de permutación.

Ve despacio y asegúrate de seguir cada paso, ya que no puedo encontrar una manera más fácil de describir esto y no puedo encontrar otros ejemplos de autores, así que tuve que trabajar esto desde cero. ¡Asegúrese de seguir cada paso, la gran parte es que la tabla final tiene toda la información necesaria en él y el algoritmo no es malo una vez que usted va a través de él!

Escribamos esta matriz en forma de tabla con los números de columna en la fila superior y los números de fila en la columna de la izquierda.

$\begin{array}{c|c|c|c} & 1 & 2 & 3\\ \hline 1 & 0 & 2 & 3 \\ 2 & 4 & 5 & 6 \\ 3 & 7 & 8 & 9 \\ \end{array}$

Desde $9$ es la mayor magnitud, queremos intercambiar la Columna 3 con la Columna 1 y también intercambiar la Fila 3 con la Fila 1 para obtener ese valor máximo en el $a_{11}$ posición. Así que ahora tenemos (muestro estos intercambios de columnas en la fila superior de la tabla y el intercambio de filas en la columna más a la izquierda si la tabla).

$\begin{array}{c|c|c|c} & 3 & 2 & 1\\ \hline 3 & 9 & 8 & 7 \\ 2 & 6 & 5 & 4 \\ 1 & 3 & 2 & 0 \\ \end{array}$

Ahora, queremos que el primer elemento en la fila 2 y en la fila 3 sea cero, por lo que tenemos (esto es sólo la eliminación gaussiana en cada una de esas filas utilizando este valor máximo de pivote):

Nueva fila 2: $m = \frac{6}{9} = \frac{2}{3} \rightarrow (6, 5, 4) - \frac{2}{3} (9, 8, 7) = (0, -\frac{1}{3}, -\frac{2}{3})$

Nueva fila 3: $m = \frac{3}{9} = \frac{1}{3} \rightarrow (3, 2, 0) - \frac{1}{3} (9, 8, 7) = (0, -\frac{2}{3}, -\frac{7}{3})$

Volvamos a escribir nuestro sistema con "todos" estos datos y continuemos el proceso, así que ahora tenemos:

$\begin{array}{c|c|c|c} & 3 & 2 & 1\\ \hline 3 & 9 & 8 & 7 \\ 2 & \frac{2}{3} & -\frac{1}{3} & -\frac{2}{3} \\ 1 & \frac{1}{3} & -\frac{2}{3} & -\frac{7}{3} \\ \end{array}$

Ahora estamos trabajando con los más pequeños $2x2$ que tiene un valor de magnitud máxima de $\frac{7}{3}$ Así que queremos intercambiar la Columna 3 con la Columna 2 y la Fila 3 con la Fila 2. Reescribamos nuestro sistema para reflejar estos intercambios (anotándolos en la fila superior y en la columna izquierda de la tabla).

$\begin{array}{c|c|c|c} & 3 & 1 & 2\\ \hline 3 & 9 & 7 & 8 \\ 1 & \frac{1}{3} & -\frac{7}{3} & -\frac{2}{3} \\ 2 & \frac{2}{3} & -\frac{2}{3} & -\frac{1}{3} \\ \end{array}$

Ahora, queremos que el segundo elemento de la fila 3 sea cero, por lo que tenemos (esto es sólo la eliminación gaussiana en cada una de esas filas utilizando este valor máximo de pivote):

Nueva fila 3: $\displaystyle m = \frac{-\frac{2}{3}}{-\frac{7}{3}}= \frac{2}{7} \rightarrow (-\frac{2}{3}, -\frac{1}{3}) - \frac{2}{7} (-\frac{7}{3}, -\frac{2}{3}) = (0, -\frac{1}{7})$

Ahora podemos escribir el resultado final de nuestro sistema y leer "todas" las matrices necesarias de este formulario.

$\begin{array}{c|c|c|c} & 3 & 1 & 2\\ \hline 3 & 9 & 7 & 8 \\ 1 & \frac{1}{3} & -\frac{7}{3} & -\frac{2}{3} \\ 2 & \frac{2}{3} & \frac{2}{7} & -\frac{1}{7} \\ \end{array}$

Ahora podemos escribir $PAQ = LU$ Utilizando la tabla anterior (todo está codificado en ella).

$P$ se forma mirando los números de la columna de la izquierda $(3, 1, 2)^T$ que indican las posiciones de las filas en las que deben colocarse los $1's$ en nuestra matriz de permutación, por lo que tenemos:

$P = \begin{pmatrix} 0 & 0 & 1\\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$

Por supuesto, $A$ se acaba de dar.

$A = \begin{pmatrix} 0 & 2 & 3\\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$

$Q$ se forma mirando los números de la fila superior $(3, 1, 2)$ que indican las posiciones de las columnas en las que deben colocarse los $1's$ en nuestra matriz de permutación, por lo que tenemos:

$Q = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$

$L$ se acaba de formar haciendo y matriz triangular inferior de la tabla y la matriz de identidad como:

$L = \begin{pmatrix} 1 & 0 & 0\\ \frac{1}{3} & 1 & 0 \\ \frac{2}{3} & \frac{2}{7} & 1 \end{pmatrix}$

$U$ se acaba de formar con una matriz triangular superior de la tabla y la matriz Cero como:

$U = \begin{pmatrix} 9 & 7 & 8\\ 0 & -\frac{7}{3} & -\frac{2}{3} \\ 0 & 0 & -\frac{1}{7} \end{pmatrix}$

Puede comprobar que efectivamente $PAQ = LU$ multiplicando ambos lados y viendo que se igualan (además se puede ver $A$ allí también.

La siguiente pregunta, ¿cómo se utiliza esto para resolver el sistema original? Mira esto Respuesta del MSE .

Puedes seguir este ejemplo (ir despacio) y hacer tu segundo ejemplo.

Saludos