Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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