コレスキー分解は対称行列に特化したLU分解であり、対称行列の分解を効率よく行えるものです。主に、線形最小二乗法の解に使われます。当ページでは、このコレスキー分解について知っておきたいことをまとめて確認することができます。具体的には以下のことがわかります。

当ページでわかること

コレスキー分解とは
コレスキー分解のやり方
Python でコレスキー分解

コレスキー分解とは

コレスキー分解は、以下のように定義されます。

\[A=L \cdot L^T\]

L は下三角行列で、\(L^T\) はその転置行列です。右辺は上三角行列でも構いません。

\[A=U^T \cdot U\]

例えば以下の行列 \(A\) は次のようにコレスキー分解できます。

\[\begin{eqnarray}
\overset{A}{
\begin{pmatrix}
2 & 1 & 1 \\
1 & 2 & 1 \\
1 & 1 & 2
\end{pmatrix}
}
&=&
\overset{L}{
\begin{pmatrix}
\sqrt{2} & 0 & 0 \\
\frac{\sqrt{2}}{2} & \sqrt{\frac{3}{2}} & 0 \\
\frac{\sqrt{2}}{2} & \sqrt{\frac{1}{6}} & 2\sqrt{\frac{1}{3}}
\end{pmatrix}
}
\overset{L^T}{
\begin{pmatrix}
l_{11} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\
0 & \sqrt{\frac{3}{2}} & \sqrt{\frac{1}{6}} \\
0 & 0 & 2\sqrt{\frac{1}{3}}
\end{pmatrix}}\\
\end{eqnarray}\]

なおコレスキー分解は、対象の行列が、LU分解が可能な対称行列である場合に使えます。

コレスキー分解のやり方

コレスキー分解のやり方は、基本的にLU分解と同じです。しかし一方が下三角行列で他方がその転置行列になるため、L と L^T は次のようになります。

\[\begin{eqnarray}
\overset{A}{
\begin{pmatrix}
2 & 1 & 1 \\
1 & 2 & 1 \\
1 & 1 & 2
\end{pmatrix}
}
&=&
\overset{L}{
\begin{pmatrix}
l_{11} & 0 & 0 \\
l_{21} & l_{22} & 0 \\
l_{31} & l_{32} & l_{33}
\end{pmatrix}
}
\overset{L^T}{
\begin{pmatrix}
l_{11} & l_{21} & l_{31} \\
0 & l_{22} & l_{32} \\
0 & 0 & u_{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}
\end{eqnarray}\]

以降のやり方は、LU分解と同じです。このことからコレスキー分解は、LU分解の半分の手間で解けることがわかります。

\(l_{11}^2=2\)
\(l_{11}l_{21}=1\)
\(l_{11}l_{31}=1\)
\(l_{21}^2+l_{22}^2=2\)
\(l_{21}l_{31}+l_{22}l_{32}=1\)
\(l_{31}^2+l_{32}^2+l_{33}^2=2\)

まず、\(l_{11}^2=2\) より \(l_{11}=\sqrt{2}\) であることが求められます。次に、\(l_{11}l_{21}=1\) より、\(\sqrt{2} \cdot l_{21}=1\) なので、\(l_{21}=\frac{\sqrt{2}}{2}\) であることが求められます。同じように \(l_{11}l_{31}=1\) より、\(l_{31}=\frac{\sqrt{2}}{2}\) であることが求められます。続いて、\(l_{21}^2+l_{22}^2=2\) より \(l_{22}=\sqrt{\frac{3}{2}}\) であることが求められます。同じように解いていくと \(l_{32}=\sqrt{\frac{1}{6}}\) 、\(l_{33}=2 \sqrt{\frac{1}{3}}\) であることが求められます。

以上のことから、行列 A のコレスキー分解は次の通りになります。

以上がコレスキー分解のやり方です。

Pythonでコレスキー分解

Python でコレスキー分解は、NumPy の linalg.cholesky() 関数として実装されています。

In [1]:

# NumPy と SciPy のインポート
import numpy as np
from scipy.linalg import cholesky

# 対称行列を定義
A = np.array([
    [2,1,1],
    [1,2,1],
    [1,1,2]])
print(A)

[[2 1 1]
 [1 2 1]
 [1 1 2]]

In [2]:

# コレスキー分解
L = cholesky(A, lower=True)
print(L)

[[1.41421356 0.         0.        ]
 [0.70710678 1.22474487 0.        ]
 [0.70710678 0.40824829 1.15470054]]

In [3]:

# 元々の行列の再作成
B= L @ L.T 
print(B)

[[2. 1. 1.]
 [1. 2. 1.]
 [1. 1. 2.]]

プログラマーのための線形代数

コレスキー分解とは

コレスキー分解のやり方

Pythonでコレスキー分解