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

The first three derivatives factor asLet $a=\sqrt{10/3}$. Sign analysis of the factors givesAll displayed endpoints are excluded because a factor vanishes there; the extra zero of $f^{\prime \prime }$ at $0$ does not create a positive interval.

The extreme value theorem guarantees extrema on the closed interval. Compare its endpoints and the stationary points $0,\pm \sqrt{10/3}$:ThusThe two-point answer in each case also follows from the even function symmetry.

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.

For the vector equation, the Jacobian matrix isWrite the updated coordinates as $(X,Y)$. The second equation of the multivariable Newton iteration gives $X-Y=0$. Substituting $X=Y$ into its first linearized equation givesHence $h(x,y)=6x^5-20y^3$, and, whenever $h\ne 0$,

Starting from $(0,1)$ gives $(x_1,y_1)=(21/20,21/20)$. Every subsequent iterate remains on the diagonal, where this is exactly the scalar Newton root-finding iteration from (b). The value $f(21/20)>0$, so $21/20<r$.

For $1\le x<r$, concavity again puts the tangent's zero at or above $r$. Alsoso $r\le N(21/20)\le N(1)=8/7<6/5$. After one scalar step the sequence therefore enters the invariant interval proved in (b). It converges to $(r,r)$ at least quadratically. If the vector error is measured in the Euclidean norm, then $\Vert (x_k,y_k)-(r,r)\Vert =\sqrt{2}|x_k-r|$, so the scalar quadratic estimate also gives a quadratic vector estimate. The initial off-diagonal step causes no difficulty because its Jacobian matrix is invertible and lands exactly on the diagonal.