2
$\begingroup$

Suppose that an equation is known to have a root on the interval $(0,1)$. How many iterations of the bisection method are needed to achieve full machine precision in the approximation to the location of the root assuming calculations are performed in IEEE standard double precision? What if the root where known to be contained in the interval $(8,9)$?

Hint: Consider the number of base 2 digits already known in the location of the root and how many base 2 digits are available in the indicated floating point system.

From: A friendly introduction to numerical analysis by Brain Bradie.

$\endgroup$

2 Answers 2

3
$\begingroup$

The minimum number with a double number is $\varepsilon=2^{-52}$, as you have $64$ bits, one is used for the sign, $11$ bits for the mantissa.

With the bisection method you have that: $$ e_n=\frac{b-a}{2^n}, $$ where $e_n$ is the absolute error, and the research interval (suitable) is $[a,b]$.

Thus, you need to find $N$ such that: $$ e_N\leq \varepsilon, $$ or, rather $$ \frac{b-a}{2^N}\leq2^{-52}, $$ so: $$ 2^{N-52}\geq b-a, $$ hence: $$ N_{min}=\log_2(b-a)+52. $$ Your case poses $b=a+1$, or, better, $b-a=1$, i.e.: $$ N_{min}(b|b=a+1)=52. $$

$\endgroup$
2
  • $\begingroup$ Why The minimum number with a double number is ε=2**-52? I suppose you meant for positive number. It could have been smaller, such as 2^-100 imho? $\endgroup$
    – zell
    Jul 9, 2014 at 15:06
  • $\begingroup$ Only one bit is needed for sign. 52 bits need to be used for the exponent and 11 for mantissa. You may want to read the following: en.wikipedia.org/wiki/Double-precision_floating-point_format $\endgroup$
    – 7raiden7
    Jul 17, 2014 at 10:07
3
$\begingroup$

If the root to be found is inside the interval $[2^{-n-1},2^{-n}]$, then you need $n$ bisections to move the right point to this goal, and one additional for the left point. At this point you have fixed the exponent of the floating point number, and the leading, implicit $1$ of the mantissa.

Each of the following bisections fixes one of the remaining $53$ explicit bits of the mantissa, making it a total of $n+54$ bisections.

$\endgroup$

You must log in to answer this question.

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