4
$\begingroup$

We know that if we iterate arithmetic and harmonic means of two numbers, we get their geometric mean.

So, basically if we need to compute the square root of $x$:

$$\sqrt{x}=\sqrt{1 \cdot x}=AHM(1,x)$$

$$a_0=1,~~~~b_0=x$$

$$a_{n+1}=\frac{a_n+b_n}{2},~~~~~b_{n+1}=\frac{2a_nb_n}{a_n+b_n}=\frac{a_nb_n}{a_{n+1}}$$

As far as I know, this expression will converge for any real positive $x$. See this and this question for example.

We can take other initial values, for example $x/2$ and $2$, but taking $1$ is enough in most cases.

I know, the idea is so simple, it's obvious. But I did not find this method anywhere among the methods for computing square roots.

It seems even better than Newton's method, because

  • we do not need to think about initial values
  • we do not need to check our result by squaring, we only need to check that $a_n-b_n=0$ with required precision.

Examples (here equality means that the provided number of digits is the same):

$$x=2:~~~~a_4=b_4=1.414213562$$

$$x=\frac{1}{3}:~~~~a_5=b_5=0.5773502692$$

$$x=\frac{1}{14}:~~~~a_6=b_6=0.2672612419$$

$$x=13:~~~~a_6=b_6=3.605551275$$

$$x=517:~~~~a_{9}=b_{9}=22.73763400$$

As you can see, even for numbers not close to $1$, the convergence is good.

And I did not even have to check if my values are correct - I only needed to look at $a_n$ and $b_n$ and see which digits are the same.

Is this method used for computing roots along with Newton's method and others? If it is, could you provide a reference where it's discussed and compared to other methods? Will it always work in the way I described for any positive $x$?

$\endgroup$
3
$\begingroup$

This is essentially the same as the Babylonian method for computing square roots, which is itself the same as Newton's method using the function $f(t) = t^2 -x$. In particular, observe that $$ a_{n+1}b_{n+1} \,=\, \biggl(\frac{a_n+b_n}{2}\biggr)\biggl(\frac{2a_nb_n}{a_n+b_n}\biggr) \,=\, a_nb_n $$ and hence $a_nb_n = a_0b_0 = x$ for all $n$. Thus $$ a_{n+1} \,=\, \frac{a_n+b_n}{2} \,=\, \frac{a_n + \dfrac{x}{a_n}}{2}. $$

$\endgroup$
  • $\begingroup$ I see now. So this is exactly the same as if I started the iterations for Babylonian (Newton's) method with $1$ and used $a_n-x/a_n$ to check the number of correct digits. Thank you $\endgroup$ – Yuriy S Apr 9 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.