Rozkład Choleskiego

Rozkład Choleskiego lub rozkład Banachiewicza[1] jest procedurą rozkładu symetrycznej, dodatnio określonej macierzy A {\displaystyle A} na iloczyn postaci:

A = L L T , {\displaystyle A=LL^{T},}

gdzie L {\displaystyle L} jest dolną macierzą trójkątną[2], a L T {\displaystyle L^{T}} jej transpozycją.

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

A = L L ∗ . {\displaystyle A=LL^{*}.}

Algorytm rozkładu

Rozpisując iloczyn A = L L T , {\displaystyle A=LL^{T},} otrzymujemy:

[ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] = [ l 11 0 ⋯ 0 l 21 l 22 ⋯ 0 ⋮ ⋮ ⋱ 0 l n 1 l n 2 ⋯ l n n ] [ l 11 l 21 ⋯ l n 1 0 l 22 ⋯ l n 2 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ l n n ] {\displaystyle {\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 {\displaystyle A} są zatem równe:

a 11 = l 11 2 →   l 11 = a 11 a 21 = l 21 l 11 →   l 21 = a 21 l 11 a 22 = l 21 2 + l 22 2 →   l 22 = a 22 − l 21 2 a 32 = l 31 l 21 + l 32 l 22 →   l 32 = a 32 − l 31 l 21 l 22 … {\displaystyle {\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[2]:

l i i = a i i − ∑ k = 1 i − 1 l i k 2 , {\displaystyle l_{ii}={\sqrt {a_{ii}-\sum _{k=1}^{i-1}l_{ik}^{2}}},}
l j i = a j i − ∑ k = 1 i − 1 l j k l i k l i i . {\displaystyle 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 {\displaystyle 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 {\displaystyle 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ż

Przypisy

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.)