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$
$\endgroup$
6
-
$\begingroup$ $10^{3}$?? Isn't it $10^{\color{red}{-}3}$ $\endgroup$– SurbCommented Dec 8, 2014 at 16:38
-
$\begingroup$ @Surb what do you mean? $\endgroup$– EmptyCommented 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$– IanCommented Dec 8, 2014 at 16:39
-
$\begingroup$ Yes...It was a mistake.... $\endgroup$– EmptyCommented 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$– Algebraic PavelCommented Dec 8, 2014 at 17:22
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
2
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$.
-
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$– MerkhCommented 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
$\begingroup$
$\endgroup$
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.
