Solving Quadratics Using Continued Fractions/Nonsimple to Simple Continued Fractions

Question

Let's say we want to find the continued fraction that solves the equation $x^2 - 2x - 1 = 0$.

Solution: $$ x = 2 + \frac1x = 2 + \dfrac1{2 + \dfrac1x} = 2 + \dfrac1{2 + \dfrac1{2 + \dfrac1x}} = [2;\overline2] $$

However, what happens if the quadratic is a bit more complicated, say, $2x^2 - 5x + 1 = 0$. If we use non-simple continued fractions to solve this, we get $$ x = \frac52 -\dfrac{\frac12}{\frac52-\dfrac{\frac12}{\frac52-\ddots}} \stackrel{how?}= [ 2; \overline{3, 1, 1} ] $$ My question is: How to convert non-simple continued fractions to simple continued fractions and in general how to solve quadratics using simple continued fractions?

Answer 1

$f(x)=2x^2-5x+1$.

$f(\alpha)=0$ for a number $\alpha$ with $2<\alpha<3$. So $a_0=2$, and $\alpha_1=1/(\alpha-a_0)$ is a zero of $f_1(x)=-x^2f(x^{-1}+2)=x^2-3x-2$.

Then $3<\alpha_1<4$, so $a_1=3$, and $f_2(x)=-x^2f_1(x^{-1}+3)=2x^2-3x-1$.

Then $a_2=1$, and $f_3(x)=-x^2f_2(x^{-1}+1)=2x^2-x-2$.

Then $a_3=1$, and $f_4(x)=-x^2f_3(x^{-1}+1)=x^2-3x-2=f_1(x)$, so from here on it repeats, giving $[2;\overline{3,1,1}]$.

