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 francia matematikus 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 a lineáris egyenletrendszerek megoldásánál, mint az LU felbontás.

Definíció

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.

Állítások

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.

Számítása

A Cholesky-algoritmus

A Cholesky-algoritmus lényegében a Gauss-elimináció módosított változata: arra használják, hogy kiszámolják a felbontott L mátrixot. 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)}=\left(\begin{array}{ccc}{\mathbf{I}}_{i-1}& 0& 0\\ 0& a_{i,i}& {\mathbf{b}}_i^{*}\\ 0& {\mathbf{b}}_i& {\mathbf{B}}^{(i)}\end{array}\right),$ ,

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:=\left(\begin{array}{ccc}{\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{array}\right),$

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)}=\left(\begin{array}{ccc}{\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{array}\right).$

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 a Cholesky–Crout-algoritmus

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

$\mathbf{A}\mathbf{=}\mathbf{L}{\mathbf{L}}^{\mathbf{T}}=\left(\begin{array}{ccc}{L}_{11}& 0& 0\\ L_{21}& L_{22}& 0\\ L_{31}& L_{32}& L_{33}\\ \end{array}\right)\left(\begin{array}{ccc}{L}_{11}& L_{21}& L_{31}\\ 0& L_{22}& L_{32}\\ 0& 0& L_{33}\\ \end{array}\right)=\left(\begin{array}{ccc}{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{array}\right)$

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

$L_{i,j}=\frac{1}{L_{j,j}}(A_{i,j}-\sum _{k=1}^{j-1}{L}_{i,k}{L}_{j,k}),\text{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}}(A_{i,j}-\sum _{k=1}^{j-1}{L}_{i,k}{L}_{j,k}^{*}),\text{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 :$\Vert \mathbf{E}{\Vert }_2\le c_n\epsilon \Vert \mathbf{A}{\Vert }_2.$ Itt || ||₂ a mátrix 2-norma c_n egy n-től függő kis állandó, $\epsilon$ 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}\mathbf{=}\mathbf{L}\mathbf{D}{\mathbf{L}}^{\mathbf{T}}=\left(\begin{array}{ccc}1& 0& 0\\ L_{21}& 1& 0\\ L_{31}& L_{32}& 1\\ \end{array}\right)\left(\begin{array}{ccc}{D}_1& 0& 0\\ 0& D_2& 0\\ 0& 0& D_3\\ \end{array}\right)\left(\begin{array}{ccc}1& L_{21}& L_{31}\\ 0& 1& L_{32}\\ 0& 0& 1\\ \end{array}\right)=$

$=\left(\begin{array}{ccc}{D}_1& & (\mathrm{s}\mathrm{z}\mathrm{i}\mathrm{m}\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{k}\mathrm{u}\mathrm{s})\\ 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{array}\right).$ 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}(A_{ij}-\sum _{k=1}^{j-1}{L}_{ik}{L}_{jk}{D}_k),\text{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}(A_{ij}-\sum _{k=1}^{j-1}{L}_{ik}{L}_{jk}^{*}{D}_k),\text{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\to \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:

$\Vert {\mathbf{L}}_k{\Vert }^2=\Vert {\mathbf{L}}_k{\mathbf{L}}_k^{*}\Vert =\Vert {\mathbf{A}}_k\Vert .$

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:

$⟨\mathbf{A}x,y⟩=⟨\lim {\mathbf{A}}_{k}x,y⟩=⟨\lim {\mathbf{L}}_k{\mathbf{L}}_k^{*}x,y⟩=⟨\mathbf{L}{\mathbf{L}}^{*}x,y⟩.$

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 $\{{{\mathscr{H}}}_n\}$ a Hilbert-terek egy sorozata! Az operátormátrix

$\mathbf{A}=\left[\begin{array}{cccc}{\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{array}\right]$

úgy hat a direkt összegzésre, hogy

${\mathscr{H}}={\oplus }_n{{\mathscr{H}}}_n,$

ahol bármely

${\mathbf{A}}_{ij}:{{\mathscr{H}}}_j\to {{\mathscr{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 \underset{n=1}{\overset{k}{\oplus }}{{\mathscr{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.