Skip to main content

Section 7.3 Bisection method

The bisection method is based on the Intermediate Value Theorem. Suppose that the function \(f\) is continuous on the interval \([a, b]\) and \(f(a)f(b) \lt 0\text{,}\) meaning that \(f\) takes on values of opposite sign at the endpoints. The Intermediate Value Theorem says that there exists some root of \(f\) between \(a\) and \(b\text{:}\) that is, there exists \(x\) in \((a, b)\) such that \(f(x)=0\text{.}\)

Figure 7.3.1. To go from positive to negative, a function function must turn to 0

An interval \([a, b]\) such that \(f(a)f(b) \lt 0\) is called a bracketing interval. As Figure 7.3.1 shows, there could be multiple roots inside of the bracketing interva. The bisection method will find one of them.

Bisection method: Divide the interval in two halves by the midpoint \(c = (a+b)/2\text{.}\) Since \(f(a)\) and \(f(b)\) have opposite signs, one of the following holds:

  • If \(f(c)\) has the same sign as \(f(a)\text{,}\) then we replace \(a\) with \(c\text{,}\) making \([c, b]\) our new bracketing interval.
  • If \(f(c)\) has the same sign as \(f(b)\text{,}\) then we replace \(b\) with \(c\text{,}\) making \([a, c]\) our new bracketing interval.
  • If \(f(c) = 0\text{,}\) we already found a root so the process stops.

The above process repeats until the bracketing interval is small enough, as discussed in Section 7.2.

Figure 7.3.2. Bisection method illustrated by marking the bracketing intervals

Find a root of equation \(e^{-x/2} + \sin(3x) = 1/2\) on the interval \([-1, 1.5]\) using bisection. (This is the function shown on Figure 7.3.2). The Matlab function sign can be used to compare the signs of values.

Solution
f = @(x) exp(-x/2) + sin(3*x) - 1/2;
a = -1;
b = 1.5;
if f(a)*f(b) >= 0    
    error('Not a bracketing interval'); 
end

while abs(b-a) >= 100*eps(a)
    c = (a+b)/2;  
    if sign(f(c)) == sign(f(a)) 
        a = c;        
    elseif sign(f(c)) == sign(f(b)) 
        b = c;
    else
        break
    end         
end

fprintf('Found a root x = %.12g\n', (a+b)/2);

If the function has the same sign at both given endpoints, the bisection method cannot run, so the command error is used to display a message and exit the program. This is a useful command to use when the computation has to be interrupted. The while loop runs until either the interval becomes small enough (length less than 100*eps(a)) or we accidentally reach \(f(c)=0\) so the loop stops.

The bisection method is not very fast, but is very reliable. If the initial bracketing interval had length \(L\text{,}\) after \(n\) iterations we get an interval of length \(2^{-n}L\text{.}\) So, it takes about 50 iterations to reduce the bracketing interval from length \(100\) to length \(10^{-13}\text{.}\) The speed of convergence of a numerical method is often visualized by plotting the logarithm of the error as a function of the number of steps. For the bisection method, the error after \(n\) steps is \(2^{-n}|a-b|\) so the logarithm is \(\log|a-b| - n \log 2\text{.}\)

Figure 7.3.4. Logarithm of error as a function of the number of steps

Generally, if some numerical method has error \(\epsilon_n\) after \(n\) steps, we say that the method is

  • linearly convergent if \(\epsilon_{n+1} \le c\epsilon_n\) with some constant \(c \lt 1\)
  • quadratically convergent if \(\epsilon_{n+1} \le M\epsilon_n^2\) with some constant \(M\)
  • convergent with order \(p\) if \(\epsilon_{n+1} \le M\epsilon_n^p\) with some constants \(M\text{,}\) \(p > 0\text{.}\)

Since for the bisection method \(\epsilon_{n+1} = \frac{1}{2}\epsilon_n\text{,}\) the bisection method is linearly convergent.