Let us assume that our calculator does not have a key for powers with fractional exponents and we want to compute the value of 2½. How would you do it? I would expand it as follows:
Note the regular appearance of this expansion or continued fraction. Next, let us compute it, truncating the formula at several levels. Such steps produce varying truncation errors, and we are led to expect that the result will be exact, if we continue the fraction ad infinitum. We find:
while our calculator gives us 2½ = 1.414 213. We note that the continued fraction converges to 2½, the approximations oscillate about the correct value, and the approximations are rational, i.e., ratios of integers. In other words, we have approximated the irrational number 2½ by a sequence of rational numbers which are, in turn, smaller and larger than 2½. This is certainly an intriguing approach which deserves further investigation. Note that related alogorithms were first proposed in India in the Sixth Century!
What we have done so far does not yet yield a proper algorithm, since we cannot start from one approximation and improve it in a next step. In our calculations, we have always started the computations from the bottom, the truncated end of the continued fraction. Moreover, in the way the formulae have been written, they take up too much space.
Consider the general continued fraction
.
Note the last term in this expression - a simpler, space saving notation, due to the German mathematician Pringsheim in 1898! A continued fraction, for which all bk are equal to 1, is called a simple continued fraction. In many interesting cases, the ak and bk are integers. As we will see later on, they may even be functions of x.
Every rational number can be converted into a finite or infinite, simple continued fraction by the following simple procedure:
,
where the rk are the remainders and the ak the integral parts of the intermediate fractions.
Compute the continued fraction for 62/19.
Find the rational numbers which approximate this fraction!
Find continued fractions for (a) 33/12, (b) 7½.
Naturally, we can apply the same method to non-integers. For example, we can represent Planck's constant 6.624·10-27 by a simple continued fraction which will be easier to remember.
However, before looking at this idea, we will deal with the earlier objection raised regarding the laboriousness of the backward evaluation of continued fractions. We have seen that a finite continued fraction yields a simple fraction
These
fractions are referred to as general or simple convergents, respectively. Since we will require these ratios for k
= -1 and k = 0 and these particular ratios are arbitrary,
it is customary, following the Swiss mathematician Leonhard Euler
(1707 - 1783), to set
where we will see in a minute why we do this.
THEOREM 1 (Formation of general convergents): The numbers Pk,Qk or pk,qk are determined by the recurrence formulae
Induction Proof for General Convergents: Let
.
Then,
Hence the theorem is correct for k = 1. Assume now that it is correct for all positive integers not exceeding k. Then, since the step over from Rk to Rk+1 is effected by replacing ak by
,
we find
.
This proves the theorem for general convergents. Setting all bk = 1, one obtains also the proof for simple convergents.
We see now that we can start evaluations of convergents from the beginning, and hence have removed the earlier mentioned objection. A good scheme for working with convergents follows:
Find 3½ to 4 decimals. My calculator says 1.7320508. We find the continued fraction
Therefore
We find
whence
,
Note how the rational approximations oscillate about the calculator value! Note also that only the ratios pk/qk are unique and that in this case of a finite continued fraction the last ratio is exact!
We can now deal with Planck's constant, multiplied by 1027. One readily finds that
,
and therefore
We see that the number 53/8 gives us Planck's constant with an error of 0.001. At the next step, ak will change to 2? Do it yourself!
Our observation that the rational approximations oscillate around the exact value requires proof. It is given by
THEOREM 2: For two successive covergents Rk and Rk+1,
PROOF
We have
,
but
,
and
,
whence follows the result. Note that for simple convergents, the theorem becomes
,
These formulae allow to give uppper bounds for the accuracy of the approximations, because consecutive convergents lie above or below the exact value of the continued fraction. This is another valuable contribution to a computer program.
In the case of Planck's constant, we find for the errors, since the bk equal 1, i.e., we are dealing with simple fractions:
We see that our rational approximations to 6.624·1027 have the upper error bound 0.025 which is, of course, larger than the actual error.
THEOREM 3:For two successive convergents of equal parity,
The proof follows the above reasoning. For simple convergents, this formula becomes
.
These theorems can be interpreted to mean that, if all ak and bk are positive, then the even and odd convergents form monotonic increasing and decreasing sequences, respectively, each convergent of even order being smaller than any convergent of odd order, i.e., the value of the continued fraction lying in between. These results confirm our observation regarding the oscillations in the values of successive convergents. They yield the absolute upper bounds
where C and c are the exact values of the general and simple continued fractions, respectively. The advantages offered by continued fractions is that they yield rational approximations, i.e., ratios of integers which are more economically stored in a computer than decimal fractions, and that their algorithm is very easily programmed. This is the reason that they became very popular with computer designers, especially, as the same methods could be applied to power series.
I will not discuss in detail the convergence of these processes, but only note that, if all ak and bk are positive,
then the convergents converge to the value of the continued fraction. Furthermore, every positive number may be expanded in a unique fashion in a simple converging continued fraction with integers. If c is a rational number, the fraction terminates, otherwise it is infinite. Examples of this fact are 62/19 and 2½.
Our objective is to expand a rational function of the form
.
We can write
with
and
.
In a similar manner, we continue:
where the last formula may be rewritten in the form
The continued fraction expansion now becomes
If the expressions in the numerator and denominator of f(x) are polynomials, this process will be a terminating continued fraction and yield lower order rational functions as approximations to f(x).
Expand into rational functions the fraction
A computer program can follow the following scheme to find the cj:
Hence
Using now the algorithm for the consecutive evaluation of convergents, we find the rational approximations:
Note that these approximations do not represent the original expression for all values of x. For example, the first one has a pole at x = 1/4, the second at x = 2/7, the original has two poles at 1/3 and 1/2. However, away from these poles, the approximations are quite good. For example,
This work displays the need to check on the applicability of the approximations, i.e., the errors involved and their limitations.
The real value of these methods arises with the expansion of power series. We have seen already that we can start from the beginning and cut off whenever we think it is time to do so. Since only the ratios P/Q are of interest, continued fraction expansions may apparently differ.
Find rational approximations for the exponential function:
Note that the coefficients are powers of 12! We can now obtain the rational functions by expanding the continued fraction.
We can now set x = 1 to obtain for e the rational number 19/7 = 2.714285714286 instead of 2.7182818. If we use the series, we find:
1+1+1/2+1/6+1\24=2.70833333
1+1+1/2+1/6+1\24+1/120=2.716666, etc.
We see that, when it comes to storing the value of e in a computer, it will be much more economical from a storage point of view to store two integers and divide them instead of employing the series. However, as regards ex, we must remember that the zeroes of the denominator of a rational function approximation will impose a restriction on its range of validity. However, we are in the case of the exponential function assisted by the knowledge that we really need only have an accurate approximation for the range 0<x<1, since we can split off from any exponent an integer and multiply the result by the corresponding power of e. I believe that this might be what your calculator does when you use the exponential function. Other functions can be treated in the same manner:
Find the first 5 rational function approximations for::
(1) sin x, (2) tan x,
(3) ln x, (4) cosh x, (5) ln{(1 + x)/(1 - x)),
(6) (1 + x)½, (7) artan x, (8) arsin x,
(9) arcosh x,
evaluate them for x = 0.5 and compare them with the best value your computer or calculator can give you. Compute also the upper bounds of the errors for this value.
Decide between the members of your class what physical constants you will approximate by sufficiently exact rational numbers.