行列のコレスキー分解の計算方法

本日は行列のコレスキー分解の概要と、その計算方法について紹介したいと思います。

行列のコレスキー分解は、適用可能な行列は限られますが、連立一次方程式を高速に解いたり、高速に逆行列を算出することにおいて有用な役割を果たします。

コレスキー分解とは

行列のコレスキー分解とは、ある正定値エルミート行列 $A$ を、下三角行列 $L$ と、その随伴行列 $L^{*}$ との積に分解することを指します。式で表すと以下の通りです。

$A = L L^{*}$

正定値エルミート行列 $A$ は、その行列要素が全て実数値のとき、実対称行列となります。すなわち、コレスキー分解を行列成分が全て実数の行列に対して定義する場合は、ある実対称行列 $A$ を下三角行列 $L$ と、その転置行列 $L^{T}$ との積に分解することであると言えます。

$A = L L^{T}$

実応用では行列要素を全て実数値で扱うことも多いことから，以後の説明は実対称行列 $A$ を対象に説明したいと思います。

実対称行列へのコレスキー分解の概要

ある正方行列 $A$ がLU分解可能であり、かつ実対称行列であるとき、コレスキー分解を行うことが可能です。下三角行列
$L = (\begin{matrix} l_{11} & 0 & 0 & \dots & 0 \\ l_{21} & l_{22} & 0 & \dots & 0 \\ l_{31} & l_{32} & l_{33} & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ l_{n 1} & l_{n 2} & l_{n 3} & \dots & l_{n n} \end{matrix})$

と、その転置行列

$L^{T} = (\begin{matrix} l_{11} & l_{21} & l_{31} & \dots & l_{n 1} \\ 0 & l_{22} & l_{32} & \dots & l_{n 2} \\ 0 & 0 & l_{33} & \dots & l_{n 3} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & l_{n n} \end{matrix})$

を用いて以下のように表現することができます。

$A = L L^{T}$

この分解を行列のコレスキー分解と呼びます。

コレスキー分解が適用可能な行列は限定されるものの、LU分解と比較して下三角行列 $L$ のみを算出すればよいため、より少ない計算量で分解が可能となります。下三角行列 $L$ を算出後は、LU分解と同様に前進代入と後退代入の手順で連立1次方程式を高速に解くことができます。そのため連立一次方程式を高速に解く場合等において、コレスキー分解が役に立ちます。

具体的な計算で見るコレスキー分解の計算方法

3×3の行列のコレスキー分解を具体的に計算する例を以下に紹介します。以下の3×3正方行列 $A$ のコレスキー分解を考えます。

$A = (\begin{matrix} 4 & 2 & 6 \\ 2 & 5 & 5 \\ 6 & 5 & 14 \end{matrix}) = (\begin{matrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{matrix}) (\begin{matrix} l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\ 0 & 0 & l_{33} \end{matrix})$

$= (\begin{matrix} {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{matrix})$

すなわち、以下の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}$ 等の式から示されるように、対角要素の正負については確定しない(コレスキー分解の解は一意ではない)点に注意してください。

ただし、「対角成分を正にする」ことを規定すれば、コレスキー分解の解は一意に定まります。対角成分を正とすることとして上記の方程式を解くと、以下の解が得られます。

$A = (\begin{matrix} 4 & 2 & 6 \\ 2 & 5 & 5 \\ 6 & 5 & 14 \end{matrix}) = (\begin{matrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 3 & 1 & 2 \end{matrix}) (\begin{matrix} 2 & 1 & 3 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{matrix})$