コレスキー分解

コレスキー分解（コレスキーぶんかい）とは、正定値エルミート行列Aを下三角行列LとLの共役転置L^*との積に分解すること。

<math>\mathbf{A} = \mathbf{L} \mathbf{L}^{*} \qquad (\mathbf{A} \in \mathbb{K}^{m \times m})</math>

Aのエルミート性を利用したLU分解の特別な場合である。Lの対角成分は実数にとることができて（符号・位相の自由度があるが）通常は、対角成分を正に採り、その場合には、Lが一意に定まる。アンドレ＝ルイ・コレスキーにちなんで名づけられた。

Aが実対称行列の場合、上式の共役転置は転置に単純化される。

<math>\mathbf{A} = \mathbf{L} \mathbf{L}^{T} \qquad (\mathbf{A} \in \mathbb{R}^{n \times n})</math>

エルミート対称行列Aが正定値であることと、Aのコレスキー分解が存在することは同値になる。

アルゴリズムの例

コレスキー法はガウスの消去法の改良版である。

ガウスの消去法はAの左方から順次Lを作用させ前進消去（LU分解に対応。）するが、

A⁽ⁱ⁾=L_iA⁽ⁱ⁺¹⁾　　　　（　または、A⁽ⁱ⁺¹⁾=L_i^-1A⁽ⁱ⁾　）

コレスキー法はAを順次LとL^*で挟んで前進消去していくと考えればよい。

A⁽ⁱ⁾=L_iA⁽ⁱ⁺¹⁾ L_i^* 　　（　または、A⁽ⁱ⁺¹⁾=L_i^-1A⁽ⁱ⁾ L_i^*-1　）

このときA⁽ⁱ⁺¹⁾のエルミート性は保たれる。

詳細は以下の解説を参照。Aが実行列の場合は単純に、エルミート→対称、共役転置→転置と読み替えればよい。

コレスキー分解の再帰的アルゴリズムでは、まず最初にA⁽¹⁾を下のように置く（定義する）。

<math>\mathbf{A}^{(1)} := \mathbf{A}</math>

以下、i回目のステップ。エルミート性を保ちながらA⁽ⁱ⁾のi行とi列を前進消去して A⁽ⁱ⁺¹⁾を生成することを考える。　A⁽ⁱ⁾はi-1行・列まで前進消去されたエルミート行列であるので、下式のように書ける。

<math>\mathbf{A}^{(i)}

= \begin{pmatrix} \mathbf{I}_{i-1} & 0 & 0 \\ 0 & a_{i,i} & \mathbf{b}_{i}^{*} \\ 0 & \mathbf{b}_{i} & \mathbf{B}^{(i)} \end{pmatrix} </math>

ここで、I_i-1はi-1次の単位行列、 a_i,iはi番目の対角要素、 b_iはi列目の下三角部、 B⁽ⁱ⁾は、A⁽ⁱ⁾のi+1行・列以降の部分でやはりエルミートある。次に、Liを

<math>\mathbf{L}_{i}

=

\begin{pmatrix} \mathbf{I}_{i-1} & 0 & 0 \\ 0 & \sqrt{a_{i,i}} & 0 \\ 0 & \frac{1}{\sqrt{a_{i,i}}} \mathbf{b}_{i} & \mathbf{I}_{n-i} \end{pmatrix} </math>

と定義するとA⁽ⁱ⁾は、

<math>\mathbf{A}^{(i)}

= \mathbf{L}_{i} \mathbf{A}^{(i+1)} \mathbf(\mathbf{L}_{i})^{*} </math>

と書ける。（　A⁽ⁱ⁺¹⁾　=　Li^-1 A⁽ⁱ⁾ Li^*-1　より。）ここで、A⁽ⁱ⁺¹⁾は

<math>

\mathbf{A}^{(i+1)}

=

\begin{pmatrix} \mathbf{I}_{i-1} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \mathbf{B}^{(i)} - \frac{1}{a_{i,i}} \mathbf{b}_{i} \mathbf{b}_{i}^{*} \end{pmatrix} </math>

である。（ 注.ここでb_i b_i^* は、行列の積。 )

以上が、i回目のステップ。A⁽ⁱ⁾からA⁽ⁱ⁺¹⁾が計算出来たことになる。 nをAの次数として、このステップをn回繰り返すとA⁽ⁿ⁺¹⁾ = I_nとなりコレスキー分解は終了する。

<math>\mathbf{A}^{(1)} = \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n} \mathbf{A}^{(n+1)} \mathbf{L}_{n}^{*} \dots \mathbf{L}_{2}^{*} \mathbf{L}_{1}^{*}</math>

であり、

<math>\mathbf{L} := \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n}</math>

と置くと、（これが最終的に求めるLである。）

<math>\mathbf{A} = \mathbf{L} \mathbf{L}^{*} </math>

であることが確認できる。

コレスキー・バナキエヴィッツ法

コレスキー・バナキエヴィッツ法 は直接下三角行列 L の各エントリを計算するための式を与える。行列 L の左上隅から始め行ごとに計算を進める。

<math> l_{i,i} = \sqrt{ a_{i,i} - \sum_{k=1}^{i-1} l_{i,k} \overline{l_{i,k}} } </math>

<math> l_{i,j} = \frac{1}{l_{j,j}} \left( a_{i,j} - \sum_{k=1}^{j-1} l_{i,k} \overline{l_{j,k}} \right), \qquad\mbox{for } i>j </math>

コレスキー・クラウト法

コレスキー・クラウト法 はコレスキー・バナキエヴィッツ法とは少し異なる方法で、下三角行列Lの各エントリを計算する。すなわち、行列Lの左上隅から始め列ごとに計算を進める。使用する計算式はコレスキー Banachiewicz 法と同一である。

修正コレスキー分解

上述した分解法では、分解後の行列Lに無理数が現れることがほとんどで、コレスキー分解の結果を利用した計算が面倒となる。そこで、この欠点を解消するために考え出された方法が修正コレスキー分解である（改訂コレスキー分解と呼ぶことがある）。修正コレスキー分解では、Aが正定値行列である必要はなく

A=LDL^*

の形に分解する。ここで、Dは対角行列で、行列Lの対角成分はすべて1とする。

注意：修正コレスキー分解は行列Aが正則であっても常に存在するとは限らない（たとえば2次の対角要素がすべて０で非対角要素が１である対称な正則行列を考えよ）。

不完全コレスキー分解

不完全コレスキー分解は、修正コレスキー分解により行列Aを

A=LDL^*

と分解するところ、行列Lを後の計算が簡略化されるものに変更し、

A=LDL^*+N

と分解する手法である（Nはある行列で，この不完全分解の残差の行列である）。

共役勾配法（傾斜法）の前処理の1つとして採用されることがある。

関連項目

• en:symbolic Cholesky decomposition
• en:minimum degree algorithm

外部リンク

Cholesky分解ノート（要Acrobat Reader）