Rozkład Choleskiego

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

$A=LL^T\,$

gdzie $L\,$ jest dolną macierzą trójkątną, 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 Choleskiego. Jeśli $A\,$ jest dodatnio określoną macierzą hermitowską to rozkład Choleskiego ma postać:

$A=LL^*\,$

Algorytm rozkładu

Rozpisując iloczyn $A=LL^T\,$, otrzymujemy:

$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}= \begin{bmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix} \begin{bmatrix} l_{11} & l_{21} & \cdots & l_{n1} \\ 0 & l_{22} & \cdots & l_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & l_{nn} \end{bmatrix}$

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

$\begin{matrix} a_{11} = l_{11}^2 & \rightarrow & l_{11} = \sqrt{a_{11}}\\ a_{21} = l_{21}l_{11} & \rightarrow & l_{21} = {a_{21}\over l_{11}}\\ a_{22} = l_{21}^2+l_{22}^2 & \rightarrow & l_{22} = \sqrt{a_{22}-l_{21}^2}\\ a_{32} = l_{31}l_{21} + l_{32}l_{22} & \rightarrow & l_{32} = {a_{32} - l_{31}l_{21} \over l_{22}}\\ &\dots& \end{matrix}$

W ogólności:

$l_{ii} = \sqrt{\left( a_{ii} - \sum_{k=1}^{i-1}l^2_{ik} \right)}$

$l_{ji} = {a_{ji} - \sum_{k=1}^{i-1}l_{jk}l_{ik} \over 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 Choleskyego 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

Linki zewnętrzne

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