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

The Newton root-finding iteration isIt is defined when $x_k\notin \{0,\pm \sqrt{10/3}\}$. Finding an exact zero of a function is a stopping condition, rather than a reason to continue dividing.

On $I=[1,7/5]$, $f^{\prime }<0$ and $f^{\prime \prime }<0$, since $x^2<2$. Hence $|f^{\prime }|$ increases and has minimum $|f^{\prime }(1)|=14$. Alsowith equality at $x=1$. Therefore

There is a unique root $r$ in $I$: $f(1)=2>0$, $f(7/5)=-5.678464<0$, and the function is strictly decreasing. Moreover $f(6/5)=-1.382016<0$, so $r<6/5=x_0$.

It remains to justify that the iteration stays where the error estimate applies. Because $f$ is a concave function, its graph lies below each tangent line. At any $x\in [r,6/5]$, the tangent has nonpositive value $f(x)$ at $x$, negative slope, and nonnegative value at $r$. Its zero $N(x)=x-f(x)/f^{\prime }(x)$ therefore satisfiesBy mathematical induction, the Newton root-finding iteration stays in $[r,6/5]$ and decreases to some limit $L\ge r$. Continuity in $x_{k+1}-x_k=-f(x_k)/f^{\prime }(x_k)$ implies $f(L)=0$, so uniqueness gives $L=r$.

Now the supplied error bound applies at every step:This proves at least quadratic convergence, with an invariant interval and a nonvanishing derivative explicitly established.

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.