Razčlenitev matrike LU je faktorizacija dane kvadratne matrike na dve trikotni matriki, eno zgornjo trikotno matriko in eno spodnjo trikotno matriko, tako da zmnožek teh dveh matric daje izvirno matriko. Predstavil ga je Alan Turing leta 1948, ki je tudi ustvaril Turingov stroj.

Metoda dekompozicije LU za faktoriziranje matrike kot produkta dveh trikotnih matrik ima različne aplikacije, kot je rešitev sistema enačb, ki je sam sestavni del številnih aplikacij, kot je iskanje toka v vezju in rešitev problemov diskretnega dinamičnega sistema. ; iskanje inverza matrike in iskanje determinante matrike.

Kaj je razgradnja L U?

Kvadratno matriko A je mogoče razstaviti na dve kvadratni matriki L in U tako, da je A = L U, kjer je U zgornja trikotna matrika, ki nastane kot rezultat uporabe Gaussove eliminacijske metode na A, L pa je spodnja trikotna matrika z diagonalnimi elementi enako 1.

Za A =egin{bmatrix} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{bmatrix} .

python operator ostankov

Imamo L = egin{bmatrix} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 1 end{bmatrix} in U =egin{bmatrix} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{bmatrix} ;

Tako, da je A = L U, tj.left[egin{array}{lll} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{array} ight]=left[egin{array}{lll} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 0 end{array} ight] cdot left[egin{array}{ccc} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{array} ight]

Tukaj je vrednost l_enaindvajset, v_enajst, itd. je mogoče primerjati in najti.

Kaj je Gaussova metoda izločanja?

Gaussova eliminacija, znana tudi kot Gauss-Jordanova eliminacija, je metoda, ki se uporablja v linearni algebri za reševanje sistemov linearnih enačb in iskanje inverza matrike. Ime je dobil po matematiku Carlu Friedrichu Gaussu in tudi matematiku Wilhelmu Jordanu, ki sta pomembno prispevala k njegovemu razvoju.

Po metodi Gaussove eliminacije:

1. Vsaka ničelna vrstica mora biti na dnu matrike.
2. Prvi neničelni vnos vsake vrstice mora biti na desni strani prvega neničelnega vnosa v prejšnji vrstici. Ta metoda reducira matriko na obliko vrstnega ešalona.

Metoda razgradnje LU

Za predelavo katere koli kvadratne matrike v dve trikotni matriki, tj. ena je spodnja trikotna matrika, druga pa zgornja trikotna matrika, lahko uporabimo naslednje korake.

• Podan niz linearnih enačb, jih najprej pretvorite v matrično obliko A X = C, kjer je A matrika koeficientov, X spremenljiva matrika in C matrika števil na desni strani enačb.
• Sedaj reducirajte matriko koeficientov A, tj. matriko, dobljeno iz koeficientov spremenljivk v vseh danih enačbah, tako da imamo za spremenljivke 'n' matriko nXn, v obliko vrstnega reda z uporabo Gaussove metode izločanja. Tako dobljena matrika je U.
• Za iskanje L imamo dve metodi. Prvi je, da predpostavimo preostale elemente kot nekaj umetnih spremenljivk, naredimo enačbe z uporabo A = L U in jih rešimo, da poiščemo te umetne spremenljivke. Druga metoda je, da so preostali elementi množilni koeficienti, zaradi katerih so ustrezni položaji postali nič v matriki U. (To metodo je nekoliko težavno razumeti z besedami, vendar bi bila jasna v spodnjem primeru)
• Zdaj imamo A (matriko koeficientov nXn), L (spodnjo trikotno matriko nXn), U (zgornjo trikotno matriko nXn), X (matriko spremenljivk nX1) in C (matriko števil nX1 na desni- stran enačb).
• Podani sistem enačb je A X = C. Nadomestimo A = L U. Tako imamo L U X = C. Postavimo Z = U X, kjer je Z matrika ali umetne spremenljivke, in najprej rešimo L Z = C in nato rešimo za U X = Z, da bi našli X ali vrednosti spremenljivk, kar je bilo zahtevano.

Primer razgradnje LU

Rešite naslednji sistem enačb z metodo razgradnje LU:

egin{equation*} x_1 + x_2 + x_3 = 1 end{equation*} egin{equation*} 4x_1 + 3x_2 – x_3 = 6 end{equation*} egin{equation*} 3x_1 + 5x_2 + 3x_3 = 4 end{equation*}

