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

ガウスの消去法の問題点

 ガウスの消去法には次のような問題点があります:
Rem.6 Step 1 の途中で対角成分 $a_{ii}$ が $0$ になると、消去に必要な
$\dps{\frac{a_{ki}}{a_{ii}}}$
が計算できない。
また、たとえ $a_{ii} \neq 0$ であっても
Rem.7 $|\,a_{ii}\,|$ が小さいと精度が良くない。
何故かというと、$|\,a_{ii}\,|$ が小さいときは $\dps{\left|\,\frac{a_{ki}}{a_{ii}}\,\right|}$ が大きいので、
$\dps{\left(\frac{a_{ki}}{a_{ii}}\right)\times }$ 第 $i$ 行
という計算で第 $i$ 行の持っていた誤差を増幅してしまうからです。

 その対策として、$a_{ii}$ が大きくなるように行を入れ換えることを考えましょう。 (方程式の式番号を取り換えることに相当します。)

部分ピボット選択

 Step 1 の処理が第 $i-1$ 行目まで進んだ時には
$\require{color} \dps{ \mat{ccc|ccc|c}{ a_{11} & \cdots & a_{1,i-1} & a_{1i} & \cdots & a_{1n} & b_1 \\[-0.5em] \vdots & \ddots & \vdots & \vdots & \cdots & \vdots &\vdots \\ 0 & \cdots & a_{i-1,i-1} & a_{i-1,i} &\cdots & a_{i-1,n} & b_{i-1} \\\hline 0 & \cdots & 0 & \textcolor{red}{a_{ii}} & \cdots & a_{in} & b_{i} \\[-0.5em] \vdots & \vdots & \vdots & \textcolor{red}{\vdots} & \ddots & \vdots & \vdots \\ 0 & \cdots & 0 & \textcolor{red}{a_{ni}} & \cdots & a_{nn} & b_n\\} }$
の形になっていますが、赤字の $a_{ii}$, $\cdots$, $a_{ni}$ の中で 絶対値最大の数が $a_{pi}$ であるとき、 第 $i$ 行と第 $p$ 行を入れ替えます。すると
新 $a_{ii}=$ 元 $a_{pi}$
の絶対値が大きくなるので上記の問題点が解消されるだろう、という作戦です。これを「部分ピボット選択」と言います。

※ バスケットボールで、軸足を止めてもう片方の足を動かす技を「ピボット」と言いますが、そのピボットです。

完全ピボット選択

 完全ピボット選択というテクニックもあります。これは
$\require{color} \dps{ \mat{ccc|ccc|c}{ a_{11} & \cdots & a_{1,i-1} & a_{1i} & \cdots & a_{1n} & b_1 \\[-0.5em] \vdots & \ddots & \vdots & \vdots & \cdots & \vdots &\vdots \\ 0 & \cdots & a_{i-1,i-1} & a_{i-1,i} &\cdots & a_{i-1,n} & b_{i-1} \\\hline 0 & \cdots & 0 & \textcolor{red}{a_{ii}} & \textcolor{red}{\cdots} & \textcolor{red}{a_{in}} & b_{i} \\[-0.5em] \vdots & \vdots & \vdots & \textcolor{red}{\vdots} & \textcolor{red}{\ddots} & \textcolor{red}{\vdots} & \vdots \\ 0 & \cdots & 0 & \textcolor{red}{a_{ni}} & \textcolor{red}{\cdots} & \textcolor{red}{a_{nn}} & b_n\\} }$
赤字の部分 $a_{ii}$, $\cdots$, $a_{nn}$ の中で 絶対値最大の数が $a_{pq}$ であるとき、 第 $i$ 行と第 $p$ 行を入れ替え、さらに第 $i$ 列と第 $q$ 列も入れ替えるものです。 精度は部分ピボット選択より向上することが期待できますが、
  • 行列が大きくなると最大要素の検索に時間が掛かる
  • ( 列に釣られて ) 未知数も入れ替わってしまうのでややこしい
のがデメリットで、普通は部分ピボット選択を採用します。