二分法

この項目では、数値解析における二分法について説明しています。ゼノンのパラドックスの二分法については「ゼノンのパラドックス」を、誤った二分法については「誤った二分法」を、論理学・哲学上の二分法（dichotomy）については「二項対立」を、数理的な二分法については「2値論理」をご覧ください。

数値解析における二分法（にぶんほう、英: bisection method）は、解を含む区間の中間点を求める操作を繰り返すことによって方程式を解く求根アルゴリズム。反復法の一種。

方法

ここでは、 $f(x)=0$ となる $x$ を求める方法について説明する。

$f(x_{1})$ と $f(x_{2})$ とで符号が異なるような区間下限 $x_{1}$ と区間上限 $x_{2}$ を定める。
$x_{1}$ と $x_{2}$ の中間点 $x_{M}$ を求める。
$f(x_{M})$ の符号が $f(x_{1})$ と同じであれば $x_{1}$ を $x_{M}$ で置き換え、 $f(x_{2})$ と同じであれば $x_{2}$ を $x_{M}$ で置き換える。
2.に戻って操作を繰り返すことにより、 $f(x)=0$ となる $x$ に近づく。

$x$ は $x_{1}$ と $x_{2}$ の間に存在するので、 $x_{1}$ と $x_{2}$ の間隔を繰り返し1/2に狭めていき、 $x_{M}$ を $x$ に近づけていくわけである。

特徴

方程式が連続であり、なおかつ関数値の符号が異なる初期条件を与えることができれば必ず収束する。関数が単調増加あるいは単調減少であれば、区間上限を十分に大きく、区間下限を十分に小さくすることで適切な初期条件となる。また、繰り返しの回数によってあらかじめ解の精度を次式で予測することができる。

{\frac {x_{2}-x_{1}}{2^{n}}}

一方、ニュートン法などと比較して収束は遅い。

記述例

perlによるプログラムの例を示す。

# 二分法
sub F {    # 関数の定義
    ($x) = @_;
    $y = cos($x / 2);     # 予想される解は$x=円周率
    return ($y);
}

$x1 = 0;     # 区間下限
$x2 = 6;     # 区間上限
$s1 = (&F($x1) <=> 0);     # 区間下限における関数値の符号
$s2 = (&F($x2) <=> 0);     # 区間上限における関数値の符号

for (1 .. 50) {                # 50回繰り返し
    $xm = ($x1 + $x2) / 2;     # 中間点を計算
    $sm = (&F($xm) <=> 0);     # 中間点における関数値の符号
    if ($sm == $s1) {
        $x1 = $xm;     # 区間下限を中間点で置き換え
    }
    else {
        $x2 = $xm;     # 区間上限を中間点で置き換え
    }
}
print "x=", $xm, "¥n";     # 結果の表示

関数値&F($x1)と&F($x2)の符号が異なるような区間下限を$x1に、区間上限を$x2に設定する。続いて中間点$xmと中間点における関数値&F($xm)の符号を計算し、区間下限における関数値と同符号であれば区間下限を中間点で置き換え、そうでなければ区間上限を中間点で置き換える。この記述例においては初期区間幅が6、繰り返し回数が50回であることから、 $6\times 2^{-50}\approx 10^{-15}$ より、おおむね15桁の精度が得られることが予測できる。