WORK IN PROGRESS. Please do not comment.
Be it for recreational or serious use, continued fractions are a formidable mathematic tool. These multi-level fractions look formidable when written out in full, but are simplified by nifty notation and cunning calculation. Ordinary fractions, or for those with refined tastes vulgar fractions, are just a way of representing the division of a numerator by a denominator. Continued fractions are like ordinary fractions, but with further fractions in the denominator, and these further fractions have denominators with further fractions ... and so on. The result is a super-duper fraction, which can be reduced to a single numerator and denominator without using division and without the drudgery usually associated with working with fractions, using the methods developed below.
Nothing beyond elementary arithmetic is required for this, although the explanations are necessarily in terms of algebra and use the principle of induction, which is explained in Basic Methods of Mathematical Proof.
Continued fraction theory has developed in two quite distinct directions, one chiefly concerned with Number Theory, the other concerned with Analysis. This introduction focuses on those aspects of continued fraction theory most useful for recreational problems, that is the approximation of arbitrary values using only integers, which can be helpful in the solution of Diophantine Equations. There are serious uses as well as recreational ones.
Problems Solved
To be used effectively, this mathematical form must be understood. Using only the methods presented here, the following types of problem are easily solved
The fraction which produces a given recurring decimal, for example 0.123454545... can readily be found. This problem can be solved by other means, and by elementary methods the given example is readily shown to be 123⁄1000 + 45⁄99000. The devil is in the detail, for after calculating the sum by the normal rules for fractions, the result must be reduced to its simplest form by removing common factors from numerator and denominator. That too can be performed by well known methods, in particular the Euclidean Algorithm. The method provided by the use of continued fractions is very easy to perform with a standard calculator.
The simple numerical ratio, that is, the fraction represented by a given decimal value, may be required. For example we may wish to know the simplest ratio represented by 0.76471, which is not merely the obvious answer of 76471/10000. The nature of decimals means that the example 0.76471 represents all numbers in the range 0.764705 to 0.764715, and then the result required is 13⁄17 or 0.764705882..., but knowing this begs the question. Continued fractions readily provide a direct route to the required answer.
It is well known that the value √2 is an irrational number, and therefore cannot be represented as a fraction. However, if an approximation is required, say with a denominator not exceeding 255, what fraction should be used. Obviously, trying every possible denominator from 1 to 255, would be extremely laborious. Continued fractions provide sequences of best approximations with ease.
Motivation
It is known that √2 is an irrational number, meaning that it cannot possibly be expressed as the ratio of two integers, that is, as a rational number. This does not preclude rational numbers being good approximations to √2, and attempting to obtain them leads naturally to continued fractions.
An approximate value for √2 is required, and obviously the more accurate this is, the better. The value must be produced from integers using only rational operations, that is add, subtract, multiply and divide. Strictly speaking, this means that √2 must be defined as the positive number x such that x2 = 2, because the square root operation is not rational. (This may be mathematical precision applied to excess, but will not impede finding approximations to √2.)
When the numbers a, b and c are all positive, then a < b < c implies that a2 < b2 < c2 and conversely. Using a = 1, b = x and c = 2 shows that 1 < x < 2, because 1 < x2 =2 < 4. Putting x = 1 + t then gives 0 < t < 1. By the well known difference of two squares formula (x + 1)(x − 1) = x2 − 1, and substituting x2 = 2, it is found that (x + 1)(x − 1) = 1, and thus that
(x − 1) = 1 ⁄ (x + 1), which in terms of t means that t = 1 ⁄ (2 + t)
| The result is that | √2 | = | 1 | + | | but there is a snag
|
****** ARTEFACT OF INCOMPLETE EDIT ******
The value √2 is 1.414214 (to six decimal places), but supposing that this is not known, one can try to √2, using only integers.
Definitions and Notation
A continued fraction is the sum of a principal part and a fraction which is the quotient of a partial numerator and a denominator which is a continued fraction. A continued fraction then has the form
as now explained, with standard nomenclature introduced.
The continued fraction begins with a principal part, shown as b0, which is added to a first quotient, whose partial numerator is shown as a1. The associated denominator is a new continued fraction, with a principal part shown as b1, to emphasise its association with a1. Development of this new continued fraction proceeds in similar fashion, but repeatedly new quotients appear. The jth quotient is typical, having a partial numerator aj, and a continued fraction denominator with principal part bj, augmented by the j+1th quotient. The entity bj is known as a partial denominator, specifically the jth partial denominator.
It is apparent that the definition does not allow a continued fraction to terminate, so its development certainly continues, but forever. A continued fraction is deemed to terminate at the first partial numerator which is zero. This convention ensures that every partial numerator is matched with a partial denominator, since quotients are present or absent in their entirety. When a continued fraction does terminate, the last quotient present becomes a simple fraction, and if the nth quotient, the continued fraction is said to be of nth order. As an nth order continued fraction is of finite form, one would expect that it could be evaluated. A finite fraction F, in which the typical quotient is the jth, and the final quotient is the nth then has the form
in which it matters not whether the expression terminated because an+1 happened to be zero, or simply does not exist. The conventional notation so far used for continued fractions is extremely cumbersome, so a more compact notation will now be used. In common use to denote F as above, the notation is
which hopefully corresponds so obviously to the conventional notation that further explanation is unnecessary. It is important to note the placement of the plus signs as an indicator that a continued fraction is represented, and it is customary to omit the term b0 if it is zero. Non-terminating continued fractions are denoted by trailing ellipsis.
The nomenclature so far used needs a little clarification. The terms partial numerator and partial denominator are widely used, but the term partial fraction is deliberately avoided, since it already has a special meaning in connection with rational functions. With only minor terminological inexactitude, the first principal part b0 is considered to be a partial denominator, although there is no associated quotient or numerator. The term principal part is never used, but was coined to postpone the problem of a denominator without a fraction to live in until now. Please dismiss this sin as an example of lying to children
Continued fractions in which all partial numerators present have the value one are frequently encountered, and are known as regular continued fractions. A yet more compact notation for them, also in wide use, is defined by
| ⁄⁄ | b0, | b1, | b2, | ··· | bj, | bj+1, | ··· | bn−1, | bn | ⁄⁄ | = | b0 | + | | | ··· | | | ··· | | |
although in this new form, to avoid ambiguity the term b0 can never be omitted, even when zero.
****** ARTEFACT OF INCOMPLETE EDIT ******
Given the continued fraction F, a related quantity obtained by truncating F at one of the partial denominators is known as a convergent, and a complete denominator will be called a tail. Denoting the jth convergent by Fj and the jth tail by Tj, then
| Fj | = | | = | b0 | + | | | ··· | | and | Tj | = | bj | + | | | ··· | | = bj | + | |
Evaluation
When a continued fraction is of finite order, then it may be evaluated from the bottom up, in a fairly obvious fashion. However, an interminable continued fraction cannot be evaluated that way, because the bottom level is inaccesible: the continued fraction has an infinite number of levels. A top down method can be derived for use in such circumstances, and it is this method which makes continued fractions so useful.
Bottom Up Evaluation
| Using | Tj | = bj | + | | repeatedly, evaluation of | F | = | b0 | + | | | ··· | | |
starts with Tn = bn, continuing with successive determination of Tn−1, Tn−2, ··· T2, T1, and finally T0 = F.
Proof of the validity of this method rests upon an appeal to the definition of a continued fraction as the sum of a principal part and an added quotient. The given order of evaluation ensures that the denominator has been determined before a quotient is to be formed. The ability to start this process depends upon the fraction being of finite order - it cannot be applied to interminable continued fractions.
As examples of bottom up evaluation, the values of the first three convergents of a continued fraction of order two or more will be determined.
| F0 | = | | = | b0 | so that trivially | F0 | = | T0 | = | b0 | = | |
| F1 | = | | = | b0 | + | | then | T1 | = | b1 | so that | F1 | = | T0 | = | b0 | + | | = | b0 | + | | = | |
| F2 | = | | = | b0 | + | | | then | T2 | = | b2 | and then further | T1 | = | b1 | + | | = | b1 | + | | = | |
| so that | F2 | = | T0 | = | b0 | + | | = | b0 | + | | = | b0 | + | | = | | b0b1b2 + b0a2 + a1b2 | | | b1b2 + a2 |
|
Top Down Evaluation
| It has been shown that | F0 | = | | = | | , | F1 | = | | = | | and | F2 | = | | = | | b0b1b2 + b0a2 + a1b2 | | | b1b2 + a2 |
|
| demonstrating that | F2 | = | | = | | . In general | Fj | = | | = | | , as will now be
|
shown by induction. The general formula is obviously correct when j = 2. Fj is obtained from Fj−1 by replacing bj−1 with bj−1 + aj ⁄ bj, so that by assuming it is true for j − 1, one obtains
| Fj−1 | = | | , | so | Fj | = | | ( | bj−1 | + | aj | ⁄ | bj | ) | Pj−2 | + | aj−1 | Pj−3 |
| | | ( | bj−1 | + | aj | ⁄ | bj | ) | Qj−2 | + | aj−1 | Qj−3 |
|
| = | | ( | bj−1 | bj | + | aj | ) | Pj−2 | + | aj−1 | bj | Pj−3 |
| | | ( | bj−1 | bj | + | aj | ) | Qj−2 | + | aj−1 | bj | Qj−3 |
|
| , | and
|
This recurrence relation is very useful, but applies only when j ≥ 2, requiring determination of P1 and Q1 to get started. By using the fictitious values P−1 = 1 and Q−1 = 0, the recurrence applies when j ≥ 1, requiring determination of P0 and Q0 to get started, which is quite easy. However, using the fictitious values P−2 = 0, Q−2 = 1 and a0 = 1, the recurrence applies when j ≥ 0, so the recurrence gives all values of Pj and Qj for j ≥ 0. It is an implementation issue whether it is easy to manufacture a0 = 1, or to produce P0 = b0 and Q0 = 1 to get started.
Properties of Convergents
The properties of convergents can be deduced from the recurrence relation. Of greatest importance are the values of Fn − Fn−1 and Fn − Fn−2, and the value of Pn−1Qn − PnQn−1 is common to both.
Now Pn−1Qn
− PnQn−1 = Pn−1(bnQn−1
+ anQn−2) − Qn−1(bnPn−1
+ anPn−2) = −an(Pn−2Qn−1 − Pn−1Qn−2), so that after n−1 applications of this reduction Pn−1Qn
− PnQn−1 = (−)n−1anan−1an−2···a2(P0Q1 − P1Q0). Since P0Q1 − P1Q0 = b0b1 − (b0b1 + a1) = −a1, it is found that Pn−1Qn
− PnQn−1 = (−)nanan−1an−2···a2a1. Then
Applications
This entry would be incomplete without some mention of the uses of continued fractions which are not covered here
Many functions which are represented by power series can also be represented as continued fractions, usually with a vast improvement in convergence.
The well known Thiele's method of interpolation by means of rational functions is in essence the expression of tabulated functions in terms of continued fractions.
Well Known Continued Fractions
The interested reader can experiment with the following continued fractions.
Mathematical Constants
The Golden Ratio
φ+k−1 = ⁄⁄ k,1,1,1,1,1,··· ⁄⁄, the most basic simple continued fraction, where every partial denominator is one.
It converges more slowly than any other simple continued fraction.
Pi
π = ⁄⁄ 3,7,15,1,292,1,1,1,2,1,3,1,14,··· ⁄⁄, a simple continued fraction with no known structure.
Its convergents include 22/7 (high by < 0.0013) and 355/113 (high by < 0.00000027)
****** ARTEFACT OF INCOMPLETE EDIT ******
Pi
π = ⁄⁄ 3,7,15,1,292,1,1,1,2,1,3,1,14,··· ⁄⁄, a simple continued fraction with no known structure.
Its convergents include 22/7 (high by < 0.0013) and 355/113 (high by < 0.00000027)
Pi
π = ⁄⁄ 3,7,15,1,292,1,1,1,2,1,3,1,14,··· ⁄⁄, a simple continued fraction with no known structure.
Its convergents include 22/7 (high by < 0.0013) and 355/113 (high by < 0.00000027)
Function Expansions
Although not covered in this entry, continued fraction expansions exist for many functions. Here are some examples.
****** ARTEFACT OF INCOMPLETE EDIT ******
On the Concept of Optimality Interval
GuideML help on Tags, Special Characters, Tables and Approved ML
More on tables in borders,
general and
guide
