📂数値解析

二分法

メソッド¹

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

---

Step 1.

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

---

Step 2.

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

---

Step 3.

$f(b) f(c) < 0$ならば$a:=c$、そうでなければ$b:=c$とおく。その後**Step 1.**に戻る。

説明

中間値の定理の代表的な応用として、解が存在する区間を半分に縮め続けながら方程式$f(x) = 0$の近似解を求める方法である。今すぐ解かなければならない方程式があるのに何のライブラリもない場合、その場で書いて使えるほど簡単である。

与えられた条件が事実上閉区間で定義された連続関数であることだけだという点と、ユーザーが指定する範囲内で解を探すという点が魅力的だが、収束次数がリニアだという欠点がある。このため、普通、簡単な方程式はニュートン・ラプソン法を使って解くことになる。

実装

以下はRで書かれたサンプルコードである。

IVT<-function(f,a,b) {f(a)*f(b)<0}
 
Bisect<-function(f,a,b,tol=10^(-8))
{
  if(!IVT(f,a,b)) {stop("Wrong Interval")}
  
  c<-b
  if (a>b) {b<-a; a<-c}
  
  c=(a+b)/2
  if(abs(f(c))<tol) {return(c)}
  
  while(1)
  {
    c=(a+b)/2 #Step 1.
    if(abs(b-c)<tol) {break} #Step 2.
    if(IVT(f,c,b)) {a=c} else {b=c} #Step 3.
  }
  
  return(c)
}
 
f<-function(x) {x^3 + 8}
Bisect(f,-7,7)
 
g<-function(x) {x^6 - x - 1}
Bisect(g,0,3)
 
h<-function(x) {exp(x)-1 }
Bisect(h,-pi,pi)
Bisect(h,-2,-1)