二分法のソースを表示

{{Otheruses|数値解析における二分法|ゼノンのパラドックスの二分法|ゼノンのパラドックス|誤った二分法|誤った二分法|論理学・哲学上の二分法（[[:en:dichotomy|dichotomy]]）|二項対立|[[数理]]的な二分法|[[2値論理]]|}}
[[数値解析]]における'''二分法'''（にぶんほう、{{lang-en-short|bisection method}}）は、解を含む区間の中間点を求める操作を繰り返すことによって[[方程式]]を解く[[求根アルゴリズム]]。[[反復法 (数値計算)|反復法]]の一種。

==方法==
[[画像:2分法.png|thumb|300px|right|2分法<br>赤線は解の存在する範囲。この範囲を繰り返し1/2に狭めていく。]] 
ここでは、<math>f(x) = 0</math>となる<math>x</math>を求める方法について説明する。

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

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

==特徴==
方程式が連続であり、なおかつ関数値の符号が異なる初期条件を与えることができれば必ず収束する。関数が単調増加あるいは単調減少であれば、区間上限を十分に大きく、区間下限を十分に小さくすることで適切な初期条件となる。また、繰り返しの回数によってあらかじめ解の精度を次式で予測することができる。
:<math>\frac{x_2 - x_1}{2^n}</math>
一方、[[ニュートン法]]などと比較して収束は遅い。

==記述例==
[[perl]]によるプログラムの例を示す。

<syntaxhighlight lang="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";     # 結果の表示
</syntaxhighlight>

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

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

 x=3.14159265358979

結果は予測される解（<tt>x=</tt>[[円周率]]）に対しておおむね15桁の精度で一致している。

==関連項目==
{{Div col}}
*[[割線法]]
*[[二分探索]]
*[[ニュートン法]]
{{Div col end}}

== 外部リンク ==
*[https://risalc.info/src/bisection-method.html 二分法とは？   アルゴリズム・収束・例題] - 理数アラカルト
*[http://nalab.mind.meiji.ac.jp/~mk/syori2-2012/jouhousyori2-2012-07/node6.html 二分法 (bisection method) の原理]
*[https://qiita.com/Sunset_Yuhi/items/e2cdb34ddf362b7128e1 二分法（Pythonで数値計算プログラムを書き直そうシリーズ）]
*[https://algorithm.joho.info/programming/c-language/bisection-method-c/ 【C言語】二分法のプログラム]
*[https://mathwords.net/nibunho 二分法の意味と平方根を計算する例]
*{{MathWorld|title=Bisection|urlname=Bisection}}

=== 動画 ===
*{{YouTube|VWl1SGaEgJw|二分法}}
*{{YouTube|QXTJdtiH3iQ|二分法と誤差基準}}
*{{YouTube|UwhWSEZnNiI|非線型方程式の解法―二分法のイメージ}}

{{デフォルトソート:にふんほう}}
[[Category:求根アルゴリズム]]
[[Category:二分法]]