二分法

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

方法 thumb|300px|right|2分法赤線は解の存在する範囲。この範囲を繰り返し1/2に狭めていく。ここでは、となるを求める方法について説明する。

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

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

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

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

記述例 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"; # 結果の表示

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

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

x=3.14159265358979

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

Źródło i licencja