LU 分解を一歩ずつ

行列を下三角と上三角に分解する方法、消去をやり直すより速い理由、そしてコレスキー分解という特別な場合。

LU 分解は、正方行列を下三角行列と上三角行列の積として書きます：A = L·U。この 2 つの因子はガウスの消去法からそのまま得られます。U は行階段形そのもので、L はそこへ至るのに使った乗数を記録したものです。

なぜ役に立つのか

分解を使い回せるからです。Ax = b を一から解くとおよそ n³/3 回の演算がかかります。L と U さえ手元にあれば、右辺が新しくなっても n² で済みます。前進代入で Ly = b を解き、後退代入で Ux = y を解くだけです。右辺が何十本もあるなら、この差は大きな利得になります。

行列式もついでに手に入ります。U の対角成分の積に、行を入れ替えた回数だけ −1 を掛けたものです。

枢軸選択

どんな行列でも素朴な A = L·U ができるわけではありません。枢軸の位置に 0 があると破綻します。対処法は置換行列を入れて P·A = L·U とすることです。実際にはいずれにせよ枢軸選択を行います。使える中で最大の枢軸を選ぶと丸め誤差を抑えられるからです。

コレスキー分解：対称な場合

A が対称かつ正定値なら、A = L·Lᵀ と分解できます——三角因子はひとつで足ります。コレスキー分解は LU のおよそ 2 倍速く、数値的にも非常に安定しているため、最適化・最小二乗法・統計で主流になっています（共分散行列は作り方からして対称正定値です）。

途中で負の数の平方根が必要になったら、その行列は正定値ではなかったということです。コレスキー分解はその判定法も兼ねています。