A (New?) Bilateral Babylonian Method for Calculating Square Roots

Question

The LFT Theory I've been working on is screaming "YES" - we can squeeze onto a square root from both sides using Heron's method. Besides the aesthetics, this is useful since we know immediately how much of an error remains.

I can't find a reference to this kind of approach, and so this is a two part question.

Question 1: Prove

Let $S > 0$ and $K > 0$ and let $K$ satisfy $K^2 < S$.

Define

$x_1 = K$

For $n \gt 1$ we define $x_{n+1}$ as follows:

If $n+1$ is even:

$x_{n+1} = \frac{S + x_n x_n}{2 x_n}$

If $n+1$ is odd:

$x_{n+1} = \frac{S + x _n x_{n-1}} {x_n + x_{n-1}}$

THEN

The subsequence of odds form an increasing sequence

$x_1 < x_3 < x_5 < ... < x_{2n+1} < ... $

and the square of any of these numbers is less than $S$ but they converge to it.

Also,

The subsequence of evens forms a decreasing sequence

$x_2 > x_4 > x_6 > ... > x_{2n} > ... $

and the square of any of these numbers is greater than $S$ but they converge to it.

Question 2: Has anyone seen this approach before?

Answer 1

If you can derive an infinite continued fraction representation of the square root in question (protip: you can, quadratics are "nice") then the convergents of the continued fraction are respectively less than, greater than the square root (provided it is an irrational). So your two sequences are interleaved in the sequence of convergents. Edit: I should say, so the two sequences which approach from below respectively above are interleaved.

Edit: Suppose we wish to find the square root of a non-square S. Pick any $a : a^2 < S$ and define $b = S - a^2$. Then a generalized continued fraction for $\sqrt{S}$ is

$$a + \frac{b}{2a + \frac{b}{2a + \cdots}}$$

And it's convergents can be found as columns of the matrix truncated infinite product $$\begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix} \prod^{\infty} \begin{pmatrix} 2a & b \\ 1 & 0 \end{pmatrix}$$

i.e the first convergent by not even multipying is $\frac{a}{1}$.

If this is true (it is) can you show your sequence is in some way bound by this sequence, perhaps by an index offset?

Later edit: After some numerology (read: computing) I have come to this conclusion, which I (alas) have not proven.

It appears your convergents are given by an accelerated product

$$\begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix} \prod_{n=0}^{\infty} \begin{pmatrix} 2a & b \\ 1 & 0 \end{pmatrix}^i \\ where~ i = 3^{\lfloor \frac{n}{2} \rfloor} = 1,~ 1,~ 3,~ 3,~ 9,~ 9,~ 27\ldots$$

I have tested this on several numbers with various K and found no exceptions. I hope this helps. I will post this edit and continue working.

Further edit based on comments Consider the LFT $F(x) = \frac{ax+b}{cx+d}$ under the substitution $x\rightarrow t+\frac{u}{x'}$

$$F(x') = \frac{a(t+\frac{u}{x'}) + b}{c(t+\frac{u}{x'}) + d} = \frac{(at+b)x' + (au)}{(ct+d)x' + (cu)} $$ But in the coefficients this is equivalent to $$\begin{pmatrix} a & b \\ c & d \end{pmatrix} \times \begin{pmatrix} t & u \\ 1 & 0 \end{pmatrix}$$

The term substitution $x \rightarrow t + \frac{u}{x'}$ is like taking a piece of a continued fraction, where $x'$ is the rest of the continued fraction. This is basically the derivation of the infinite matrix product I gave above.

If you can show that your recurrence relation computes this, then you will have proven that this 1) converges to $\sqrt{S}$ 2) odd terms underestimate the true value 3) even terms overestimate the true value. Incidentally this is why the exponent is $3^i$ above and all $i$ are odd. If it were another way your sequence would miss the convergents on one side or the other.

Unfortunately because of the repeated exponentiation involved I am not able to easily show it or I would have.

Answer 2

Before giving the answer I want to express the main idea in a way that might be useful for other modes of attack.

Define

$u_1 = K$

We define $u_{n+1}$ as follows:

$u_{n+1} = \frac{S + K u_{n}} {K + u_{n}}$

The following proposition and proof should be compared to my Proof of Convergence for the Babylonian Method.

Proposition: The $x_n$ sequence is a subsequence of the convergent $u_n$ sequence.

Proof:

The $u_n$ are actually the same as the numbers ($K$, $K_2$, $K_3$, ...) discussed in Proposition 2' and Proposition 3' in my Simple LFT Theory. It is evident that

$x_1$ = $u_1$

$x_2$ = $u_2$

$x_3$ = $u_3$

Continuing,

$x_4 = \frac{S + x_3 x_3}{2 x_3} = \frac{S + u_3 u_3}{2 u_3} = K_6 = u_6$

$x_5 = \frac{S + x_4 x_3}{x_4 + x_3} = \frac{S + u_6 u_3}{u_6 + u_3} = K_9 = u_9$

$x_6 = \frac{S + x_5 x_5}{2 x_5} = \frac{S + u_9 u_9}{2 u_9} = K_{18} = u_{18}$

$x_7 = \frac{S + x_6 x_5}{x_6 + x_5} = \frac{S + u_{18} u_9}{u_{18} + u_9} = K_{27} = u_{27}$

$x_8 = \frac{S + x_7 x_7}{2 x_7} = \frac{S + u_{27} u_{27}}{2 u_{27}} = K_{54} = u_{54}$

$x_9 = \frac{S + x_8 x_7}{x_8 + x_7} = \frac{S + u_{54} u_{27}}{u_{54} + u_{27}} = K_{81} = u_{81}$

$x_{10} = \frac{S + x_9 x_9}{2 x_9} = \frac{S + u_{81} u_{81}}{2 u_{81}} = K_{162} = u_{162}$

You can of course continue this calculation; you will find that

For odd $n$:

$x_{2n+1} = u_{3^{n}}$

For even $n$:

$x_{2n} = u_{2 (3^{n-1})}$

QED