Continued fraction

In mathematics, and in particular the theory of numbers, a continued fraction ( continued fraction ) is an expression of the form

A chain- breaking is therefore a mixed fraction of the mold, in which the denominator x again is in the form of a mixed fraction, wherein the assembly further so continues.

Each real number can be expressed as ... a chain breaking with integers a, b, c, d, e, f. Continued fractions can therefore be called a number system, such as the decimal system. However, they are primarily not for calculating, but rather are used to solve approximation problems: They deliver in number theory approximations for real numbers, in that they are expressed by a fraction of integers (Example: π is approximately) and in the numerical analysis are approximated by functions it, similar to what is achieved by means of a power series.

Of particular importance are regular continued fractions. In this form, all counters ( b, d, f, ... ) returns 1 A regular continued fraction is thus the result of a, c, e, ... determined, and to write it to save space as [a, c, e, ... ]. In this notation, circle number π has the regular continued fraction expansion of π = [ 3; 7,15,1,292,1, ...].

Continued fractions also play an important role in number theory. So with their help, for example, Joseph Liouville in 1844 showed that transcendental numbers exist. Except in number theory are continued fractions as in cryptography, algebraic geometry, topology, function theory and numerical analysis are used.

• 3.1 Finite continued fractions and their convergents
• 3.2 Matrix representation
• 3.3 Finite continued fractions and the Euclidean algorithm

• 4.1 infinite continued fractions: convergence and approximation breaks
• 4.2 infinite continued fractions and generalized Euclidean algorithm
• 4.3 Equivalent numbers

• 5.1 Euler- Lagrange
• 5.2 Examples
• 5.3 Pellsche equation

• 6.1 Two ways best approximation
• 6.2 convergents are best approximations
• 6.3 Approximation of up and down, side convergents
• 6.4 Theorems on quadratic approximability

• 7.1 Khinchin constant
• 7.2 Comparison of continued fraction and decimal

History

Continued fractions are used since the 16th century to find " good convergents " for irrational numbers. The best known example is the approximation 22/7 for π.

Rafael Bombelli used continued fractions already in 1579 in order to calculate square roots. In 1613 Pietro Cataldi published a book in which appear among other continued fractions. 1636 continued fractions found in the book " Deliciae Physic - Mathematicae " by Daniel Schwenter and from 1655 in several books by John Wallis. Out of the need to approximate fractions with large denominators as well as natural constants, first Christiaan Huygens employed in the 17th century with continued fractions. He calculated so from the periods of the planets, the gear ratio of the gears for his gear model of the solar system. Huygens determined the orbital period around the Sun the ratio between Saturn and Earth as

The continued fraction for this begins with [ 29; 2,2,1,5,1,4, ...]. We approximate this relationship with the proximity breach, which arises when one uses only the first four entries, then the error is only 0.003123, as

In Leonhard Euler's correspondence continued fractions occur, however, first in a completely different context, namely in connection with the Riccatischen differential equation. Soon, however, Euler was interested in continued fractions for its own sake. Namely He discovered the following three important properties:

Some of these findings had already won Huygens, Euler whose work was, however, unknown. Euler's work - and, based on the Joseph -Louis Lagrange - founded the theory of continued fractions.

For rational approximation in addition to the algorithm of Euler also exists an algorithm of Lord William Brouncker. Euler demonstrated to 1759, that the two algorithms are identical. Johann Heinrich Lambert continued fractions used in his work from 1766 to show the irrationality of. Its continued fraction expansion of the tangent function is shown in the right figure.

Moritz Abraham Stern created in 1832 the first systematic summary of the theory of continued fractions. In the 19th century, the theory of a summary of the knowledge that as a standard work is still regarded (new edition 1954/57 ) developed rapidly on and so Oskar Perron published in 1913.

Other important applications were and are: evidence of irrationality or transcendence of special numbers and the determination of leap years ( as a year of 365.24219 days slightly shorter than 365 ¼ days is, it also needs to leap day every four years, a further correction, the best choice for it can be combined with continued fractions justified).

Definition

Term of the continued fraction

An (infinite ) continued fraction is a continued fraction of the form

With and for.

The fractures and are called partial fractions, ie the i- th partial numerator and the i-th partial denominator. A continued fraction that does not continue to be made after a partial break, is a finite continued fraction.

