Cholesky-felbontás

A lineáris algebrában a Cholesky-felbontás a szimmetrikus, pozitív definit mátrixok felbontása alsó trianguláris mátrixok és azok konjugált transzponáltjainak szorzatává.

Ezt az eljárást André-Louis Cholesky fedezte fel a valós mátrixokhoz.

Az alsó trianguláris mátrix az eredeti pozitív definit mátrix Cholesky-háromszöge.

Hogyha ez alkalmazható, akkor a Cholesky-felbontás nagyjából kétszer eredményesebb, mint az LU felbontás a lineáris egyenletrendszerek megoldásánál.

ÁllításSzerkesztés

Ha A-nak valós elemei vannak, és szimmetrikus (vagy általánosabban hermitikus) és pozitív definit, akkor A felbontható

 

ahol L alsó trianguláris mátrix szigorúan pozitív főátlóbeli elemekkel, és L* a konjugált transzponáltja (más nevén adjungáltja, vagy Hermite-transzponáltja) L-nek. Ez a Cholesky-felbontás.

A Cholesky-felbontás egyértelmű: adott egy hermitikus, pozitív definit A mátrix, csak egy alsó trianguláris L mátrix létezik, szigorúan pozitív főátlóbeli tagokkal, amivel A=LL*. A fordított eset triviális: ha A felírható, mint LL*, valamely invertálható L (nem feltétlen alsó trianguláris) mátrixra, akkor A hermitikus és pozitív definit.

Azt a feltételt, hogy a diagonális szigorúan pozitív legyen, elhagyhatjuk, hogy kiterjesszük a felbontást pozitív definit esetre. Az állításban szerepel: a négyzetes A mátrixnak van Cholesky-felbontása, akkor és csak akkor, ha A hermitikus és pozitív szemidefinit. A Cholesky-felbontás pozitív szemidefinit mátrixokra általában nem egyértelmű.

Speciális esetben az A szimmetrikus, pozitív definit mátrix valós elemekkel, feltehetjük, hogy L szintén valós elemekkel rendelkezik.

AlkalmazásSzerkesztés

A Cholesky-felbontást főleg az Ax = b alakú lineáris mátrixegyenletek numerikus megoldására használják. Ha az A mátrix szimmetrikus és pozitív definit, akkor Ax = b megoldható. A megoldás menete a következő:

  • Első lépésként Cholesky-felbontással kiszámoljuk A = LLT mátrixegyenletben szereplő L-t,
  • majd megoldjuk Ly = b-t y-ra,
  • végül LTx = y-t x-re.

Lineáris legkisebb négyzetekSzerkesztés

A gyakorlatban gyakran fordulnak elő Ax = b alakú rendszerek, ahol A szimmetrikus és pozitív definit. Például a lineáris legkisebb négyzetek problémájában a normál egyenletek ilyen alakúak. A akár egy energiafüggvényből is származhat, így annak fizikai megfontolások miatt pozitívnak kell lennie. Ez gyakran fordul elő parciális differenciálegyenlet-rendszerek megoldásánál.

Monte Carlo szimulációSzerkesztés

A Cholesky-felbontást gyakran alkalmazzák a Monte Carlo-módszerben arra, hogy egymással korreláló változókat szimuláljanak. Alkalmazva ezt korreláló részvények vektorára, u előállít egy Lu vektort azokkal a kovarianciatulajdonságokkal, amivel a rendszert modellezzük.

A Cholesky-felbontás számításaSzerkesztés

A Cholesky-algoritmusSzerkesztés

A Cholesky-algoritmust arra használják, hogy kiszámolják a felbontott L mátrixot, lényegében a Gauss elimináció módosított változata.

A rekurzív algoritmus i:=1-gyel indul és

 

Az i-edik lépésnél a A(i) mátrix a következő:

  ,

ahol Ii‒1 az i ‒ 1 dimenziójú egységmátrixot jelöli.

Ha most meghatározzuk az Li mátrixot

 

akkor felírhatjuk A(i) mátrixot, mint

 

ahol

 

Megjegyezzük, hogy bi bi* egy külső szorzat, ezért ezt az algoritmust külső szorzatos változatnak nevezik (Golub & Van Loan).

Ezt ismételjük i-re 1-től n-ig. Az n-edik lépés után A(n+1) = I eredményt kapjuk. Ezért az alsó trianguláris L mátrixra adódik:

 

A Cholesky-Banachiewicz és Cholesky-Crout algoritmusSzerkesztés

Ha kiírjuk az A = LL* mátrix-szorzást részleteiben, akkor:

 

