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

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.