Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 4 / 13F / Solution

The contraction mapping theorem says that if a nonempty complete metric space $(X,d)$ has a map $T:X\to X$ satisfying $d(Tx,Ty)\le qd(x,y)$ for every $x,y$ and some fixed $0\le q<1$, then $T$ has a unique fixed point $p$, and $T^{n}x\to p$ for every starting point. In particular $d(T^{n}x,p)\le q^{n}d(x,p)$; an estimate using only consecutive iterates is $d(T^{n}x,p)\le q^{n}d(x,Tx)/(1-q)$.

Let $s=\sqrt{a}$ and $T(x)=(x+a/x)/2$ for $x>0$. Direct subtraction givesThus every iterate after the first lies in $[s,\infty )$. On this interval,The mean value theorem gives a uniform Lipschitz constant $1/2$, and $T$ maps the interval into itself. The interval is closed in $\mathbb{R}$, hence complete. By the contraction mapping theorem, its iterates converge to its unique fixed point, which is $s$. Therefore every positive initial guess converges to $\sqrt{a}$.

The local error $e_n=x_n-s\ge 0$ satisfies the sharper exact recursionIn relative error ${\delta }_n=e_n/s$, this is ${\delta }_{n+1}={\delta }_n^2/[2(1+{\delta }_n)]$. Thus when ${\delta }_n\approx 10^{-d}$, the next relative error is approximately $\frac{1}{2}10^{-2d}$: one step roughly doubles the number of correct decimal digits. In particular one further step suffices for one additional digit once the iteration is sufficiently close. For absolute-error accuracy, the precise sufficient condition $e_n\le s/5$ gives $e_{n+1}\le e_n/10$; this states explicitly how close is sufficient when $a$ has an arbitrary scale.