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ás

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

$\mathbf {A} =\mathbf {L} \mathbf {L} ^{*},$

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á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 = LL^T mátrixegyenletben szereplő L-t,
• majd megoldjuk Ly = b-t y-ra,
• végül L^Tx = y-t x-re.

Lineáris legkisebb négyzetek

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ó

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ása

A Cholesky-algoritmus

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

$\mathbf {A} ^{(1)}:=\mathbf {A} .$

Az i-edik lépésnél a A⁽ⁱ⁾ mátrix a következő:

$\mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},$ ,

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

Ha most meghatározzuk az L_i mátrixot

$\mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},$

akkor felírhatjuk A⁽ⁱ⁾ mátrixot, mint

$\mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}$

ahol

$\mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.$

Megjegyezzük, hogy b_i b_i^* 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⁽ⁿ⁺¹⁾ = I eredményt kapjuk. Ezért az alsó trianguláris L mátrixra adódik:

$\mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.$

A Cholesky-Banachiewicz és Cholesky-Crout algoritmus

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

${\mathbf {A=LL^{T}} }={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\begin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\\\end{pmatrix}}={\begin{pmatrix}L_{11}^{2}&&(szimmetrikus)\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\\\end{pmatrix}}$

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

$L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right),\qquad {\mbox{ahol }}i>j.$

$L_{i,i}={\sqrt {A_{i,i}-\sum _{k=1}^{i-1}L_{i,k}^{2}}}.$

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:

$L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}^{*}\right),\qquad {\mbox{ahol }}i>j.$

$L_{i,i}={\sqrt {A_{i,i}-\sum _{k=1}^{i-1}L_{i,k}L_{i,k}^{*}}}.$

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ása

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 :$\|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.$ Itt || ||₂ a mátrix 2-norma c_n egy n-től függő kis állandó, $\varepsilon$ 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ése

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

${\mathbf {A=LDL^{T}} }={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}={\begin{pmatrix}D_{1}&&(\mathrm {szimmetrikus} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}\\\end{pmatrix}}.$

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:

$L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}D_{k}\right),\qquad {\mbox{ahol }}i>j.$

$D_{i}=A_{ii}-\sum _{k=1}^{i-1}L_{ik}^{2}D_{k}$

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

$L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}D_{k}\right),\qquad {\mbox{ahol }}i>j.$

$D_{i}=A_{ii}-\sum _{k=1}^{i-1}L_{ik}L_{ik}^{*}D_{k}$

Pozitív szemidefinit mátrixok Cholesky-felbontása

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 {A_k} = {A + (1/k)I_n} sorozat tagjai pozitív definitek. Továbbá

$\mathbf {A} _{k}\rightarrow \mathbf {A} \,$

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

$\|\mathbf {L} _{k}\|^{2}=\|\mathbf {L} _{k}\mathbf {L} _{k}^{*}\|=\|\mathbf {A} _{k}\|.$

Tehát {L_k} 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 {L_k} 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:

$\langle \mathbf {A} x,y\rangle =\langle \lim \mathbf {A} _{k}x,y\rangle =\langle \lim \mathbf {L} _{k}\mathbf {L} _{k}^{*}x,y\rangle =\langle \mathbf {L} \mathbf {L} ^{*}x,y\rangle .$

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ás

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

$\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}&\;\\\mathbf {A} _{12}^{*}&\mathbf {A} _{22}&\mathbf {A} _{23}&\;\\\mathbf {A} _{13}^{*}&\mathbf {A} _{23}^{*}&\mathbf {A} _{33}&\;\\\;&\;&\;&\ddots \end{bmatrix}}$

úgy hat a direkt összegzésre, hogy

${\mathcal {H}}=\oplus _{n}{\mathcal {H}}_{n},$

ahol bármely

$\mathbf {A} _{ij}:{\mathcal {H}}_{j}\rightarrow {\mathcal {H}}_{i}$

egy korlátos operátor. Ha A pozitív (szemidefinit) abban az értelemben, hogy minden véges k-ra és bármely $h\in \oplus _{n=1}^{k}{\mathcal {H}}_{k},$, akkor van olyan L operátormátrix úgy, hogy A = LL*.

Online kalkulátor

• Online mátrix kalkulátor Mátrixok internetes Cholesky-felbontás-számítója.