A little about continued fractions(This file is best viewed in a nonproportional font.) Definition of Continued FractionsContinued 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.
References
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 moved to write this program after Bob Delaney wrote a continued fraction program to compute arctangents. How to evaluate continued fractionsWhat one actually evaluates is a convergent f_n. There are two common ways of doing this, which Jones and Thron call the "backward recurrence algorithm" and the "forward recurrence algorithm". Backward Recurrence AlgorithmThis is the more intuitive method. It consists of evaluating the expression for f_n by starting at the end (or bottom) and working ones way back to the begining (or top). Thus one first finds b_n / a/n. Then one adds a_(n-1), takes the reciprocal, multiplies by b_(n-1) adds a_(n-2) and so on... One advantage of this method is that it is easy to understand and program. Also, according to Jones and Thron (page 26), This method is often more numerically stable than the forward recurrence method. Its big disadvantage is that you don't necessarily know in advance what value of n you want to go to. If you have found f_n using this method, you need to start over from scratch to find f_(n+1). Forward recurrence AlgorithmThis method allows one to evaluate the convergents f-1, f_2 and so on recursively.
The advantage of this method is that the work done in finding f_n can be reused
if one then decides to find f_(n+1). A possible disadvantage, according to Jones
and Thron, is that in some situations, it may be less numerically stable than the
backward recurrence algorithm.
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:christopher e reed at cs . com> This page was created on June 9, 2002. It was changed/fiddled with on February 18, 2009. Homepage |