数値解析 第11回 (5) ピボット選択

ピボット選択の必要性

 Step 1、Step 2 では $\dps{\frac{1}{\ell_{ii}}}$ の値が必要ですので、 ガウスの消去法のときと同様に、 $\ell_{ii}=0$ では計算できませんし、 $|\,\ell_{ii}\,|$ が小さくても精度が良くありません。 そこで、やはり部分ピボット選択を使います。

ピボット選択実装上の注意

  1. Setp 1 のアルゴリズム ver.1 では「 $\ell_{ii}$ になり得る値」の計算に手間がかかりますので、 ver.2 を用います。第 $i-1$ 行までの処理が終わった時点で $a_{ii}$, $\cdots$, $a_{ni}$ の中で絶対値最大の要素を $a_{pi}$ として、第 $i$ 行と第 $p$ 行を入れ替えます。
  2. LU 分解法の Step 1 では $\bbb$ を扱いませんので、 行の入れ替えを行うと未知数の番号も入れ替わってしまいます。 その「入れ替わり方」を覚えておかないといけません。 具体的には次のようにします:
  1. int 型の配列 s[ ] を用意し、初期値は s[i] = i とする
  2. 第 $i$ 行と第 $p$ 行を入れ替えたら s[i] と s[p] を入れ替える
  3. Step 2 では b[i] の代わりに b[s[i]] を入れて計算する