コレスキー分解

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

コレスキー分解(コレスキーぶんかい、: Cholesky decomposition, Cholesky factorization)とは、正定値エルミート行列 A下三角行列 LL共役転置 L* との積に分解することをいう。

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

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

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

アルゴリズムの例[編集]

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

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

A(i) = Li A(i+1)    ( または、A(i+1) = Li−1 A(i) )

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

A(i) = Li A(i+1) L*   ( または、A(i+1) = Li−1 A(i) Li−1* )

このとき A(i+1) のエルミート性は保たれる。

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


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

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

ここで、Ii−1i − 1 次の単位行列ai, ii 番目の対角要素、bii 列目の下三角部、B(i) は、A(i) のi+1行・列以降の部分でやはりエルミートある。次に、Li

と定義するとA(i)は、

と書ける(A(i+1) = Li−1 A(i) Li*−1より)。ここで、A(i+1)

である( .ここで bi bi* は、行列の積 )。

以上が、i 回目のステップである。これにより、A(i) から A(i+1) が計算出来たことになる。nA の次数として、このステップを n 回繰り返すと A(i+1) = Inとなりコレスキー分解は終了する。

であり、

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

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

コレスキー・バナキエヴィッツ法[編集]

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

コレスキー・クラウト法[編集]

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

修正コレスキー分解[編集]

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

の形に平方根演算を使わずに四則演算だけを用いて分解の計算を行なうことができる。ここで、D対角行列で、行列 L の対角成分はすべて1とする。

注意:対称行列は正則であってもその修正コレスキー分解が存在しない場合がある(たとえば対角要素が0で非対角要素が1である2次の対称行列は、正則でも修正コレスキー分解が存在しない例である)。正定値行列であれば,分解は必ず存在する。

不完全コレスキー分解[編集]

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

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

と分解する手法である(N はある行列で,この不完全分解の残差の行列である)。

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

関連項目[編集]

外部リンク[編集]