2

I follow why the error at the nth step of the bisection method has $\epsilon_n \le\frac{1}{2^{n+1}}|b_0-a_0|$. Where $\epsilon_n=|\alpha-c_n|$: $c_n=\frac{a_n+b_n}{2} $, $\alpha$ is the root.

My question is:

Suppose $f$ is a continuous function and I want to solve $f(x)=0$ by bisection. But I use $|f(c_n)|\lt\delta$ as the termination criterion and I don't know how many steps it takes to get to this point. What does this imply for $\epsilon_n$? Is there a formula or 'less than or equal to bound' for $\epsilon_n$ in terms of $\delta$?

Thanks!

2 Answers2

0

In a similar line of thought as Peter's answer, one may approximate the derivative by the difference quotient:

$$f_n'=\frac{f(a_n)-f(b_n)}{a_n-b_n}$$

Using a linear approximation this let's us relate the expected error of $x_n$, the last estimate of the root, to the magnitude of $f(x_n)$:

$$f(x_n)\approx f_n'\cdot(x_n-x_\star)=\frac{f(a_n)-f(b_n)}{a_n-b_n}(x_n-x_\star)$$

So if you desire to acquire $|x_n-x_\star|<\epsilon$ then you should test for

$$|f(x_n)|<\left|\frac{f(a_n)-f(b_n)}{a_n-b_n}\right|\epsilon$$

This is particularly useful if one desires a termination condition for a method where a termination criterion such as $|a_n-b_n|<\epsilon$ is not available.

Simply Beautiful Art
  • 74,685
0

If you know bounds for the derivation of f(x), you can use the mean value theorem to bound the difference of the x-values using the difference of the y-values :

$$\frac{f(b)-f(a)}{b-a}=f'(c) for\ some\ c\in[a,b]$$

So if you know the bounds for f '(x) , you can calculate bounds for b-a.

Peter
  • 84,454
  • This is very useful but what if I don't know the derivative? –  Jan 07 '14 at 23:06
  • 1
    If the derivatives are near 0, your method is not practible because large differences of the x-values may cause only small differences of the y-values. – Peter Jan 07 '14 at 23:12
  • This is the reason, why usually the x-values are used. – Peter Jan 07 '14 at 23:14