I know how to find a zero of a function by the bisection method. But I am not sure how to find the number of iterations needed within a certain degree of accuracy.

Let's say, when we use the bisection method to find the zero $x^*$ of the function $g(x)=x\log(x+1)+x-1$, how many evaluations of log do we need to find $x^*$ to an accuracy of $|x_n-x^*|\leq0.01$ without really computing the iterates?

Could anybody give me some clue on what formula to use or is there any other way to approach the problem?

  • $\begingroup$ It depends on the interval you start with. Just think about, what the bisection method does to your interval. Then you immediately get your answer. $\endgroup$ – Severin Schraven May 8 '16 at 12:40

On $[0,1]$, the first iteration is you try $0.5$ and this will give you an error of no more than $0.5$. Second iteration you try either $0.25$ or $0.75$ and the error is no more than $0.25$. After n steps the error is no more than $\frac 1 {2^n}$. What is the least $n$ for which this error is less than $0.01$? The general answer will have to do with the negative of the logarithm in base 2 of the error bound you want as a fraction of the length of the interval you started with.


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.