コレスキー分解

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

${\boldsymbol {A}}={\boldsymbol {L}}{\boldsymbol {L}}^{*}\qquad ({\boldsymbol {A}}\in {\boldsymbol {K}}^{m\times m})$${\boldsymbol {A}}={\boldsymbol {L}}{\boldsymbol {L}}^{*}\qquad ({\boldsymbol {A}}\in {\boldsymbol {K}}^{m\times m})$
A のエルミート性を利用したLU分解の特別な場合である。L の対角成分は実数にとることができて︵符号・位相の自由度があるが︶通常は、対角成分を正の実数に採り、その場合には、L は一意に定まる。アンドレ＝ルイ・コレスキー︵仏語の発音はショレスキー︶にちなんで名づけられた。

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

${\boldsymbol {A}}={\boldsymbol {L}}{\boldsymbol {L}}^{T}\qquad ({\boldsymbol {A}}\in \mathbb {R} ^{n\times n})$${\boldsymbol {A}}={\boldsymbol {L}}{\boldsymbol {L}}^{T}\qquad ({\boldsymbol {A}}\in \mathbb {R} ^{n\times n})$
エルミート対称行列 Aが正定値であることと、A のコレスキー分解が存在することは同値になる。

アルゴリズムの例

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

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

A⁽ⁱ⁾ = L_iA⁽ⁱ⁺¹⁾　　　　︵　または、A⁽ⁱ⁺¹⁾ = L_i⁻¹ A⁽ⁱ⁾　︶

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

A⁽ⁱ⁾ = L_iA⁽ⁱ⁺¹⁾ L^*　 　︵　または、A⁽ⁱ⁺¹⁾ = L_i⁻¹ A⁽ⁱ⁾ L_i^−1*　︶

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

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


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

${\displaystyle {\boldsymbol {A}}^{($1)}:={\boldsymbol {A}}}  

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

${\displaystyle {\boldsymbol {A}}^{($i)}={\begin{bmatrix}{\boldsymbol {I}}_{i-1}&0&0\\0&a_{i,i}&{\boldsymbol {b}}_{i}^{*}\\0&{\boldsymbol {b}}_{i}&{\boldsymbol {B}}^{(i)}\end{bmatrix}}}  

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

${\boldsymbol {L}}_{i}:={\begin{bmatrix}{\boldsymbol {I}}_{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\dfrac {1}{\sqrt {a_{i,i}}}}{\boldsymbol {b}}_{i}&{\boldsymbol {I}}_{n-i}\end{bmatrix}}$ 

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

${\displaystyle {\boldsymbol {A}}^{($i)}={\boldsymbol {L}}_{i}{\boldsymbol {A}}^{(i+1)}{\boldsymbol {L}}_{i}^{*}}  

と書ける︵A⁽ⁱ⁺¹⁾ = L_i⁻¹ A⁽ⁱ⁾ L_i^*−1より︶。ここで、A⁽ⁱ⁺¹⁾ は

${\displaystyle {\boldsymbol {A}}^{(i+1)}={\begin{bmatrix}{\boldsymbol {I}}_{i-1}&0&0\\0&1&0\\0&0&{\boldsymbol {B}}^{($i)}-{\dfrac {1}{a_{i,i}}}{\boldsymbol {b}}_{i}{\boldsymbol {b}}_{i}^{*}\end{bmatrix}}}  

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

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

${\displaystyle {\boldsymbol {A}}^{($1)}={\boldsymbol {L}}_{1}{\boldsymbol {L}}_{2}\dotsb {\boldsymbol {L}}_{n}{\boldsymbol {A}}^{(n+1)}{\boldsymbol {L}}_{n}^{*}\dotsb {\boldsymbol {L}}_{2}^{*}{\boldsymbol {L}}_{1}^{*}}  

であり、

${\boldsymbol {L}}:={\boldsymbol {L}}_{1}{\boldsymbol {L}}_{2}\dotsb {\boldsymbol {L}}_{n}$ 

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

