Links forward

Everything we know is only some kind of approximation, because we know that we do not know all the laws yet. Therefore, things must be learned only to be unlearned again or, more likely, to be corrected.

— Richard Feynman

Speed of the bisection algorithm

As we saw previously, one nice aspect of the bisection algorithm is that it always works. We now consider its accuracy more precisely, and how long it takes to work.

In order to examine the accuracy of the method, we find the length of each $[a_n, b_n]$. Exercise 2 asked you to find the length of each $[a_n, b_n]$ in terms of the original interval $[a_0, b_0] = [a,b]$. Now $[a_0, b_0] = [a,b]$ has length $b-a$, and at each step we bisect this interval. So the length $b_n - a_n$ of $[a_n, b_n]$ is obtained by dividing $b-a$ by $2$, $n$ times:

\[ b_n - a_n = \frac{b-a}{2^{n}}. \]

Hence, $[a_n, b_n]$ provides us an accuracy of $\frac{b-a}{2^n}$ for a solution.

Exercise 13

Suppose you apply the bisection method to solve $f(x) = 0$ in the interval $[a,b]$.

After $n$ iterations, you make a best guess for the solution. How close is your guess to a solution?

In fact, we can calculate just how many steps are required in the bisection algorithm to obtain a desired degree of accuracy.

Example

Using the bisection algorithm to find a solution to the equation $f(x) = 0$, starting from the interval $[a,b] = [3, 5]$, to an accuracy of $0.001$, how many steps are required?

Solution

From above, the $n$'th interval $[a_n, b_n]$ has length

\[ b_n - a_n = \frac{b-a}{2^{n}} = \frac{5-3}{2^n} = 2 \cdot 2^{-n}. \]

To obtain a solution to within an accuracy of $0.001$, we require $b_n - a_n < 0.001$, so

\begin{align*} 2 \cdot 2^{-n} &< 0.001, \quad \text{hence} \quad \frac{2}{0.001} < 2^n \\ n &> \log_2 \left( \frac{2}{0.001} \right) = \log_2 2000 \sim 10.966. \end{align*}

So if we take $n=11$ steps, we will have the desired accuracy.

Note that to find how many steps are required, we do not need any information about the function $f$! All we need to know is the length of $[a,b]$, and the desired accuracy.

Exercise 14

Starting from the interval $[a,b] = [-5,5]$, how many steps are required in the bisection algorithm to obtain a solution to an accuracy of $0.05$?

In general, to obtain an accuracy of $\epsilon$, starting from the interval $[a,b]$, the bisection method will require $N$ iterations, where

\[ N > \log_2 \left( \frac{b-a}{\epsilon} \right) \quad \text{steps}. \]

Exercise 15

Prove this.

Next page - Links forward - Bisection and binary numbers