2分法のアルゴリズム

区間 $[a, b]$ の連続関数 $f(x)$ について, 中間値の定理が成り立つ.

定理     $f(a), f(b)$ の符号が異なるとき, すなわち，$f(a)f(b)<0$ ならば, $f(\alpha)=0$ を満たす実数 $\alpha$ が, $a, b$ の間に少なくとも1つ存在する.

この定理を利用して, 方程式の近似解を求めるのが 2分法です. 関数 $f(x)$ は, 区間 $[a, b]$ において連続で, $f(a)f(b)<0$ を満たすとします. また, 方程式 $f(x)=0$ はこの区間でただ 1つの解をもつと仮定します. このとき, 区間$[a, b]$の中点を $${c=\frac{a+b}{2}}$$とすると $f(c)$ の値は 0となるか, または$f(a), f(b)$のいずれかと異符号となります.

ここで, $f(c)=0$ なら $c$ は方程式の解であり, $f(a)f(c)<0$なら, 方程式は区間$[a,c]$に解をもち, $f(b)f(c)<0$なら, 方程式は区間$[c,b]$に解をもちます.

このように, 区間の中点を考えることにより, 解の存在する範囲を初めの半分に縮小することができます. そして, この操作を繰り返すと, 誤差の限界を必要なだけ小さくした近似解が得られます. double 型の計算機イプシロンが $2^{-52}$ ですから, 52回くらい繰り返すと, 計算機の精度を越えます.

このようにして近似解を求める方法を2分法といいます.

一般に, 方程式 $f(x)=0$ の近似解を, 誤差の限界が $\varepsilon$ として 2分法で求める手順は次のようになります.

1. 変数 $a, b$ に数値を入力して, $f(a)f(b)<0$ を満たすかどうか判断し, 正しければ (2) にすすみ, 正しくなければ計算不能と表示する.
2. 区間 $[a, b]$ の中点 $${c=\frac{a+b}{2}}$$ を求める.
3. $f(c)=0$ ならば, $c$ を解とする. $f(a)f(c)<0$ ならば, 変数 $b$ に $c$ の値を代入し, $f(a)f(c)>0$ ならば, 変数 $a$ に $c$ の値を代入する.
4. $\left\vert a-b \right\vert\leq \varepsilon$かどうかを判断し, 正しければ $c$ の値を近似解とする. 正しくなければ(2)に戻る.

上の(3)において, $f(c)\neq 0$ のとき, 変数 $a, b$ の値をこのようにおき換えると, $f(a)f(b)<0$ となり. 真の解 $\alpha$ は区間 $[a, b]$ にあります. またこのとき, $c$ の値は $a$ か $b$ に等しいから, $\vert c-\alpha\vert \leq \vert a-b\vert$ となり. $c$ を近似解としたときの誤差の限界は $\vert a-b\vert$ となります. 従って, (4)で誤差の限界が判定されます.

方程式 $f(x)=0$ が区間 $[a, b]$ で3つの実数解 $l,m,n \quad (a<l<m<c<n<b)$ をもち, $f(a)>0,f(c)>0,f(b)<0$ とする. $c$ を $a$ と $b$ の中点として 2分法を適用すると, 第 2段階以後区間 $[a,c]$ は無視されて, 区間$[c,b]$にある解だけを近似することになります. このように, ある区間で方程式が 2つ以上の解をもつ場合, 2分法で近似解を求めると, 1つの解以外は無視されます. また, 例えば, 方程式$(x-1)^2=0$の重解 1の近似値は, 2分法では求めることが できません. 従って, 2分法を適用する場合, あらかじめ解について定性的に 調べておくことが必要です.