${\boldsymbol {A}}={\boldsymbol {L}}{\boldsymbol {L}}^{*}$ 

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

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

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

$l_{i,i}={\sqrt {a_{i,i}-\sum _{k=1}^{i-1}l_{i,k}{\overline {l_{i,k}}}}}$

$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$

コレスキー・クラウト法

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

修正コレスキー分解

上述した分解法では、計算に平方根演算を用いるため、分解後の行列Lに無理数が現れるのが普通であり、コレスキー分解の結果を利用した後の計算が面倒となる。特にAが実対称であっても正定値でないときには平方根の中に負の数が現れるので、単純に適用すると複素数の演算が必要になる。そこで、この欠点を解消するために考え出された方法が修正コレスキー分解である︵改訂コレスキー分解と呼ぶことがある︶。この方法では平方根演算を用いずに四則演算だけで計算を行う。そのため行列が実対称であれば計算は実数の四則演算だけで行える。 修正コレスキー分解では、

${\boldsymbol {A}}={\boldsymbol {LDL}}^{*}$ 

の形に分解の計算を行なう。ここで、D は対角行列で、行列 Lの対角成分はすべて1とする。 ただし分解途中で零ピボットによる割り算が生じると計算は破綻し分解が存在しない可能性もある。

注意‥修正コレスキー分解は行列が正則であっても存在しない場合がある︵たとえば対角要素が0で非対角要素が1である2次の対称行列は、正則であるがコレスキー分解や修正コレスキー分解が存在しない簡単な例である︶.行列が定値であるときには分解は必ず存在する. 零による割り算の困難を対称なピボット交換で回避できる場合もあるが、上記の2次の対称行列の例のように回避が不可能な場合がある。

修正コレスキー分解をさらに拡張して、Ｄを対称な三重対角行列とするAasenの方法、あるいはＤを1次あるいは2次の対称行列からなるブロック対角行列とする分解を行うBunch-Kaufmanの方法などが知られており、それらの場合には分解が必ず存在する.

なお、行列$A$ が複素対称︵$A^{T}=A$ ︶の場合にも、実対称の場合と同様の四則演算を複素数を用いて行うことにより︵途中で計算が破綻しなければ︶分解$A=LDL^{T}$ が得られる。

不完全コレスキー分解

不完全コレスキー分解とは、係数が︵通常は疎な︶対称行列$A$ の連立1次方程式を解くのに際して、修正コレスキー分解であれば行列 Aを

${\boldsymbol {A}}={\boldsymbol {LDL}}^{*}$ 

と分解するところを、分解途中と分解後の前進後退代入の計算量を減らすためおよび行列$L$ の非零要素を格納する記憶の量を抑えるために、なるべく行列 Lの非零要素数を抑えて、

${\boldsymbol {A}}={\boldsymbol {LDL}}^{*}+{\boldsymbol {N}}$ 

の形に分解する手法である。ここで、行列 Nは分解の残差と呼ばれる。

共役勾配法︵傾斜法︶などの反復法による連立1次方程式の解法において前処理の1つとして利用されることがある。

参考文献

英文

• Dereniowski, Dariusz; Kubale, Marek (2004). "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs". 5th International Conference on Parallel Processing and Applied Mathematics. Lecture Notes on Computer Science. 3019. Springer-Verlag. pp. 985–992. doi:10.1007/978-3-540-24669-5_127. ISBN 978-3-540-21946-0.
• Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. en:Cambridge University Press. ISBN 0-521-38632-2.
• Trefethen, Lloyd N.; Bau, David (1997). Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9.

和文

• 山本哲朗『数値解析入門』サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月、増訂版。ISBN 4-7819-1038-6。
• 森正武. 数値解析 第2版. 共立出版.
• 数値線形代数の数理とHPC, 櫻井鉄也, 松尾宇泰, 片桐孝洋編（シリーズ応用数理 / 日本応用数理学会監修, 第6巻）共立出版, 2018.8

関連項目

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

外部リンク

• Cholesky分解ノート (PDF)