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$
Asked
Active
Viewed 3.9k times
4
-
$10^{3}$?? Isn't it $10^{\color{red}{-}3}$ – Surb Dec 08 '14 at 16:38
-
@Surb what do you mean? – Empty Dec 08 '14 at 16:39
-
3I 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). – Ian Dec 08 '14 at 16:39
-
Yes...It was a mistake.... – Empty Dec 08 '14 at 16:42
-
How we find out the solution of this type of problems? – Empty Dec 08 '14 at 16:54
-
1For 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. – Algebraic Pavel Dec 08 '14 at 17:22
2 Answers
6
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$.
Dante
- 1,908
-
1The 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. – Merkh Oct 30 '16 at 23:17
-
Do you round the result of the expression up or down? Or do you simply round to the nearest whole number? – Peter Chaula Jun 02 '21 at 17:26
0
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.
orion
- 15,781