コレスキー分解

テンプレート:脚注の不足 コレスキー分解（コレスキーぶんかい、テンプレート:Lang-en-short）とは、正定値エルミート行列 テンプレート:Mvar を下三角行列 テンプレート:Mvarと テンプレート:Mvar の共役転置 テンプレート:Mvar との積に分解することをいう。

$𝑨=𝑳{𝑳}^{*}(𝑨\in {𝑲}^{m\times m})$

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

テンプレート:Mvar が実対称行列の場合、上式の共役転置は転置に単純化される。

$𝑨=𝑳{𝑳}^T(𝑨\in {ℝ}^{n\times n})$

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

アルゴリズムの例

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

ガウスの消去法は テンプレート:Mvar の左方から順次 テンプレート:Mvar を作用させ前進消去（LU分解に対応）するが、

テンプレート:Math　　　　（　または、テンプレート:Math　）

コレスキー法は テンプレート:Mvar を順次 テンプレート:Mvar とテンプレート:Mvar で挟んで前進消去していくと考えればよい。

テンプレート:Math　 　（　または、テンプレート:Math　）

このとき テンプレート:Math のエルミート性は保たれる。

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

コレスキー分解の再帰的アルゴリズムでは、まず最初に テンプレート:Math を下のように置く（定義する）。

${𝑨}^{(1)}:=𝑨$

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

${𝑨}^{(i)}=\left[\begin{array}{ccc}{𝑰}_{i-1}& 0& 0\\ 0& a_{i,i}& {𝒃}_i^{*}\\ 0& {𝒃}_i& {𝑩}^{(i)}\end{array}\right]$

ここで、テンプレート:Math は テンプレート:Math 次の単位行列、テンプレート:Math は テンプレート:Mvar 番目の対角要素、テンプレート:Math は テンプレート:Mvar 列目の下三角部、テンプレート:Math は、テンプレート:Math のi+1行・列以降の部分でやはりエルミートである。次に、テンプレート:Math を

${𝑳}_i:=\left[\begin{array}{ccc}{𝑰}_{i-1}& 0& 0\\ 0& \sqrt{a_{i,i}}& 0\\ 0& \frac{1}{\sqrt{a_{i,i}}}{𝒃}_i& {𝑰}_{n-i}\end{array}\right]$

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

${𝑨}^{(i)}={𝑳}_i{𝑨}^{(i+1)}{𝑳}_i^{*}$

と書ける（テンプレート:Mathより）。ここで、テンプレート:Math は

${𝑨}^{(i+1)}=\left[\begin{array}{ccc}{𝑰}_{i-1}& 0& 0\\ 0& 1& 0\\ 0& 0& {𝑩}^{(i)}-\frac{1}{a_{i,i}}{𝒃}_i{𝒃}_i^{*}\end{array}\right]$

である（ 注.ここで テンプレート:Math は、行列の積 )。

以上が、テンプレート:Mvar 回目のステップである。これにより、テンプレート:Math から テンプレート:Math が計算出来たことになる。テンプレート:Mvar を テンプレート:Mvar の次数として、このステップを テンプレート:Mvar 回繰り返すと テンプレート:Math = テンプレート:Mathとなりコレスキー分解は終了する。

${𝑨}^{(1)}={𝑳}_1{𝑳}_2\cdots {𝑳}_n{𝑨}^{(n+1)}{𝑳}_n^{*}\cdots {𝑳}_2^{*}{𝑳}_1^{*}$

であり、

$𝑳:={𝑳}_1{𝑳}_2\cdots {𝑳}_n$

と置くと、（これが最終的に求める テンプレート:Mvar である。）

$𝑨=𝑳{𝑳}^{*}$

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

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

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

$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}}(a_{i,j}-\sum _{k=1}^{j-1}{l}_{i,k}\overline{l_{j,k}}),\text{for }i>j$

コレスキー・クラウト法

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

修正コレスキー分解

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

$𝑨={𝑳𝑫𝑳}^{*}$

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

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

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

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

不完全コレスキー分解

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

$𝑨={𝑳𝑫𝑳}^{*}$

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

$𝑨={𝑳𝑫𝑳}^{*}+𝑵$

の形に分解する手法である。ここで、行列 テンプレート:Mvar は分解の残差と呼ばれる。

共役勾配法（傾斜法）などの反復法による連立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

外部リンク

• テンプレート:PDFlink