Jump to navigation

Belépés
  • Elfelejtettem a jelszavam
Regisztráció
 
  • Hogyan működik a mateking?
  • Mire jó a matek?
  • Matek érettségi
  • Képletgyűjtemény
  • Feladatgyűjtemény
  • Rólunk
  • Matek 5. osztály próbaüzem
  • Matek 6. osztály próbaüzem
  • Matek 7. osztály próbaüzem
  • Matek 8. osztály próbaüzem
  • Matek 9. osztály
  • Matek 10. osztály
  • Matek 11. osztály
  • Matek 12. osztály
  • Középiskolai matek (teljes)
  • Középszintű matek érettségi
  • Emelt szintű matek érettségi
  • Egyetemi matek alapozó
Összes egyetemi tantárgy
Legnépszerűbb tantárgyak:
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Valószínűségszámítás
  • Lineáris algebra
  • Diszkrét matematika
  • Statisztika

mateking

Login
 

Lineáris algebra

Kategóriák
  • Mátrixok és vektorok
  • Egy kis geometria
  • Vektorterek, független és összefüggő vektorok
  • Lineáris egyenletrendszerek, mátrixok rangja és inverze
  • Determináns, adjungált, kvadratikus alakok
  • Sajátérték, sajátvektor, sajátfelbontás
  • Lineáris leképezések
  • Síkbeli és térbeli leképezések és mátrixaik
  • Egyenletrendszerek optimális megoldása, pszeudoinverz
  • Vektornorma, mátrixnorma, mátrixok kondíciószáma
  • Ortogonális mátrixok, Fourier-együtthatók, Gram-Schmidt ortogonalizáció
  • Mátrixok LU-felbontása és QR-felbontása
  • Iterációs módszerek egyenletrendszerek megoldására
  • Komplex számok
  • Polinomok
  • Interpolációs polinomok
  • Oszthatóság
  • Euklideszi algoritmus, Diofantoszi egyenletek
  • Kongruenciák, Euler-Fermat tétel
  • Csoportok, gyűrűk, testek

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

  • Epizódok
  • Képletek
01
 
Mátrixok LU-felbontása
02
 
Az LU-felbonthatóság feltétele
03
 
LU-felbontás bármely nxn-es mátrixra
04
 
Az LU-felbontás módszere nem négyzetes mátrixokra
05
 
Mátrixok Cholesky-felbontása
06
 
Mátrixok QR-felbontása
07
 
QR-felbontás Givens-forgatásokkal
08
 
QR-felbontás Householder-tükrözésekkel

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.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

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

Megnézem a kapcsolódó epizódot

A témakör tartalma


Mátrixok LU-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…


Az LU-felbonthatóság feltétele

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…


LU-felbontás bármely nxn-es mátrixra

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.


Az LU-felbontás módszere nem négyzetes mátrixokra

Mátrixok Cholesky-felbontása

Mátrixok QR-felbontása

QR-felbontás Givens-forgatásokkal

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.
 


QR-felbontás Householder-tükrözésekkel

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.


 


Kapcsolatfelvétel
  • Segítségnyújtás
  • Hibabejelentés
  • Kapcsolatfelvétel
  • Mateking torrent bejelentés
Rólunk
  • A projektről
  • Médiamegjelenések
  • Legyen élmény a matek
  • Mire jó a matek?
Tartalomjegyzék
  • Középiskolai matek
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Lineáris algebra
  • Valószínűségszámítás
  • Diszkrét matematika
  • Statisztika
  • További tantárgyak
  • Egyetemi tematikák
  • Matek érettségi
GYIK Általános szerződési feltételek Adatkezelési tájékoztató Felhasználás oktatási célra

Cookie-használat módosítása

© Minden jog fenntartva!

Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!

barion
macroweb
  • Tantárgyaim