二分法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

方法[編集]

2分法
赤線は解の存在する範囲。この範囲を繰り返し1/2に狭めていく。

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

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

xx_1x_2の間に存在するので、x_1x_2の間隔を繰り返し1/2に狭めていき、x_Mxに近づけていくわけである。

特徴[編集]

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

\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桁の精度が得られることが予測できる。

以下に実行結果例を示す。

x=3.14159265358979

結果は予測される解(x=円周率)に対しておおむね15桁の精度で一致している。

関連項目[編集]

(二分法のようなアイデアで、ソート済みのリストや配列に入ったデータを高速検索する方法)