lu faktorisering

Heyhey Heymel,

Relationen $M_k=I-me^T_k$ gäller bara när du vill addera en multipel av en rad till en annan rad. Den bakvända relationen $M_k^{-1}=I+me^t_k=L_k$ med teckenbyte gäller därför bara när du gör denna operation.

I ditt första steg byter du plats på några rader med transformationsmatrisen M1, det ger en annan invers (L_1):

$M_1=\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \quad M^{-1}_1=L1=\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}$

Från ovanstående steg gäller alltså:

$L=L_2L_3L_4=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 2 & -2 & 1 & 1 \end{bmatrix} \quad U=M_4M_3M_2B=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & -1 & 1 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 4 \end{bmatrix}$

Där $B=M_1A$  är matrisen där du redan bytt plats enligt ordningsföljden (3 4 1 2) som du gör i ditt första steg:

$B=LU=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & -1 & 2 & 1 \\ 0 & 0 & 1 & -1 \\ 2 & 2 & 1 & 1 \end{bmatrix}$

Detta är inte samma sak som att LU-faktorisera A.  Kanske vill din lärare / uppgiften att du ska förstå partial pivotering (dvs permutationen $M_1A=LU$, kallas LUP-faktorisering).

Guggle skrev :

Heyhey Heymel,

 

Relationen $M_k=I-me^T_k$ gäller bara när du vill addera en multipel av en rad till en annan rad. Den bakvända relationen $M_k^{-1}=I+me^t_k=L_k$ med teckenbyte gäller därför bara när du gör denna operation.

I ditt första steg byter du plats på några rader med transformationsmatrisen M1, det ger en annan invers (L_1):

$M_1=\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \quad M^{-1}_1=L1=\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}$

Från ovanstående steg gäller alltså:

$L=L_2L_3L_4=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 2 & -2 & 1 & 1 \end{bmatrix} \quad U=M_4M_3M_2B=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & -1 & 1 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 4 \end{bmatrix}$

Där $B=M_1A$  är matrisen där du redan bytt plats enligt ordningsföljden (3 4 1 2) som du gör i ditt första steg:

$B=LU=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & -1 & 2 & 1 \\ 0 & 0 & 1 & -1 \\ 2 & 2 & 1 & 1 \end{bmatrix}$

Detta är inte samma sak som att LU-faktorisera A.  Kanske vill din lärare / uppgiften att du ska förstå partial pivotering (dvs permutationen $M_1A=LU$, kallas LUP-faktorisering).

ja det stämmer att det är PA=LU faktorisering vi ska göra :) 

Men får man inte byta rader på matrisen A då, för då påverkas L och U matrisen?. Antar att M1 här vara min permutationsmatris?

Vad står L2L3L4 för?

Mk likaså? 

”tt plats enligt ordningsföljden (3 4 1 2)” ska det där vara rader?

Jag tolkar det som att du vill lära dig  PA=LU med pivotering:

För att uppnå en numeriskt stabil implementation av Gausselimination vill man hålla pivotelementen under kontroll för att begränsa den numeriska feltillväxten. Ett enkelt sätt att göra detta är att använda "partial pivoting" eller pivotering där man i varje steg väljer det största värdet på eller under diagonalen som pivotelement. Detta begränsar $|m_n|<1$.

Det betyder att man under varje steg först 1. permuterar med $P_n$ och sedan 2. eliminerar med $M_n$.

I ditt givna A ser vi att rad 2 innehåller det största pivotelementet. $P_1$ ska alltså byta plats på rad 1 och 2.

Sedan eliminerar vi subdiagonala bidrag i första kolonnen med $M_1$:

Notera att inversen av $M_1$ dvs $L_1$ bara är $M_1$ med ombytta tecken på elementen som inte ligger på diagonalen

Nu är vi färdiga med kolonn 1 och går till kolonn 2. Vi gör på exakt samma sätt. Först permuterar vi ($P_2$), sedan eliminerar vi $M_2$

rad 4 innehåller det största pivotelementet, alltså ska permutationen $P_2$ byta plats på rad 4 och rad 2.

Vad $M_2$ blir lämnas som övning.

Slutligen går vi till kolonn 3. Vi gör på exakt samma sätt. Först permuterar vi ($P_3$) sedan eliminerar vi $M_3$

$P_3$ och $M_3$ lämnas som övning.

slutligen är

$L=M^{-1}=(M_3P_3M_2P_2M_1P_1)^{-1}=P^{T}_1L_1P^{T}_2L_2P^{T}_3L_3$

där $A=LU$

Vill man hellre ha L på "äkta" triangulär form kan man alltså bilda

$PA=LU$ där vi multiplicerar tillbaka $P=P_3P_2P_1$ på L och låter  i vårt fall blir det:

Med $M_k$ avses en elementär eliminationsmatris eller om man så vill en Gausstransformation. Jag tror att du redan använt (en version) av $M_k$ i din egen uträkning ovan. Vi noterar att inversen av $M_k^{-1}=L_k$ ges av att byta tecken på multiplikatorerna, detta verkar du också redan känna till.

