3.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$ を出力することにも意味がある。)