A more formal definition can be found in section representation as a composition of mappings.

Regular continued fractions are the most important by far continued fraction type in number theory. In the approximation of ( real or complex ) functions are also used continued fractions with unknowns, see for example the Lambert's continued fraction for the tangent function in the "History " section. Sometimes it takes a finite regular continued fraction, in which the last entry is a real ( non- whole ) number. This allows, for example, the notation, etc., for the Golden number. Also, sometimes general continued fractions with use.

Notation

The shorthand notation for a general continued fraction is

Based on the sum and product signs Σ and Π Gauss led this and the following notation:

A regular continued fraction is often written in the following manner:

Is therefore only listed separately because it is off, the following are always getting out.

The notation for finite continued fractions is accordingly

Representation as a composition of mappings

One can represent a continued fraction as a composition of pictures. This provides a more formal definition than the previously given.

For this purpose is given to and receives

The definition of infinite continued fractions is performed by a threshold consideration in Section infinite continued fractions.

Finite continued fractions

Finite continued fractions and their convergents

From now on, we consider only regular continued fractions. If you break the chain fraction [ b0, b1, ..., bN ] in accordance with the nth term, ie as

Be the n-th approximation break (or nth convergent ). The first convergents apparently loud

In the example 41/29 = [1; 2,2,2,2 ] those are the breaks. The third approximation is broken, and the fourth is the same, ie identical to the initial fracture.

By mathematical induction we prove the Education Act for the convergents (pn and qn are pro forma defined for n = -1, -2, so that the formulas from n = 0 votes ):

And the relationship

It follows that the convergents are always present in abbreviated form (if pn and qn both by a natural number > 1 would be divisible, then the right side would also be divisible by this number, but this is not the case ). Divided by one, it follows:

(1)

For example, it has for the second and third proximity fraction of 41/29, the relationship

Similarly, one shows

And

(2)

These formulas are fundamental for the convergence issues discussed below in infinite continued fractions.

Matrix representation

The Education Act for the convergents can also be elegantly written in matrix form. We then obtain ( again by induction to prove ):

Since the determinant of each of the arrays on the left -1, immediately followed by:

And multiplying by -1 again shows the above mentioned equation.

By transposition of the matrices now follows (since the transposition of the order of the matrices is reversed ), and apply that.

Example: The convergents of noisy 1/1, 2/1, 5/3 and 17 / 10th It is

And you get as well.

Finite continued fractions and the Euclidean algorithm

The conversion of a rational number into a continued fraction is performed using the Euclidean algorithm.

As an example, we expect the following:

See also the section continued fraction in the article about the Euclidean algorithm. In the figure, this process is illustrated. From the following equation chain can be seen that the continued fraction produced by repeatedly inserting the equations of the Euclidean algorithm:

