The bisection method is another approach to finding the root of a continuous function \(f(x)\) on an interval \([a, b]\). The method takes advantage of a corollary of the intermediate value theorem called Bolzano’s theorem which states that if the values of \(f(a)\) and \(f(b)\) have opposite signs, the interval must contain at least one root. The iteration steps of the bisection method are relatively straightforward, however; convergence towards a solution is slow compared to other root-finding methods.

Performing the Bisection Method

The bisection method begins by calculating the midpoint, \(m = \frac{a + b}{2}\), of the interval. The function is then evaluated at that point \(f(m)\). Recalling Bolzano’s theorem, if \(f(a)\) and \(f(m)\) have opposite signs, the method replaces \(b\) with the computed midpoint, or if \(f(b)\) and \(f(m)\) have opposite signs, \(a\) is replaced by the midpoint. This step ensures there is still a root contained in the interval. The procedure then continues to the next iteration. The solution is said to be found once the function equals \(0\) at \(f(m)\) or is small enough to be sufficient.

The Bisection Method in R

The NLRoot package, which was used in a previous example of the secant method, also contains a function for finding the root of a function with the bisection method.

library(NLRoot)

We wish to find the root of the function \(x^3 - 2x - 5\). It is often valuable to plot the function to find an interval containing the root.

func <- function(x) {
  x^3 - 2 * x - 5
}

curve(func, xlim=c(-3,3), col='blue', lwd=1.5, lty=2)
abline(h=0)
abline(v=0)

The root appears to lie close to 2, so we will use the interval \([2, 3]\). The NLRoot package function for the bisection method is BFfzero().

BFfzero(func, 2, 3)
## [1] 1
## [1] 2.094553
## [1] 1.262094e-05
## [1] "finding root is successful"

The output of the function shows the root is located at \(x = 2.094553\), which matches the results found in previous examples on other root finding methods such as the Newton-Raphson method and secant method.

We can also write a function that implements the bisection method using the iteration steps detailed at the beginning of the post.

bisection <- function(f, a, b, n = 1000, tol = 1e-7) {
  # If the signs of the function at the evaluated points, a and b, stop the function and return message.
  if (!(f(a) < 0) && (f(b) > 0)) {
    stop('signs of f(a) and f(b) differ')
  } else if ((f(a) > 0) && (f(b) < 0)) {
    stop('signs of f(a) and f(b) differ')
  }
  
  for (i in 1:n) {
    c <- (a + b) / 2 # Calculate midpoint
    
    # If the function equals 0 at the midpoint or the midpoint is below the desired tolerance, stop the 
    # function and return the root.
    if ((f(c) == 0) || ((b - a) / 2) < tol) {
      return(c)
    }
    
    # If another iteration is required, 
    # check the signs of the function at the points c and a and reassign
    # a or b accordingly as the midpoint to be used in the next iteration.
    ifelse(sign(f(c)) == sign(f(a)), 
           a <- c,
           b <- c)
  }
  # If the max number of iterations is reached and no root has been found, 
  # return message and end function.
  print('Too many iterations')
}

Find the root of the equation using the same interval with the new function.

bisection(func, 2, 3)
## [1] 2.094552

The function matches the output of the BFfzero function to the fifth decimal place, which is adequate for our purpose of demonstration.

Summary

The bisection method is another approach to finding the root of a function in a particular interval. It is a robust method compared to other methods previously examined such as the secant and Newton-Raphson methods; however, it can be comparatively slow in reaching a solution.

References

Bisection method (2016). In Wikipedia. Retrieved from https://en.wikipedia.org/wiki/Bisection_method

Weisstein, E. W. (2008, March 13). Bolzano’s theorem. Retrieved from http://mathworld.wolfram.com/BolzanosTheorem.html

Weisstein, & Theorem, E. B. W. (2016). Intermediate value theorem. In Wikipedia. Retrieved from https://en.wikipedia.org/wiki/Intermediate_value_theorem