数値解析 第11回 (5) ピボット選択
ピボット選択の必要性
Step 1、Step 2 では $\dps{\frac{1}{\ell_{ii}}}$ の値が必要ですので、
ガウスの消去法のときと同様に、
$\ell_{ii}=0$ では計算できませんし、
$|\,\ell_{ii}\,|$ が小さくても精度が良くありません。
そこで、やはり部分ピボット選択を使います。
ピボット選択実装上の注意
- Setp 1 のアルゴリズム ver.1 では「 $\ell_{ii}$ になり得る値」の計算に手間がかかりますので、
ver.2 を用います。第 $i-1$ 行までの処理が終わった時点で $a_{ii}$, $\cdots$, $a_{ni}$ の中で絶対値最大の要素を $a_{pi}$ として、第 $i$ 行と第 $p$ 行を入れ替えます。
- LU 分解法の Step 1 では $\bbb$ を扱いませんので、
行の入れ替えを行うと未知数の番号も入れ替わってしまいます。
その「入れ替わり方」を覚えておかないといけません。
具体的には次のようにします:
- int 型の配列 s[ ] を用意し、初期値は s[i] = i とする
- 第 $i$ 行と第 $p$ 行を入れ替えたら s[i] と s[p] を入れ替える
- Step 2 では b[i] の代わりに b[s[i]] を入れて計算する