The graphical method can be described: one starts with a large 17x10 rectangle. It is charged under so many squares of side length 10 as possible (in this example that's only once). It remains a 10x7 rectangle of uncovered, on the one applied by the further consideration. The number of squares used in each case are part of the denominator of the chain fracture.

Infinite continued fractions

Infinite continued fractions: convergence and approximation breaks

For ( endless ) chain due to the fracture can only be defined when the result of the approximation converges fractures. In this case the endless chain is the breakdown value.

Since we restrict ourselves to regular continued fractions, the following applies: Every infinite continued fraction converges.

This can be seen as follows: the sequence of convergents with even indices, ie, due to equation (2) is monotonically increasing, while the sequence with odd indices is monotonically decreasing, see Figure. In addition, since each odd proximity fraction is greater than any straight, both sequences are monotonic and bounded and therefore converge. Her two limits are but due to equation ( 1) is equal (since the be arbitrarily large, the difference goes to 0 ).

We now consider

From the above formulas can be the difference between α and estimate the n-th approximation break:

(3)

As an example of equation (3) we consider the continued fraction of the square root of 2 we show later in Section Periodic continued fractions that. The first approximation breaks this endless chain breakdown are 1/1, 3/2, 7/5, 17/ 12, 41/29, and equation (3 ) implies in this case for n = 2:

It is clear now that every rational number has a finite continued fraction and that every finite continued fraction is a rational number. This representation is not unique, since one can write the end of the continued fraction in two ways, without changing the value: you can choose between the representations and change. But every irrational number has a unique representation:

Theorem ( Rational and irrational numbers, uniqueness of the representation ):

Each real number can be represented as ( normal ) chain to break. For irrational numbers, the continued fraction is infinite and unique. Rational numbers correspond to finite continued fractions and each rational number has exactly two continued fraction representations.

The proof of the statement that every infinite continued fraction is an irrational number is not difficult: we look at and assume that would be rational. Then we have

Since the be arbitrarily large for increasing n and the number between the amount of strokes is always an integer, which gives a contradiction. Thus, it is not rational.

Infinite continued fractions and generalized Euclidean algorithm

Irrational numbers, a generalization of the Euclidean algorithm. This also works for rational numbers; We therefore consider in each step whether the algorithm terminates:

This process is continued until one receives an integer (of course, this happens only if the starting value is rational). In an irrational method does not exit. The numbers are called complete quotient. It is

Similar to the Education Act for the convergents can be proved:

(4)

Examples: We compute the continued fraction expansion of up to the second point:

So is denominated. Other places there are in the article circle figure representing a pattern, however, was not yet discovered in the regular continued fraction expansion of.

In contrast, we find a clear pattern in the continued fraction of Euler's number e:

In the third root of there is again no pattern:

As an example of the use of Equation (4), consider the successive approximation openings 17 /12 and 41/29 of.

Because the complete quotients are the same for n> 0, the following applies:

As mentioned in the "History " section, Euler found that periodic continued fractions ( such as the square root of 2 or the golden number ) quadratic irrational numbers correspond to Lagrange and later showed that all these figures have periodic continued fractions. This topic is dedicated to the next section over.

Equivalent numbers

Two real numbers are called equivalent if there are integers, so true. It is easily seen that this definition actually provides an equivalence relation on the real numbers: with the reflexivity is shown with the following symmetry, and transitivity can be explicitly recalculate.

Every rational number is equivalent to 0, so all rational numbers form an equivalence class. Therefore, this classification of real numbers is mainly of interest for irrational numbers. The relationship with their regular continued fractions is given by the following set of Serret:

Sentence: Two irrational numbers are accurate then equivalent if their continued fraction representations and are such that there are natural numbers, and so applies to all.

The correspondence in their continued fraction representations to a different initial sequence results in equivalent numbers to asymptotically same approximation properties. An example is the section sets forth on quadratic approximability (Equation 5).

Periodic continued fractions

In the decimal real numbers periodic representations correspond to the rational numbers. A distinction is purely periodic decimal fractions, eg 1/3 = 0.33333 ..., and those with a previous period, such as 1/6 = 0.16666 ...

In periodic continued fractions representations also play a special role. How Euler and Lagrange found out they correspond to the quadratic irrational numbers ( irrational solutions of quadratic equations with rational coefficients). In particular, the chain breaks those real numbers that are not rational or irrational numbers square, non- periodically.

A continued fraction is called periodic if there are n numbers, k is so true for the partial denominators for all. The minimal k with this property is called the period of the continued fraction, then in the form

Is written. Is also n minimally chosen, the sequence is called the previous period and n 1 their length.

Euler- Lagrange

Pack: Each periodic continued fraction is a quadratic irrational number, and vice versa.

The first part of the theorem is easier to prove and comes from Euler, while the converse is more difficult and was later proved by Lagrange.

Examples

Pellsche equation

Periodic continued fractions can be used to solve the Pell equation.

Best approximations

Two ways best approximation

In the introduction it was mentioned that the determination of " good approximation breaks " is an important application of continued fractions. Namely, it is considered that any breakage of the chain Proximity fraction expansion of a real number is a particularly good approximation of the rational number.

Since any irrational number can be approximated arbitrarily closely by rational numbers, there is no absolute best approximation to an irrational number. Instead, there are two types of " record approximations ":

Definition: A fraction a / b is a best approximation first kind for the real number if and only if for all fractions c / d with d ≤ b and a / b ≠ c / d:

A better approximation break so you can only get if you allowed larger denominator than b.

(For simplicity, we restrict ourselves to positive real numbers and therefore consider only natural numbers a, b ​​, c, d as the numerator and denominator. ) Next:

A fraction a / b is a best approximation of second kind for the real number if and only if for all fractions c / d with d ≤ b and a / b ≠ c / d:

Both terms best approximation are - depending on the application - used.

The stronger is the second condition: Assuming that there is a break c / d with d ≤ b, and then supplies the multiplying by the inequality d ≤ b. This shows that a fraction, which is not the best approximation of the first type, may also be not the best approximation of the second type. It follows that any kind of a best approximation of the second type is the best approximation of the first well.

Example: We consider 17/10 = [1; 1,2,3 ]. The convergents p1/q1, p2/q2, p3/q3 be 2/1, 5/3 and 17/ 10 and they form the complete list of best approximations Article 2 However, there are other best approximations first type, namely 3 / 2 and 12 / 7th This topic is covered in the next two sections.

Convergents are best approximations

The usefulness of the convergents is reflected in the following sentence:

Theorem ( Lagrange ): For any real number: each proximity fraction pn / qn with n> 0 is a best approximation type 2 (and therefore also a best approximation type 1 ).

This is not always true for a 0-th approximation fraction, since this example, at 17/10 has the value 1, but the integer 2 represents a better approximation of the denominator 1.

You can set this in the case of best approximations second type reverse:

Sentence: Every best approximation second kind of a real number is an approximate breakdown of its continued fraction expansion.

However, this does not apply for approximations first type, shown above in Example 17/10. However, one can characterize the fractures also occur: they occur as mediant ( Farey sums) of proximity fractures, and are called secondary convergents. For details see the next section.

For example, suppose that you are looking for the smallest natural number q for which the distance from the nearest whole number less than 1/ 1000. Due to the last sentence must q in the sequence of approximate break - denominator qn be included from. Are the first denominator, as already calculated above, 1, 2, 5, 12, 29 They meet due to the periodic part of the denominator of the recursion qn = 2 · qn -1 qn -2 ( a Lucas sequence ). The approximate breakdown is p7/q7 equal 577/408 and it is, so that the distance to 577 is smaller than the required accuracy. The searched q is thus equal to 408, since the accuracy of 1/ 1000 for p6/q6 is not reached.

The same question for the golden number φ leads to the verification of fn · fn φ for elements of the Fibonacci sequence and the result obtained is q = 610

Approximation of the top and bottom side proximity breaks

Already 1770 Lagrange had dealt with the subject, which approximations 1st type in addition to the proximity fractures occur (see figure at right). He was led to the " fractions secondaires ", which are mentioned in the German secondary convergents.

It is mediant convergents of adjacent:

Definition: For two positive fractions a / b and c / d, a / b < c / d is ( a c ) / (b d ) of the Mediant (or Farey sum ) of the two openings. The Mediant has simply to be shown property that a / b < (a c ) / (b d) < c / d

Because of this property can be the formation of the mediant repeatedly run ( iterate ) and gets fractions of the form

Form an increasing sequence. For the following definition of the secondary convergents ie iterated mediant adjacent convergents are formed:

Definition: belonging to a continued fraction fractions

Hot side convergents. They lie between the nth and the n 2 th approximation break. For n even, they form an increasing sequence and for odd n is a decreasing sequence.

Note: in the particular case of n = -1, is used p- 1 = 1, q = 0 and 1 is replaced by a falling sequence, which is greater than p1/q1.

Rate: ( Lagrange 1798) Every kind of best approximation of a real number 1 is approximate break or a by proximity breach of its continued fraction expansion.

A characterization of the amount of approximation openings and side openings approximation can be obtained as follows:

Rate: ( Lagrange 1798) For any real number α:

A) Any fraction that is between α and a proximity or secondary approximation fraction has a denominator larger than the latter.

