Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics, and probability / Continuous mathematics / 6 / d

For Newton's method in optimization, let $\Delta =H(f{)}^{-1}\nabla f$. Its second row equation is $-4{\Delta }_x+4{\Delta }_y=4y-4x$, so ${\Delta }_y={\Delta }_x+y-x$. Therefore $y_{n+1}=y_n-{\Delta }_y=x_n-{\Delta }_x=x_{n+1}$. The given first coordinate yieldsThe Newton step is defined where $\det H(f)=16(3x^2-1)\ne 0$; both coordinates after any defined step are equal.

By the diagonal reduction in a two-variable Newton iteration, $y_n=x_n$ for $n\ge 1$. Put $e_n=x_n-1$. Direct factorization gives the exact Newton map in optimization error identityThe assumed convergence $x_n\to 1$ makes the final factor tend to $3/2$, so it is bounded for all sufficiently large $n$. Hence $|e_{n+1}|\le C|e_n{|}^2$. For the Euclidean norm error $E_n=\Vert (x_n,y_n)-(1,1)\Vert =\sqrt{2}|e_n|$, this becomes $E_{n+1}\le (C/\sqrt{2})E_n^2$, proving quadratic convergence. Unless the exact limit is reached in finitely many steps, $E_{n+1}/E_n^2\to 3/(2\sqrt{2})$.