Tehát a következő képleteket nyerjük a mátrix elemeire:

 
 

A négyzetgyök alatti kifejezés mindig pozitív, ha A elemei a valós számok közül kerülnek ki és pozitív definit. A komplex hermitikus mátrixokra a következők érvényesek:

 
 

Tehát ki tudjuk számítani az i-edik oszlop j-edik elemét, ha tudjuk a tőle balra és fölötte elhelyezkedő értékét. A számításra két különböző sorrendet szoktak követni.

  • A Cholesky-Banachiewicz algoritmus a bal felső sarokban kezdi a felbontást, és soronként halad.
  • A Cholesky-Crout algoritmus szintén a bal felső sarokban kezdődik, viszont oszloponként halad.

A számítás stabilitásaSzerkesztés

A Cholesky-felbontás alkalmas lineáris egyenletrendszerek megoldására. Az LU felbontás numerikusan instabil módszer, hacsak nem pivot elemekkel *főelem-kiválasztással?* hajtjuk végre azt. A fellépő hibák a felbontandó mátrix ún. növekedési faktorától függenek, ami az esetek többségében alacsony értéket vesz fel. Ezzel szemben, ha a Cholesky-felbontással dolgozunk, kétszer olyan gyorsan haladhatunk, főleg, hogy nincs szükség pivot elemek kijelölésére *főelem-kiválasztásra?*. Ezzel a módszerrel a hiba mindig kicsi lesz. Ha az Ax = b lineáris egyenletrendszerre y-t kaptunk megoldásnak, akkor a valódi gyöktől való eltérés leírható a következőképpen: (A + E)y = b , ahol :  Itt || ||2 a mátrix 2-norma cn egy n-től függő kis állandó,   pedig a gépepszilon. Egyetlen ismert hátránya van a Cholesky-felbontásnak. Az algoritmus során négyzetgyököket kell számítani, viszont a kerekítési hibákból adódóan előfordulhat, hogy negatív számok kerülnek a gyök alá. Szerencsére ez a gond csak nagyon rosszul rendezett mátrixok esetén szokott fellépni.

A négyzetgyökvonás kikerüléseSzerkesztés

A felbontás egy másik módja:

 

Ebben a formában nincsen szükség négyzetgyökökre. Ha A pozitív definit, akkor D főátlóbeli elemei mind pozitívak. Ugyanakkor használható D helyett bármilyen négyzetes és szimmetrikus mátrix. A következő rekurzív formulákkal meghatározhatóak D és L tagjai:

 
 

Komplex hermitikus mátrixok esetén pedig a következők érvényesek:

 
 

Pozitív szemidefinit mátrixok Cholesky-felbontásaSzerkesztés

Láthattuk, hogy minden pozitív definit mátrixnak van Cholesky-felbontása. A módszerünk kiterjeszthető (itt nem teljesen részletezett érveléssel) pozitív szemidefinitekre is. Sajnos ez esetben nem jutunk explicit numerikus algoritmusokhoz, amikkel végrehajtható a felbontás. Ha A pozitív szemidefinit n×n-es mátrix, akkor az {Ak} = {A + (1/k)In} sorozat tagjai pozitív definitek. Továbbá

 

az operátornorma esetén. Pozitív definit esetben minden Ak-nak van Cholesky-felbontása, Ak = LkLk*. Az operátornorma tulajdonságaiból adódóan:

 

Tehát {Lk} a Banach-tér operátorainak egy korlátos készlete, és relatív kompakt (mivel a vektortér dimenzióinak száma véges). Következésképp van konvergens sorozata, amit az {Lk} sorozat jelöl ki, és a határértéke L. Ha L a határértéke ennek a sorozatnak, akkor megmutatható, hogy ez az L alsó trianguláris nemnegatív diagonális elemekkel és A = LL*. Bármely x-re és y-ra:

 

Ebből A = LL*. Mivel a tárgyalt vektorterünk dimenzióinak száma véges, ezért minden topológia az operátorok terén ekvivalens.

ÁltalánosításSzerkesztés

A Cholesky-felbontás általánosítható akár nem véges mátrixokra is operátorok segítségével. Legyen   a Hilbert-terek egy sorozata! Az operátormátrix

 

úgy hat a direkt összegzésre, hogy

 

ahol bármely

 

egy korlátos operátor. Ha A pozitív (szemidefinit) abban az értelemben, hogy minden véges k-ra és bármely  , akkor van olyan L operátormátrix úgy, hogy A = LL*.

Online kalkulátorSzerkesztés