数値解析 第10回 (5) ピボット選択
ガウスの消去法の問題点
ガウスの消去法には次のような問題点があります：
Rem.6 Step 1 の途中で対角成分 $a_{ii}$ が $0$ になると、消去に必要な
$\dps{\frac{a_{ki}}{a_{ii}}}$
が計算できない。
また
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$ 行の持っていた誤差を増幅してしまうからです。
その対策は
部分ピボット選択
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}$ から $a_{nn}$ の中で絶対値最大の数が $a_{pq}$ であるとき、
第 $i$ 行と第 $p$ 行を入れ替え、さらに第 $i$ 列と第 $q$ 列も入れ替えるものです。
精度は部分ピボット選択より向上することが期待できますが、
- 行列が大きくなると最大要素の検索に時間が掛かる
- ( 列に釣られて ) 未知数も入れ替わってしまうのでややこしい
のがデメリットで、普通は部分ピボット選択を採用します。