| Continued Fraction |
Article Index for Continued Fraction |
Articles about Continued Fraction |
Website Links For Fraction |
Information AboutContinued Fraction |
| CATEGORIES ABOUT CONTINUED FRACTION | |
| continued fractions | |
| mathematical analysis | |
|
: where ''a''0 is some Integer and all the other numbers ''a''''n'' are ''positive'' integers. Longer expressions are defined analogously. If the partial numerators and '''partial denominators''' are allowed to assume arbitrary values, which may in some contexts include Function s, the resulting expression is a Generalized Continued Fraction . When it is necessary to distinguish the standard form above from generalized continued fractions, it may be called a '''simple''' or '''regular continued fraction''', or is said to be in '''canonical form'''. MOTIVATION The study of continued fractions is motivated by a desire to have a "mathematically pure" representation for the Real Number s. Most people are familiar with the Decimal Representation of real numbers: : where ''a''0 may be any integer, and each other ''a''''i'' is an element of {0, 1, 2, ..., 9}. In this representation, the number π, for example, is represented by the sequence of integers {3, 1, 4, 1, 5, 9, 2, ...}. This decimal representation has some problems. For example, the constant 10 is used in this case because we are computing here in the base 10 numeral system. We might wish to use base 8 ( Octal ) or base 2 ( Binary ). Another problem is that many Rational Number s lack finite representations in this system. For example, the number 1/3 is represented by the infinite sequence {0, 3, 3, 3, 3, ....}. Continued fraction notation is a representation for the real numbers that avoids both these problems. Let us consider how we might describe a number like 415/93, which is around 4.4624. This is approximately 4. Actually it is a little bit more than 4, about 4 + 1/2. But the 2 in the denominator is not correct; the correct denominator is a little bit ''more'' than 2, about 2 + 1/6, so 415/93 is approximately 4 + 1/(2 + 1/6). But the 6 in the denominator is not correct; the correct denominator is a little bit more than 6, actually 6+1/7. So 415/93 is actually 4+1/(2+1/(6+1/7)). This ''is'' exact. Dropping the redundant parts of the expression 4 + 1/(2 + 1/(6 + 1/7)) gives the abbreviated notation The continued fraction representation of real numbers can be defined in this way. It has several desirable properties:
This last property is extremely important, and is not true of the conventional decimal representation. Truncating the decimal representation of a number yields a rational approximation of that number, but not usually a very good approximation. For example, truncating 1/7 = 0.142857... at various places yields approximations such as 142/1000, 14/100, and 1/10. But clearly the best rational approximation is "1/7" itself. Truncating the decimal representation of π yields approximations such as 31415/10000 and 314/100. The continued fraction representation of π begins 7, 15, 1, 292, ... . Truncating this representation yields the excellent rational approximations 3, 22/7, 333/106, 355/113, 103993/33102, ... The denominators of 314/100 and 333/106 are almost the same, but the error in the approximation 314/100 is nineteen times as large as the error in 333/106. As an approximation to π, 7, 15, 1 is more than one hundred times more accurate than 3.1416. CALCULATING CONTINUED FRACTION REPRESENTATIONS Consider a real number ''r''. Let ''i'' be the integer part and ''f'' the fractional part of ''r''. Then the continued fraction representation of ''r'' is To calculate a continued fraction representation of a number ''r'', write down the integer part (technically the Floor ) of ''r''. Subtract this integer part from ''r''. If the difference is 0, stop; otherwise find the reciprocal of the difference and repeat. The procedure will halt if and only if ''r'' was rational.
SOME USEFUL THEOREMS If ''a''0, ''a''1, ''a''2, ... is an infinite sequence of positive integers, define the sequences and recursively: Theorem 1 For any positive : Theorem 2 The convergents of ''a''1, ''a''2, ... are given by : Theorem 3 If the ''n''th convergent to a continued fraction is , then : Corollary 1: Each convergent is in its lowest terms (for if and had a nontrivial common divisor it would divide , which is impossible). Corollary 2: The difference between successive convergents is a fraction whose numerator is unity: : Corollary 3: The continued fraction is equivalent to a series of alternating terms: : Corollary 4: The matrix :
Theorem 4 Each (''s''th) convergent is nearer to a subsequent (''n''th) convergent than any preceding (''r''th) convergent is. In symbols, if the ''n''th convergent is taken to be , then Corollary 1: any convergent is nearer to the continued fraction than any other fraction whose denominator is less than that of the convergent Corollary 2: any convergent which immediately precedes a large quotient is a near approximation to the continued fraction. SEMICONVERGENTS If and are successive convergents, then any fraction of the form : where is a nonnegative integer and the numerators and denominators are between the and terms inclusive are called ''semiconvergents'', secondary convergents, or intermediate fractions. Often the term is taken to mean that being a semiconvergent excludes the possibility of being a convergent, rather than that a convergent is a kind of semiconvergent. The semiconvergents to the continued fraction expansion of a real number include all the rational approximations which are better than any approximation with a smaller denominator. Another useful property is that consecutive semiconvergents a/b and c/d are such that . BEST RATIONAL APPROXIMATIONS A ''best rational approximation'' to a real number ''x'' is a rational number ''n''⁄''d'', ''d'' > 0, that is closer to ''x'' than any approximation with a smaller denominator. The simple continued fraction for ''x'' generates ''all'' of the best rational approximations for ''x'' according to three rules: #Truncate the continued fraction, and possibly decrement its last term. #The decremented term cannot have less than half its original value. #If the final term is even, a special rule decides if half its value is admissible. (See below.) For example, 0.84375 has continued fraction {Link without Title} . Here are all of its best rational approximations. The strictly monotonic increase in the denominators as additional terms are included permits an algorithm to impose a limit, either on size of denominator or closeness of approximation. To incorporate a new term into a rational approximation, only the two previous convergents are necessary. If ''a''''k''+1 is the new term, then the new numerator and denominator are n d The initial "convergents" (required for the first two terms) are 0⁄1 and 1⁄0. For example, here are the convergents for {Link without Title} . One formal description of the half rule is that the halved term, 1⁄2 ''a''''k'', is admissible if and only if : ''a''''k''−1, …, ''a''1 > ''a''''k''+1, … . In practice, something like Euclid's GCD algorithm is often used to generate the terms sequentially, and the auxiliary values it provides allow a more convenient test. For example, here is the term generation for 0.84375 = 27⁄32. Using the ''f'' values so generated, the 1⁄2 ''a''''k'' admissibility test is ''d''''k''−2 ⁄ ''d''''k''−1 > ''f''''k'' ⁄ ''f''''k''−1. For ''a''3 of the example, ''d''1 ⁄ ''d''2 = 1⁄6 and ''f''3 ⁄ ''f''2 = 1⁄2, so 1⁄2 ''a''3 is not admissible; while for ''a''4, ''d''2 ⁄ ''d''3 = 6⁄13 and ''f''4 ⁄ ''f''3 = 0⁄1, so 1⁄2 ''a''4 is admissible. : where each of the numerators is an Odd Number Squared . OTHER CONTINUED FRACTION EXPANSIONS Periodic continued fractions The numbers with periodic continued fraction expansion are precisely the irrational solutions of Quadratic Equation s with rational coefficients (rational solutions have finite continued fraction expansions as previously stated). The simplest examples are the Golden Ratio φ = 1, 1, 1, 1, 1, ... and √ 2 = 2, 2, 2, 2, ... ; while √14 = and √42 = [6;2,12,2,12,2,12... . All irrational square roots of integers have a special form for the period; a symmetrical string, like the empty string (for √ 2) or 1,2,1 (for √14), followed by the double of the leading integer. A property of the golden ratio φ An interesting result, stemming from the fact that the continued fraction expansion for φ doesn't use any integers greater than 1, is that φ is one of the most "difficult" real numbers to approximate with rational numbers. One theorem states that any real number ''k'' can be approximated by rational ''m''/''n'' with Regular patterns in continued fractions While one cannot discern any pattern in the simple continued fraction expansion of π, this is not true for ''e'', the Base Of The Natural Logarithm : : We also have, when ''n'' is an integer greater than one, : Another, more complex pattern appears in this continued fraction expansion: : Other continued fractions of this sort are : where ''n'' is a positive integer; also : and, for integral ''n''>1, : If ''I''''n''(''x'') is the modified, or hyperbolic, Bessel Function of the first kind, we may define a function on the rationals ''p''/''q'' by : which is defined for all rational numbers, with ''p'' and ''q'' in lowest terms. Then for all nonnegative rationals, we have : with similar formulas for negative rationals; in particular we have : The last two formulas are most easily proven in terms of the Bessel-Clifford Function . Typical continued fractions Most irrational numbers do not have any periodic or regular behavior in their continued fraction expansion. Nevertheless is a constant (known as Khinchin's Constant , ''K'' ≈ 2.6854520010...) independent of the value of ''x''. Paul Lévy showed that the ''n''th root of the denominator of the ''n''th convergent of the continued fraction expansion of almost all real numbers approaches an asymptotic limit, which is known as Lévy's Constant . PELL'S EQUATION Continued fractions play an essential role in the solution of Pell's Equation . For example, for positive integers and , if and only if is a convergent of . CONTINUED FRACTIONS AND CHAOS Continued fractions also play a role in the study of Chaos , where they tie together the Farey Fractions which are seen in the Mandelbrot Set with Minkowski's Question Mark Function and the Modular Group Gamma. The backwards of this map is called the Gauss-Kuzmin-Wirsing Operator . The distribution of the digits in continued fractions is given by the zero'th Eigenvector of this operator, and is called the Gauss-Kuzmin Distribution . HISTORY OF CONTINUED FRACTIONS
: Cataldi represented a continued fraction as & & & with the dots indicating where the following fractions went.
SEE ALSO
EXTERNAL LINKS
REFERENCES
|
|
|