5.1 Approximation by Convergents
5.1.1 High-quality Approximation A tiring march has finally brought you to the goal of your journey. This chapter will disclose the purpose served by continued fractions. In 1.1.1, we have interpreted the problem of approximation in a very broad sense. We switch now to a more specific problem. Take the set R of real numbers* and select in it the subset Mq of all fractions with denominators not greater than q. The problem is to find for each number a Î R the number r Î Mq which is closest to a.
* It is sufficient to consider only the set of positive real numbers, because nothing basically new arises by adding negative numbers: if p » 22/7, then - p » -22/7.
Assume now that you were able to find such a number, that is, that you have found an approximation a » r. The usefulness of this approximation is that the accuracy cannot be improved without increasing the denominator; indeed, in Mq, r is the number closest to a.
Note that if you choose to take the set of fractions with denominators exactly equal to q, this approximation would not, in general, be of high quality in the sense outlined above. For example, you see from Table 1 in 1.4.4 that the approximation of p in units of 1/10 has low quality in comparison with larger fractional units, namely, 1/9, 1/8, 1/7 and 1/6.
In approximation theory, the concept of quality does not have a single, sharply defined meaning, so that you must specify each time in what sense this term is being used.
5.1.2. The Main Property of Convergents We can define the best rational approximation to a number a as a fraction p/q which yields a lower absolute error than any other fraction with a denominator £ q (obviously, in this sense, the best approximation is not unique). By this definition, convergents provide the best approximations to a continued fraction. At times, this property is said to constitute the main property of convergents. Let us give it the formulation:
Theorem If pn/qn (n ³ 1) is a convergent for the number a and p/q is any other fraction with q £ qn, then
This means that the convergent yields an approximation which cannot be improved without increasing the denominator.
Proof: Consider the two cases: 1. q < qn and 2. q = qn (we shall see that the second is trivial).
1. The number a belongs to a segment between the two convergents pn/qn and pn+1/qn+1 (Fig. 12). The length of this segment is |Dn| = 1/qnqn+1. The point a may either be an internal point of this segment or coincide with pn+1/qn+1 (if a is rational and pn+1/qn+1 is the last convergent). Hence
Let p/q be an arbitrary fraction the denominator of which is less that qn, whence it certainly is less than qn+1:
Find the distance from p/q to the ends of the segment [pn/qn, pn+1/qn+1]:
These inequalities are only strengthened if q on the right hand sides are replaced by qn and qn+1:
The inequalities show that each end of segment a segment [pn/qn, pn+1/qn+1] and the point p/q are seperated by a distance which is larger than the length of the segment |Dn|. Marking off the segment |Dn| to the left and to the right of the points pn/qn and pn+1/qn+1 (Fig. 12), you find the forbidden zone |AB|-[pn/qn-Dn, pn+1/qn+1+ Dn] which cannot contain the fraction p/q (since the points A and B are also forbidden). It is now clear that p/q is a poorer approximation to a than pn/qn. Indeed,
whence
2. Analyse the case q = qn. Can another fraction with the same denominator provide a better or equally good approximation than the convergent? In other words, can it happen that
For the sake of definiteness, assume that pn/qn lies to the left of a (Fig. 13),
that is, n is even (the argument is quite similar if n is odd). Can a be closer to (pn+1)/qn than to pn/qn or at least lie at the centre, that is, can possibly
This is equivalent to
On the other hand, we know that
The inequalities (36) and (37) yield
that is, qn+1 £ 2.
It means that the inequality (36) is only possible if qn+1 = 1 or 2. This situation occurs only if n = 0 and 1.
The following example shows that (36) can indeed hold under these conditions:
[2; 2] = 2 + 1/2.
In this example, p0/q0 = 2/1. Although the fraction 3/1 is not a convergent, it provides an approximation that is just as good. No such example can be given for n = 4, because 1 cannot be the last term of a continued fraction.
Note that the converse theorem does not hold, that is, the property proved above does not exclusively concern convergents. There exist fractions which are not convergents, but nevertheless give better approximations to a number a than any fraction with a smaller denominator. For example, 3.1.1 lists the convergents of 61/27 = [2; 3, 1, 6]. You can verify* that the approximations
are the best. Their absolute errors
are less than those for any fraction with a smaller denominator, although these two fractions are not convergents. The theorem, as it has been proved, does not mean therefore that convergents provide the best approximations to real numbers.
* Cf. footnote at the end of Chapter IV.
5.1.3. Convergenta have the Highest Quality If the quality of an approximation is evaluated in a different sense, that is, as described in 1.1.4, then convergents have no competitors.
The point is that it would be unfair to evaluate the quality of an approximation by the quantity |a - p/q| independently of the magnitude of the fractional unit. Higher accuracy can be demanded from smaller fractional units (i.e. those with a larger q). Consequently, it is desirable to estimate the absolute error |a - p/q| on a q-dependent scale, for example, multiplying |a - p/q| by q. The result is the normalized absolute error
or the quality factor
Judging by these characteristics, the choice are the convergents, and nothing else but them. They have the highest quality: The normalized absolute error of a convergent is smaller (and hence, the quality factor is greater) than in all other fractions with smaller (or identical) denominators.
But this is not yet the end. Convergents are found to have a quality higher than not only that of fractions with smaller or equal denominators, but even of fractions with the nearest greater denominators: The quality will not be increased by increasing the denominator until you reach the denominator of the next convergent.
These arguments hide two trivial exceptions which will surface in the course of our analysis.
We will now summarize the above reasoning in two theorems which are the inverse of each other.
Theorem 1 If pn/qn is a convergent for a number a and p/q is an arbitrary fraction with q < qn+1, then
The equality sign occurs only if: 1. a = pn+1/qn+1, that is, pn/qn is the last but one convergent, 2. n = 0, a = [a0; 2].
Proof: Note that p/q is a different fraction, that is, we eliminate the uninteresting case p/q = pn/qn. Hereafter, we will assume that the fraction p/q is irreducible to lower terms.
We shall consider separately the two cases: 1. 0 <q < qn+1, q ¹ qn, 2. q = qn.
1. Represent p and q by identical linear combinations (with identical coefficients) of the corresponding terms of the convergents pn/qn and pn+1/qn+1, that is
This system yields the coeffidents x and y.
The determinant of (38) - pn+1qn - pn/qn+1 - is recalled from (12):
The system (38) determines the pair of numbers xand y in a single-valued manner because Dn ¹ 0. Moreover, |Dn |, = 1, whence we conclude that x and y are integers.
Both x and y are non-zero. Indeed, if x = 0, the system (38) yields y = 1 (because both fractions p/q and pn+1/qn+1 are irreducible to lower terms) and q = qn+1, in contradiction to the imposed condition. And if y = 0, you likewise obtain q = qn, which is the case to be analysed below.
The coefficients x and y cannot have the same sign. It x > 0 and y > 0, then the first equation (38) would yield q > qn+1. If x < 0 and y < 0, then p and q would be negative. Hence, x and y have different signs.
In order to find the normalized absolute error of the fraction p/q, start by multiplying the first equation by a and subtract from it the second equation:
The differences in the brackets on the left-hand side of (39) have different signs (because the convergents pnqn and pn+1qn+1 approximate a from opposite sides). The numbers x and y also have different signs. Both terms on the left hand side are therefore positive (more precisely, the first is strictly positive and the second is non-negative). Hence,
and therefore
as had to be proved.
Determine now the conditions corresponding to the equality sign in (40). As follows from the above analysis, this is only possible if
Consider (41) in more detail. If x = 1, y < 0. But then the first equation (38) would yield q < 0, whence x ¹ 1 and therefore x = -1. This entails y = 1. Indeed, if it is assumed that y > I, then the first equation (38) can be rewritten
and implies q > qn+1. The assumed situation in the case (41) thus becomes x=-1, y=1, that is,
This entails the equality sign in (40).
Note that the first condition in (42) can be transformed into
In the case under consideration, an+1 is the last term of the continued fraction, whence, an+1 ³ 2. The last equality thus implies
Thus, in (40), equality cannot occur when q < qn.
2. Next, consider the case q = qn. It is known from 5.1.1 that then for p ¹ pn
Multiplying both sides of this inequality by qn, you obtain
which completes the proof (of course, the exceptional case when n = 0 is also included here). The theorem has thus been proved for all q < qn+1.
Theorem 2 (converse) If the normalized absolute error for a number a and a fraction p/q is less than that for any other fraction p'/q' and q' £ q, then p/q is a convergent for a.
Proof: As always, assume that the fraction p/q cannot be reduced to lower terms. Besides, if a is rational, i.e., a = pn+1/qn+1, then q cannot be greater than qn+1, because the normalized absolute error for the fraction pn+1/qn+1 is zero, while, according to the initial condition, it should be greater than |qa - p|.
Assume now that p/q is not a convergent. Then its denominator lies somewhere between the denominators of two neighbouring convergents, that is,
The direct theorem then yields
This contradicts the condition stated in the theorem: Since qn < q, p/q must yield a smaller normalized absolute error than pn/qn. Hence the assumption that p/q is not a convergent is false.
Note 1 It has been proved that convergents, and only convergents provide a smaller normalized absolute error and hence a larger quality factor than all other fractions with smaller denominators.
Why with smaller denominators only? Could it apply to fractions with slightly larger denominators?
No, it could not! Only the direct theorem holds for denominators q in the interval qn < q < qn+1, and it cannot be converted.
Note 2. Consider in more detail the case (41):
We shall directly demonstrate that although the fraction
is not a convergent and qn < q < qn+1, this fraction nevertheless has the same quality as the convergent pn/qn.
The following manipulations need not be explained:
that is, |qa - p| = |qna - pn| . Recall that this would be impossible in the case q<qn: It implies |qa - p| < |qna - pn|.
For example, the consecutive convergents for the fraction a = 61/27 (cf. 3.1.1) are
The fraction p/q = (p2 - p3)/(q2 - q3) = 52/23 has the same quality as 9/4 despite the fact that 4 < 23 < 27.
Note 3. Compare the approximations of the fraction a = 61/27 with denominators 1, 2, 3, 4 (Table 2),
Inspection of this table lets you without expanding the number 61/27 into a continued fraction determine that 9/4 is its convergent: The quality factor of 9/4 is larger than all preceding factors. The same is true for the fraction 7/3. However, 5/2 is not a convergent because its quality factor is less than that of 2/1.