The Bisection Method for Approximating Roots
We will now look at our first method for approximating a root $\alpha$ of a continuous function $f$ over a closed interval $[a, b]$. We note that if $f(a) \cdot f(b) < 0$, then this implies that $f(a)$ and $f(b)$ have different signs, that is either $f(a) > 0$ and $f(b) < 0$ or $f(a) < 0$ and $f(b) > 0$. In either case, since $f$ is a continuous function on $[a, b]$, then the Intermediate Value Theorem implies that for any $k$ between $f(a)$ and $f(b)$, there exists a $c \in [a, b]$ such that $f(c) = k$. More specifically, since $f(a) \cdot f(b) < 0$ then $0$ is between $f(a)$ and $f(b)$ and so there exists an $\alpha \in [a,b]$ such that $f(\alpha) = 0$, that is, $\alpha$ is a root of $f$.
The idea behind the Bisection Method is intuitively really simple, which we will describe in the following theorem:
| Theorem 1 (The Bisection Method): Suppose that $f$ is a continuous function on the interval $[a, b]$ and $f(a) \cdot f(b) < 0$. Then there exists a root $\alpha \in (a, b)$ which can be approximated within an allowable error $\epsilon$ using the following steps: Step 1: Let $c_1$ be the midpoint of the interval $[a, b] = [a_1, b_1]$, that is let $c_1 = \frac{a_1 + b_1}{2}$. Step 2: If $b_1 - c_1 = \frac{b_1 - a_1}{2} ≤ \epsilon$ then stop and accept $c_1$ as a sufficient approximation of $\alpha$. If $b_1 - c_1 = \frac{b_1 - a_1}{2} > \epsilon$, then move on to step 3. Step 3: If $f(b_1)f(c_1) < 0$ then set $a_2 = c_1$ and $b_2 = b_1$, otherwise set $a_2 = a_1$ and $b_2 = c_1$ and then return to step 1 (replacing the indices).  |
One good way to remember step 3 is that if the product $f(b) \cdot f(c) < 0$ ($f(b)$ and $f(c)$ have different signs) then change $a$, and if $f(b) \cdot f(c) > = 0$ ($f(b)$ and $f(c)$ have the same sign) then change $b$.
What's great about the Bisection Method is that provided the conditions above are satisfied (and hence a root $\alpha$ exists in the interval $[a, b]$ by the Intermediate Value Theorem), then this method is guaranteed to zone into our root with better and better approximations. The main drawback to the Bisection Method is that this method is relatively to slow to converge as it may take many iterations $n$ before we can guarantee that $c_n$, our approximation, has error less than $\epsilon$ from the true value of the root $\alpha$.
Nevertheless though, the following corollary will give us a bound on our error after each iteration.
| Corollary 1: Let $f$ be a continuous function on the interval $[a, b]$, and suppose that $f(a) \cdot f(b) < 0$ so that there exists a root $\alpha \in (a, b)$. Then the sequence $\{ c_n \}$ of midpoint approximations of $\alpha$ has its error bounded and $\mid c_n - \alpha \mid ≤ \frac{b - a}{2^n}$. |
- Proof: The length of the interval $[a_1, b_1] = [a, b]$ is $b - a$. The length of the interval $[a_2, b_2]$ is $b_2 - a_2 = \frac{b - a}{2}$, and in general, the length of the interval $[a_n, b_n]$ is $b_n - a_n = \frac{b - a}{2^{n-1}}$ (for $n ≥ 1$) since after each iteration, we take the previous interval and reduce the search interval by half, and so $\alpha \in (a_n, b_n)$.
- Now using the Bisection Method, we defined $c_n = \frac{a_n + b_n}{2}$. So the approximation approximation $c_n$ will be within one half of the length of the interval of $[a_n, b_n]$. Making the appropriate substitution, we have that:
To verify Corollary 1 further, note that we obtain two main sequences $\{ a_n \}$ and $\{ b_n \}$ (which are respectively the left and right end points of each interval after each iteration) with $\alpha \in (a_n, b_n)$ for each iteration $n$. More importantly though, we can define a third sequence $\{ c_n \}$ of the midpoints (approximations of the root $\alpha$) of our successive intervals:
(2)We note that the length of each interval $[a_{n+1}, b_{n+1}]$ is half of $[a_n, b_n]$ for $n ≥ 1$, and so:
(3)Thus we see that the distance between our $n^{\mathrm{th}}$ approximation $c_n$ and the root $\alpha$ is $\mid c_n - \alpha \mid$ and recursively using the formula above, we have that:
(4)Since $\lim_{n \to \infty} \frac{b - a}{2^n} = 0$, we have that $\lim_{n \to \infty} \mid c_n - \alpha \mid = 0$ and so as $n \to \infty$ we have that $c_n \to \alpha$, so indeed, the Bisection Method always converges to a root $\alpha$, though, relatively slowly in general.
Now, suppose that we want to ensure that our approximation is within $\epsilon$ of our root $\alpha$. Then if we have that for some $n \in \mathbb{N}$ that $\frac{b - a}{2^n} ≤ \epsilon$ then $\mid c_n - \alpha \mid ≤ \epsilon$ which implies that $\alpha - \epsilon ≤ c_n ≤ \alpha + \epsilon$ and so $c_n$ will be within $\epsilon$ of $\alpha$. We can manipulate this inequality $\frac{b - a}{2^n} ≤ \epsilon$ to isolate $n$ as follows:
(5)Thus if $n$ satisfies the above inequality, then $\mid c_n - \alpha \mid ≤ \frac{b - a}{2^n} ≤ \epsilon$. We will summarize the formula above in the following Corollary 2 below.
| Corollary 2: Suppose that $f$ is a continuous function on $[a, b]$ and $f(a) \cdot f(b) < 0$ so that there exists a root $\alpha \in (a, b)$. If the Bisection Method is used to obtain midpoint approximations $c_n$ of $\alpha$ from the intervals $[a_n, b_n]$ and if $n$ is such that $n ≥ \log \left ( \frac{b - a}{\epsilon} \right ) \bigg / \log (2)$ then $\mid c_n - \alpha \mid ≤ \epsilon$. |
Usually we will want to choose the smallest $n$ that satisfies the above inequality because we often want to minimize the number of iterations we must go through until we get approximation $c_n$ of $\alpha$ with error less than or equal to $\epsilon$.
Example 1
Show that there exists a root $\alpha \in (1, 2)$ for the function $f(x) = x^5 - 3x^2 + 1$ and use the Bisection Method to approximate this root with error less than or equal to $\epsilon = 0.05$.
We will first show that there exists a root $\alpha \in (1, 2)$. Clearly $f$ is a continuous function as polynomials are continuous on their entire domain. Note that $f(1) = -1 < 0$ and $f(2) = 21 > 0$. Therefore we have that $f(1)f(2) < = -21 < 0$ and so by the Intermediate Value Theorem there exists an $\alpha \in (1, 2)$ such that $f(\alpha) = 0$, that is, $\alpha$ is a root of $f$.
Now we want to make an approximation of $\alpha$ with error less than or equal to $\epsilon = 0.05$. To do so, we will use the following formula to figure out the minimum number of iterations of the Bisection Method we need to complete in order to get this desired accuracy:
(6)Therefore the approximation $c_5$ of the Bisection Method will have error less than or equal to $\epsilon$. The following table outlines all $5$ iterations:
| Iteration Number | $a$ | $b$ | $c$ | $b - c$ | $f(c)$ |
|---|---|---|---|---|---|
| $1$ | $1.000$ | $2.000$ | $1.500$ | $0.500$ | $1.844$ |
| $2$ | $1.000$ | $1.500$ | $1.250$ | $0.250$ | $-0.634$ |
| $3$ | $1.250$ | $1.500$ | $1.375$ | $0.125$ | $0.243$ |
| $4$ | $1.250$ | $1.375$ | $1.313$ | $0.063$ | $-0.269$ |
| $5$ | $1.313$ | $1.375$ | $1.344$ | $0.032$ | $-0.034$ |
Therefore $c \approx 1.344$ is an approximation of $\alpha$ with error less than or equal to $\epsilon = 0.05$. Our root approximation $(1.344, 0)$ is plotted below with a zoomed in portion of the graph of $f$.
