2015F MATH3600 08.31 Continued Fractions

2270 days ago by calkin

Continued Fractions and $\sqrt{2}$.

 

Continued fractions, introduced sporadically throughout history, were first really studied by Wallis, and then more extensively by Euler.

Subsequent mathematicians (especially Lambert, Lagrange, Jacobi, Perron, Hermite, Gauss, Cauchy, and Stieljes) proved many many more nice results.

We will study some of the simple things to find about continued fractions.

print sqrt(2).n() print sqrt(2).n()-1 
       
1.41421356237310
0.414213562373095
1.41421356237310
0.414213562373095

We see that $\sqrt{2}$ can be written as $1+r$  where $r$ is a real number in $[0,1)$

Since $r\in [0,1)$, if $r\neq 0$ then $1/r>1$.  Writing $x=1/r$, we get 

\[  \sqrt{2} = 1 + \frac{1}{x}\]

print 1/(sqrt(2).n()-1) 
       
2.41421356237309
2.41421356237309

Hah!  It appears that $x =1 +\sqrt{2}$!

Indeed, if we check, 

\[  \sqrt{2} = 1 + \frac{1}{1+\sqrt{2}}\]

is indeed true.  (Hint: multiply both sides by $(1-\sqrt{2})$ and simplify).

Now, if we take any rational number greater than 1, we can write it in this way too: so, for example,

\[ \frac{17}{12} = 1 + \cfrac{5}{12} = 1 + \cfrac{1}{\cfrac{12}{5}} =1 + \cfrac{1}{2 + \cfrac{2}{5}} = 1 + \cfrac{1}{\cfrac{12}{5}} =1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2}}}  \] 

or 

\[ \frac{36}{25} = 1 + \cfrac{11}{25} = 1 + \cfrac{1}{\cfrac{25}{11}} 1 + \cfrac{1}{2+\cfrac{3}{11}}=1 + \cfrac{1}{\cfrac{25}{11}} 1 + \cfrac{1}{2+\cfrac{1}{\cfrac{11}{3}}} = 1 + \cfrac{1}{2+\cfrac{1}{3 + \cfrac{2}{3}}}  =  1 + \cfrac{1}{2+\cfrac{1}{3 + \cfrac{1}{\cfrac{3}{2}}}}  = 1 + \cfrac{1}{2+\cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2}}}} \]

 If we start with any rational number $r$, (allowing $a_0$ to take negative values if necessary) then we find that there is a $k$ so that this process terminates after $k$ steps, and the rational number can be written as a finite continued fraction.

\[  r = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 +\cfrac{1}{\dots + \cfrac{1}{a_k}} }}.\]

The values 

\[ c_0 = a_0\]

\[ c_1 = a_0 + \cfrac{1}{a_1} \].

\[ c_2 =  a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 }}\]

\[ c_3 = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 +\cfrac{1}{a_3} }}\]

\[  \vdots\]

\[  c_k = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 +\cfrac{1}{\dots + \cfrac{1}{a_k}} }}\]

are called the convergents of the continued fraction expansion.

For real numbers we can do the same thing, except that we don't terminate.

Then, for  example, for $1 + \sqrt{2}$, we have 

\[ 1 + \sqrt{2} = 2 + \cfrac{1}{1 + \sqrt{2}}=2 + \cfrac{1}{2 + \cfrac{1}{1+\sqrt{2}}}=2 + \cfrac{1}{2 + \cfrac{1}{2+\cfrac{1}{1+\sqrt{2}}}} \] 

\[ = 2 + \cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\dots}}}}\]

Then we naturally see that the continued fraction for $\sqrt{2}$ is 

\[ \sqrt{2} = 1 +  \cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\dots}}}}\]

What is the connection between this and the approximations given by Newton's method?

Recall that the approximations from Newton's method were $\frac{3}{2},\frac{17}{12},\frac{577}{408},\dots$

\[ \frac{3}{2} = 1 + \cfrac{1}{2}\]

\[ \frac{17}{12} = 1 + \cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}}\]

\[ \frac{577}{408} = 1 + \cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}}}}}}\]

continued_fraction(577/408)