# Continued fractions for $\sqrt{x}$ and beyond, valid formula?

For $x > 0$, is this trick valid?

I use $$( \sqrt{x}-1)(\sqrt{x}+1)=x-1$$

then $$\sqrt{x}+1 = \frac{x-1}{\sqrt{x}+1-2}$$

so I can use iterations to get the rational approximant

$$\sqrt{x} \approx \frac{a(0)+a(1)x+...a(n)x^{n}}{b(0)+b(1)x+..+b(m)x^{m}}$$

By repeating this procedure I can use this method to get a rational approximant to $x^{2^{-n}}$ for integer $n$ valid for positive $x$.

-
What makes you scrupulous and think it might be invalid? – Hagen von Eitzen Mar 10 '13 at 11:07
don't know but i had some similar guess which turned to be invalid :D – Jose Garcia Mar 10 '13 at 11:19
For any natural number $n$, $\sqrt{n}$ has a very nice repeating simple continued fraction - but there seems to be no pattern in cubic or higher roots. – user58512 Mar 10 '13 at 12:09
@JoseGarcia: I made one substantive edit to your Question, namely that by repeated square roots we find $x^{2^{-n}}$, not $x^{\frac{1}{2n}}$. – hardmath Mar 11 '13 at 0:02

Background stuff you can ignore this if you already know it.

Recall that simple continued fractions are like this $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \ddots}}}}$$ with $a_i$ positive, and these always converge and always have a unique value assigned to them. The reason for that is we have $a_i \ge 1$. You will also be familiar with the fact we can truncate a continued fraction to get a good approximation. In the following if I set $\alpha$ to any number from 0 to $\infty$ then $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \alpha}}$$ still approximates very well.

Call $\alpha$ the seed, if we pick $\alpha$ correctly we get the exact value rather than an approximation.

Any finite number of iterations of $$\sqrt{x}+1 = \cfrac{x-1}{-2+(\sqrt{x}+1)}$$ are valid, but the problem is when you go infinite or equivalently throw away the seed (defined earlier). The reason for that is that the continued fraction $$\sqrt{x}+1 = \cfrac{x-1}{-2+\cfrac{x-1}{-2+\cfrac{x-1}{-2+\cfrac{x-1}{-2+\ddots}}}}$$ is not simple so we don't know a-priori that it's going to converge or have a uniquely assigned value.

We can see a lot of trouble with that continued fraction though, it has it's "$a_i$" negative, instead of numerator $1$ it has $x-1$ which dominates $2$ in absolute value if $x < -1$ or $x > 3$. The algebraic manipulation that produced it doesn't have any say on which branch of the square root we pick: So applying it to different seed values will give different results - we don't have that nice gravity towards a unique value like in the simple case. And any trunction of the continued fraction will for $x < 0$ will have imaginary LHS but real RHS so we expect it to diverge (indeed look at what happens when you take successive convergents for $x=-3$, the values seem to jump around randomly).

The question then would be how to determinate seed values which lie in a stable neighborhood so that we can assure will converge to the correct square root we are interested in (it's not even clear that using the value we want as the seed will be numerically stable) - or to throw it away.

Here is a numerical example to show the sensitivity to initial conditions

? 6/(-2+6/(-2+6/(-2+6/(...(-2+6/(-2+(sqrt(7)+1-0.1)))...))))
% = -1.6457173944347541959729764099899018936
? 6/(-2+6/(-2+6/(-2+6/(...(-2+6/(-2+(sqrt(7)+1+0.0)))...))))
% = 3.6457513110645905905016157536392362230
? 6/(-2+6/(-2+6/(-2+6/(...(-2+6/(-2+(sqrt(7)+1+0.1)))...))))
% = -1.6457865347755941001945839627170441275


-
but for positive $x >1$ the fraction should converge since $x-1 >0$ will be positive :) only for divergent values or for $x=1$ may we have some problems. – Jose Garcia Mar 10 '13 at 12:26
@JoseGarcia, how do you deduce convergence from "x-1 positive"? I've added a numerical example that shows the kind of sensitivity to initial conditions that makes this stuff difficult. – user58512 Mar 10 '13 at 12:43
it seems like the positive root always repels actually. – user58512 Mar 10 '13 at 12:45

Convergence would be easier to prove if the other factor had been chosen as denominator:

$$\sqrt{x} - 1 = \frac{x-1}{\sqrt{x} + 1} = \frac{x-1}{2 + (\sqrt{x} - 1)}$$

which upon repeated substitution gives effectively:

$$\sqrt{x} = 1 + \cfrac{x-1}{2 + \cfrac{x-1}{2 + \cfrac{x-1}{2 + \cfrac{x-1}{2 + \ddots}}}}$$

If we assume $x \gt 1$ ($x = 1$ is trivial), then this continued fraction converges (and actually the finite truncations give alternating upper and lower bounds).

In this case the convergents of the continued fraction correspond to fixed-point iterates:

$$y_0 = 1$$

$$y_{k+1} = f(y_k) = 1 + \frac{x-1}{1+y_k}$$

Here $y_0 = 1$ is a "seed" as referred to in user58512's Answer, and we want to show that the sequence $\{y_k\}$ converges to $\sqrt{x}$, assuming $x \gt 1$. [We mentioned already the triviality of case $x=1$, and as a sidenote the cases $0 \lt x \lt 1$ are covered by the Śleszyński–Pringsheim theorem.]

