二分法 - 暇つぶしWikipedia

二分法

.mw-parser-output .hatnote{margin:0.5em 0;padding:3px 2em;background-color:transparent;border-bottom:1px solid #a2a9b1;font-size:90%}

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

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

ここでは、 f ( x ) = 0 {\displaystyle f(x)=0} となる x {\displaystyle x} を求める方法について説明する。
f ( x 1 ) {\displaystyle f(x_{1})} と f ( x 2 ) {\displaystyle f(x_{2})} とで符号が異なるような区間下限 x 1 {\displaystyle x_{1}} と区間上限 x 2 {\displaystyle x_{2}} を定める。

x 1 {\displaystyle x_{1}} と x 2 {\displaystyle x_{2}} の中間点 x M {\displaystyle x_{M}} を求める。

f ( x M ) {\displaystyle f(x_{M})} の符号が f ( x 1 ) {\displaystyle f(x_{1})} と同じであれば x 1 {\displaystyle x_{1}} を x M {\displaystyle x_{M}} で置き換え、 f ( x 2 ) {\displaystyle f(x_{2})} と同じであれば x 2 {\displaystyle x_{2}} を x M {\displaystyle x_{M}} で置き換える。

2.に戻って操作を繰り返すことにより、 f ( x ) = 0 {\displaystyle f(x)=0} となる x {\displaystyle x} に近づく。

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

方程式が連続であり、なおかつ関数値の符号が異なる初期条件を与えることができれば必ず収束する。関数が単調増加あるいは単調減少であれば、区間上限を十分に大きく、区間下限を十分に小さくすることで適切な初期条件となる。また、繰り返しの回数によってあらかじめ解の精度を次式で予測することができる。 x 2 − x 1 2 n {\displaystyle {\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 × 2 − 50 ≈ 10 − 15 {\displaystyle 6\times 2^{-50}\approx 10^{-15}} より、おおむね15桁の精度が得られることが予測できる。

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

Size:9 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef