1.5 参考: 二分法 (bisection method) の原理

(情報処理教室で実習中に、 ここを読む時間はほとんどないでしょうから、 余裕のあるときに読んで下さい。)

微積分で基本的な中間値の定理を復習しましょう。

(つまり $f(\alpha)f(\beta)<0$ となる $\alpha$ , $\beta$ があれば、方程 式 $f(x)=0$ の解 $x=c$ が区間 $(\alpha,\beta)$ 内に存在するということ。)

この定理の証明の仕方は色々ありますが、 代表的なものに区間縮小法を使ったものがあります。 それは以下のような筋書きです。

次の手順で帰納的に数列 $\{a_n\}$ , $\{b_n\}$ を定める。

(i)

$a_0=\alpha$ , $b_0=\beta$ とする。

(ii)

第 $n$ 項 $a_n$ , $b_n$ まで定まったとして、 $c_n=(a_n+b_n)/2$ とおき、 $f(a_n)f(c_n)<0$ なら $a_{n+1}=a_n$ , $b_{n+1}=c_n$ , そうでないなら $a_{n+1}=c_n$ , $b_{n+1}=b_n$ とする。

すると、

$$a_0 \le a_1 \le a_2 \le \cdots \le a_n \le a_{n+1} \le \cdots, \quad \cdots \le b_{n+1} \le b_n \le \cdots \le b_2 \le b_1 \le b_0$$

$$a_n < b_n \le b_0 \quad\hbox{($n\in\N$)}\quad \hbox{さらに} \quad a_0\le a_n < b_n \quad\hbox{($n\in \N$)},$$

$$b_n-a_n=(\beta-\alpha)/2^n \to 0 \quad \hbox{(as $n\to \infty$)},$$

$$f(a_n)f(b_n)\le 0 \quad\hbox{($n\in\N$)}.$$

これから

$$\lim_{n\to+\infty}a_n=\lim_{n\to+\infty}b_n=c, \quad \alpha < c < \beta$$

と収束して

$$f(c)=0$$

が成り立つことが分かる。$\qedsymbol$

以上の証明の手続きから、 $f(\alpha)f(\beta)<0$ となる $\alpha$ , $\beta$ が分かっている場合に、 方程式 $f(x)=0$ の近似解を求める次のアルゴリズムが得られます (以下では $\leftarrow$ は変数への代入を表す)。

二分法のアルゴリズム

(1)

要求する精度 $\varepsilon$ を決める。

(2)

$a \leftarrow \alpha$ , $b \leftarrow \beta$ とする。

(3)

$c \leftarrow (b + a) / 2$ として $f(a)f(c)<0$ ならば $b \leftarrow c$ 、そう でなければ $a \leftarrow c$ とする

(4)

$\vert b-a\vert \ge \varepsilon$ ならば (3) に戻る。 そうでなければ $\dfrac{a+b}{2}$ を解として出力する。
($[a,b]$ 内に真の解が存在することが分かるので、 $a$ と $b$ を出力することにも意味がある。)