A proof of Newton's Iteration for Finding Square Roots

Question

I find this theorem in my textbook:
Assume that $A>0$ is a real number and let $p_0>0$ be an initial approximation to $\sqrt{A}$. Define the sequence $\{p_k\}_{k=0}^\infty$ using the recursive rule

$p_k=\frac{p_{k-1}+\frac{A}{p_{k-1}}}{2}$, for $k=1,2,...$

Then the sequence $\{p_k\}_{k=0}^\infty$ converges to $\sqrt{A}$; that is, $\lim_{k\to \infty}p_k=\sqrt{A}$.

My textbook tells me that the recursive rule is generated by using Newton-Raphson iteration formula, but it doesn't prove that the sequence will converge to $\sqrt{A}$ for any starting value $p_0>0$. And here is my proof:

$|p_{n+1}-\sqrt{A}|=|\frac{p_n}{2}+\frac{A}{2p_n}-\sqrt{A}|=|p_n-\sqrt{A}+\frac{A}{2p_n}-\frac{p_n}{2}|$
Let $\frac{p_n}{2}-\frac{A}{2p_n}=2(p_n-\sqrt{A})$, and we can get

$3p_n^2-4\sqrt{A}p_n+A=0$.
Solving this equation we can get two roots of this equation:
$p_{n1}=\frac{\sqrt{A}}{3},p_{n2}=\sqrt{A}$

According to the information above, we can get two conclusions below:

(1)If $p_n\in(\sqrt{A},+\infty)$, then $3p_n^2-4\sqrt{A}p_n+A>0\Rightarrow \frac{p_n}{2}-\frac{A}{2p_n}<2(p_n-\sqrt{A})$. Since $p_n>\sqrt{A}$, we know that $\frac{p_n}{2}>\frac{\sqrt{A}}{2}$ and $\frac{A}{2p_n}<\frac{\sqrt{A}}{2}.$ So $-2(p_n-\sqrt{A})<\frac{A}{2p_n}-\frac{p_n}{2}<0\Rightarrow-(p_n-\sqrt{A})<p_n-\sqrt{A}+\frac{A}{2p_n}-\frac{p_n}{2}<p_n-\sqrt{A}$
So we can get $|p_{n+1}-\sqrt{A}|<|p_n-\sqrt{A}|,p_n\in(\sqrt{A},+\infty)$.

(2)It is easy to prove that for any $p_n>0,p_{n+1}\ge\sqrt{A}$.

1.If $p_0=\sqrt{A}$, obviously, the sequence converges to $\sqrt{A}$.

2.If $p_0>\sqrt{A}$, from (2) we know that $p_k>\sqrt{A},k=1,2,...$. According to (1) we can find a positive number $k(k<1)$ such that $|p_{n+1}-\sqrt{A}|\le k|p_n-\sqrt{A}|$. So
$|p_n-\sqrt{A}|\le k|p_{n-1}-\sqrt{A}|\le ...\le k^n|p_0-\sqrt{A}|$.
Since $k<1$, $\lim_{n\to \infty}(k^n|p_0-\sqrt{A}|)=0$. So $\lim_{n\to \infty}(|p_n-\sqrt{A}|)=0$. That is, the sequence converges to $\sqrt{A}$

3.If $0<p_0<\sqrt{A}$, from (2) we know that $p_1>\sqrt{A}$. According to 2, it is obvious that the sequence converges to $\sqrt{A}$.

According to the statements above, we can draw a conclusion that the sequence will converge to $\sqrt{A}$ for any starting value $p_0>0$.

I think my proof is right but I think it is a little complicated. I want to know if there is some proof that is easier. Please tell me. Thanks in advance!

Answer 1

It is useful to notice that the study can be carried out with a reduced variable, $q_n:=\dfrac{p_n}{\sqrt A}$, because

$$p_{n+1}=\frac{p_n^2+A}{2p_n}\iff\frac{p_{n+1}}{\sqrt A}=\frac{\dfrac{p_n^2}A+1}{2\dfrac{p_n}{\sqrt A}}\iff q_{n+1}=\frac{q_n^2+1}{2q_n}.$$

Now observe that

$$q_{n+1}-1=\frac{q_n^2-2q_n+1^2}{2q_n}=\frac{(q_n-1)^2}{2q_n},$$ and similarly with a plus sign,

$$q_{n+1}+1=\frac{(q_n+1)^2}{2p_n}.$$

Taking the ratio, we get the magical formula

$$\color{green}{\frac{q_{n+1}-1}{q_{n+1}+1}=\left(\frac{q_n-1}{q_n+1}\right)^2}.$$

Then by induction,

$$\frac{q_n-1}{q_n+1}=\left(\frac{q_0-1}{q_0+1}\right)^{2^n}.$$

We see that convergence to $q_\infty=1$ is guaranteed when

$$r_0:=\left|\frac{q_0-1}{q_0+1}\right|<1$$ and this is true for every non-negative $q_0$.

---

The explicit formula for the $n^{th}$ iterate is

$$q_n=\frac{1+r_0^{2^n}}{1-r_0^{2^n}}.$$

We can conclude that the number of iterations required to reach a given relative precision $\epsilon$ is given by

$$n=\log_2\frac{\log\epsilon}{\log r_0}.$$

E.g., with $p_0=2\sqrt A$ (corresponding to $r_0=\dfrac13$) and $\epsilon=2^{-53}$ (double precision floating-point accuracy), $6$ iterations are enough.

Answer 2

Defining the function $$ f(x):=\frac{x+A/x}{2}=\frac{x^2+A}{2x} $$ your sequence becomes $p_k=f^k(p_0)$. Furthermore $$ f'(x)=\frac{1}{2}-\frac{A}{2x^2} $$ so for $|x|<\sqrt A$ the function $f$ is decreasing and for $|x|>\sqrt A$ it is increasing with $f'(x)<0.5$. In addition to that we have $f(\sqrt A)=\sqrt A$ so at this point $f$ crosses the line $y=x$. This point is also a local minimum for $f$ since $f'(\sqrt A)=0$. So in effect the graph looks similar to the graph for the particular case $A=2$:

So for $p_0>0$ where $p_0$ is not equal to $\sqrt A$ we see that $p_k=f^k(p_0)>\sqrt A$ and since for $x>\sqrt A$ we have $f(x)<x$ the subsequence $p_1,p_2,...$ is strictly decreasing. Note that for $x>\sqrt A$ we have $f'(x)<0.5$ so $f$ never intersects $y=x$ for larger values of $x$ which is why $f(x)<x$ holds.

Suppose for contradiction that it converged to a constant $q>\sqrt A$. Then we know that $f(q)<q$ and by continuity of $f$ there would be a small interval $x\in[q,q+\varepsilon]$ where $f(x)<q$. But then at some point $p_k$ would enter the interval $[q,q+\varepsilon]$ since it converges to $q$ and then $p_{k+1}=f(p_k)<q$ would contradict that the decreasing sequence can converge to $q$. It follows that it must converge to $\sqrt A$.