(This file should be viewed in a nonproportional font.)
Continued fractions have been used for an amazing variety of things, including solving quadratic equations, proving that Pi is irrational, calculating the date of Easter, predicting eclipses, and investigating chaos.
Homepage
So what is a continued fraction?
A finite continued fraction f can be written like so:
f = a_0 + b_1
____________
a_1 + b_2
___________
a_2 + b_3
_________
a_3 + .
.
.
a_{m-1} + b_m
____ .
a_m
Equivalently, it may be written on one line using parentheses:
f = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ... a_{m-1} + b_m/a_m))) ... ),
where there are m-1 right parentheses at the end.
Many books prefer to write this using subscripted plus signs like so:
f = a_0 + b_1/a_1 _+ b_2/a_2 _+ b_3/a_3 _+ ... _+ b_m/a_m .
If we stop the computation at a_n and b_n with 0 <= n <= m, we have produced
the n-th "convergent" of f, which we write f_n.
Thus f_0 = a_0, and
f_1 = a_0 + b_1/a_1.
For 1 <= n <= m,
f_n = a_0 + b_1
____________
a_1 + b_2
______________
a_2 + b_3
_________
a_3 + .
.
.
a_{n-1) + b_n
____ ,
a_n
or
f_n = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ... a_{n-1} + b_n/a_n))) ... ),
or
f = a_0 + b_1/a_1 _+ b_2/a_2 _+ b_3/a_3 _+ ... _+ b_n/a_n .
An infinite continued fraction is written in the same way except that it does
not terminate. So it can be written as
f = a_0 + b_1
____________
a_1 + b_2
___________
a_2 + b_3
___________
a_3 + .
.
.
or
f = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ...
or f = a_0 + b_1/a_1 _+ b_2/a_2 _+ b_3/a_3 _+ ... .
One might wonder what this means. If f is an infinite continued fraction,
you can define its convergents using the same equations as above.
Consider the infinite sequence f_0, f_1, f_2, ... . If this sequence
converges to some fixed value, we assign that value to f.
If a continued fraction (either finite or infinite) has all its b_i equal to
1, and all its a_i are integers, and all the a_i with i > 0 are non-negative,
it is called a simple continued fraction. Simple continued fractions are
often written by listing their a_i, like so:.
f = [a_0, a_1, a_2, ... a_m] for a finite continued fraction,
or f = [a_0, a_1, a_2, ...] for an infinite continued fraction.
All simple continued fractions converge to some value.
Continued fractions that are not simple are called general continued
fractions.
Simple continued fractions are important in number theory. They can be used
to approximate irrational numbers by fractions, to prove that particular
irrational numbers are in fact irrational and to solve Diophantine equations.
General continued fractions are sometimes used in analysis to find the value
of special functions in regions where power series converge poorly. They are
related to the theory of how to approximate functions with ratios of two
polynomials (rational approximation or Pade approximation). Any power series
can be rewritten as a general continued fraction. A special function with a
three term recursion relation (such as an orthogonal polynomial), can be
written as a general continued fraction. General continued fractions also
crop up when one is inverting a tridiagonal matrix, and as a substitute for
the transfer matrix method.
"Continued Fractions" by C. D. Olds, copyright 1963. This little book is oriented towards number theory. It can be understood by bright high school students. It's also a good introduction to continued fractions. Unfortunately, it's out of print.
"Continued Fractions Analytical Theory and Applications (volume 11 of Encyclopedia of Mathematics and Its Applications)" by William B. Jones, copyright 1980. This is a tome. Unfortunately, it also is out of print.
Here is a program written in C that uses continued fractions to compute arctangents and error functions. It is a text file. The algorithm is as described below. I was inspired to write this program after Bob Delaney wrote a continued fraction program to compute arctangents.
A good way to evaluate a continued fraction is to evaluate the
convergents recursively.
We write the convergent f_i as a fraction f_i = P_i/Q_i.
f_0 = a_0 so we can take P_0 = a_0 and Q_0 = 1.
f_1 = (a_1 * a_0 + b_1)/a_1.
So we can take P_1 = a_1*a_0 + b_1 and Q_1 = a_1.
Then it can be shown by mathematical induction (proof below) that, for i > 1
P_{i+1} = a_{i+1} * P_i + b_{i+1} * P_{i-1} (1a)
and
Q_{i+1} = a_{i+1} * Q_i + b_{i+1} * Q_{i-1} . (1b)
If you define P_{-1} = 1 and Q_{-1} = 0 you can use these recursion relations
for i > 0.
In this way, if you want just one more convergent, you need to do just a
little more work instead of starting over from the beginning. These recursion
relations can be formally rewritten in terms of 2*2 matrices:
___ ___ ___ ___ ___ ___
| P_{i+1} | = | a_{i+1} b_{i+1}| | P_i |
| P_i | | 1 0 | | P_{i-1} |
--- --- --- --- --- ---
and similarly
___ ___ ___ ___ ___ ___
| Q_{i+1} | = | a_{i+1} b_{i+1}| | Q_i |
| Q_i | | 1 0 | | Q_{i-1} | .
--- --- --- --- --- ---
Proof of the recursion relationships (1)
First we show that they are true for i=2.
We to write f_2 as f_2 = P_2/Q_2.
What follows looks lengthy, but only because I wrote out all the steps.
f_2 = a_0 + b_1/(a_1 + b_2/a_2)
= a_0 + b_1/[(a_2*a_1 +b_2)/a_2]
= a_0 + b_1*a_2/(a_2*a_1 +b_2)
= (a_2*a_1*a_0 + b_2*a_0 + b_1*a_2) / (a_2*a_1 + b_2)
= [a_2*(a_1*a_0 + b_1) + b_2*a_0] / [a_2*a_1 + b_2*1]
= [a_2*P_1 + b_2*P_0] / [a_2*Q_1 + b_2*Q_0].
So we can take P_2 = a_2*P_1 + b_2*P_0 and Q_2 = a_2*Q_1 + b_2*Q_0.
So equations(1) are true for i = 2. Now assume that they're true for i =
1, 2, ... n. Then let's show that they must also be true for i = n+1.
f_{n+1} = a_0 + b_1
____________
a_1 + b_2
____________
a_2 + b_3
_____________
a_3 + .
.
.
a_{n-1} + b_n
_____________
a_n + b_{n+1}
_______ .
a_{n+1}
But, similarly to what we just did,
b_n
____________
a_n + b_{n+1}
_______
a_{n+1}
= b_n / [a_n + b_{n+1}/a_{n+1}]
= b_n / [(a_{n+1}*a_n + b_{n+1})/a_{n+1}]
= a_{n+1}*b_n / (a_{n+1}*a_n + b_{n+1})
= b'_n/a'_n
where a'_n = a_{n+1}*a_n + b_{n+1}
and b'_n = a_{n+1}*b_n.
So f_{n+1} can be put in the same form as an nth convergent except with a_n
replaced by a'_n and b_n replaced by b'_n:
f_{n+1} = a_0 + b_1
____________
a_1 + b_2
________________
a_2 + b_3
_____________
a_3 + .
.
.
a_{n-1} + b'_n
_____ .
a'_n
So, since the recursion relations (1) are assumed to be true for 1 < i <= n,
we can rewrite f_{n+1} as
f_{n+1} = [a'_n*P_{n-1} + b'_n*P_{n-2}] / [a'_n*Q_{n-1} + b'_n*Q_{n-2}].
That is, we can take
P_{n+1} = a'_n*P_{n-1} + b'_n*P_{n-2} and
Q_{n+1} = a'_n*Q_{n-1} + b'_n*Q_{n-2} .
Now work with these expressions for P_{n+1} and Q_{n+1}. Start with P_{n+1}.
Remembering what a'_n and b'_n are:
P_{n+1} = [a_{n+1}*a_n + b_{n+1}]*P_{n-1} + [a_{n+1}*b_n]*P_{n-2}
= a_{n+1}*[a_n*P_{n-1} + b_n*P_{n-2}] + b_{n+1}*P_{n-1} .
But a_n*P_{n-1} + b_n*P_{n-2} = P_n, since (1a) is assumed to be true for
1 < i <= n. So
P_{n+1} = a_{n+1}*P_n + b_{n+1}*P_{n-1}, which is (1a) for i = n+1.
Similarly,
Q_{n+1} = a'_n*Q_{n-1} + b'_n*Q_{n-2}
= [a_{n+1}*a_n + b_{n+1}]*Q_{n-1} + [a_{n+1}*b_n]*Q_{n-2}
= a_{n+1}*[a_n*Q_{n-1} + b_n*Q_{n-2}] + b_{n+1}*Q_{n-1}
= a_{n+1}*Q_n + b_{n+1}*Q_{n-1}, which is (1b) for i = n+1.
So we have shown that the recursion relations (1) are true for i=2 and that if
they are true for i = 1, 2, ... n they are also true for i=n+1. So, by
mathematical induction, they are true for all n > 1.
Now, if you arbitrarily define P_-1 = 1 and Q_-1 = 0,
P_1 = a_1*a_0 + b_1 = a_1*a_0 + b_1*1 = a_1*P_0 + b_1*P_-1
and
Q_1 = a_1 = a_1*1 +b_1*0 = a_1*Q_0 + b_1*Q_-1 .
So with these arbitrary definitions of P_-1 and Q_-1 the recursion relation (1)
works for all n>= 1.
<To get my e-mail address, replace "at" with "@" & remove the spaces: Homepage