Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 5 / b / iii

About five steps are certified by the uniform worst-case estimate; the actual iteration reaches double-precision accuracy in about four. Put $K=15/14$. The initial enclosure gives $e_0=|x_0-r|<1/5$, and repeated squaring yieldsFor $k=4$ this is about $1.84\times 10^{-11}$, while for $k=5$ it is below $4\times 10^{-22}$. Thus five ideal-arithmetic steps push this bound well below the approximately $10^{-16}$ relative resolution of double-precision floating-point format.

The bound is conservative. Factoring $f(x)=(x^2+1)(x^4-6x^2+6)$ identifiesHigh-precision evaluation of the actual successive errors gives approximately $7.40\times 10^{-2}$, $3.56\times 10^{-3}$, $9.91\times 10^{-6}$, $7.73\times 10^{-11}$ and $4.70\times 10^{-21}$. Thus the fourth step would already exceed double-precision accuracy in exact arithmetic. In floating-point evaluation, cancellation in the residual and other roundoff errors prevent the subsequent theoretical digits from being realized.