コレスキー分解

コレスキー分解#

  • 読み: これすきーぶんかい

  • 英名: Cholesky Factorization

対称正定値行列 \(A\) を下三角行列 \(L\) とその転置の積に分解する手法.行列が正定値でなければ存在しない.零または負の固有値が存在する行列の場合にはピボットが零,負になるのがその理由である.負の固有値がある行列においても分解が存在するのは \(LDL^\top\) 分解である(\(D\) は対角行列,\(L\) は対角が 1 であるような下三角行列).零の固有値がある行列では,\(D\) は対角行列ではなく,\(2 \times 2\) のブロック行列を対角に並べた行列と定義すれば分解が可能となる(Bunch-Parlett 分解).

初期(’80年代)の内点法の実装では,対称正定値行列の分解を核としていたため,コレスキー分解を用いる方法が主流であったが,その方法は非零要素の多い列が係数行列に現れると行列の疎行列構造が破壊されるなどの問題があったので,現在においては,対称不定値行列を用いる方法が主流になっている.

行列の分解は内点法の性能を最も左右する部分であり,様々な工夫が凝らされてきた.ピボッティングや行列の並べ換え(リオーダーリング)もその一つである.内点法に固有の事情として,解に近づいた場合の数値的性質が悪化しやすく,現実規模の問題では,ランク落ちすることが頻繁に起きるので,その修正を行う方法が実装上のコツとして知られている.