B) If, conversely, a fraction A / B of the type that every fraction that is between α and a / b, a common denominator greater than B, then a / b is an approximation or secondary approximation breakage.

In other words, only considering approximating fractions greater than α (or vice versa smaller than α ), the record approximations are completely described by the set of the approximation or secondary approximation breaks.

In the definition of the best approximation type 1 but the approximations from above and below are considered simultaneously. The analysis of this situation ( refinement of the penultimate sentence ) gives:

Sentence: Let m = bn 2-1 the number of secondary convergents between the nth and the n 2 th approximation break. Then: m is even, then results in the second half of the secondary convergents best approximations first kind, the first half is not. The same applies - with the exception of the central member - if m is odd. For the middle fraction, there is a more complicated condition that we do not specify here.

Examples

A) We consider the simple example [1, 5,2 ] = 13 / 11th The approximate fractions are 1/1, 6/ 5 and 13 / eleventh The secondary approximation breaks n = -1 2 /1, 3/2, 4/3, 5/4 (greater than 6/5) and for n = 0, it is the fraction 7/6 (between 1 /1 and 13 / 11).

B) For the circular constant π = [ 3; 7,15,1,292, ...] are the first convergents 3/1, 22/7, 333/106 and 355 / 113. The secondary convergents are the fractions 4/1, 7/ 2, 10/3, 13/ 4, 16 /5, 19/6 for n = -1. To form a falling sequence, and the last three are best approximations, first article (the first three are further away than the proximity of π p0/q0 fraction = 3 /1). For n = 0 to find the secondary approximation breaks 25/8, 47 /15, 69/22, 91/29, 113/36, 135/43, 157/50, 179/57, 201/64, 223 /71 245 / 78, 267/85, 289/92, 311 /99. These 14 fractures form an increasing sequence and the last seven are best approximations 1st Art

