Rozkład Choleskiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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_{12}\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_{23} - 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_{ij} - \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[edytuj | edytuj kod]

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[edytuj | edytuj kod]