logo

二分法 📂数値解析

二分法

メソッド 1

閉区間$[a,b]$で定義された連続関数 $f$ が $f(a) f(b) < 0$ と等しいとする。許容誤差は $\varepsilon$ である。$f(c) = 0$ を満たす $c \in [a,b]$ は以下のように求めることができる。


ステップ 1.

$$c:= {{a+b} \over {2}}$$


ステップ 2.

$b-c \le \varepsilon$ ならば $c$ を返す。


ステップ 3.

$f(b) f(c) < 0$ ならば $a:=c$、そうでなければ $b:=c$ とする。その後、ステップ 1. に戻る。

説明

20180831\_133259.png

中間値定理の典型的な応用として、解が存在する区間を継続的に半分にして、方程式$f(x) = 0$の近似解を見つけ出す方法である。すぐに方程式の解を求める必要があり、ライブラリも何もない場合、その場で作成して使用するほど簡単である。

事実上閉区間で定義された連続関数であること、ユーザーが指定した範囲内で解を見つけることの魅力的な部分があるが、収束次数がリニアである点が欠点である。このため、通常は単純な方程式を解くにはニュートン-ラフソン メソッドを使用する。

実装

20180831\_143733.png

以下はRで書かれた例示コードである。


  1. Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p56~57. ↩︎