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$?
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}. $$