二分法

数値解析における二分法（にぶんほう、）は、解を含む区間の中間点を求める操作を繰り返すことによって方程式を解く求根アルゴリズム。反復法の一種。
方法.
ここでは、formula_1となるformula_2を求める方法について説明する。
formula_2はformula_5とformula_6の間に存在するので、formula_5とformula_6の間隔を繰り返し1/2に狭めていき、formula_9をformula_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"; # 結果の表示
関数値&F($x1)と&F($x2)の符号が異なるような区間下限を$x1に、区間上限を$x2に設定する。続いて中間点$xmと中間点における関数値&F($xm)の符号を計算し、区間下限における関数値と同符号であれば区間下限を中間点で置き換え、そうでなければ区間上限を中間点で置き換える。この記述例においては初期区間幅が6、繰り返し回数が50回であることから、formula_27より、おおむね15桁の精度が得られることが予測できる。
以下に実行結果例を示す。
 x=3.14159265358979
結果は予測される解（x=円周率）に対しておおむね15桁の精度で一致している。