Jag tror att det är lättare att förstå vad L och M är genom att studera exemplet ovan, men här kommer en mer "matematisk" definintion:

$M_k$ är en triangulär matris med 1:or utmed diagonalen och ett tillskott i kolonn k av faktorer $m_i$ sådana att resultatet av $M_k A$ eliminerar element I $A$ under diagonalen i kolonn k.

$M_k=I-me^{T}_k$ där $m=[0,\ldots,0,m_{k+1},\ldots, m_n]^{T}$ och $e_k$ är kolonn k i enhetsmatrisen.

Ber om ursäkt för de många posterna och konstiga typsetting men det är fortfarande lite buggigt att posta här.

Guggle skrev :

Sedan eliminerar vi subdiagonala bidrag i första kolonnen med $M_1$:

Nu, hehe några dagar senare har jag läst igenom det här, men det verkar som att det där verkar mkt mer krångligare än de typ som vi lärt oss? då var det bara typ att göra så som jag ish la upp från början.? 

Jag visade en stegvis gausselimination med pivotering för att erhålla en LU-faktorisering.

Det betyder att man i varje steg först permuterar och sedan eliminerar. Det är lite mer avancerat än "vanlig" LU=PA. Det skulle underlätta om du postade uppgiftstext eller förklarade vilken kurs du går så jag kan anpassa nivån, just nu förutsätter jag att du läser numerisk analys och går andra eller tredje året på teknisk högskola.

$M=M_3M_2M_1$ är matrisprodukten av varje enskilt eliminationssteg.

Om vi tar det från början har du matrisen A.  Sedan multiplicerar du den med matrisen $P_1$.

$P_1$ byter i sin tur bara plats på rad 1 och rad två i din ursprungliga matris.

$P_1A$ är en ny matris.

Slutligen lägger du till -0.5 av rad1 i $P_1A$ till rad 3 i $P_1A$ och -0.5 av rad 1 till rad 4 i $P_1A$. Detta kan du göra genom att multiplicera $M_1$ med $P_1A$ och därmed får du en tredje matris  $M_1P_1A$.

Matrisen

Lägger alltså till -0.5 av rad 1 till rad 3 och -0.5 av rad 1 till rad 4 när man multiplicerar den med en annan matris.

Vi multiplicerar den med matrisen $P_1A$ och får:

Den permutation du använde från början byter plats enligt

Alltså ordningsföljd (rader) 3 4 1 2 i den ursprunliga matrisen. Detta kan vara ett "P" i en enkel PA=LU. U får du genom vanlig "eliminering" på matrisen PA. I mitt första inlägg B=LU (se mitt första inlägg i tråden). L är bara inversen av din eliminering (se mitt första inlägg i tråden).

Naa det är linjär algebra 2 faktiskt :) 

och de stod inget i uppg att man ska göra det med pivotering. Men ja, man ska ju ändå få pivot element oavsett tänker jag? eller?

för när jag gauss eliminerade a´ detta: https://www.pixeltopic.com/image/fqcvnkbekclrkz/ (för måste pivoten vara 1 i diagonalen?) i första matrisen så har jag ju bytt rader så då kommer min p matris at vara 

0 0 0 1

0 0 1 0

0 1 0 0

1 0 0 0

?

sedan så kommer jag i de sista matrisen att få 

U = (I-E_{43}) (I+E_{42}) (I-E_{41}) (I-2E_{21})

och så ska L vara inversen på M? Alltså kommer vi bara att byta tecken på allt till: 

U^(-1) = L  = (I+E_{43}) (I-E_{42}) (I+E_{41}) (I+2E_{21})

kolomn&rad, så alltså rad 4 och kolonn 2 ska vi placera dit en 1a.

Så kommer den här se ut i en matris:

1 2 0 0 

0 1 0 0

0 0 1 0

0 -1 1 1

och det är ju 0:or där vid under diagnoalen, och det vill jag ju inte ha? eller? då undrar jag om jag ens har gauss eliminerat rätt? 

för sedan ska jag ju bara ta min P matris, som jag har gjort, A matris som är given, och mitt U matris (som jag antar är rätt) och L för att få PA=LU, men jag måste ha gjort något fel vid U och L?

för man ska ju gauss eliminera tills man har fått sitt U matris, sedan bara ta inversen på den? för att få L, men det blir så konstigt med tanke på nollorna när jag ställer upp den i matrisen? Eller det kanske inte gör något?

Någonting, på mitt sätt ^^^, känns fel.

heymel skrev :

i första matrisen så har jag ju bytt rader så då kommer min p matris at vara 

0 0 0 1

0 0 1 0

0 1 0 0

1 0 0 0

?

 Nej, permutationsmatrisen P, om du vill ha ordningsföljden du själv visar på bilden, är:

Kontrollera att P*A verkligen ger dig de byten av rader (permutation) du själv valt.

sedan så kommer jag i de sista matrisen att få 

