本日は行列のコレスキー分解の概要と、その計算方法について紹介したいと思います。
行列のコレスキー分解は、適用可能な行列は限られますが、連立一次方程式を高速に解いたり、高速に逆行列を算出することにおいて有用な役割を果たします。
目次
コレスキー分解とは
行列のコレスキー分解とは、ある正定値エルミート行列$\mathbf{A}$を、下三角行列$\mathbf{L}$と、その随伴行列$\mathbf{L^{*}}$との積に分解することを指します。式で表すと以下の通りです。
$$\mathbf{A} = \mathbf{L} \mathbf{L^\mathrm{*}}$$
正定値エルミート行列$\mathbf{A}$は、その行列要素が全て実数値のとき、実対称行列となります。すなわち、コレスキー分解を行列成分が全て実数の行列に対して定義する場合は、ある実対称行列$\mathbf{A}$を下三角行列$\mathbf{L}$と、その転置行列$\mathbf{L^{\mathrm{T}}}$との積に分解することであると言えます。
$$\mathbf{A} = \mathbf{L} \mathbf{L^\mathrm{T}}$$
実応用では行列要素を全て実数値で扱うことも多いことから，以後の説明は実対称行列$\mathbf{A}$を対象に説明したいと思います。
実対称行列へのコレスキー分解の概要
ある正方行列$\mathbf{A}$がLU分解可能であり、かつ実対称行列であるとき、コレスキー分解を行うことが可能です。下三角行列
$$
\mathbf{L} =
\begin{pmatrix}
l_{11} & 0 & 0 & \dots & 0 \\
l_{21} & l_{22} & 0 & \dots & 0 \\
l_{31} & l_{32} & l_{33} & \dots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
l_{n1} & l_{n2} & l_{n3} & \dots & l_{nn}
\end{pmatrix}
$$
と、その転置行列
$$\mathbf{L^\mathrm{T}} = \begin{pmatrix}
l_{11} & l_{21} & l_{31} & \dots & l_{n1} \\
0 & l_{22} & l_{32} & \dots & l_{n2} \\
0 & 0 & l_{33} & \dots & l_{n3} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \dots & l_{nn}
\end{pmatrix}$$
を用いて以下のように表現することができます。
$$\mathbf{A} = \mathbf{L} \mathbf{L^\mathrm{T}}$$
この分解を行列のコレスキー分解と呼びます。
コレスキー分解が適用可能な行列は限定されるものの、LU分解と比較して下三角行列$\mathbf{L}$のみを算出すればよいため、より少ない計算量で分解が可能となります。下三角行列$\mathbf{L}$を算出後は、LU分解と同様に前進代入と後退代入の手順で連立1次方程式を高速に解くことができます。そのため連立一次方程式を高速に解く場合等において、コレスキー分解が役に立ちます。
具体的な計算で見るコレスキー分解の計算方法
3×3の行列のコレスキー分解を具体的に計算する例を以下に紹介します。以下の3×3正方行列$\mathbf{A}$のコレスキー分解を考えます。
$$
\mathbf{A} =
\begin{pmatrix}
4 & 2 & 6 \\
2 & 5 & 5 \\
6 & 5 & 14
\end{pmatrix}
=
\begin{pmatrix}
l_{11} & 0 & 0 \\
l_{21} & l_{22} & 0 \\
l_{31} & l_{32} & l_{33}
\end{pmatrix}
\begin{pmatrix}
l_{11} & l_{21} & l_{31} \\
0 & l_{22} & l_{32} \\
0 & 0 & l_{33}
\end{pmatrix}
$$
$$
=
\begin{pmatrix}
{l_{11}}^2 & l_{11}l_{21} & l_{11}l_{31} \\
l_{11}l_{21} & {l_{21}}^2 + {l_{22}}^2 & l_{21}l_{31} + l_{22}l_{32} \\
l_{11}l_{31} & l_{21}l_{31} + l_{22}l_{32} & {l_{31}}^2 + {l_{32}}^2 + {l_{33}}^2
\end{pmatrix}
$$
すなわち、以下の6本の方程式が成り立ちます。
$$ 4 = {l_{11}}^2 $$
$$ 2 = l_{11}l_{21} $$
$$ 6 = l_{11}l_{31} $$
$$ 5 = {l_{21}}^2 + {l_{22}}^2 $$
$$ 5 = l_{21}l_{31} + l_{22}l_{32} $$
$$ 14 ={l_{31}}^2 + {l_{32}}^2 + {l_{33}}^2 $$
6個の変数に対して6本の方程式が成立するため、この式を解くことでコレスキー分解が可能です。
ただし、$4={l_{11}}^2$等の式から示されるように、対角要素の正負については確定しない(コレスキー分解の解は一意ではない)点に注意してください。
ただし、「対角成分を正にする」ことを規定すれば、コレスキー分解の解は一意に定まります。対角成分を正とすることとして上記の方程式を解くと、以下の解が得られます。
$$
\mathbf{A} =
\begin{pmatrix}
4 & 2 & 6 \\
2 & 5 & 5 \\
6 & 5 & 14
\end{pmatrix}
=
\begin{pmatrix}
2 & 0 & 0 \\
1 & 2 & 0 \\
3 & 1 & 2
\end{pmatrix}
\begin{pmatrix}
2 & 1 & 3 \\
0 & 2 & 1 \\
0 & 0 & 2
\end{pmatrix}
$$