二分法
メソッド 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. に戻る。
説明
中間値定理の典型的な応用として、解が存在する区間を継続的に半分にして、方程式$f(x) = 0$の近似解を見つけ出す方法である。すぐに方程式の解を求める必要があり、ライブラリも何もない場合、その場で作成して使用するほど簡単である。
事実上閉区間で定義された連続関数であること、ユーザーが指定した範囲内で解を見つけることの魅力的な部分があるが、収束次数がリニアである点が欠点である。このため、通常は単純な方程式を解くにはニュートン-ラフソン メソッドを使用する。
実装
以下はRで書かれた例示コードである。
Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p56~57. ↩︎