U = (I-E_{43}) (I+E_{42}) (I-E_{41}) (I-2E_{21})

Du har nog slarvat lite. Om det ska följa dina egna operationer på bilden och i beskrivning blir det

M=(I-E_{43}) (I+2E_{42}) (I-2E_{41}) (I-E_{21})

Ser du skillnaden?

och så ska L vara inversen på M? Alltså kommer vi bara att byta tecken på allt till: 

 L  = (I+E_{43}) (I-E_{42}) (I+E_{41}) (I+2E_{21})

Nej, du måste reversera ordningsföljden på matriserna också, enligt regeln (AB)^-1 = B^-1A^-1

L=(I+E_{21})(I+2E_{41}) (I-2E_{42})(I+E_{43})

L blir då:

Nu kan du kontrollera att PA=LU, med givet A, P enligt ovan och det U=MPA du själv eliminerat fram på bilden.

Guggle skrev :

heymel skrev :

i första matrisen så har jag ju bytt rader så då kommer min p matris at vara 

0 0 0 1

0 0 1 0

0 1 0 0

1 0 0 0

?

 Nej, permutationsmatrisen P, om du vill ha ordningsföljden du själv visar på bilden, är:

Kontrollera att P*A verkligen ger dig de byten av rader (permutation) du själv valt.

sedan så kommer jag i de sista matrisen att få 

U = (I-E_{43}) (I+E_{42}) (I-E_{41}) (I-2E_{21})

Du har nog slarvat lite. Om det ska följa dina egna operationer på bilden och i beskrivning blir det

M=(I-E_{43}) (I+2E_{42}) (I-2E_{41}) (I-E_{21})

Ser du skillnaden?

och så ska L vara inversen på M? Alltså kommer vi bara att byta tecken på allt till: 

 L  = (I+E_{43}) (I-E_{42}) (I+E_{41}) (I+2E_{21})

Nej, du måste reversera ordningsföljden på matriserna också, enligt regeln (AB)^-1 = B^-1A^-1

L=(I+E_{21})(I+2E_{41}) (I-2E_{42})(I+E_{43})

L blir då:

Nu kan du kontrollera att PA=LU, med givet A, P enligt ovan och det U=MPA du själv eliminerat fram på bilden.

Jaa okej!!! jag trodde inte L behövde ändra ordningen, jag trodde de bara ändrade tecken! Ska försöka nu igen :) hehe , annars återkommer jag. ^^^

Guggle skrev :

heymel skrev :

i första matrisen så har jag ju bytt rader så då kommer min p matris at vara 

0 0 0 1

0 0 1 0

0 1 0 0

1 0 0 0

?

 Nej, permutationsmatrisen P, om du vill ha ordningsföljden du själv visar på bilden, är:

Kontrollera att P*A verkligen ger dig de byten av rader (permutation) du själv valt.

sedan så kommer jag i de sista matrisen att få 

U = (I-E_{43}) (I+E_{42}) (I-E_{41}) (I-2E_{21})

Du har nog slarvat lite. Om det ska följa dina egna operationer på bilden och i beskrivning blir det

M=(I-E_{43}) (I+2E_{42}) (I-2E_{41}) (I-E_{21})

Ser du skillnaden?

och så ska L vara inversen på M? Alltså kommer vi bara att byta tecken på allt till: 

 L  = (I+E_{43}) (I-E_{42}) (I+E_{41}) (I+2E_{21})

Nej, du måste reversera ordningsföljden på matriserna också, enligt regeln (AB)^-1 = B^-1A^-1

L=(I+E_{21})(I+2E_{41}) (I-2E_{42})(I+E_{43})

L blir då:

Nu kan du kontrollera att PA=LU, med givet A, P enligt ovan och det U=MPA du själv eliminerat fram på bilden.

Men en fråga redan nu, om jag i min A matris, byter rad 1 mot rad 4, och 2 mot 3. 

Då ska ju 

1 0 0 0  ---> rad 4 stå här ---> 0 0 0 1 
0 1 0 0 ----> rad 3 stå här --> 0 0 1 0 
0 0 1 0  ---> rad 2 stå här --> 0 1 0 0 
0 0 0 1  ---> rad 1 stå här --> 1 0 0 0

:o

heymel skrev :

Men en fråga redan nu, om jag i min A matris, byter rad 1 mot rad 4, och 2 mot 3. 

Då ska ju 

1 0 0 0  ---> rad 4 stå här ---> 0 0 0 1 
0 1 0 0 ----> rad 3 stå här --> 0 0 1 0 
0 0 1 0  ---> rad 2 stå här --> 0 1 0 0 
0 0 0 1  ---> rad 1 stå här --> 1 0 0 0

Men på ditt papper sätter du rad 3 överst, sedan rad 4, sedan 1 och sedan 2. Alltså ordningsföljd 3,4,1,2. Inte 4 3 2 1. Låt mig visa PA för de två ordningsföljderna:

Jämför med

Ser du skillnaden? Det är det första exemplet du själv har använt på ditt papper.