数値解析 第3回 (2) 二分法

二分法のアイデア

 情報科学では「二分割する作戦」が良く出てきますが、ここでは「解の存在範囲」を二分割します。 「存在範囲を二分割する」する作業を繰り返して解を追い詰めていこう、という作戦です。 そのキーポイントは
中間値の定理 $f(x)$ が連続関数で、区間 $[\,a,\ b,]$ の両端で
$f(a) \times f(b) \lt 0$
であれば、その区間内に少なくとも1つ $f(x)=0$ の解 $\alpha$ が存在する。
 これをどう使うかと言うと、
二分法のアイデア さらに $a$ と $b$ の中点 $\dps{c=\frac{a+b}{2}}$ を考える。
  1. もし $f(a) \times f(c) \leqq 0$ であれば、区間 $a \lt x \leqq c$ に少なくとも1つ $f(x)=0$ の解が存在し、
  2. そうでなければ区間 $c \lt x \lt b$ に少なくとも1つ $f(x)=0$ の解が存在する。
いずれにしても、解の存在範囲の区間幅を半分に狭めることができる。

二分法のアルゴリズム

Alg.3 ( 二分法 ) 
  1. $f(a) \times f(b) \lt 0$ を満たす $a$, $b$ を入力する
  2. $\dps{c=\frac{a+b}{2}}$ とおく
  3. if ( $f(a) \times f(c) \leqq 0$ ) $b = c;$ else $a = c$;
  4. if ( 終了条件 ) $c$ を出力して終了; else 2° へ戻れ;
 終了条件としては次のような条件を設定します。
  • 反復回数が十分大きい
  • $|\,f(c)\,|$ が十分に小さい
  • $|\,a-b\,|$ が十分に小さい
Rem.4 1回のループで区間幅が半分になるということは、2進数として精度が1桁向上することになります。 $2^{20}$ ≒ $10^6$ ですから、ループを 20 回まわせば10進数としての精度が6桁向上します。
Rem.5 2重解はこのままでは求めることができません。 解の左右では $f(x)$ が同符号なので、解の付近で $f(a) \times f(b) \lt 0$ が成立しないからです。
 そこで次の定理を使います。
Th.6  $\alpha$ が $f(x)=0$ の2重解であること $\Leftrightarrow$ $f(\alpha) = f'(\alpha) = 0$.
このとき $\alpha$ は $f'(x)=0$ の単根ですので、$f'(x)=0$ について二分法を適用することで $\alpha$ が求まります。