Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 6

The critical points satisfy both first partial derivatives equal to zero:Substitute $x=-y/2$ into the second equation to get $y(3y-1/2)=0$. Thus the candidates are $(0,0)$ and $(-1/12,1/6)$.

The Hessian matrix and its determinant areAt $(0,0)$ the determinant is $-1$, so the Hessian matrix is indefinite and the point is a saddle point. At $(-1/12,1/6)$ the determinant is $1$ and $h_{xx}=2>0$, so the Hessian matrix is positive definite and the point is a strict local minimum, with valueThere is no local maximum. Along $x=0$, $h(0,y)=y^3$ is unbounded above and below, so there are no global extrema either.

The constraint is a compact set, so the continuous objective attains both extrema by the extreme value theorem. Use Lagrange multipliers with $q(x,y)=9x^2+y^2$:Since the second component makes $\lambda \ne 0$, the two equations give $4/(18x)=1/(2y)$, or $y=9x/4$. Substitution into the constraint yieldswith matching signs. The objective values are thereforeThe constraint gradient never vanishes on the ellipse, so these are all the possible extrema. As a direct check, set $u=3x$, $v=y$; then $u^2+v^2=36$ and the Cauchy-Schwarz inequality gives $|4u/3+v|\le 6\sqrt{16/9+1}=10$, with equality at the same points.

Rewrite the rational function asIf $x>2$, then $x-1>1$, so $0<1/(x-1)<1$. Subtracting from $1$ and dividing by $2$ proves

The tangent line to $f$ at $x_n$ is $y=f(x_n)+f^{\prime }(x_n)(x-x_n)$. Its intersection with the horizontal axis gives Newton's method:Each step requires $f^{\prime }(x_n)\ne 0$. Convergence to a zero of a function additionally depends on the starting point and the local behavior of $f$; the update formula alone is not a convergence guarantee.

Since $f^{\prime }(x)=2x-2$, Newton's method becomesFor $x_n>2$, subtraction from $2$ givesAlso $x_n-x_{n+1}=x_n(x_n-2)/(2(x_n-1))>0$. Hence $2<x_{n+1}<x_n$. Equivalently, the positive excess above $2$ is multiplied by the function from part (c): $x_{n+1}-2=g(x_n)(x_n-2)$, with $0<g(x_n)<1/2$.

Thus the iterates form a decreasing sequence bounded below by $2$. By the monotone convergence theorem for sequences they have a limit $\ell \ge 2$. Passing to the limit in the continuous update gives $2\ell (\ell -1)={\ell }^2$, or $\ell (\ell -2)=0$. Therefore $x_n\to 2$. The exact error formula also shows quadratic convergence near this root.

For $1<x_0<2$, the same Newton's method formula givesThus the first step overshoots the root to $x_1>2$. Part (e) then applies from index $1$: the remaining sequence decreases to $2$. The first step can be very large when $x_0$ is close to $1$, where the derivative vanishes, but every starting value strictly between $1$ and $2$ still gives convergence to $2$. The entire sequence is not decreasing, since $x_1>2>x_0$.