Numerical Analysis: Bisection — Accuracy

Suppose we have a computer program that estimates the root of an equation $f(x) = 0$ by bisection.

Given that its truncation error $\leq$ a & rounding error for evaluating $f(x)$ is $\leq$ b (for a given range of x), what is the estimated accuracy of the root?

I am told that the Taylor expansion of $f(x)$ would be useful but I don't know how to proceed.

Thanks for any help!

-

Hint: At the point $x$ where you think $f(x)=0,$ you only really know that $|f(x)| \lt a+b.$ Then how far off from the real root can you be? You might think about the cases $f(x)=x$ and $f(x)=x^4$, which have rather different behavior.
Is the following right? Let r be s.t. f(r) = 0. Then $f(x) = f(r) + (x-r)f'(r) + O(h^2)$. So the estimated error is $|x-r| \approx \frac{|f(x)|}{f'(r)} = \frac{a+b}{f'(r)}$? –  Hitchhiker Aug 9 '11 at 7:39
@Hitchhiker: Yes, that's the general idea. Now think about what happens for $f(x) = x^4$. –  Jitse Niesen Aug 9 '11 at 8:32
@Jitse Niesen: Thanks. I am guessing that for $f(x) = x^4$ I would use a higher order expansion, s.t. I won't have to divide by 0? i.e. $|x - r| \approx \frac{a+b}{24}$ ? –  Hitchhiker Aug 9 '11 at 9:15
@Hitchhiker: You don't need to use the Taylor series, as you can use the whole function when they are this simple. The Taylor series just gets you the local behavior when the expression of the function is more complicated. In the case $f(x)=x^4\lt a+b, x \lt \sqrt[4]{a+b}.$ As $a+b$ is presumably much less than $1$, the error in $x$ can be very large compared to the error in $f(x)$. –  Ross Millikan Aug 9 '11 at 12:58
@Hitchhiker: in fact the Taylor series for $x^4$ around zero is $\frac{f^{(iv)}(x)}{24},$ the fourth derivative divided by $24$, which is just $x^4$ again. Also, this problem obtains for any root-finding process, not just bisection. If the function is very flat near a root, you cannot locate the root well by any means. –  Ross Millikan Aug 9 '11 at 13:24