1 基本概念
Cholesky分解は、実対称正定値行列を、下三角行列とその転置の積に表す方法である。元の行列の構造を直接利用するため、一般の分解法より計算の手間が少なく、数値計算の基本手法として広く扱われる。
1.1 定義
正方行列 \(A\) が実対称正定値であるとき、ある下三角行列 \(L\) を用いて \[ A = LL^{\mathsf T} \] と表す分解をCholesky分解という。複素数の場合には、転置の代わりに共役転置を用いる。
1.2 対象となる行列
この分解が適用されるのは、対称性と正定値性を満たす行列である。両方の条件がそろうことで、計算途中に現れる平方根や割り算が安定に定義される。
1.2.1 対称性
対称行列とは、転置しても成分が変わらない行列である。Cholesky分解では、元の行列の上側と下側が一致していることを前提に、計算対象を半分程度に絞ることができる。
1.2.2 正定値性
正定値性とは、零でない任意のベクトル \(x\) に対して \(x^{\mathsf T}Ax>0\) が成り立つ性質をいう。これは分解の各段階で対角成分の平方根を取る際に、負の値が現れないことを保証する。
1.3 分解の表現
分解の結果として得られる \(L\) は下三角行列であり、対角成分は通常正の実数に取る。こうすると分解は標準形として定まり、以後の計算や比較が容易になる。
2 性質
Cholesky分解は、単なる記法上の変形ではなく、解の一意性や計算効率に関して明確な利点を持つ。特に、対称正定値行列に限ることで、一般分解よりも簡潔な手順が成立する。
2.1 一意性
対角成分を正に選ぶと、Cholesky分解は一意に定まる。別の選び方を許すと符号の自由度が生じるが、通常は対角を正に固定して標準的な形を採用する。
2.2 存在条件
分解が存在するのは、基本的に実対称正定値行列である場合である。実用上は、行列が厳密に正定値かどうか、あるいは丸め誤差の影響で近似的にその条件を満たすかが重要になる。
2.3 数値安定性
この分解は、LU分解を一般に適用するよりも、対称正定値行列に対して安定なことが多い。余分な演算を抑えられるため、誤差の蓄積が比較的小さく、実装上も信頼性が高い。
2.4 計算量
対称性を利用することで、必要な演算回数は一般の行列分解より少なくなる。n次正方行列に対して、計算量はおおむね \(O(n^3)\) だが、定数係数が小さく、実際には高速に動作する。
3 計算法
Cholesky分解の計算は、各成分を順に求める方法として導かれる。理論式から直接構成するやり方と、実装に適した逐次的なアルゴリズムの両方が知られている。
3.1 成分ごとの導出
行列の積 \(A=LL^{\mathsf T}\) を成分表示すると、対角要素と非対角要素に対応する連立関係が得られる。これを上から順に解くと、各列の要素が前に求めた値から計算できる。
3.2 行列形式による導出
行列を部分行列に分けて考えると、未確定部分をまとめて扱える。これにより、分解の構造が見通しよくなり、ブロック演算や高性能実装への接続もしやすくなる。
3.3 アルゴリズム
実際の計算では、行列を左上から順に処理し、既知の部分を使って次の要素を決定する。対称性を活かして不要な領域を再計算しないことが、効率化の要点である。
3.3.1 標準的な計算手順
標準法では、対角成分を求め、続いて同じ列の下側成分を計算する。各段階で内積を使い、既に得られた値を差し引いたうえで平方根や割り算を行う。
3.3.2 逐次計算
逐次計算では、1行または1列ずつ処理を進める。メモリ使用量を抑えやすく、巨大な行列を扱う場面でも実用的である。
3.3.3 ブロック分割法
ブロック分割法では、行列を小さな部分に区切って分解を行う。行列演算をまとまった単位で処理できるため、キャッシュ効率や並列化の面で有利になる。
4 応用
Cholesky分解は、線形方程式の解法をはじめ、行列式、逆行列、統計学、最適化などに応用される。いずれの用途でも、対称正定値という性質が計算の簡略化に直結する。
4.1 連立一次方程式の解法
\(Ax=b\) を解くとき、まず \(A=LL^{\mathsf T}\) と分解し、次に \(Ly=b\) と \(L^{\mathsf T}x=y\) を順に解く。前進代入と後退代入を組み合わせることで、直接法として効率よく解を得られる。
4.2 行列式の計算
行列式は、三角行列の対角成分の積で求められる。したがって、\(A=LL^{\mathsf T}\) なら、\(\det(A)\) は \(L\) の対角成分を用いて比較的簡単に計算できる。
4.3 逆行列の計算
逆行列を明示的に作る必要がある場合も、分解を介すると扱いやすい。実際には、逆行列そのものを直接求めるより、必要な右辺に対して連立方程式を解く形で利用することが多い。
4.4 統計学への応用
統計学では、共分散行列の分解や確率分布の生成に用いられる。特に多変量のデータ解析では、相関構造を反映した計算を安定に行える点が重視される。
4.4.1 共分散行列の分解
共分散行列はしばしば対称正定値となるため、Cholesky分解の典型的な対象である。分解によって、変数間の依存関係を扱いやすい形に変えられる。
4.4.2 多変量正規分布
多変量正規分布の乱数生成では、独立な標準正規乱数に分解行列を掛けることで、所望の共分散を持つサンプルを作れる。これにより、シミュレーションやモンテカルロ計算が容易になる。
4.5 最適化問題への応用
制約付き・制約なしの最適化では、ヘッセ行列が正定値のときにCholesky分解が利用される。二次計画やニュートン法では、連立方程式の解法を安定に支える補助手段となる。
5 派生と一般化
基本形のほかにも、符号や構造を変えた類似の分解がある。対象行列の性質が異なる場合には、拡張版や修正版が使い分けられる。
5.1 上三角型分解
下三角行列の代わりに上三角行列を用いる表現もある。この場合は \[ A = R^{\mathsf T}R \] の形で書かれ、記法の違いにすぎないが、実装や文脈によってこちらが選ばれることもある。
5.2 不定値行列への拡張
対称だが正定値ではない行列には、通常のCholesky分解はそのまま適用できない。こうした場合には、符号を含む別の分解法が検討され、負の固有値を含む構造を扱えるようにする。
5.3 修正分解
元の行列が厳密な条件を満たさない場合、数値計算上の都合から修正版が用いられる。これにより、失敗を避けたり、近似的に扱ったりできる。
5.3.1 数値的改良
対角要素の微調整や丸め誤差への対策を行い、実際の計算で分解不能になる事態を減らす。大規模計算では、こうした改良が安定動作に重要である。
5.3.2 近似分解
厳密な分解の代わりに、元の行列に近い正定値行列を構成して分解する方法がある。近似誤差を管理しながら、計算可能な形へ置き換える発想である。
6 関連する分解
Cholesky分解は、他の行列分解と深く関係している。とくにLU分解、固有値分解、QR分解との比較により、その特徴が明確になる。
6.1 ＬＵ分解との関係
LU分解は一般の正方行列に使えるが、Cholesky分解は対称正定値行列に特化している。その代わり、対称性を活かして計算が簡潔になり、通常はより少ない演算で済む。
6.2 固有値分解との関係
固有値分解は行列を固有ベクトルと固有値に基づいて表す方法である。Cholesky分解とは目的が異なるが、正定値性の判定や行列の構造理解において相補的に用いられる。
6.3 ＱＲ分解との比較
QR分解は直交行列と上三角行列に分ける手法で、最小二乗法などに頻用される。Cholesky分解は対象が限定される一方、条件が合えばより軽量に計算できる点が利点である。
7 歴史
Cholesky分解は、20世紀初頭の数値計算や測地、測量の文脈で発展した。理論的背景と実務上の需要が結びつき、後に線形代数の標準的手法として定着した。
7.1 研究の背景
行列計算の体系化が進むにつれて、対称正定値行列を効率よく扱う方法が求められた。特に手計算や初期の機械計算では、演算数の削減が重要な課題だった。
7.2 名称の由来
名称は、関連する方法を整備したフランスの将校・数学者アンドレ＝ルイ・シャルル・ショレの名に由来する。英語表記の綴りがそのまま一般化し、現在の呼称として定着した。
7.3 発展と普及
計算機の発達に伴い、Cholesky分解は数値線形代数の基本部品となった。現在では、科学計算、統計解析、工学シミュレーションなどで標準的に用いられている。