3.1 二分法

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

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

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

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

1. $a_0=\alpha$, $b_0=\beta$ とする。
2. 第 $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$ は変数への代入を表します)。

[

l]2分法のアルゴリズム

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$ ならば (1) に戻る。そうでなければ $c$ を 解として出力する。