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

^{18 19}

ARRAY(0xdd33ac)