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

The arithmetic-geometric mean inequality for the positive numbers $x$ and $a/x$ givesEquality holds precisely when $x=a/x$, hence at $x=\sqrt{a}$. Thus $\boxed{\underset{x>0}{\min }g(x)=\sqrt{a}}$, attained only at $\boxed{x=\sqrt{a}}$. Equivalently, the exact identity $g(x)-\sqrt{a}=(x-\sqrt{a}{)}^2/(2x)$ proves the same global bound.

For $f(x)=x^2-a$, its derivative is $f^{\prime }(x)=2x$. Substitution into Newton's method givesEvery positive input gives another positive input, so a starting value $x_0>0$ keeps the denominator nonzero at every step.

The update in Newton's method is exactly $x_n=g(x_{n-1})$. Positivity is preserved, and the arithmetic-geometric mean inequality from part (a) applies to every update. ConsequentlyThis holds even when $0<x_0<\sqrt{a}$: the first update moves to or above the positive square root.

Subtract the previous iterate in Newton's method:The denominator is positive and the numerator is negative. If $x_{n-1}=\sqrt{a}$, the difference is zero and all subsequent iterates equal the root.

After the first update, the sequence lies in $[\sqrt{a},x_1]$ and is nonincreasing. The monotone convergence theorem for sequences gives a limit $L\ge \sqrt{a}$. The update is continuous on this interval, so passing to the limit givesPositivity forces $\boxed{x_n\to \sqrt{a}\text{ for every }{x}_0>0}$. If an iterate reaches the root exactly, the constant tail gives the same conclusion. The Exact Newton error identity for a quadratic here is $x_n-\sqrt{a}=(x_{n-1}-\sqrt{a}{)}^2/(2x_{n-1})$, also showing quadratic convergence once the error is small.

The constraint implies $x^2=z^2+1$, so $x\ne 0$ and its gradient $(2x,0,-2z)$ never vanishes on the feasible set. The Lagrange multiplier equations $\nabla f=\lambda \nabla g$ giveThus $\lambda =1$, $y=0$, $z=-1/2$, and feasibility gives $x=\pm \sqrt{5}/2$. The two stationary points and their values areThey are both global minima. Indeed, on the constraint, completing the square givesEquality holds only at the two displayed points. There are no other constrained stationary points, and the objective is unbounded above as $|y|\to \infty$.