Iterative Process for Estimating Square Roots

Theorem

Let $a \in \R$ be a real number such that $a > 0$.

Let $x_1 \in \R$ be a real number such that $x_1 > 0$.

Let $\left \langle {x_n} \right \rangle$ be the sequence in $\R$ defined recursively by:

$\displaystyle \forall n \in \N^*: x_{n+1} = \frac {x_n + \dfrac a {x_n}} 2$

Then $x_n \to \sqrt a$ as $n \to \infty$.

Proof

It is clear that $x_n > 0$ (if necessary, this can be proved by induction on $n$).

Also:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x_{n+1}\)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac {x_n + \dfrac a {x_n} } 2\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle 2 x_n x_{n+1}\)	\(=\)	\(\displaystyle \)	\(\displaystyle x_n^2 + a\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle x_n^2 - 2 x_n x_{n+1} + a\)	\(=\)	\(\displaystyle \)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)

This is a Quadratic Equation in $x_n$.

We know that this eqn must have a real solution, because $x_n$ originally comes from the iterative process defined above.

Thus its discriminant $b^2 - 4 a c \ge 0$, where:

• $a = 1$
• $b = -2 x_{n+1}$
• $c = a$

Thus $x_{n+1}^2 \ge a$.

Since $x_{n+1}$ it follows that $x_{n+1} \ge \sqrt a$ for $n \ge 1$.

Thus $x_n \ge \sqrt a$ for $n \ge 2$.

Now, consider $x_n - x_{n+1}$.

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x_n - x_{n+1}\)	\(=\)	\(\displaystyle \)	\(\displaystyle x_n - \frac {x_n + \dfrac a {x_n} } 2\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 n} \left({x_n^2 - a}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\ge\)	\(\displaystyle \)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)	for $n \ge 2$	as $x_n \ge \sqrt a$ for $n \ge 2$

So, providing we ignore the first term (about which we can state nothing), the sequence $\left \langle {x_n} \right \rangle$ is decreasing and bounded below by $\sqrt a$.

Thus by the Monotone Convergence Theorem (Real Analysis), $x_n \to l$ as $n \to \infty$, where $l \ge \sqrt a$.

Now we want to find exactly what that value of $l$ actually is.

By Limit of Subsequence we also have $x_{n+1} \to l$ as $n \to \infty$.

But $\displaystyle x_{n+1} = \frac {x_n + \frac a {x_n}} 2$.

Because $l \ge \sqrt a$ it follows that $l \ne 0$.

So by the Combination Theorem for Sequences, $\displaystyle x_{n+1} = \frac {x_n + \dfrac a {x_n}} 2 \to \dfrac {l + \dfrac a l} 2$ as $n \to \infty$.

Since a Convergent Real Sequence has Unique Limit, that means $\displaystyle l = \frac {l + \dfrac a l} 2$ and so (after some straightforward algebra) $l^2 = a$.

Thus $l = \pm \sqrt a$ and as $l \ge +\sqrt a$ it follows that $l = +\sqrt a$.

Hence the result.

$\blacksquare$

Further Investigation

This time, we suppose $a > 0$ but make no statement about $x_1$.

Again, we specify $\displaystyle x_{n+1} = \frac {x_n + \dfrac a {x_n}} 2$.

Now:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x_{n+1} - \sqrt a\)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac {x_n + \dfrac a {x_n} } 2 - \sqrt a\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 x_n} \left({x_n^2 - 2 x_n \sqrt a + a}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 x_n} \left({x_n - \sqrt a}\right)^2\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 x_n} \left({\dfrac{\left({x_{n-1} - \sqrt a}\right)^2}{2 x_{n-1} } }\right)^2\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 x_n} \frac 1 {\left({2 x_{n-1} }\right)^2} \left({x_{n-1} - \sqrt a}\right)^4\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 x_n} \frac 1 {\left({2 x_{n-1} }\right)^2} \frac 1 {\left({2 x_{n-2} }\right)^4} \left({x_{n-2} - \sqrt a}\right)^8\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \frac 1 {2 x_n} \frac 1 {\left({2 x_{n-1} }\right)^2} \cdots \frac 1 {\left({2 x_1}\right)^{2n-1} } \left({x_1 - \sqrt a}\right)^{2n}\)	\(\displaystyle \)	\(\displaystyle \)

If we now assume that $x_1 \ge \sqrt a$, then it follows (as above) that $x_n \ge \sqrt a$.

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{x_{n+1} - \sqrt a}\right\vert\)	\(\le\)	\(\displaystyle \)	\(\displaystyle \left({\frac 1 {2 \sqrt a} }\right)^{1 + 2 + 2^2 + \cdots + 2^{n-1} } \left({x_1 - \sqrt a}\right)^{2n}\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \left({\frac 1 {2 \sqrt a} }\right)^{\dfrac {2^n - 1} {2 - 1} } \left({x_1 - \sqrt a}\right)^{2n}\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle 2 \sqrt a \left({\frac {x_1 - \sqrt a} {2 \sqrt a} }\right)^{2n}\)	\(\displaystyle \)	\(\displaystyle \)

If $\left|{y}\right| < 1$, then $y^n \to 0$ as $n \to \infty$ from Power of a Number Less Than One.

So, by Limit of Subsequence, $y^{2^n} \to 0$ as $n \to \infty$.

Thus we see that $x_n \to \sqrt a$ as $n \to \infty$ provided that $\frac {x_1 - \sqrt a} {2 \sqrt a} < 1$, that is, that $\sqrt a \le x_1 < 3 \sqrt a$.

We have assumed (above) that $x_1 \ge \sqrt a$.

Now we have shown that $x_n \to \sqrt a$ as $n \to \infty$ provided that $\sqrt a \le x_1 < 3 \sqrt a$.

However, we have already shown that $x_n \to \sqrt a$ as long as $x_1 \ge 0$.

The advantage to this analysis is that this gives us an opportunity to determine how close $x_n$ gets to $\sqrt a$.

$\blacksquare$

Sources

• K.G. Binmore: Mathematical Analysis: A Straightforward Approach (1977)... (previous)... (next): $\S 5.5, \ \S 5.6$