コレスキー分解のソースを表示

{{脚注の不足|date=2022年7月}}
'''コレスキー分解'''（コレスキーぶんかい、{{Lang-en-short|Cholesky decomposition, Cholesky factorization}}）とは、[[固有値#正定値と半正定値|正定値]][[エルミート行列]] {{Mvar|'''A'''}} を[[三角行列|下三角行列]] {{Mvar|'''L'''}}と {{Mvar|'''L'''}} の[[随伴作用素|共役転置]] {{Mvar|'''L'''<sup>*</sup>}} との積に分解することをいう。
: <math>\boldsymbol{A} = \boldsymbol{L} \boldsymbol{L}^{*} \qquad (\boldsymbol{A} \in \boldsymbol{K}^{m \times m})</math>

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

{{Mvar|'''A'''}} が実[[対称行列]]の場合、上式の共役転置は[[転置行列|転置]]に単純化される。

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

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

== アルゴリズムの例 ==
'''コレスキー法'''は[[ガウスの消去法]]の改良版である。

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

{{Math|1='''''A'''''<sup>(''i'')</sup> = '''''L'''''<sub>''i''</sub> '''''A'''''<sup>(''i''+1)</sup>}}　　　　（　または、{{Math|1='''''A'''''<sup>(''i''+1)</sup> = '''''L'''''<sub>''i''</sub><sup>&minus;1</sup> '''''A'''''<sup>(''i'')</sup>}}　）

コレスキー法は {{Mvar|A}} を順次 {{Mvar|L}} と{{Mvar|''L''<sup>*</sup>}} で挟んで前進消去していくと考えればよい。

{{Math|1='''''A'''''<sup>(''i'')</sup> = '''''L'''''<sub>''i''</sub> '''''A'''''<sup>(''i''+1)</sup> '''''L'''''<sup>*</sup>}}　   　（　または、{{Math|1='''''A'''''<sup>(''i''+1)</sup> = '''''L'''''<sub>''i''</sub><sup>&minus;1</sup> '''''A'''''<sup>(''i'')</sup> '''''L'''''<sub>''i''</sub><sup>&minus;1*</sup>}}　）

このとき {{Math|''A''<sup>(''i''+1)</sup>}} のエルミート性は保たれる。

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


コレスキー分解の再帰的アルゴリズムでは、まず最初に {{Math|'''''A'''''<sup>(1)</sup>}} を下のように置く（定義する）。

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

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

: <math>\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}
</math>

ここで、{{Math|'''''I'''''<sub>''i''&minus;1</sub>}} は {{Math|''i'' &minus; 1}} 次の[[単位行列]]、{{Math|''a''<sub>''i'', ''i''</sub>}} は {{Mvar|i}} 番目の対角要素、{{Math|'''''b'''''<sub>''i''</sub>}} は {{Mvar|i}} 列目の下三角部、{{Math|'''''B'''''<sup>(''i'')</sup>}} は、{{Math|'''''A'''''<sup>(''i'')</sup>}} の''i''+1行・列以降の部分でやはりエルミートである。次に、{{Math|'''''L'''''<sub>''i''</sub>}} を

:<math>\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}
</math>

と定義すると'''''A'''''<sup>(''i'')</sup>は、

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

と書ける（{{Math|1='''''A'''''<sup>(''i''+1)</sup> = '''''L'''''<sub>''i''</sub><sup>&minus;1</sup> '''''A'''''<sup>(''i'')</sup> '''''L'''''<sub>''i''</sub><sup>*&minus;1</sup>}}より）。ここで、{{Math|'''''A'''''<sup>(''i''+1)</sup>}} は

:<math>
\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}
</math>

である（ '''注'''.ここで {{Math|'''''b'''''<sub>''i''</sub> '''''b'''''<sub>''i''</sub><sup>*</sup>}} は、行列の積 )。

以上が、{{Mvar|i}} 回目のステップである。これにより、{{Math|'''''A'''''<sup>(''i'')</sup>}} から {{Math|'''''A'''''<sup>(''i''+1)</sup>}} が計算出来たことになる。{{Mvar|n}} を {{Mvar|'''A'''}} の次数として、このステップを {{Mvar|n}} 回繰り返すと {{Math|'''''A'''''<sup>(''i''+1)</sup>}} = {{Math|'''''I'''''<sub>''n''</sub>}}となりコレスキー分解は終了する。

:<math>\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}^{*}</math>
であり、
:<math>\boldsymbol{L} := \boldsymbol{L}_{1} \boldsymbol{L}_{2} \dotsb \boldsymbol{L}_{n}</math>
と置くと、（これが最終的に求める {{Mvar|'''L'''}} である。）
: <math>\boldsymbol{A} = \boldsymbol{L} \boldsymbol{L}^{*} </math>
であることが確認できる。
=== コレスキー・バナキエヴィッツ法 ===
'''コレスキー・バナキエヴィッツ法''' は直接下三角行列 {{Mvar|'''L'''}} の各エントリを計算するための式を与える。行列 {{Mvar|'''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>

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

=== 注意 ===
コレスキー Banachiewicz 法とコレスキークラウト法をまとめて'''平方根法'''と呼ぶこともある。
-->

== 修正コレスキー分解 ==
上述した分解法では、計算に平方根演算を用いるため、分解後の行列Lに無理数が現れるのが普通であり、コレスキー分解の結果を利用した後の計算が面倒となる。特に{{Mvar|'''A'''}}が実対称であっても正定値でないときには平方根の中に負の数が現れるので、単純に適用すると複素数の演算が必要になる。そこで、この欠点を解消するために考え出された方法が'''修正コレスキー分解'''である（'''改訂コレスキー分解'''と呼ぶことがある）。この方法では平方根演算を用いずに四則演算だけで計算を行う。そのため行列が実対称であれば計算は実数の四則演算だけで行える。
修正コレスキー分解では、
: <math>\boldsymbol{A} = \boldsymbol{LDL}^{*} </math>
の形に分解の計算を行なう。ここで、{{Mvar|'''D'''}} は[[対角行列]]で、行列 {{Mvar|'''L'''}} の対角成分はすべて1とする。
ただし分解途中で零ピボットによる割り算が生じると計算は破綻し分解が存在しない可能性もある。

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

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

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

== 不完全コレスキー分解 ==
'''不完全コレスキー分解'''とは、係数が（通常は疎な）対称行列<math>A</math>の連立1次方程式を解くのに際して、修正コレスキー分解であれば行列 {{Mvar|'''A'''}} を
: <math>\boldsymbol{A} = \boldsymbol{LDL}^{*} </math>
と分解するところを、分解途中と分解後の前進後退代入の計算量を減らすためおよび行列<math>L</math>の非零要素を格納する記憶の量を抑えるために、なるべく行列 {{Mvar|'''L'''}} の非零要素数を抑えて、
: <math>\boldsymbol{A} = \boldsymbol{LDL}^{*} + \boldsymbol N </math>
の形に分解する手法である。ここで、行列 {{Mvar|'''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]]

== 外部リンク ==
* {{PDFlink|[http://nalab.mind.meiji.ac.jp/~mk/labo/text/cholesky.pdf Cholesky分解ノート]}}

{{linear algebra}}
{{DEFAULTSORT:これすきふんかい}}
[[Category:行列]]
[[Category:行列の分解]]
[[Category:数値線形代数]]
[[Category:関数解析学]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]