消去法を記録する
ガウスの消去法は、ある行の定数倍を下の行から引いていき、上三角行列 U にして Ax=b を解きます。使った係数(乗数)は記録しておく価値があります。対角成分が1の下三角行列 L の対角より下に並べると A=LU になります。この分解は消去の全過程を記録しているので、計算は一度だけで再利用できます。
A=LU,Ly=b,Ux=y(1) 解くときは、まず Ly=b を前進代入(上から下)で、次に Ux=y を後退代入(下から上)で解きます。それぞれ約 n2 回の演算で、分解自体は約 32n3 回です。右辺が多数ある(同じ行列で多くのシナリオを試す)場合は、一度分解すればシナリオごとに n2 だけで済みます。
LU分解を手で行うA=(2415) とします。乗数は
4/2=2 で、第2行から第1行の2倍を引くと
U=(2013)、
L=(1201) です。確認:
LU=(2412+3)=A。
Ax=(3,9) を解くと、
Ly=b から
y1=3、
y2=9−2⋅3=3。次に
Ux=y から
x2=1、
2x1+1=3 なので
x=(1,1) です。
- L:下三角行列。対角は1で、その下に消去の乗数が並ぶ。
- U:上三角行列。消去の結果で、対角成分がピボット。
- ピボット選択:行を入れ替えてピボットを大きくし、置換行列 P を使って PA=LU とする。
ゼロや極小のピボットには行の入れ替えが必要(0111) では最初のピボットが0なので、単純な消去は0で割ってしまいますが、この行列は完全に正則です。行を入れ替えれば解決します。ピボットが0ではなく極小の場合は、止まりはしませんが巨大な乗数が生じて精度が壊れます。実際のライブラリが必ずピボット選択を行う理由です。 ラボ:採点される内容
- 行列 L15点
- 行列 U15点
- U から行列式を求める15点
- LとUで解く15点
- なぜピボット選択か15点
- LUで解く手順10点
- 一度だけ分解する理由15点