'Inverting' the Babylonian Method to Get Lower Approximations of a Square Root (making the approximation error exactly known)

Question

Update: I'm changing the question to

What is the best way to exploit this idea?

(I tried but everything goes in a circle; you wind up implementing the Babylonian Method).

---

Let $S \gt 0$.

If one 'runs' the Babylonian Method in the usual fashion, we get a decreasing sequence that converges to $\sqrt S$. By using an inversion trick, we can get an increasing sequence with the same limit:

With seed $l_0 \gt 0$, define

$$\tag 1 l_{n+1} = \frac{2\, S\, l_n}{S + l_n^{\;2}}$$

I performed some googling trying to find this recursion, but came up empty handed. I would be surprised if it isn't already an algorithm known to numerical analysts.

What is the name of this technique?

We can combine (1) with the Babylonian method,

$$\tag 2 u_{n+1} = \frac{1}{2} \, (u_n + \frac{S}{u_n}) $$

to get convergence with built-in error bounds.

Here is a Python program implementing the proposed algorithm; it can be contrasted with the wikipedia example of the Babylonian method.

#--------*---------*---------*---------*---------*---------*---------*---------*
# Desc: Calculate square root of 125,348
#--------*---------*---------*---------*---------*---------*---------*---------*

S = 125348
u = 600              # rough estimation of an over-estimate

print('+', u)

for i in range(0,5):
    if i % 2 == 0:   # proess '+', an over-estimate
        l = (2 * S * u) / (S + u * u)
        print('-', l)
    else:            # proess '-', an under-estimate
        u = .5 * (l + S/l)
        print('+', u)

* OUTPUT *

+ 600
- 309.91700800250544
+ 357.186837334586
- 354.03137921119
+ 354.0451951246895
- 354.04519485512014

Answer 1

If $l_{n+1} = \frac{2\, S\, l_n}{S + l_n^{\;2}} $ then $l_{n+1} = \frac{2}{\frac{1}{l_n} + \frac{l_n}{S}} $ so $\frac1{l_{n+1}} = \frac{\frac{1}{l_n} + \frac{l_n}{S}}{2} $.

Letting $a_n = \frac1{l_n}$, $a_{n+1} = \frac{a_n + \frac{1}{Sa_n}}{2} = \frac{a_n + \frac{1/S}{a_n}}{2} $ and this is Newton's iteration for $\frac1{S} $.

So, whatever direction Newton's converges, this will converge in the opposite direction.