Come cambiare le righe nella matrice L quando si scompone la matrice A in PA = LU?

Question

Trova la matrice di permutazione $P$, la matrice triangolare inferiore $L$ e la matrice triangolare superiore $U$ tale che $$ PA=LU $$ Dato $$ 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}$$

Sono arrivato fin qui

$$ 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}$$ e $$ L= \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 1 & 1 & 0 \\ -4 & 3 & 0 & 1 \end{pmatrix}$$ L'ultimo passaggio che devo fare è cambiare la quarta riga con la terza ma non so esattamente come modificare le voci nella matrice triangolare inferiore L. Qualcuno può spiegare cosa devo esattamente cambiare in L?

Answer 1

Risposta lunga: pensa al risultato dell'eliminazione in avanti come a un'equazione di matrice della forma$U=E_r P_r E_{r-1} P_{r-1} \dots E_1 P_1 A$ dove $E_i$ sono matrici di "eliminazione" (eliminando la colonna sotto $i$th pivot nel solito modo) e $P_i$ sono matrici di permutazione che spostano il $i$th perno nel $i$a riga oppure l'identità (se non hai effettuato uno scambio in quel passaggio). Le matrici di eliminazione sono triangolari inferiori e rimangono tali quando vengono moltiplicate insieme. Ma quando le matrici di permutazione vengono incluse, smettono di essere triangolari inferiori.

Quindi ora in genere vuoi invertire quel prodotto di $E_i P_i$ isolare $A$. Se li tieni tutti insieme, l'inverso non sarà triangolare inferiore, che in$PA=LU$vuoi che sia. Quindi quello che fai invece è riscrivere il prodotto$E_r P_r \dots E_1 P_1$, in modo che tutte le matrici di permutazione siano a destra e tutte le matrici di eliminazione a sinistra. Per farlo, è sufficiente capire come scrivere$PE$ come $E' P'$.

Questo può essere fatto con $P'=P$ e $E'=P E P^{-1} = P E P^T$, come è facile verificare: $E' P'=P E P^{-1} P=PE$. Questo$E'$ prendere questa forma è un'istanza di una situazione comune in algebra, dove la coniugazione è usata per applicare un'operazione "nel contesto" di un'altra operazione invertibile già applicata.

Facendolo più e più volte, puoi spostare tutte le matrici di permutazione verso destra. Il risultato è questo:

$$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.$$

Così ora

$$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)$$

Cosa significa in poche parole? Significa che per ottenere il corretto$L^{-1}$, devi spostare le voci non banali nel tuo file "computed $L^{-1}$"in base a tutti gli scambi di righe che hai eseguito dopo il calcolo di tali voci. Inversione$L^{-1}$ alla fine funziona ancora allo stesso modo (basta capovolgere il segno sulle voci non banali).

Così nel tuo esempio, l'effetto dello scambio di righe $3$ e $4$ è che aggiorni $L$ scambiando i ruoli degli indici $3$ e $4$, con il risultato di:

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

Nota che questo non è la stessa cosa del semplice scambio di riga$3$ con riga $4$.

Dopo che il gioco è fatto, in questo particolare esempio, ma se non lo fossi, allora si avrebbe non cambio$3$ con $4$ nelle fasi successive.

Risposta breve: la tua matrice finale$P$ottiene tutti gli scambi di riga che hai fatto. Ottenere$L$, ogni volta che si esegue uno scambio di righe che si otterrebbe moltiplicando a sinistra per una matrice di permutazione $P$, sostituisci il tuo attuale $L$ con $P L P^T$, il che significa che esegui quella permutazione sia sulle righe che sulle colonne della tua corrente $L$ (ma non in finale $L$).

Answer 2

Usando la riduzione delle righe, siamo arrivati ​​a

$$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}$$

Come approccio alternativo all'eccellente scrittura di @Ian (+1), avresti potuto invertire i passaggi di riduzione delle righe, incluso lo scambio, come $$A = E_1^{-1}E_2^{-1}E_3^{-1}E_4^{-1}U$$

Questo risulta in

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

Lo vediamo $L$ non è triangolare inferiore e dobbiamo solo scambiare le righe tre e quattro, risultando in

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

Quello scambio richiede una matrice di permutazione

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

Ora possiamo verificare

$$PA = LU$$

Puoi anche verificarlo $$A = PLU = P^T LU = P^{-1} LU$$

Vedere, ad esempio, come può essere utilizzata la fattorizzazione LU in una matrice non quadrata?