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{.}\)
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.
Example 7.3.3. Finding a root by bisection.
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.
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{.}\)
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.