📂Numerical Analysis

Bisection Method

Method¹

Suppose a continuous function $f$ satisfies $f(a) f(b) < 0$ on the closed interval $[a,b]$. The tolerance is $\varepsilon$. A $c \in [a,b]$ satisfying $f(c) = 0$ can be found as follows.

---

Step 1.

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

---

Step 2.

If $b-c \le \varepsilon$, return $c$.

---

Step 3.

If $f(b) f(c) < 0$, set $a:=c$; otherwise, set $b:=c$. Then return to Step 1.

Explanation

As a representative application of the intermediate value theorem, it is a method that finds an approximate solution to the equation $f(x) = 0$ by repeatedly halving the interval in which a solution exists. It is simple enough that, if you have an equation that must be solved right away and no library at all, you could write it up on the spot.

It is attractive in that the only given condition is essentially a continuous function defined on a closed interval, and that it finds a solution within a range specified by the user, but it has the drawback that its order of convergence is linear. For this reason, simple equations are usually solved with the Newton-Raphson method.

Implementation

Below is an example code written in 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)