Rozkład Choleskiego

Rozkład Choleskiego lub rozkład Banachiewicza 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{aligned}&a_{11}=l_{11}^{2}&\rightarrow \ &l_{11}={\sqrt {a_{11}}}\\&a_{21}=l_{21}l_{11}&\rightarrow \ &l_{21}={\frac {a_{21}}{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}={\frac {a_{32}-l_{31}l_{21}}{l_{22}}}\\&\dots \end{aligned}}$

W ogólności:

$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

• ZenonZ. Fortuna ZenonZ., BohdanB. Macukow BohdanB., JanuszJ. Wąsowski JanuszJ., Metody numeryczne, Warszawa: Wydawnictwa Naukowo-Techniczne, 1993, ISBN 83-204-1551-9 .

Linki zewnętrzne

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