The proof of convergence mixes a bit of global and local analysis of the iteration. First a global note, that the mapping $f$ sends $y_0 = 1$ to a positive value, and thereafter sends positive $y_k$ to positive $y_{k+1}$. It's easy to ask ourselves what fixed points $y = f(y)$ are possible, and the answer on $\mathbb{R}^+$ is that only $y = \sqrt{x}$ is.

Next a piece of local analysis. Consider the "errors" $\epsilon_k = y_k - \sqrt{x}$. Since $y_k = \sqrt{x} + \epsilon_k$, these must satisfy:

$$\epsilon_{k+1} = 1 + \frac{x-1}{1+\sqrt{x}+\epsilon_k} - \sqrt{x} = - \frac{\epsilon_k (\sqrt{x} - 1)}{\sqrt{x} + 1 + \epsilon_k}$$

This doesn't quite get us to the contraction mapping conclusion, but it does two good things. Because $\epsilon_k = y_k - \sqrt{x}$ and $y_k$ is positive, the above surely demonstrates our early claim that the convergents alternate between upper and lower bounds on $\sqrt{x}$, i.e. that the $\epsilon_k$ alternate in sign (as long as nonzero). Also we have that once $\epsilon_k \gt -2$, the errors really will begin contracting. However at the beginning $\epsilon_0 = 1-\sqrt{x}$, so we need to proceed with further analysis.

The fact that the convergents are switching back and forth across $\sqrt{x}$ suggest we want to look at taking two steps, mapping $\epsilon_k$ to $\epsilon_{k+2}$. After some algebra we find:

$$\epsilon_{k+2} = \frac{\epsilon_k (\sqrt{x} - 1)^2}{(\sqrt{x} + 1)^2 + 2\epsilon_k}$$

and this is enough to give us a strict contraction by half every two steps when $\epsilon_k \ge -\sqrt{x}$ (as of course it is). QED

-
how do you get convergence when $x > 3$? – user58512 Mar 10 '13 at 15:54
and by $x>3$ I mean $x-1 > 2$. I'm sure youre right I just don't see how to prove it. – user58512 Mar 10 '13 at 16:01
I think I can throw together an ad hoc proof for this case, based on a contraction mapping property. Strictly speaking the expression is a simple continued fraction (see Defn.2) only when $x=2$, as then the numerators are 1 and the entries $a_i = 2$ are positive integers. – hardmath Mar 10 '13 at 16:08
"contraction mapping" - I see it now! thank you! – user58512 Mar 10 '13 at 16:11
@user58512: I was a bit rushed when posting, though I had ample "yellow pad" time to get my ideas down. Let me know if you find further goofs! – hardmath Mar 10 '13 at 23:50

regarding @Hardmaths answer here is the same numerical situation I pointed out before, except this continued fraction picks out positive roots rather than negative ones:

? f(x,a) = 1 + (x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+(x-1)/(2+a))))))))))))))))
? f(4,-3.0)
% = -2.0000000000000000000000000000000000000
? f(4,-3.0-0.01)
% = 2.0000372621864075721223091776486352376
? f(4,-3.0+0.01)
% = 1.9999629243489459922057503498491885171


Setting aside the original focus on continued fractions, if our goal were simply finding rational approximants of $\sqrt{x}$, then a Newton iteration would give faster convergence:

$$y \mapsto (y + x/y)/2$$

say with starting value $y = 1$ for the positive root (or $y = -1$ for the negative root). The 16 iterations used in the continued fraction above would, with comparable operations, give approximately $2^{15}$ digits correct for $\sqrt{4}$.

-

It is possible to use ratio of polynomials from continues fraction expansion: $$\sqrt x = 1 + \cfrac{x-1}{2+ \cfrac{x-1}{2 + \cfrac{x-1}{...}}}$$ so $f_{k}=(2+(x-1)\cdot f_{k-1})^{-1}$ and $y_k=1+(x-1)\cdot f_k$ with initial condition $f_0=1$ and $k\in\mathbb{N}$. For example: $$y_{6}= {x \cdot {{x^3+21 \cdot x^2+35 \cdot x+7}\over{7 \cdot x^3+35 \cdot x^2+21 \cdot x+1}}}$$ $$y_{10}= {x \cdot {{x^5+55 \cdot x^4+330 \cdot x^3+462 \cdot x^2+165 \cdot x+11}\over{11 \cdot x^5+165 \cdot x^4+462 \cdot x^3+330 \cdot x^2+55 \cdot x+1}}}$$ The main property is exact zero value at $x=0$ and ${d\over dx }y_k(x)|_{x=0}=k+1$ so for infinitely large $k$ the derivative trends to infinity. Note that different properties of $y_k$ for even and odd $k$ is obtained: for even $k$ and $x\to\infty$ function $y_k$ trends to slant asymptote and for odd $k$ trends to constant. Square root approximation Green lines is for even $k$ and blue for odd, red line is for $\sqrt x$.
Open question is closed form for polynomial coefficients. As can be noted the coefficients at the $y_k$ function's numerator and denominator are in reverse order. This function can be used for $|x|$ approximation via substitution $x=t^2$ with important features $y_k(t)|_{t=0}=0$ and $y_k(t)|_{t=1}=1$.

-