Cholesky-felbontás

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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átrix-nak 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[szerkesztés | forrásszöveg szerkesztése]

A Cholesky-felbontást főleg az Ax = b alakú lineáris mátrixegyenletek numerikus megoldására használják. Ha 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égyzetek[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

A Cholesky algoritmus[szerkesztés | forrásszöveg szerkesztése]

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(i) 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 Ii‒1 az i ‒ 1 dimenziójú egységmátrixot jelöli.

Ha most meghatározzuk az Li 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(i) 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 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:

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

A Cholesky-Banachiewicz és Cholesky-Crout algoritmus[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 \le c_n \varepsilon \|\mathbf{A}\|_2. Itt || ||2 a mátrix 2-norma cn 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[szerkesztés | forrásszöveg szerkeszté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}^2D_1 + D_2& \\ 
   L_{31}D_1 & L_{31}L_{21}D_{1}+L_{32}D_2 & L_{31}^2D_1 + L_{32}^2D_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[szerkesztés | forrásszöveg szerkesztése]

Láthattuk, hogy minden pozitív definit mátrixnak van Cholesky-felbontása. A módszerünk kiterjesztjető (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á


\mathbf{A}_k \rightarrow \mathbf{A} \,

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:

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

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:


\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[szerkesztés | forrásszöveg szerkesztése]

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 oprá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[szerkesztés | forrásszöveg szerkesztése]