数値解析 第3回 (2)　二分法
前へ / 戻る / 次へ

二分法のアイデア

　情報科学では「二分割する作戦」が良く出てきますが、ここでは「解が存在する範囲」を二分割します。 「解の存在範囲を二分割する」する作業を繰り返して解を追い詰めていこう、という作戦です。 そのキーポイントは
中間値の定理　$f(x)$ が連続関数で、区間 $[\,a,\ b]$ の両端で関数値が逆符号
$f(a) \times f(b) \lt 0$
であれば、その区間内に少なくとも１つ $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$ に少なくとも１つ $f(x)=0$ の解が存在し、
  2. そうでなければ区間 $c \lt x \lt b$ に少なくとも１つ $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　１回のループで区間幅が半分になるということは、２進数として精度が１桁向上することになります。 $2^{20}$ ≒ $10^6$ ですから、ループを 20 回まわせば10進数としての精度が６桁向上します。
Rem.5　２重解はこのままでは求めることができません。 解の左右では $f(x)$ が同符号なので、解の付近で $f(a) \times f(b) \lt 0$ が成立しないからです。
　そこで次の定理を使います。
Th.6　 $\alpha$ が $f(x)=0$ の２重解であること $\Leftrightarrow$ $f(\alpha) = f'(\alpha) = 0$.
　２重解 $\alpha$ は $f'(x)=0$ の単根ですので、$f'(x)=0$ について二分法を適用することで $\alpha$ が求まります。 （一般に $m$ 重解は $f^{(m-1)}(x)=0$ の単根になります。）

前へ / 戻る / 次へ