正方行列を入力し、分解タブを開いて LU(A) を押してください。答えが一つの 行列ではなく行列の対であるため、結果はすべて計算過程のパネルの中にあります。パネルはひとりでに開き、 最後に L と U を並べて表示します。Cholesky(A) も同じタブにあり、下で説明する対称な場合に 使います。
二つの因子とは何か
LU 分解は行列を A = L·U と書きます。L が下三角、U が上三角です。どちらも神秘的なもの ではありません。U は掃き出し法で得られる階段 行列そのものであり、L は途中で使った乗数を記録したものです。掃き出しを一度行えば、両方が手に入ります。
例題
| 4 | 3 |
| 6 | 3 |
| 1 | 0 |
| 3/2 | 1 |
| 4 | 3 |
| 0 | −3/2 |
L にある 3/2 は、主成分の下の 6 を消した乗数です。行列式がもう手に入っていることに注目してください。 U の対角成分を掛けて 4 · (−3/2) = −6、これに行を入れ替えた回数だけ −1 を掛けたものです。
なぜ手間をかける価値があるのか
分解が使い回せるからです。Ax = b を一から解くには n³/3 回ほどの演算が必要 です。L と U が手元にあれば、右辺が新しくなっても n² 回で済みます。前進代入で Ly = b を解き、次に後退代入で Ux = y を解くだけです。同じ連立方程式を多くの 異なる b について解く場合——工学やシミュレーションでは普通のこと——節約は膨大になります。100×100 の 行列と 50 個の右辺なら、50 回の完全な掃き出しではなく、1 回の分解と 50 回の安価な求解で済みます。
前進代入と後退代入を実際にやってみる
上に読み込まれている 3×3 の行列で見てみましょう。一度の掃き出しで二つの因子が得られます。
| 2 | 1 | 1 |
| 4 | −6 | 0 |
| −2 | 7 | 2 |
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| −1 | −1 | 1 |
| 2 | 1 | 1 |
| 0 | −8 | −2 |
| 0 | 0 | 1 |
L の成分は掃き出しで使った乗数そのものです。2 が 4 を、−1 が −2 を消し、−1 が第 2 列に残ったものを 消しました。ここで b = (4, −2, 7) について Ax = b を解きます。まず Ly = b を上から下へ。右側がすべて 0 なので、各行がその場で新しい値を一つ与えてくれます。
y₁ = 4。次に 2·4 + y₂ = −2 なので y₂ = −10。続いて −4 + 10 + y₃ = 7 なので y₃ = 1。
次に Ux = y を下から上へ。x₃ = 1。次に −8x₂ − 2 = −10 なので x₂ = 1。続いて 2x₁ + 1 + 1 = 4 なので x₁ = 1。解は (1, 1, 1) で、対角成分以外で割り算をした場面は一度もありません。行列式も同じ因子から ただで得られます。2 · (−8) · 1 = −16 です。
ピボット選択
どんな行列でも素朴な A = L·U が成り立つわけではありません。主成分の位置に 0 があると 破綻します。手当ては置換行列を入れることで、P·A = L·U となります。実際にはいずれにせよ ピボット選択を行います。利用できる中で最大の主成分を選ぶことで、丸め誤差を抑えられるからです。約束を 一つ決めれば分解は一意になります。この計算機は L の対角に 1 を置く Doolittle の約束を採用しています。
コレスキー分解——対称な場合
A が対称かつ正定値なら、A = L·Lᵀ と分解できます。行列にとっての平方根に あたるもので、三角行列は一つで足ります。対称とは A = Aᵀ のこと、正定値とはすべての固有値が 0 より 大きいことです。制約が厳しく聞こえますが、これに当てはまる行列はいたるところにあります。共分散行列、 グラム行列、最小二乗法の正規方程式、有限要素法の剛性行列は、その作られ方からしてどれも対称正定値です。
| 4 | 2 |
| 2 | 5 |
| 2 | 0 |
| 1 | 2 |
| 2 | 1 |
| 0 | 2 |
L の対角成分はどれも平方根です。ここでは √4 = 2 と √(5 − 1²) = 2 です。だからこそこの方法は、どの 根号の中身も正のままであることを要求します。この要求こそが正定値性そのものであり、アルゴリズムは そのまま判定法にもなります。分解が最後まで進めばその行列は正定値、根号の中で 0 以下の値にぶつかれば 正定値ではありません。コレスキー分解は LU のおよそ 2 倍速く、記憶領域は半分で済み、ピボット選択なしで 安定です。だから求解器はまず対称性を調べ、可能なときは必ずこちらを使います。
よくある誤り
- どんな行列でも分解できると思い込む。主成分の位置の 0 は素朴な LU を破綻させます。手当ては置換行列です：
P·A = L·U。 - 対称でない行列にコレスキー分解を使う。A = L·Lᵀ は作りからして対称なので、対称でない入力にそのような分解はありません。LU を使ってください。
- 対称でありさえすればよいと考える。負の固有値を持つ対称行列は不定値で、アルゴリズムの途中で失敗します。
- 因子が整数になると期待する。コレスキー分解の対角には平方根が入るので、A が整数でも L はたいてい無理数になります。
- 行列式で行の入れ替えを忘れる。入れ替えるたびに符号が反転します。