This works not just for quadratics, but for any real algebraic number (although of course it's not periodic for nonquadratics).

Some references:

Cantor et al., A continued fraction algorithm for real algebraic numbers, Math Comp 26 (1972) 785-791.

Lang and Trotter, Continued fractions for soe algebraic numbers, J Reine Angew Math 255 (1972) 112-134; Addendum, 267 (1974) 219-220.

Richtmyer et al., Continued fraction expansions of algebraic numbers, Numer Math 4 (1962) 68-84.

Bombieri and van der Poorten, Continued fractions of algebraic numbers, in Computational Algebra and Number Theory, Sydney, 1992, Math Appl 325 (1995) 137-152.

Brent et al., A comparative study of algorithms for computing continued fractions of algebraic numbers, in Algorithmic Number Theory, Lecture Notes in Computer Science 1122 (Springer, 1996) 35-47.

Answer 2

As far as i know it's possible to represent all quadratic equations by Simple Continued Fractions (SCF). The accepted answer is just fine but the common method to convert quadratics into SCF is slightly different and more intuative. For a second degree polynomial, we need a rational expression of $x$ as a quotitent so that we can recurse to obtain the SCF. Given the quadratic;

$ cx^2+(d-a)x-b = 0 \implies x=\frac{ax+b}{cx+d} $

Our $2x^2-5x+1=0$ equation becomes a quotient of two linear equations $x=\lfloor\frac{6x-1}{2x+1}\rfloor$. So for what integer $x$ value, the floor of the fraction gives $x$?

As you may notice from the quadratic to quotitent conversion formula given above, we are free to chose $a$ and $d$ by keeping their difference the same.

As for starters, for the genaral case of $x=\frac{ax+b}{cx+d}$ equation, in order to obtain the coefficient $a_i$ I do like $\lfloor\frac{a}{c} - (\frac{d}{c} - \frac{b}{a})\rfloor$. However this is not very reliable. To be on the safe side we aim to make $\lfloor\frac{a}{c}\rfloor\cong\lfloor\frac{b}{d}\rfloor$. Like in this case you may guess it sometimes. Try $x=\lfloor\frac{4x-1}{2x-1}\rfloor$ which would suffice at $x=2$. One other point to remember is if $a,b,c,d>0$ then your $x$ value is for sure somewhere between $\frac{a}{c}$ and $\frac{b}{d}$ so playing with $a$ and $d$ by keeping the distance the same, if we can make these fractions close enough to have the same integer value then we are done. As a last resort you can do like $m=a-d$ and solve $\frac{a}{c}=\frac{b}{a-m}\implies a^2-ma-bc=0$ for $a$ by $\frac{m+\sqrt{m^2+4bc}}{2}$ as both $b,c$ and $m$ are known constants. Then simply$\lfloor\frac{a}{c}\rfloor$ is your first coefficient ($a_0$) to start with.

So with all this information at hand we can easily generate a regular (simple) continued fraction for second degree polynomials. Lets proceed with the solution of the question.

Step 1

For $2x^2-5x+1=0$

$x=\frac{6x-1}{2x+1}$

$a_0 =\lfloor\frac{6}{2} - (\frac{1}{2} - \frac{-1}{6})\rfloor = \lfloor\frac{7}{3}\rfloor = 2$

$x=2+\frac{1}{x_1}$.

This means we can now substitude $2+\frac{1}{x_1}$ at the place of $x$ in the above formula and move on.

Step 2

$2+\frac{1}{x_1}=\frac{6(2+\frac{1}{x_1})-1}{2(2+\frac{1}{x_1})+1}= \frac{11x_1+6}{5x_1+2}\implies\frac{1}{x_1}=\frac{11x_1+6}{5x_1+2}-2=\frac{x_1+2}{5x_1+2}\implies x_1=\frac{5x_1+2}{x_1+2};a_1=3$

Step 3

$3+\frac{1}{x_2}=\frac{5(3+\frac{1}{x_2})+2}{(3+\frac{1}{x_2})+2}= \frac{17x_2+5}{5x_2+1}\implies\frac{1}{x_2}=\frac{17x_2+5}{5x_2+1}-3=\frac{2x_2+2}{5x_2+1}\implies x_2=\frac{5x_2+1}{2x_2+2};a_1=1$

Step 4

One interesting part of this step is, calculating $a_3$ would result in an integer rather than a rational to floor. I think that marks the end of the period. But still..

$x_3=\frac{4x_3+2}{2x_3+3};a_1=1$

Step 5

Here we reach to what we calculated at Step 2 hence this repeats from here on.

$x_4=\frac{5x_4+2}{x_4+2};a_1=3$

Now that we have the coefficients at hand, we can say;

$2x^2-5x+1=0 \implies x=[2;\overline{3,1,1}]$

Answer 3

I believe the methods above overcomplicate things.

If $x = a + \frac{b}{x}$, then $x^2 - ax - b = 0$ which is a quadratic. Dividing both sides of $2x^2-5x+1 =0$ by $2$ gives $x^2 - \frac{5}{2}x + \frac{1}{2}$, and so comparing coefficients, $a = \frac{5}{2}, b = - \frac{1}{2}$.

Thus $x = \frac{5}{2} - \frac{1/2}{x}$ gives both solutions to $x$. We can replace the $x$ in the denominator by itself to get:

$$x = \frac{5}{2} - \frac{1/2}{x} = \frac{5}{2} - \frac{1/2}{\frac{5}{2} - \frac{1/2}{x}} = \frac{5}{2} - \frac{1/2}{\frac{5}{2} - \frac{1/2}{\frac{5}{2} + \frac{1/2}{x}}}$$ $$= \frac52 -\dfrac{\frac12}{\frac52-\dfrac{\frac12}{\frac52-\ddots}}$$

Assuming that this infinite, periodic continued fraction converges to a limit $L$, then we have $L = \frac{5}{2} - \frac{1/2}{L}$ and we can solve the quadratic.

However, this only converges to one of the roots of the given quadratic. This is the larger root in this case as if $L < \frac{5}{4}$, we have that $\frac{5}{2} - \frac{1/2}{L} < \frac{5}{4} \implies L < \frac{2}{5}$ and the maximum value of L keeps getting smaller each time.