0
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ For homework problems such as the OP's, it's typically much better to give some tips and assistance than to just solve the problem. $\endgroup$ Dec 11 '14 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.