LU-felbontás és QR-felbontás
LU-felbontás
Egy mátrix LU felbontása azt jelenti, hogy a mátrixot felbontjuk egy alsó és egy felső háromszögmátrix szorzatára. Módszere a Gauss eliminációra épül.
LU-felbonthatóság feltétele
Egy nxn-es mátrixnak akkor létezik LU-felbontása, ha az első n-1 főminora nem nulla.
LU-felbontás bármely nxn-es mátrixra
Hogyha egy olyan mátrix LU felbontására van szükségünk, amelynek valamelyik (nem utolsó) főminora 0, akkor megtehetjük azt, hogy egy premutációs mátrix segítségével felcseréljük a sorait. Hiszen a sorcsere hatására a mátrix determinánsa, az egyenletrendszer megoldása stb. nem változnak.
LU-felbontás bármely mátrixra
Az LU-felbontás módszere nem négyzetes mátrixokra ugyanolyan, mint eddig, a Gauss elimináció segítségével történik. Legfeljebb az U mátrix nem lesz négyzetes, így nem lesz valódi felső háromszög mátrix.
Cholesky-felbontás
Ha az $A$ mátrix szimmetrikus és pozitív definit mátrix, akkor egyértelműen létezik olyan pozitív diagonálisú L alsó háromszögmátrix, amelyre:
\( A = L \cdot L^T \)
Ezt a felbontást Cholesky-felbontásnak nevezzük. Ez tulajdonképpen egy olyan LU-felbontás, ahol az U mátrix az L-nek a transzponáltja.
QR-felbontás
Hogyha az $A$ egy olyan nxk-as mátrix, $n \geq k$, és a mátrix teljes oszloprangú, vagyis az oszlopvektorok rangja $k$, akkor létezik olyan nxn-es $Q$ ortogonális mátrix, és olyan $R$ felső háromszögmátrix, hogy
\( A = Q \cdot R \)
Ezt a felbontást nevezzük QR-felbontásnak.
QR-felbontás Givens-forgatással
QR-felbontást kaphatunk akkor is, ha az $A$ mátrixot addig-addig szorozgatjuk Givens forgatások mátrixaival, amíg felső háromszögmátrixot nem kapunk.
QR-felbontás Householder-tükrözéssel
Az $A$ mátrixból először készítünk egy felső háromszögmátrixot a Householder-tükrözések segítségével.
Hogyha $\underline{a}$ és $\underline{b}$ különböző vektorok, és teljesül rájuk, hogy $\mid \underline{a} \mid = \mid \underline{b} \mid$ akkor létezik olyan Householder-tükrözés, ami az $\underline{a}$ vektort a $\underline{b}$ vektorba transzformálja.
\( H = I -2 \cdot \frac{ \underline{v} \cdot \underline{v}^T }{ \underline{v}^T \cdot \underline{v} } \)
ahol $ \underline{v}=\underline{a}-\underline{b} $.
Van itt ez a mátrix.
És most egy őrülten jó dolgot fogunk csinálni vele…
Felbontjuk egy alsó és egy felső háromszögmátrix szorzatára.
Nem sokkal később pedig azt is megtudjuk, hogy valójában mire jó mindez.
A módszert LU-felbontásnak nevezzük, és az egész a Gauss eliminációra épül.
Egy icipicit módosított Gauss eliminációra…
Ahhoz, hogy ezt a sor elején álló 6-ost megkapjuk…
Az első sort 3-mal kell szorozni.
Ehhez a 10-eshez pedig…
Hát igen, ehhez 5-tel.
Ezeket az értékes információkat eltároljuk itt alul.
És aztán jön a kinullázás, ahogy ez a Gauss-nál lenni szokott.
A folytatás is úgy működik, ahogy a Gauss-nál…
Csak éppen nem csinálunk ebből a 3-asból 1-est.
Marad így, ahogy van.
A 3-as alatt viszont ezt a 6-ost mindjárt kinullázzuk.
Ahhoz, hogy a 6-ost megkapjuk…
A második sort 2-vel kell szorozni.
Bekönyveljük ezt is ide az alsó mátrixba.
Aztán jön a kinullázás.
Végül már csak egyetlen dolog van hátra.
Ezt a mátrixot elnevezzük felső mátrixnak…
A másikat pedig alsónak.
Ja, és a főátlójába 1-eseket írunk.
Felülre meg nullákat.
És készen is van az LU-felbontás.
Nézzünk meg egy másikat is.
Ezzel a 3-assal kezdünk…
És alatta kinullázunk.
Ezeket a szorzókat felírjuk szépen ide.
Aztán jön a kinullázás.
Most ezzel a 2-essel folytatjuk…
Legyártjuk ezt a 4-est.
Ennek érdekében a második sort 2-vel kell szorozni.
Aztán kinullázunk.
És kész is.
Most pedig lássuk mire jó ez az egész.
Azon kívül persze, hogy remek szórakozás esős, hideg délutánokon…
A lényeg az U mátrixban van.
Az U mátrix segítségével meg tudjuk mondani, hogy mekkora az eredeti mátrix rangja, mennyi a determinánsa, segít az egyenletrendszerek megoldásában és az idegenek inváziója elleni harcban.
Az utóbbi esetben a hatékonysága még nem bizonyított.
Az eredeti mátrix rangja annyi, ahány nem nulla elem van az U mátrix főátlójában.
Rang=3
Az eredeti mátrix determinánsa az U mátrix főátlójában lévő elemek szorzata.
Hogyha pedig van egy ilyen egyenletrendszer:
Itt a valamilyen vektor…
Mondjuk ez.
Akkor ennek az egyenletrendszernek a megoldása is gyorsan leolvasható.
És most lássuk, ezen kívül mit tud még az LU-felbontás…
Van itt egy kis probléma.
Itt ez a teljesen tisztességes mátrix…
Ami ráadásul egy reguláris mátrix, vagyis a determinánsa nem nulla.
Hogyha azonban megpróbáljuk elkészíteni az LU-felbontását…
Ennél a résznél elakadunk.
A Gauss eliminációnál ilyenkor egy sorcserével megoldható a probléma…
De a sorcsere sajnos megváltoztatja az eredeti A mátrixot.
Ha csak meg kell oldanunk az egyenletrendszert, akkor ez persze nem gond.
De most igen.
Ha nem változtathatjuk meg az A mátrix sorainak eredeti sorrendjét, akkor az LU-felbontást nem tudjuk megcsinálni.
A problémát ez a blokk okozza.
Ebben a blokkban ugyanis két egymással összefüggő sor van.
A második sor az első sor 3-szorosa.
Ez okozza az elakadást.
Az elakadást bármelyik bal felső blokk okozhatja.
Ezeknek a blokkoknak a determinánsát főminornak vagy másként sarokfőminornak nevezzük.
Egy -es mátrixnak akkor létezik LU-felbontása, ha az első főminora nem nulla.
Ennél az A mátrixnál tehát az első két főminornak nem kéne nullának lennie…
Hát igen, a második főminor nulla, így aztán nincs LU-felbontás.
Most nézzük, mi a helyzet ezzel.
Végülis kár előre azon aggódni, hogy létezik-e LU-felbontás.
Ez menet közben úgyis kiderül.
De most gyorsan nézzük meg, hogy kipróbáljuk ezt a főminoros módszerünket.
Remek hír, úgy néz ki, hogy most létezik LU-felbontás.
Már jön is az LU-felbontás.
Nézzünk meg még egyet.
Most nem bajlódunk itt a főminorokkal.
Lesz ami lesz, jöjjön azonnal az LU-felbontás.
A folyamat itt elakadt…
Mázli, hogy pont a végén.
Hogyha esetleg valakit érdekelnek az elméleti jellegű részletek, a B mátrix most olyan…
hogy az első főminor nem nulla…
a második főminor sem nulla…
de a harmadik igen.
Csak éppen ez már mindegy.
Kész az LU-felbontás.
És most itt az ideje megnézni, hogy mit kezdhetnénk azokkal a mátrixokkal, ahol az LU-felbontás folyamata menet közben elakad…
Most egy teljesen reménytelen vállalkozásba kezdünk bele…
Megpróbáljuk elkészíteni ennek a mátrixnak az LU-felbontását.
A dolog emiatt a 0 miatt eleve kudarcra van ítélve.
Hát, akkor ennyi volt. Azért legalább megpróbáltuk…
Az A mátrixnak nincs LU-felbontása.
Létezik viszont egy permutációs mátrix.
Ezt egy közönséges egységmátrixból kapjuk úgy, hogy néhány sorát fölcseréljük.
Hogyha most egy másik mátrixot megszorzunk ezzel a permutációs mátrixszal…
Akkor a sorcsere abban a mátrixban is megtörténik.
Nekünk itt éppen egy ilyen sorcserére van szükségünk.
Vesszük ezt a permutációs mátrixot…
És megszorozzuk vele az A mátrixot.
Csak arra vigyázzunk, hogy a sorcseréhez mindig balról kell szorozni.
És most jöhet az LU-felbontás.
Nem érdemes nagyon elkeserednünk amiatt, hogy csak ennek a sorcserés mátrixnak tudjuk megcsinálni az LU-felbontását.
Hiszen, ha belegondolunk, hogy mennyi kudarc ért már életünk során…
Nem, inkább ne ebbe gondoljunk bele.
Abba gondoljunk bele, hogy a sorcsere hatására a mátrix rangja nem változik…
az egyenletrendszer megoldásai sem változnak…
a mátrix determinánsa pedig csak előjelet vált.
Vagyis minden dolog, ami miért az LU-felbontást csináljuk ugyanúgy működik a sorcserés mátrixra is.
Végül még egy dolog.
A permutációs mátrixoknak van egy nagyon vicces tulajdonsága.
Ha megszorozzuk őket saját magukkal, akkor mindig az egységmátrixot kapjuk.
Mindezt arra tudnánk használni, hogy…
Bármely -es mátrixnak van alakú felbontása, ahol L és U a szokásos háromszögmátrixok és P egy permutációmátrix.
Számoljuk ki a rangját és a determinánsát ennek a B mátrixnak, és adjuk meg az LU-felbontását.
Az már biztos, hogy szükség lesz egy sorcserére.
És ha látjuk egy kicsit előre a jövőt…
Akkor nem ezeket a sorokat cseréljük föl.
Hanem ezeket.
Mégpedig ennek a permutációs mátrixnak a segítségével.
És most jöhet az LU-felbontás.
Végül válaszoljunk a kérdésekre.
A rang úgy tűnik 3.
A determináns pedig…
Csak éppen ezt még meg kell szorozni a permutációs mátrix determinánsával.
Ezt a felbontást hívjuk QR-felbontásnak.
És most itt jön egy újabb módszer, amivel a QR-felbontást meg tudjuk csinálni.
A módszer lényege, hogy addig-addig szorozgatjuk az A mátrixot Givens forgatások mátrixaival, amíg felső háromszögmátrixot nem kapunk.
Mindenekelőtt persze tisztázzuk, hogy mi is az a Givens forgatás.
Már jön is.
Most pedig készítsük el ennek a mátrixnak a QR-felbontását Givens forgatások segítségével.
Először ezt fogjuk kinullázni.
És ennek az szögnek azt kell tudnia, hogy…
Akkor készen is van a kinullázás.
De ezzel még nincs vége…
Most egy második Givens forgatással ezt is kinullázzuk.
A módszer ugyanaz lesz, mint az előbb.
Kiválasztjuk ezt a vektort…
Hopp, ez nem lesz jó…
Hiszen ennek a vektornak az egyik koordinátája már eleve nulla.
Kénytelenek leszünk ezt választani.
Ennek a második Givens forgatásnak a síkja tehát a jelek szerint az első és a harmadik koordinátatengelyek által kifeszített sík lesz.
A második Givens forgatás mátrixa pedig…
És most már komolyabb rajzolgatás nélkül...
Hogyha pedig még emlékszünk rá, kell ide egy transzponálás is.
Mindezt általánosítva:
Az a Givens forgatás, ami b-t inullázza…
QR-felbontás Givens forgatásokkal:
Annak a Givens forgatásnak a mátrixa, ami b-t lenullázza:
Próbáljuk is ki a legújabb képletünket.
Folytatjuk a kinullázást ezzel.
Ebben a síkban fogunk forgatni…
És a képlet szerint…
El is készült a felső háromszögmátrix.
Ezek itt mind ortogonális mátrixok…
És a szorzatuk is ortogonális mátrix lesz.
Meg is van a QR-felbontás.
Nem kell mást tennünk, mint az egészet beszorozni a G mátrix inverzével.
Hatalmas szerencse, hogy G ortogonális mátrix, így az inverze megegyezik a transzponáltjával.
Itt jön egy harmadik módszer a mátrixok QR-felbontására…
Egy jópofa kis tükrözés segítségével.
A szokásos háromdimenziós térben az origón átmenő a normálvektorú síkra tükrözést Householder-tükrözésnek nevezzük.
Ez itt a Householder-tükrözés mátrixa:
A QR-felbontáshoz készítünk belőle egy felső háromszögmátrixot a Householder-tükrözések segítségével.
Itt van a mátrix első oszlopvektora…
Kezdetnek kinullázzuk itt szépen ezeket.
Egy újabb Householder-tükrözéssel pedig…
Itt is nullát fogunk gyártani.
Közben arra azért vigyázzunk, hogy a meglévő nullákat ne rontsuk el.
Elhagyjuk a mátrix első sorát és oszlopát…
és csak az így megmaradó mátrixra alkalmazzuk az újabb Householder-tükrözést.
A korábban legyártott nulláink így biztonságban vannak.
A Householder-tükrözéssel ebből a vektorból gyártunk egy olyan vektort, aminek a második koordinátája nulla.
A két vektor hossza pedig egyforma.
Meg is van a második Householder-mátrix.
Egyetlen kis probléma vele, hogy ez nem egy 3x3-as mátrix.
De ezen könnyen lehet segíteni.
Az üres helyeket szépen feltöltjük…
Az egységmátrix megfelelő elemeivel.
A dolog általánosan így néz ki…
A QR-felbontás Householder-mátrixai:
És már meg is van a felső háromszögmátrix…
Hogyha ezt egészet beszorozzuk H inverzével, akkor meg is van a QR-felbontás.
