Comment changer de ligne dans la matrice L lors de la décomposition de la matrice A en PA = LU?

Question

Trouvez la matrice de permutation $P$, la matrice triangulaire inférieure $L$ et la matrice triangulaire supérieure $U$ tel que $$ PA=LU $$ Donné $$ A= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ -2 & -3 & -4 & -5 & -6 & -7 \\ 3 & 7 & 11 & 16 & 21 & 27 \\ -4 & -5 & -5 & -5 & -5 & -5 \end{pmatrix}$$

Je suis venu jusqu'ici

$$ U = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}$$ et $$ L= \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 1 & 1 & 0 \\ -4 & 3 & 0 & 1 \end{pmatrix}$$ La dernière étape que je dois faire est de changer la quatrième ligne avec la troisième mais je ne sais pas exactement comment changer les entrées de la matrice triangulaire inférieure L. Quelqu'un peut-il expliquer exactement ce que je dois changer en L?

Answer 1

Réponse longue: considérez le résultat de l'élimination directe comme une équation matricielle de la forme$U=E_r P_r E_{r-1} P_{r-1} \dots E_1 P_1 A$ où $E_i$ sont des matrices "d'élimination" (effacer la colonne sous le $i$e pivot de la manière habituelle) et $P_i$ sont soit des matrices de permutation qui déplacent le $i$ème pivot dans le $i$e ligne ou bien l'identité (si vous n'avez pas fait d'échange à cette étape). Les matrices d'élimination sont triangulaires inférieures et le restent lorsqu'elles sont multipliées ensemble. Mais lorsque les matrices de permutation sont incluses, elles cessent d'être triangulaires inférieures.

Alors maintenant, vous voulez généralement inverser ce produit de $E_i P_i$ isoler $A$. Si vous les conservez tous ensemble, l'inverse ne sera pas triangulaire inférieur, ce qui en$PA=LU$vous voulez que ce soit le cas. Donc ce que vous faites à la place est de réécrire le produit$E_r P_r \dots E_1 P_1$, de sorte que toutes les matrices de permutation sont à droite et toutes les matrices d'élimination sont à gauche. Pour ce faire, il suffit de savoir comment écrire$PE$ comme $E' P'$.

Cela peut être fait avec $P'=P$ et $E'=P E P^{-1} = P E P^T$, comme il est facile de vérifier: $E' P'=P E P^{-1} P=PE$. Ce$E'$ prendre cette forme est un exemple d'une situation courante en algèbre, où la conjugaison est utilisée pour appliquer une opération "dans le contexte" d'une autre opération inversible ayant déjà été appliquée.

En faisant cela encore et encore, vous pouvez déplacer toutes les matrices de permutation vers la droite. Le résultat ressemble à ceci:

$$U=E_r (P_r E_{r-1}^T P_r^T) \cdot ((P_r P_{r-1}) E_{r-2} (P_r P_{r-1})^T) \cdot \dots \cdot ((P_r \dots P_2) E_1 (P_r \dots P_2)^T) \\ \cdot P_r \cdot \dots \cdot P_1 \cdot A.$$

Alors maintenant

$$L^{-1}=E_r (P_r E_{r-1} P_r^T) \cdot ((P_r P_{r-1}) E_{r-2} (P_r P_{r-1})^T) \cdot \dots \cdot ((P_r \dots P_2) E_1 (P_r \dots P_2)^T)$$

Qu'est-ce que cela signifie en un mot? Cela signifie que pour obtenir le bon$L^{-1}$, vous devez déplacer les entrées non triviales dans votre "calcul $L^{-1}$"basé sur tous les échanges de lignes que vous avez effectués après le calcul de ces entrées. Inverser$L^{-1}$ à la fin fonctionne toujours de la même manière (il vous suffit de retourner le signe sur les entrées non triviales).

Ainsi, dans votre exemple, l'effet de l'échange de lignes $3$ et $4$ est-ce que vous mettez à jour $L$ en échangeant les rôles d'indices $3$ et $4$, résultant en:

$$L=\begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -4 & 3 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix}.$$

Notez que ce n'est pas la même chose que de simplement échanger une ligne$3$ avec rangée $4$.

Après cela, vous avez terminé, dans cet exemple particulier, mais si vous ne l'étiez pas, vous n'échangeriez pas$3$ avec $4$ dans les étapes suivantes.

Réponse courte: votre matrice finale$P$réalise tous les échanges de lignes que vous avez effectués. Obtenir$L$, à chaque fois que vous effectuez un échange de lignes qui serait réalisé en multipliant à gauche par une matrice de permutation $P$, vous remplacez votre actuel $L$ avec $P L P^T$, ce qui signifie que vous effectuez cette permutation à la fois sur les lignes et sur les colonnes de votre $L$ (mais pas sur la finale $L$).

Answer 2

En utilisant la réduction des lignes, nous sommes arrivés à

$$U = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}$$

Comme approche alternative à l'excellente rédaction de @Ian (+1), vous auriez pu inverser les étapes de réduction de ligne, y compris le swap, comme $$A = E_1^{-1}E_2^{-1}E_3^{-1}E_4^{-1}U$$

Cela se traduit par

$$L = \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 1 &0 & 1 \\ -4 & 3 & 1 & 0 \end{pmatrix}$$

On voit ça $L$ n'est pas triangulaire inférieur et nous avons juste besoin d'échanger les lignes trois et quatre, ce qui entraîne

$$L = \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -4 & 3 & 1 & 0 \\3 & 1 &0 & 1\end{pmatrix}$$

Ce swap nécessite une matrice de permutation

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

Maintenant nous pouvons vérifier

$$PA = LU$$

Vous pouvez également vérifier que $$A = PLU = P^T LU = P^{-1} LU$$

Voir, par exemple, Comment la factorisation LU peut-elle être utilisée dans une matrice non carrée?