Deriving the error bound for Bisection Method

Question

This is a homework question, I would like to know if someone can shed some light on it.

Let $x_n = \frac{a_n + b_n}{2} , r=\lim_{n \to \infty}x_n$ and $e_n =r-x_n$.

Here $[a_n,b_n]$ with $n\geq0$ denotes that successive intervals that arise in the bisection method when it is applied to a continuous function $f$.

Show that $|e_n| \leq 2^{-(n+1)}(b_0 - a_0)$.

Answer 1

The bisection method for finding the zeros of a continuous function $f$ begins with a selection of points $a_0 < b_0$ that bracket a zero.

If $f(a_0)f(b_0) < 0$, then $f(a_0)$ and $f(b_0)$ have opposite sign. By the intermediate value property of continuous functions, there must be a zero at a point $r$ such that $a_0 < r < b_0$.

The next step is to calculate the midpoint $x_0 = (a_0 + b_0)/2$. There are three possible cases:

$$f(a_0)f(x_0) < 0 \implies r \text{ is between} \,\,a_0 \,\,\text{and}\,\, x_0,\\f(a_0)f(x_0) > 0 \implies r \text{ is between} \,\,x_0 \,\,\text{and}\,\, b_0,\\f(a_0)f(x_0) = 0 \implies r = x_0. $$

In the first case, set $a_1 = a_0 $ and $b_1 = x_0$. In the second case, set $a_1 = x_0 $ and $b_1 = b_0$. In the third case, the zero is found to be $r = x_0$ to within machine precision.

At this stage, the true zero $r$ must lie in either $[a_0,x_0]$ or $[x_0,b_0]$. These intervals have identical lengths. The error of approximation is bounded by

$$|e_0| = |x_0 - r| \leqslant x_0 - a_0 = b_0 - x_0 = (b_0 - a_0)/2.$$

Repeat the procedure with the interval $[a_1, b_1]$. The new approximation is $x_1 = (a_1 + b_1)/2$ with error bound

$$|e_1| \leqslant (b_1 - a_1)/2 = (b_0 - a_0)/2^2 = 2^{-2}(b_0-a_0)$$.

Continuing, iteratively, we find a sequence of approximations $x_n = (a_n + b_n)/2$ for $n = 1, 2, 3, \ldots$ with error bound

$$|e_n| \leqslant (b_n - a_n)/2.$$

Since

$$|e_n| \leqslant |x_n - a_n| = |b_n - x_n| = 2^{-1}(b_n - a_n) = 2^{-2}(b_{n-1} - a_{n-1}) ,$$

it follows by induction that

$$|e_n| \leqslant 2^{-(n+1)}(b_0 - a_0).$$

This also proves that the bisection method always converges to a zero of a continuous function when the initial interval is selected appropriately.