Rešitev: Tukaj imamo A =

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} , X = egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

in

C = egin{bmatrix} 1 6 4 end{bmatrix}

tako da je A X = C. Zdaj najprej razmislimo

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix}

in ga pretvorite v obliko vrstnega ešalona z uporabo Gaussove metode izločanja. Torej, z delom

egin{equation} R_2 o R_2 – 4R_1 end{equation} egin{equation} R_3 o R_3 – 3R_1 end{equation}

dobimo

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} sim

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 2 & 0 end{bmatrix}

Zdaj pa z delom

egin{equation} R_3 o R_3 – (-2)R_2 end{equation}

Dobimo

sim egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(Ne pozabite, da vmes vedno držite znak '-', znak '+' zamenjajte z dvema znakoma '-') Zato dobimo L =

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix}

in U =

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(upoštevajte, da je v matriki L

l_{21} = 4

je iz (1),

l_{31} = 3

je iz (2) in

l_{32} = -2

je iz (3)) Zdaj predpostavimo, da je Z

= egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

in reši L Z = C.

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix} egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

= egin{bmatrix} 1 6 4 end{bmatrix}

java vrže izjemo

Torej, imamo

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

Reševanje, dobimo

z_1 = 1

,

z_2 = 2

in

z_3 = 5

. Zdaj rešimo U X = Z

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix} egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

= egin{bmatrix} 1 2 5 end{bmatrix}

Zato dobimo

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Tako je rešitev danega sistema linearnih enačb

x_1 = 1

,

x_2 = 0.5

,

x_3 = -0.5

in od tod matriko X =

egin{bmatrix} 1 0.5 -0.5 end{bmatrix}

Vaja o razgradnji LU

V LU razpad matrike

| 2 2 |
| 4 9 |

, če sta oba diagonalna elementa U 1, potem je spodnji diagonalni vnos l22 L (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Za rešitev glejte VRATA | GATE-CS-2015 (Sklop 1) | 65. vprašanje .

Pogosta vprašanja o razgradnji LU

Kaj je metoda dekompozicije LU?

LU dekompozicija, okrajšava za Lower-Upper decomposition, je tehnika faktorizacije matrike, ki se uporablja za razčlenitev kvadratne matrike na produkt spodnje trikotne matrike (L) in zgornje trikotne matrike (U). Običajno se uporablja za poenostavitev reševanja sistemov linearnih enačb in izračunavanje determinant.

Zakaj je razgradnja LU edinstvena?

Razčlenitev LU je edinstvena, ker zagotavlja način za edinstveno faktorizacijo kvadratne matrike A na spodnje in zgornje trikotne matrike (L in U), kar omogoča učinkovito reševanje linearnih sistemov in izračun determinant.

'bančnikov algoritem'

Kako se izračuna razčlenitev LU?

Razčlenitev LU se izračuna z uporabo Gaussove eliminacije, kjer kvadratno matriko A pretvorite v spodnjo (L) in zgornjo (U) trikotno matriko z izvajanjem vrstičnih operacij, medtem ko spremljate spremembe v ločenih matrikah. Ta proces je iterativen in se nadaljuje, dokler se A popolnoma ne razgradi. Metoda z vsemi koraki za razgradnjo LU je podana v članku.

Kdaj razgradnja LU ni mogoča?

Razgradnja LU morda ne bo mogoča, če je matrika A singularna (neinvertibilna) ali ko zahteva vrtenje za stabilnost, vendar vrtilni element postane nič, kar povzroči deljenje z nič med postopkom razgradnje.

Ali obstajajo druge možnosti za razgradnjo LU?

Da, alternative za razgradnjo LU vključujejo Razgradnja Choleskyja za simetrične pozitivno določene matrike, QR dekompozicija za splošne matrike in metode, ki temeljijo na lastnih vrednostih, kot sta spektralna dekompozicija in singularna dekompozicija vrednosti (SVD) za različne matrične operacije in aplikacije.

Ali je mogoče dekompozicijo LU uporabiti za nekvadratne matrike?

Razčlenitev LU se običajno uporablja za kvadratne matrike. Za pravokotne matrike se pogosteje uporablja QR dekompozicija. Vendar pa lahko različice, kot je dekompozicija LUP, obravnavajo tudi pravokotne matrike, kjer je P permutacijska matrika.