二分法 (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 \cdo... ...\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$$

が成り立つことが分かる。

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