Rozkład Choleskiego

Rozkład Choleskiego lub rozkład BanachiewiczaSzablon:Odn jest procedurą rozkładu symetrycznej, dodatnio określonej macierzy $A$ na iloczyn postaci:

$A=L{L}^T,$

gdzie $L$ jest dolną macierzą trójkątnąSzablon:Odn, a $L^T$ jej transpozycją.

Macierz dowolnego typu można rozłożyć na iloczyn dolnej i górnej macierzy trójkątnej postaci $A=LU$ stosując metodę LU. Jedynie w przypadku macierzy symetrycznych i dodatnio określonych możliwy jest rozkład CholeskiegoSzablon:Odn. Jeśli $A$ jest dodatnio określoną macierzą hermitowską to rozkład Choleskiego ma postać:

$A=L{L}^{*}.$

Algorytm rozkładu

Rozpisując iloczyn $A=L{L}^T,$ otrzymujemy:

$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]=\left[\begin{array}{cccc}{l}_{11}& 0& \cdots & 0\\ l_{21}& l_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & 0\\ l_{n1}& l_{n2}& \cdots & l_{nn}\end{array}\right]\left[\begin{array}{cccc}{l}_{11}& l_{21}& \cdots & l_{n1}\\ 0& l_{22}& \cdots & l_{n2}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & l_{nn}\end{array}\right]$

Współczynniki macierzy $A$ są zatem równe:

$\begin{array}{cccc}& a_{11}=l_{11}^2& \to & l_{11}=\sqrt{a_{11}}\\ & a_{21}=l_{21}{l}_{11}& \to & l_{21}=\frac{a_{21}}{l_{11}}\\ & a_{22}=l_{21}^2+l_{22}^2& \to & l_{22}=\sqrt{a_{22}-l_{21}^2}\\ & a_{32}=l_{31}{l}_{21}+l_{32}{l}_{22}& \to & l_{32}=\frac{a_{32}-l_{31}{l}_{21}}{l_{22}}\\ & \dots \end{array}$

W ogólnościSzablon:Odn:

$l_{ii}=\sqrt{a_{ii}-\sum _{k=1}^{i-1}{l}_{ik}^2},$

$l_{ji}=\frac{a_{ji}-\sum _{k=1}^{i-1}{l}_{jk}{l}_{ik}}{l_{ii}}.$

W zależności od tego czy kolejne elementy macierzy $L$ są wyznaczane wierszami czy kolumnami, powyższy algorytm nosi nazwę algorytmu Choleskiego-Banachiewicza lub algorytmu Choleskiego-Crouta. Ze względu na to, że $A$ jest dodatnio określona, wyrażenie pod pierwiastkiem jest zawsze dodatnie.

Zastosowanie

Podobnie jak rozkład LU, rozkład Choleskiego stosuje się w rozwiązywaniu równań liniowych. Stosuje się go również przy generowaniu wektorów losowych o wielowymiarowym rozkładzie normalnym.

Aby zastosować rozkład Choleskiego do rozwiązywania układów równań z niesymetryczną macierzą główną układu należy pomnożyć lewostronnie układ równań przez transpozycję macierzy głównej układu.

Zobacz też

• metoda LU
• rozkład QR

Bibliografia

• Szablon:Cytuj

Linki zewnętrzne

• „Numerical Recipes in C” rozdział 2.9 implementacja algorytmu rozkładu Choleskiego w języku C. (en.)