Mátrixok LU-felbontása és QR-felbontása

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.