In the figure on the right are these (secondary) convergents illustrated: on the y- axis is plotted against q on the x- axis. In addition to the approximations from the bottom ( red) and from above ( blue ) contains the graphics nor the bound 1 / ( √ 5 × q ²), whose importance in the next section is clear. Good to see that only the second half of the secondary convergents, for n = 0 provides a better approximation than 22 / 7th In addition, you can see that the approximation by 355/113 is exceptionally good ( reason: the next part of the denominator is very large with 292).

Theorems on quadratic approximability

In this section we present results that " Diophantine approximation " reconciled to the topic. Substantive sentences one finds therefore in

From equation ( 3) follows because for every irrational number, there are an infinite number of fractions a / b with

Conversely, for every real number:

Set ( Legendre ): Meets a fraction a / b, the inequality so is a / b is an approximate breakdown of

This inequality is not satisfied by any approximate break. But it is true:

Set ( Vahlen, 1895 ): From two successive approximation breaks the real number at least one satisfies the inequality

In particular, there are infinitely many irrational here for fractures with this property.

Incorporating three convergents in the selection of one, so even applies:

Set ( Émile Borel, 1903): From three successive approximation breaks the real number at least one satisfies the inequality

In particular, there are infinitely many irrational for fractures with this property.

One might think, given these results, that one can exacerbate the condition by including four or more consecutive convergents on. This is not the case:

Theorem ( Hurwitz, 1891 ): Let the golden number. Then for every real number c with only finitely many breaks a / b with

An aggravation can now be achieved only if one excludes the equivalent to numbers:

Theorem ( Hurwitz, 1891): For all irrational numbers which are not equivalent to, there are infinitely many fractions a / b with

(5)

By further excluding equivalence classes can further enlarge the constant. The values ​​occurring form the so-called Lagrange spectrum. They converge to the number 3 and are related to the Markoff numbers.

Properties of almost all irrational numbers

Khinchin constant

The so-called metric continued fraction theory is concerned with properties that are typical of real numbers. It goes back to the same article by Alexander Khinchin in the journal Compositio Mathematica in 1935, but Gauss already dealt with similar issues. It is typical here in the measure theoretic sense to understand: It formulates properties that possess all real numbers except for a null set. In this case we say that almost all real numbers have this property.

The result of Khinchin is: converges for almost all real numbers

Against the constant

The geometric mean of the partial denominators almost every real number converges to a fixed constant. The exceptions include all rational numbers, since they only finitely many partial denominator - but they also make up only a null set of real numbers.

It is not known whether these so-called Khinchin constant is rational, algebraic irrational or transcendent.

The continued fractions of numbers, for which the limit value does not exist or is not equal to the constant Khinchin are usually very frequently. Examples are the square root of 2 (periodic continued fraction expansion ), the Euler number e ( pattern has been previously mentioned) and its square e ² = [ 7; 2,1,1,3,18,5,1,1,6,30, 8,1,1,9,42,11,1,1,12,54, ...].

Comparison of continued fraction and decimal

The set of hole states the following: for almost every real number between 0 and 1 you get in the long run for each additional member of a continued fraction - many valid decimal places ( here we use the term for the natural logarithm ). Thus, the representation of continued fractions ( for almost all numbers) is only slightly more efficient than the decimal. The hole - constant is related to the Lévy constant ( it is twice the logarithm of the Lévy constant).