コレスキー分解とは？

コレスキー分解（Cholesky decomposition）は、対称で正定値な行列 $A$ を、ある下三角行列 $L$ と、その転置行列 $L^T$（上三角行列）の積に分解することです。

$$
A = L L^T
$$

これは、数値の「平方根」を行列の世界に拡張したようなイメージです。

なぜコレスキー分解が重要か？

コレスキー分解は、特に科学技術計算や統計学の分野で非常に重要です。

計算が速い: 一般的なLU分解などに比べて、計算に必要な処理が約半分で済みます。
数値的に安定している: 計算誤差が累積しにくい特性があります。
連立一次方程式を簡単に解ける: $Ax = b$ という方程式を、逆行列 $A^{-1}$ を使わずに高速かつ正確に解くことができます。
モンテカルロ・シミュレーション: 相関を持つ乱数を生成する際に利用されます。

具体的な計算例 (3x3行列)

行列 $A$ をコレスキー分解 $A = LL^T$ してみます。

$$
A = \begin{pmatrix}
4 & 12 & -16 \\
12 & 37 & -43 \\
-16 & -43 & 98
\end{pmatrix}
$$

目標は、以下の下三角行列 $L$ を見つけることです。

$$
L = \begin{pmatrix}
l_{11} & 0 & 0 \\
l_{21} & l_{22} & 0 \\
l_{31} & l_{32} & l_{33}
\end{pmatrix}
$$

$A = LL^T$ の関係から、各成分を左上から順に計算します。

計算ステップ

1. 1列目の決定 ($l_{11}, l_{21}, l_{31}$)

(1,1)成分: $l_{11}^2 = a_{11} = 4 \implies l_{11} = 2$
(2,1)成分: $l_{11} l_{21} = a_{21} = 12 \implies 2 \times l_{21} = 12 \implies l_{21} = 6$
(3,1)成分: $l_{11} l_{31} = a_{31} = -16 \implies 2 \times l_{31} = -16 \implies l_{31} = -8$

2. 2列目の決定 ($l_{22}, l_{32}$)

(2,2)成分: $l_{21}^2 + l_{22}^2 = a_{22} = 37 \implies (6)^2 + l_{22}^2 = 37 \implies 36 + l_{22}^2 = 37 \implies l_{22}^2 = 1 \implies l_{22} = 1$
(3,2)成分: $l_{31}l_{21} + l_{32}l_{22} = a_{32} = -43 \implies (-8)(6) + l_{32}(1) = -43 \implies -48 + l_{32} = -43 \implies l_{32} = 5$

3. 3列目の決定 ($l_{33}$)

(3,3)成分: $l_{31}^2 + l_{32}^2 + l_{33}^2 = a_{33} = 98 \implies (-8)^2 + (5)^2 + l_{33}^2 = 98 \implies 64 + 25 + l_{33}^2 = 98 \implies 89 + l_{33}^2 = 98 \implies l_{33}^2 = 9 \implies l_{33} = 3$

分解結果

$$
L = \begin{pmatrix}
2 & 0 & 0 \\
6 & 1 & 0 \\
-8 & 5 & 3
\end{pmatrix}
$$

具体例：コレスキー分解による連立方程式の解法

コレスキー分解の最大の利点である「連立一次方程式の高速な解法」を、上で求めた $L$ を使って実行します。

1. 問題設定

解きたい連立一次方程式 $Ax = b$ を以下のように定めます。

$$
A = \begin{pmatrix}
4 & 12 & -16 \\
12 & 37 & -43 \\
-16 & -43 & 98
\end{pmatrix}, \quad
x = \begin{pmatrix}
x_1 \\ x_2 \\ x_3
\end{pmatrix}, \quad
b = \begin{pmatrix}
0 \\ 6 \\ 39
\end{pmatrix}
$$

$A = LL^T$ と分解できているので、$Ax=b$ は $L(L^T x) = b$ と書き換えられます。

2. 手順

$L^T x = y$ とおくと、方程式は以下の2ステップに分かれます。

Step 1 (前進代入): $Ly = b$ を解いて、中間ベクトル $y$ を求めます。
Step 2 (後退代入): $L^T x = y$ を解いて、最終的な解 $x$ を求めます。

3. Step 1: $Ly = b$ を解く (前進代入)

$$
\begin{pmatrix}
2 & 0 & 0 \\
6 & 1 & 0 \\
-8 & 5 & 3
\end{pmatrix}
\begin{pmatrix}
y_1 \\
y_2 \\
y_3
\end{pmatrix}

\begin{pmatrix}
0 \\
6 \\
39
\end{pmatrix}
$$

$L$ は下三角行列なので、上から順に $y_1, y_2, y_3$ を代入計算だけで求められます。

1行目:
$2y_1 = 0 \implies y_1 = 0$
2行目: (求めた $y_1$ を使う)
$6y_1 + 1y_2 = 6$
$6(0) + y_2 = 6 \implies y_2 = 6$
3行目: (求めた $y_1, y_2$ を使う)
$-8y_1 + 5y_2 + 3y_3 = 39$
$-8(0) + 5(6) + 3y_3 = 39$
$30 + 3y_3 = 39$
$3y_3 = 9 \implies y_3 = 3$

これで、中間ベクトル $y = (0, 6, 3)^T$ が求まりました。

4. Step 2: $L^T x = y$ を解く (後退代入)

次に、Step 1で求めた $y$ を使って $L^T x = y$ を解きます。

$$
\begin{pmatrix}
2 & 6 & -8 \\
0 & 1 & 5 \\
0 & 0 & 3
\end{pmatrix}
\begin{pmatrix}
x_1 \\
x_2 \\
x_3
\end{pmatrix}

\begin{pmatrix}
0 \\
6 \\
3
\end{pmatrix}
$$

$L^T$ は上三角行列なので、今度は下から順に $x_3, x_2, x_1$ を代入計算だけで求められます。

3行目:
$3x_3 = 3 \implies x_3 = 1$
2行目: (求めた $x_3$ を使う)
$1x_2 + 5x_3 = 6$
$x_2 + 5(1) = 6$
$x_2 + 5 = 6 \implies x_2 = 1$
1行目: (求めた $x_3, x_2$ を使う)
$2x_1 + 6x_2 - 8x_3 = 0$
$2x_1 + 6(1) - 8(1) = 0$
$2x_1 - 2 = 0$
$2x_1 = 2 \implies x_1 = 1$

5. 結論

最終的な解 $x = (1, 1, 1)^T$ が得られました。

このように、逆行列 $A^{-1}$ を一切計算することなく、2回の簡単な代入計算（前進代入と後退代入）だけで連立一次方程式を解くことができました。