One root of the equation $e^{x}-3x^{2}=0$ lies in the interval $(3,4)$, the least number of iterations of the bisection method, so that $|\text{Error}|<10^{-3}$ is

(a) $10$

(b) $6$

(c) $8$

(d) $4$

  • $\begingroup$ $10^{3}$?? Isn't it $10^{\color{red}{-}3}$ $\endgroup$ – Surb Dec 8 '14 at 16:38
  • $\begingroup$ @Surb what do you mean? $\endgroup$ – Empty Dec 8 '14 at 16:39
  • 3
    $\begingroup$ I assume you mean $10^{-3}$. In this case it will be $-\log_2(10^{-3})$ (possibly plus or minus one depending on how you define the start and end of the algorithm). $\endgroup$ – Ian Dec 8 '14 at 16:39
  • $\begingroup$ Yes...It was a mistake.... $\endgroup$ – Empty Dec 8 '14 at 16:42
  • 1
    $\begingroup$ For any numerical method, it is very hard to find a non-trivial lower bound on the convergence rate (or iteration counts) a priori which strongly depends on how lucky your initial guess is. $\endgroup$ – Algebraic Pavel Dec 8 '14 at 17:22

It's very easy. For Bisection method we always have $$n\ge \frac{\log{(b-a)}-\log{\epsilon}}{\log2}$$ Here we have $\epsilon=10^{-3}$, $a=3$, $b=4$ and $n$ is the number of iterations $$n\ge \frac{\log{(1)}-\log{10^{-3}}}{\log2}\approx 9.9658$$ Then $n=10$.

  • 1
    $\begingroup$ The number of iterations can be less than this, if the root happens to land near enough to a point $x = 3 + \frac{m}{2^{n}}, \; m = 0,1,\dots, 2^{n},$ where $n$ is the iteration number. For example, if the root was at $x = 3.5001,$ 10 iterations wouldn't be necessary to achieve the error bound. 10 is an upper bound, the question seeks the least number of iterations. $\endgroup$ – Merkh Oct 30 '16 at 23:17

The number of bisection steps is simply equal to the number of binary digits you gain from the initial interval (you are dividing by 2). Then it's a simple conversion from decimal digits to binary digits.


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.