4
$\begingroup$

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$

$\endgroup$
6
  • $\begingroup$ $10^{3}$?? Isn't it $10^{\color{red}{-}3}$ $\endgroup$
    – Surb
    Commented Dec 8, 2014 at 16:38
  • $\begingroup$ @Surb what do you mean? $\endgroup$
    – Empty
    Commented Dec 8, 2014 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
    Commented Dec 8, 2014 at 16:39
  • $\begingroup$ Yes...It was a mistake.... $\endgroup$
    – Empty
    Commented Dec 8, 2014 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$ Commented Dec 8, 2014 at 17:22

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
2
  • 2
    $\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
    Commented Oct 30, 2016 at 23:17
  • $\begingroup$ Do you round the result of the expression up or down? Or do you simply round to the nearest whole number? $\endgroup$ Commented Jun 2, 2021 at 17:26
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .