Dies ist ein als lesenswert ausgezeichneter Artikel.

Kettenbruch

Aus AnthroWiki
Wechseln zu: Navigation, Suche

In der Mathematik und insbesondere der Zahlentheorie ist ein Kettenbruch (fortgesetzter Bruch) ein Ausdruck der Form

LaTeX: a + \cfrac{b}{c+\cfrac{d}{e+\cfrac{f}{\ddots}}}\quad.

Ein Kettenbruch (eng. continued fraction) ist also ein gemischter Bruch der Form LaTeX: a + \tfrac{b}{x}, bei dem der Nenner LaTeX: x wieder die Form eines gemischten Bruchs besitzt, wobei sich dieser Aufbau weiter so fortsetzt.

Jede reelle Zahl kann als ein Kettenbruch mit ganzen Zahlen LaTeX: a, b, c, d, e, f, \dotsc ausgedrückt werden. Kettenbrüche können daher als Zahlensystem bezeichnet werden, wie das Dezimalsystem. Sie dienen jedoch in erster Linie nicht zum Rechnen, sondern werden dazu verwendet, Approximationsaufgaben zu lösen: So liefern sie in der Zahlentheorie Näherungen für reelle Zahlen, indem diese durch einen Bruch aus ganzen Zahlen ausgedrückt werden, und in der numerischen Mathematik approximiert man durch sie Funktionen, ähnlich wie dies auch mittels Potenzreihen erreicht wird.

Von besonderer Bedeutung sind regelmäßige Kettenbrüche, auch reguläre oder einfache Kettenbrüche genannt. Ein solch regelmäßiger (regulärer/einfacher) Kettenbruch (eng. regular/simple continued fraction) zeichnet sich dadurch aus, dass alle Zähler LaTeX: (b, d, f, \dotsc) den Wert LaTeX: 1 haben. Ein regulärer Kettenbruch ist also durch die Folge LaTeX: a, c, e, \dotsc bestimmt, und man schreibt ihn platzsparend als LaTeX: [a; c, e, \dotsc].[1]

Daneben spielen die mit den regulären Kettenbrüchen eng verwandten negativ-regelmäßigen Kettenbrüche eine Rolle. Bei ihnen sind alle Zähler LaTeX: (b, d, f, \dotsc) auch alle gleich, jedoch gleich LaTeX: -1.[2]

Kettenbrüche spielen zudem eine große Rolle in der Zahlentheorie. So zeigte zum Beispiel Joseph Liouville 1844 mit ihrer Hilfe, dass transzendente Zahlen existieren. Außer in der Zahlentheorie kommen Kettenbrüche in der Kryptographie, algebraischen Geometrie, Topologie, Funktionentheorie, numerischen Mathematik und bei der Analyse chaotischer Systeme zur Anwendung.[3]

Joseph-Louis Lagrange gilt zusammen mit Leonhard Euler als der Begründer der Kettenbruchtheorie.

Geschichte

LaTeX: \sqrt{2}= 1+\cfrac{1} {2+\cfrac{1} {2+\cfrac{1} {2+\cfrac{1} {2+\cfrac{1}{\ddots}}}}}
Regulärer Kettenbruch[4]
LaTeX: \cfrac{4}{\pi}= 1+\cfrac{1^2} {3+\cfrac{2^2} {5+\cfrac{3^2} {7+\cfrac{4^2} {9+\cfrac{5^2}{\ddots}}}}}
Lamberts Kettenbruch für LaTeX: 4/\pi
LaTeX: \tan(z)= \cfrac{z} {1-\cfrac{z^2} {3-\cfrac{z^2} {5-\cfrac{z^2} {7-\cfrac{z^2}{\ddots}}}}}
Lamberts Kettenbruch für den Tangens[5]

Kettenbrüche werden seit dem 16. Jahrhundert dazu verwendet, „gute Näherungsbrüche“ für irrationale Zahlen zu finden. Das bekannteste Beispiel ist die Näherung LaTeX: 22/7 für LaTeX: \pi.

Deliciae physico-mathematicae, 1636

Rafael Bombelli verwendete Kettenbrüche bereits 1579, um damit Quadratwurzeln zu berechnen. Im Jahr 1613 veröffentlichte Pietro Cataldi ein Buch, in dem unter anderem auch Kettenbrüche auftauchen. 1636 finden sich Kettenbrüche im Buch „Deliciae Physico-Mathematicae“ von Daniel Schwenter und ab 1655 in mehreren Büchern von John Wallis. Aus dem Bedürfnis, Brüche mit großen Nennern sowie natürliche Konstanten zu approximieren, beschäftigte sich zunächst Christiaan Huygens im 17. Jahrhundert mit Kettenbrüchen. Er berechnete damit aus den Umlaufzeiten der Planeten das Übersetzungsverhältnis der Zahnräder für sein Zahnradmodell des Sonnensystems. Huygens ermittelte für die Umlaufzeit um die Sonne das Verhältnis zwischen Saturn und Erde als

LaTeX: \frac{77\,708\,431}{2\,640\,858} \approx 29{,}425448.

Der reguläre Kettenbruch hierfür beginnt mit LaTeX: [29; 2, 2, 1, 5, 1, 4, \dotsc]. Approximiert man dieses Verhältnis mit dem Näherungsbruch, der entsteht, wenn man nur die ersten vier Einträge verwendet, dann beträgt der Fehler[6] nur LaTeX: 0{,}003123, da

LaTeX: 29 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1}}} = \cfrac{206}{7} \approx 29{,}428571.

In Leonhard Eulers Korrespondenz[7] treten Kettenbrüche hingegen zuerst in einem ganz anderen Zusammenhang auf, nämlich in Verbindung mit der Riccatischen Differentialgleichung. Bald jedoch interessierte sich Euler für Kettenbrüche um ihrer selbst willen. Er entdeckte nämlich die folgenden drei wichtigen Eigenschaften:

  1. Jede rationale Zahl kann durch einen endlichen regulären Kettenbruch dargestellt werden (der mit Hilfe des euklidischen Algorithmus berechnet werden kann).
  2. Periodische reguläre Kettenbrüche stellen quadratische Irrationalzahlen dar; diese Aussage bewies Euler als Erster.
  3. Die Entwicklung jeder reellen Zahl in einen regulären Kettenbruch liefert die besten rationalen Approximationen für diese Zahl.

Einige dieser Erkenntnisse hatte bereits Huygens gewonnen, dessen Arbeit Euler aber unbekannt war.[8] Eulers Arbeiten – und darauf aufbauend die von Joseph-Louis Lagrange[9] – begründeten die Theorie der Kettenbrüche.

Zur rationalen Approximation existiert neben dem Algorithmus von Euler auch ein Algorithmus von Lord William Brouncker. Euler zeigte um 1759, dass die beiden Algorithmen identisch sind. Johann Heinrich Lambert benutzte Kettenbrüche in seiner Arbeit von 1766 dazu, die Irrationalität von LaTeX: \pi zu zeigen. Seine Kettenbruchentwicklung der Tangensfunktion ist in der Abbildung rechts dargestellt.

Moritz Abraham Stern schuf 1832 die erste systematische Zusammenfassung der Theorie der Kettenbrüche.[10] Im 19. Jahrhundert entwickelte sich die Theorie rasch weiter und so veröffentlichte Oskar Perron im Jahre 1913 eine Zusammenfassung des Wissensstandes, die bis heute als ein Standardwerk gilt (Neuauflage 1954/57).

Weitere wichtige Anwendungen waren und sind: Beweise für die Irrationalität oder die Transzendenz spezieller Zahlen und die Ermittlung von Schaltjahren (da ein Jahr mit 365,24219 Tagen etwas kürzer als 365¼ Tage ist, bedarf es zusätzlich zum Schalttag alle vier Jahre einer weiteren Korrektur; die beste Wahl dafür lässt sich mit Kettenbrüchen begründen).

Definition

Begriff des Kettenbruchs

Ein (unendlicher) Kettenbruch ist ein fortgesetzter Bruch der Form

LaTeX: b_0+\cfrac{a_1}{b_1+\cfrac{a_2}{b_2+\cfrac{a_3}{b_3+\cfrac{a_4}{\;\,\ddots}}}}\quad oder (regulärer Fall) LaTeX: b_0+\cfrac{1}{b_1+\cfrac{1}{b_2+\cfrac{1}{b_3+\cfrac{1}{\;\,\ddots}}}}

mit LaTeX: b_0 \in \Z und LaTeX: a_i, b_i \in \N für LaTeX: i \in \N.

Die Brüche LaTeX: \tfrac{a_i}{b_i} bzw. LaTeX: \tfrac{1}{b_i} werden Teilbrüche genannt, LaTeX: a_i heißt der LaTeX: i-te Teilzähler und LaTeX: b_i der LaTeX: i-te Teilnenner.[11] Die Teilzähler und Teilnenner nennt man (an Oskar Perron anschließend) auch Elemente des Kettenbruchs.[12]

Ein Kettenbruch, der sich nach einem Teilbruch LaTeX: \tfrac{a_i}{b_i} nicht weiter fortsetzt, ist ein endlicher Kettenbruch.

Eine formalere Definition findet man im Abschnitt Darstellung als Komposition von Abbildungen.

Reguläre Kettenbrüche sind in der Zahlentheorie der bei weitem wichtigste Kettenbruch-Typ. Bei der Approximation von (reellen oder komplexen) Funktionen verwendet man auch Kettenbrüche mit Unbekannten, siehe zum Beispiel den Lambertschen Kettenbruch für die Tangensfunktion im Abschnitt „Geschichte“. Manchmal benötigt man einen endlichen regulären Kettenbruch, bei dem der letzte Eintrag LaTeX: b_n eine reelle (nicht-ganze) Zahl ist. Dies ermöglicht zum Beispiel die Schreibweise LaTeX: \textstyle \phi=[1;\phi]=[1;1,\phi] usw. für die goldene Zahl. Auch werden bisweilen allgemeine Kettenbrüche mit LaTeX: a_i \in \Z benutzt.

Notation

Die Kurzschreibweise für einen allgemeinen Kettenbruch ist

LaTeX: b_0 + \frac{a_1|}{|b_1} + \frac{a_2|}{|b_2} + \frac{a_3|}{|b_3} + \cdots

In Anlehnung an die Summen- und Produktzeichen LaTeX: \sum und LaTeX: \prod führte Gauß hierfür auch die folgende Schreibweise ein:

LaTeX: b_0+\underset{i=1}{\overset{\infty}{\mathbf{K}}} \frac{a_i}{b_i}\,.

Ein regulärer Kettenbruch wird oft in der folgenden Weise geschrieben:[13]

LaTeX: [b_0; b_1, b_2, \dotsc]

LaTeX: b_0 wird nur deshalb gesondert aufgeführt, weil es aus LaTeX: \Z ist, die nachfolgenden LaTeX: b_i aber immer nur aus LaTeX: \N sind.

Die Notation für endliche Kettenbrüche ist dementsprechend

LaTeX: b_0 + \frac{a_1|}{|b_1} + \frac{a_2|}{|b_2} + \cdots + \frac{a_n|}{|b_n}\,, \quad b_0+\underset{i=1}{\overset{n}{\mathbf{K}}} \frac{a_i}{b_i}\,,\quad [b_0; b_1, \dotsc, b_n]\,.

Darstellung als Komposition von Abbildungen

Man kann einen Kettenbruch auch als eine Komposition von Abbildungen LaTeX: T_i\colon \mathbb{R}\to\mathbb{R} darstellen. Dies liefert eine formalere Definition als die bisher gegebene.

Hierfür setzt man LaTeX: T_i(x)=\tfrac{a_i}{b_i+x} und erhält

LaTeX: b_0+\underset{i=1}{\overset{n}{\mathbf{K}}} \frac{a_i}{b_i} := b_0 + T_1 \circ T_2 \circ \cdots \circ T_{n-1} \circ T_n(0).

Die Definition unendlicher Kettenbrüche erfolgt durch eine Grenzwertbetrachtung im Abschnitt Unendliche Kettenbrüche.

Endliche Kettenbrüche

Endliche Kettenbrüche und ihre Näherungsbrüche

Von nun an betrachten wir ausschließlich reguläre Kettenbrüche. Bricht man den Kettenbruch LaTeX: [b_0; b_1, \dotsc, b_N] nach dem LaTeX: n-ten Glied ab für ein LaTeX: n \le N, so heißt

LaTeX: \frac{p_n}{q_n}=[b_0; b_1, \dotsc, b_n]

sein LaTeX: n-ter Näherungsbruch (oder auch LaTeX: n-te Konvergente). Die ersten Näherungsbrüche lauten offenbar

LaTeX: \frac{p_0}{q_0} = \frac{b_0}{1}, \quad \frac{p_1}{q_1} = b_0+\cfrac{1}{b_1}= \frac{b_0 b_1 + 1}{b_1} , \quad \frac{p_2}{q_2} = b_0+\cfrac{1}{b_1+\cfrac{1}{b_2}} = \frac{b_0 b_1 b_2 + b_0 + b_2}{b_1 b_2 + 1} .

Bei dem Beispiel 41/29 = [1;2,2,2,2] sind das die Brüche LaTeX: \tfrac{1}{1}, \tfrac{3}{2}, \tfrac{7}{5}. Der dritte Näherungsbruch lautet LaTeX: \tfrac{17}{12} und der vierte ist gleich LaTeX: \tfrac{41}{29}, also identisch mit dem Ausgangsbruch.

Mit vollständiger Induktion beweist man das Bildungsgesetz für die Näherungsbrüche (LaTeX: p_n und LaTeX: q_n werden pro forma auch für LaTeX: n={-1},{-2} definiert, damit die Formeln ab LaTeX: n=0 stimmen):

LaTeX: p_n =b_n p_{n-1}+p_{n-2}\, LaTeX: p_{-1}=1\, LaTeX: p_{-2}=0\,
LaTeX: q_{n}=b_n q_{n-1}+q_{n-2}\, LaTeX: q_{-1}=0\, LaTeX: q_{-2}=1\,

sowie die Beziehung

LaTeX: q_n p_{n-1} - p_n q_{n-1} = (-1)^n\,.

Daraus folgt, dass Näherungsbrüche stets in gekürzter Form vorliegen (wenn LaTeX: p_n und LaTeX: q_n beide durch eine natürliche Zahl größer als LaTeX: 1 teilbar wären, dann müsste auch die rechte Seite durch diese Zahl teilbar sein, was aber nicht der Fall ist). Dividiert man durch LaTeX: q_n q_{n-1}, so folgt:

Vorlage:NumBlk

Beispielsweise hat man für den zweiten und dritten Näherungsbruch von LaTeX: 41/29 die Beziehung

LaTeX: \frac{7}{5}-\frac{17}{12} = \frac{(-1)^3}{60} = \frac{-1}{60}.

Auf ähnliche Weise zeigt man

LaTeX: q_n p_{n-2} - p_n q_{n-2} = (-1)^{n-1}b_n

und

Vorlage:NumBlk

Diese Formeln sind grundlegend für die weiter unten besprochenen Konvergenzfragen bei unendlichen Kettenbrüchen.

Matrixdarstellung

Das Bildungsgesetz für die Näherungsbrüche lässt sich auch elegant in Matrixform schreiben. Man erhält dann (wieder mit vollständiger Induktion zu beweisen):

LaTeX: \begin{pmatrix} b_0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} b_1 & 1 \\ 1 & 0 \end{pmatrix}\cdots \begin{pmatrix} b_n & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix}.

Da die Determinante jeder der Matrizen auf der linken Seite LaTeX: -1 beträgt, folgt sofort

LaTeX: p_n q_{n-1} - q_n p_{n-1} = (-1)^{n+1}

und Multiplikation mit LaTeX: -1 zeigt erneut die oben angegebene Gleichung.

Durch Transponieren beider Seiten der Gleichung folgt nun (da die Transposition des Produktes auf der linken Seite die Reihenfolge seiner Faktoren umkehrt), dass LaTeX: [b_n; b_{n-1}, \dotsc, b_0] = \tfrac{p_n}{p_{n-1}} und LaTeX: [b_n; b_{n-1}, \dotsc, b_1] = \tfrac{q_n}{q_{n-1}} gelten.

Beispiel: Die Näherungsbrüche von LaTeX: [1;1,2,3] = \tfrac{17}{10} lauten LaTeX: \tfrac11, LaTeX: \tfrac21, LaTeX: \tfrac53 und LaTeX: \tfrac{17}{10}. Es gilt

LaTeX: \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 3 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 17 & 5 \\ 10 & 3 \end{pmatrix}

und die Transposition

LaTeX: \begin{pmatrix} 3 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 17 & 10 \\ 5 & 3 \end{pmatrix}

ergibt LaTeX:  [3;2,1,1] = \tfrac{17}{5} sowie LaTeX: [3;2,1] = \tfrac{10}{3}.[14]

Endliche Kettenbrüche und der euklidische Algorithmus

Umformung von 17/10 nach [1;1,2,3] geometrisch veranschaulicht

Die Umwandlung einer rationalen Zahl in einen Kettenbruch erfolgt mit Hilfe des euklidischen Algorithmus.

Als Beispiel rechnen wir für LaTeX: \tfrac{17}{10} = [1;1,2,3] wie folgt:

LaTeX: \begin{align}</dd></dl>
<p>17 &= 1 \cdot 10 + 7 \\
10 &= 1 \cdot  7 + 3 \\
</p>
<pre>7 &= 2 \cdot  3 + 1 \\
3 &= 3 \cdot  1
</pre>
<p>\end{align}

Siehe dazu auch den Abschnitt Kettenbruchzerlegung im Artikel über den euklidischen Algorithmus. In der Abbildung ist dieses Verfahren veranschaulicht. Aus der folgenden Gleichungskette ist ersichtlich, dass die Kettenbruchentwicklung durch wiederholtes Einsetzen der Gleichungen des euklidischen Algorithmus entsteht:

LaTeX: \frac{17}{10}=1+\dfrac{7}{10}=1+\dfrac{\ \ 1\ \ }{\dfrac{10}{7}}=1+\dfrac{1}{1+\dfrac{3}{7}}=1+\dfrac{1}{1+\dfrac{1}{\dfrac{7}{3}}}=1+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{3}}}

Das graphische Verfahren kann so erläutert werden: Man beginnt mit einem LaTeX: 17 \times 10 großen Rechteck. Darin bringt man so viele Quadrate der Seitenlänge LaTeX: 10 unter, wie möglich (in diesem Beispiel geht das nur einmal). Es bleibt nun ein LaTeX: 10 \times 7 großes Rechteck unbedeckt, auf das man die Überlegung weiter anwendet. Die Anzahl der jeweils verwendeten Quadrate sind dabei die Teilnenner des Kettenbruchs.[15]

Unendliche Kettenbrüche

Unendliche Kettenbrüche: Konvergenz und Näherungsbrüche

Die Näherungsbrüche mit geradem Index bilden eine steigende Folge, solche mit ungeradem Index eine fallende Folge. Beide konvergieren gegen LaTeX: \alpha.

Für eine (unendliche) Folge LaTeX: b_0, b_1, \dotsc ist der Kettenbruch LaTeX: [b_0; b_1, \dotsc] nur dann definiert, wenn die Folge der Näherungsbrüche LaTeX: (p_n/q_n)_n konvergiert. In diesem Fall hat der unendliche Kettenbruch LaTeX: [b_0; b_1, \dotsc] den Wert LaTeX: \lim_{n \to \infty}[b_0; b_1, \dotsc, b_n].

Da hier nur reguläre Kettenbrüche behandelt werden, gilt: Jeder unendliche Kettenbruch konvergiert.[16]

Das erkennt man folgendermaßen: Die Folge der Näherungsbrüche mit geraden Indizes, also LaTeX: p_0/q_0, p_2/q_2, \dotsc ist aufgrund Gleichung (2) monoton steigend, während die Folge mit ungeraden Indizes LaTeX: p_1/q_1, p_3/q_3, \dotsc monoton fallend ist, siehe Abbildung. Da außerdem jeder ungerade Näherungsbruch größer ist als jeder gerade, sind beide Folgen monoton und beschränkt und konvergieren daher. Ihre beiden Grenzwerte sind aber aufgrund Gleichung (1) gleich (da die LaTeX: q_n beliebig groß werden, geht die Differenz gegen 0).

Nun betrachte man LaTeX: \alpha=[b_0; b_1, \dotsc].

Aus den oben angegebenen Formeln lässt sich die Differenz zwischen LaTeX: \alpha und dem LaTeX: n-ten Näherungsbruch abschätzen:

Vorlage:NumBlk

Als Beispiel für Gleichung (3) betrachte man den Kettenbruch der Quadratwurzel von 2. Im Abschnitt Periodische Kettenbrüche wird gezeigt, dass LaTeX: \sqrt{2}=[1; 2, 2, \dotsc].

Die ersten Näherungsbrüche dieses unendlichen Kettenbruchs sind LaTeX: 1/1, LaTeX: 3/2, LaTeX: 7/5, LaTeX: 17/12, LaTeX: 41/29 und Gleichung (3) besagt in diesem Fall für LaTeX: n=2:

LaTeX: \frac{2}{5 \cdot 29} < \left|\sqrt{2}-\frac{7}{5}\right| < \frac{1}{5 \cdot 12}.

Klar ist nun, dass jede rationale Zahl einen endlichen Kettenbruch hat und dass jeder endliche Kettenbruch eine rationale Zahl darstellt. Diese Darstellung ist nicht eindeutig, da man das Ende des Kettenbruchs auf zwei Arten schreiben kann, ohne den Wert zu verändern: Man kann zwischen den Darstellungen LaTeX: [\dotsc, b_n+1] und LaTeX: [\dotsc, b_n, 1] wechseln. Jede irrationale Zahl hat aber eine eindeutige Darstellung:

Satz (Rationale und irrationale Zahlen, Eindeutigkeit der Darstellung):

Jede reelle Zahl kann als (regulärer) Kettenbruch dargestellt werden. Für irrationale Zahlen ist die Kettenbruchdarstellung unendlich und eindeutig. Rationale Zahlen entsprechen endlichen Kettenbrüchen und jede rationale Zahl hat genau zwei Kettenbruchdarstellungen.

Für den Beweis der Aussage, dass jeder unendliche Kettenbruch eine irrationale Zahl darstellt, gilt: Betrachtet man LaTeX: \alpha=[b_0; b_1, \dotsc] und nimmt an, dass LaTeX: \alpha=c/d rational wäre, so ist

LaTeX: 0 < \left|\frac{c}{d}-\frac{p_n}{q_n}\right| < \frac{1}{q_n q_{n+1}}

und Multiplikation mit LaTeX: d und LaTeX: q_n ergibt

LaTeX: 0 < |c q_n - d p_n| < \frac{d}{q_{n+1}}.

Da die LaTeX: q_{n+1} für wachsendes LaTeX: n beliebig groß werden und die Zahl zwischen den Betragsstrichen stets eine ganze Zahl ist, liefert das einen Widerspruch. Somit ist LaTeX: \alpha nicht rational.

Unendliche Kettenbrüche und der verallgemeinerte euklidische Algorithmus

Für irrationale Zahlen LaTeX: \alpha wird eine Verallgemeinerung des euklidischen Algorithmus verwendet. Dieser funktioniert auch für rationale Zahlen; wir prüfen deshalb in jedem Schritt, ob der Algorithmus abbricht:

  1. Ist LaTeX: \alpha keine ganze Zahl, so setzt man LaTeX: b_0 = \lfloor\alpha\rfloor (Ganzteil von LaTeX: \alpha) und LaTeX: \alpha_1 auf das Inverse des Rests, also LaTeX: \alpha_1 = 1/(\alpha - b_0).
  2. Falls LaTeX: \alpha_1 nicht ganz ist, dann setzt man LaTeX: b_1 = \lfloor\alpha_1\rfloor und LaTeX: \alpha_2 = 1/(\alpha_1 - b_1).

Dieses Verfahren wird fortgesetzt, bis man ein ganzzahliges LaTeX: \alpha_n erhält (das geschieht natürlich nur dann, wenn der Startwert rational ist). Bei einem irrationalen LaTeX: \alpha bricht das Verfahren nicht ab. Die Zahlen LaTeX: \alpha_n werden vollständige Quotienten genannt. Es gilt

LaTeX: \alpha = [b_0; b_1, \dotsc, b_n, \alpha_{n+1}].

Ähnlich wie das Bildungsgesetz für die Näherungsbrüche beweist man:

Vorlage:NumBlk

Beispiele: Wir berechnen die Kettenbruchentwicklung von LaTeX: \pi bis zur zweiten Stelle:

LaTeX: \alpha_0 = \pi\, also LaTeX: b_0 = 3\,,
LaTeX: \alpha_1 = 1/(\pi - 3) = 7{,}0625\ldots also LaTeX: b_1 = 7\,,
LaTeX: \alpha_2 = 1/0{,}0625\ldots = 15{,}996\ldots also LaTeX: b_2 = 15\,.

Sie lautet also LaTeX: [3; 7, 15, \dotsc]. Weitere Stellen gibt es im Artikel Kreiszahl, ein Muster wurde jedoch bislang in der regulären Kettenbruchentwicklung von LaTeX: \pi nicht entdeckt.

Im Gegensatz dazu findet man ein klares Muster im Kettenbruch der eulerschen Zahl LaTeX: e:

LaTeX: e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, \dotsc].

Bei der dritten Wurzel von LaTeX: 2 gibt es wiederum kein Muster:

LaTeX: \sqrt[3]{2} = [1; 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, \dotsc]

Als Beispiel für die Verwendung von Gleichung (4) betrachte man die aufeinanderfolgenden Näherungsbrüche 17/12 und 41/29 von LaTeX: \sqrt{2}=[1;\overline{2}].

Da die vollständigen Quotienten für LaTeX: n>0 gleich LaTeX: [2;\overline{2}]=1+\sqrt{2} sind, gilt:

LaTeX: \sqrt{2}=\frac{41\cdot (1+\sqrt{2}) + 17}{29 \cdot (1+\sqrt{2}) + 12}

Wie im Abschnitt „Geschichte“ erwähnt, fand Euler heraus, dass periodische Kettenbrüche (so wie bei der Quadratwurzel von LaTeX: 2 oder bei der goldenen Zahl) quadratischen Irrationalzahlen entsprechen, und Lagrange zeigte später, dass alle diese Zahlen periodische Kettenbrüche haben. Diesem Thema ist der übernächste Abschnitt gewidmet.

Äquivalente Zahlen

Zwei reelle Zahlen LaTeX: x,y heißen äquivalent,[17] wenn es ganze Zahlen LaTeX: a,b,c,d mit LaTeX: ad-bc = \pm 1 gibt, sodass LaTeX: y = \tfrac{ax+b}{cx+d} gilt. Das heißt, sie sind durch eine ganzzahlige Möbiustransformation mit Determinante LaTeX: \pm 1 verbunden (Elementen der speziellen linearen Gruppe LaTeX: \operatorname{SL}(2, \mathbb Z)). Man sieht leicht, dass diese Definition tatsächlich eine Äquivalenzrelation auf den reellen Zahlen liefert: Mit LaTeX: a=d=1,b=c=0 ist die Reflexivität gezeigt, mit LaTeX: x = \tfrac{b-dy}{-a+cy} folgt die Symmetrie, und die Transitivität kann man explizit nachrechnen.

Jede rationale Zahl ist äquivalent zu 0, alle rationalen Zahlen bilden also eine Äquivalenzklasse. Daher ist diese Einteilung der reellen Zahlen hauptsächlich für irrationale Zahlen interessant. Die Beziehung zu ihren regelmäßigen Kettenbruchentwicklungen ergibt sich durch folgenden Satz von Serret:

Satz: Zwei irrationale Zahlen LaTeX: x,y sind genau dann äquivalent, wenn ihre Kettenbruchdarstellungen LaTeX: x=[u_0; u_1, u_2, \dotsc] und LaTeX: y=[v_0; v_1, v_2, \dotsc] so beschaffen sind, dass es natürliche Zahlen LaTeX: h und LaTeX: k gibt, sodass für alle LaTeX: i \in \N LaTeX: u_{h+i}=v_{k+i} gilt.[18]

Die Übereinstimmung in ihren Kettenbruchdarstellungen bis auf eine unterschiedliche Anfangssequenz führt bei äquivalenten Zahlen zu asymptotisch gleichen Approximationseigenschaften. Ein Beispiel ist im Abschnitt Sätze über quadratische Approximierbarkeit angeführt (Gleichung 5).

Andere unendliche Kettenbrüche

In der Analysis kommen auch unendliche Kettenbrüche vor, die von den oben genannte Regularitätsbedingungen abweichen, wobei die Teilnenner und die Teilzähler jedoch Folgen von reellen oder komplexen Zahlen bilden, die gewissen Konvergenzbedingungen genügen.[19][20]

In diesem Zusammenhang wird immer wieder der Fall behandelt, bei dem alle Teilnenner (bis auf den 0-ten) gleich LaTeX: 1 sind. Ein klassisches Beispiel dazu bietet die schon von Leonhard Euler angegebene Kettenbruchdarstellung des Logarithmus von LaTeX: 2, nämlich:[21]

LaTeX:  \ln 2 = {\cfrac{1}{1+\cfrac{1}{1+\cfrac{4}{1+\cfrac{9}{1+\cfrac{16}{1+\cfrac{25}{1+\cfrac{36}{1+\cfrac{49}{1+\dotsb}}}}}}}} },

bei der die Teilzähler ab dem 2-ten aus der Folge der Quadratzahlen hervorgehen.

Periodische Kettenbrüche

Kettenbruch der Quadratwurzel von 13 in Eulers De usu novi algorithmi in problemate Pelliano solvendo von 1767

Bei der Dezimaldarstellung reeller Zahlen entsprechen periodische Darstellungen den rationalen Zahlen. Man unterscheidet rein-periodische Dezimalbrüche, z. B. LaTeX: 1/3 = 0,\mathbf{3}3333\ldots, und solche mit einer Vorperiode, wie bei LaTeX: 1/6 = 0{,}1\mathbf{6}666\ldots.

Bei Kettenbrüchen spielen periodische Darstellungen ebenfalls eine besondere Rolle. Wie Euler und Lagrange herausfanden, entsprechen sie den quadratischen Irrationalzahlen (irrationale Lösungen quadratischer Gleichungen mit rationalen Koeffizienten). Insbesondere sind die Kettenbrüche derjenigen reellen Zahlen, die weder rational noch quadratische Irrationalzahlen sind, nicht-periodisch.

Ein Kettenbruch wird periodisch genannt, wenn es Zahlen LaTeX: n, k gibt, so dass für die Teilnenner LaTeX: b_{j+k} = b_j für alle LaTeX: j \geq n + 1 gilt. Das minimale LaTeX: k mit dieser Eigenschaft nennt man die Periode des Kettenbruchs, der dann in der Form

LaTeX: x = [b_0; b_1, \dotsc, b_n, \overline{b_{n+1}, \dotsc, b_{n+k}}]

geschrieben wird. Ist auch LaTeX: n minimal gewählt, heißt die Folge LaTeX: b_0, \dotsc, b_n die Vorperiode und LaTeX: n+1 ihre Länge.

Satz von Euler-Lagrange

Satz: Jeder periodische Kettenbruch ist eine quadratische Irrationalzahl und umgekehrt.

Der erste Teil des Satzes ist einfacher zu beweisen und stammt von Euler, während die Umkehrung schwieriger ist und erst später von Lagrange bewiesen wurde.[22]

Beispiele

  1. Sei LaTeX: x = [1;\overline{1}]. Dann gilt LaTeX: x = 1+\tfrac{1}{x}, also ist LaTeX: x Wurzel der quadratischen Gleichung LaTeX: x^2-x-1 = 0, woraus LaTeX: x = \tfrac{1+\sqrt{5}}{2} folgt (da die andere Nullstelle negativ ist). Daher ist LaTeX: x die goldene Zahl (siehe auch den Artikel Goldener Schnitt).
  2. Sei LaTeX: x = [1;\overline{2}]. Wir betrachten LaTeX: y = x-1. Dann ist LaTeX: y = \tfrac{1}{2 + y}, woraus LaTeX: y^2+2y = 1 und LaTeX: y+1 = \pm\sqrt{2} folgt. Da LaTeX: y > 0 gilt, muss LaTeX: y+1= \sqrt{2} sein. Daher gilt LaTeX: x=\sqrt{2}.
  3. Sei LaTeX: x = [1;\overline{1,2}]. Wir betrachten LaTeX: y = x-1. Dann ist LaTeX: y = \tfrac{1}{1 + \frac{1}{2 + y}}, also LaTeX: y = \tfrac{2+y}{3+y}, woraus LaTeX: y^2+2y+1 = 3 und LaTeX: y+1 = \pm\sqrt{3} folgt. Da LaTeX: y > 0 gilt, muss LaTeX: y+1 = \sqrt{3} sein. Daher gilt LaTeX: x = \sqrt{3}.
  4. Eine besondere Form periodischer unendlicher Kettenbrüche haben die sogenannten „noblen Zahlen“: Ihre Kettenbruchentwicklung endet stets mit LaTeX: [\dotsc,\overline{1}]. Die goldene Zahl ist das wohl prominenteste Beispiel einer noblen Zahl.
  5. Die Kettenbrüche irrationaler Quadratwurzeln rationaler Zahlen größer als 1 haben eine besondere Symmetrie: Für jede rationale Zahl LaTeX: r > 1, die nicht Quadrat einer rationalen Zahl ist, gilt
LaTeX: \sqrt{r} = [b_0; \overline{b_1, b_2, \dotsc, b_2, b_1, 2b_0}] \text{ mit } b_0 > 0
und umgekehrt ist das Quadrat jedes Kettenbruchs dieser Form eine rationale Zahl.[23]
Die Vorperiode hat also stets Länge LaTeX: 1, der periodische Block ist symmetrisch und wird beendet mit LaTeX: 2b_0. Beispiele dafür sind außer den Wurzeln von LaTeX: 2 und LaTeX: 3:
LaTeX: \sqrt{7} = [2;\overline{1,1,1,4}]
LaTeX: \sqrt{14} = [3;\overline{1,2,1,6}]
Der Kettenbruch der Quadratwurzel von LaTeX: 13 in einem Werk von Euler über die Pellsche Gleichung ist rechts abgebildet.[24] Die goldene Zahl aus Beispiel 1 hat diese Form nicht. Ein weiteres „Gegen“-Beispiel dieser Art ist LaTeX: \sqrt{3} + \tfrac{1}{2} = [2;\overline{4,3}].

Pellsche Gleichung

Periodische Kettenbrüche werden zur Lösung der Pellschen Gleichung LaTeX: x^2-d\cdot y^2=\pm 1 verwendet.


Beste Näherungen

Zwei Möglichkeiten bester Näherung

In der Einleitung wurde erwähnt, dass die Bestimmung von „guten Näherungsbrüchen“ eine wichtige Anwendung von Kettenbrüchen ist. Es gilt nämlich, dass jeder Näherungsbruch der Kettenbruchentwicklung einer reellen Zahl eine besonders gute rationale Näherung dieser Zahl ist.

Da man jede irrationale Zahl beliebig genau durch rationale Zahlen approximieren kann, gibt es keine absolute beste Näherung an eine irrationale Zahl. Man unterscheidet stattdessen zwei Arten von „Rekordnäherungen“:

Definition: Ein Bruch LaTeX: a/b ist eine beste Näherung 1. Art für die reelle Zahl LaTeX: \alpha, wenn für alle Brüche LaTeX: c/d mit LaTeX: d \leq b und LaTeX: a/b \neq c/d gilt:

LaTeX: \left|\alpha-\frac{a}{b}\right| < \left|\alpha-\frac{c}{d}\right|.

Einen besseren Näherungsbruch kann man also nur bekommen, wenn man größere Nenner als LaTeX: b erlaubt.

(Der Einfachheit halber beschränken wir uns auf positive reelle Zahlen und betrachten daher nur natürliche Zahlen LaTeX: a,b,c,d als Zähler und Nenner.) Weiter:

Ein Bruch LaTeX: a/b ist eine beste Näherung 2. Art für die reelle Zahl LaTeX: \alpha, wenn für alle Brüche LaTeX: c/d mit LaTeX: d \leq b und LaTeX: a/b \neq c/d gilt:

LaTeX: \left|b \cdot \alpha - a\right| < \left|d \cdot \alpha - c\right|

Beide Begriffe bester Näherung werden – je nach Anwendung – gebraucht.

Die stärkere Bedingung ist die zweite: Angenommen, es gibt einen Bruch LaTeX: c/d mit LaTeX: d \leq b und LaTeX: \left|\alpha-\tfrac{c}{d}\right| \le \left|\alpha-\tfrac{a}{b}\right|, dann liefert die Multiplikation mit LaTeX: d \leq b die Ungleichung LaTeX: \left|d \cdot \alpha - c\right| \le \left|b \cdot \alpha - a\right|. Das zeigt, dass ein Bruch, der nicht beste Näherung der 1. Art ist, auch keine beste Näherung 2. Art sein kann. Daraus folgt, dass jede beste Näherung 2. Art ebenso eine beste Näherung 1. Art ist.

Beispiel: Wir betrachten LaTeX: 17/10 = [1;1,2,3]. Die Näherungsbrüche LaTeX: p_1/q_1, LaTeX: p_2/q_2, LaTeX: p_3/q_3 lauten LaTeX: 2/1, LaTeX: 5/3 und LaTeX: 17/10 und sie bilden die vollständige Liste der besten Näherungen 2. Art. Es gibt jedoch weitere beste Näherungen 1. Art, nämlich LaTeX: 3/2 und LaTeX: 12/7. Dieses Thema wird in den nächsten beiden Abschnitten behandelt.

Näherungsbrüche sind beste Näherungen

Die Nützlichkeit der Näherungsbrüche zeigt sich in folgendem Satz:

Satz (Lagrange):[25] Für jede reelle Zahl gilt: Jeder Näherungsbruch LaTeX: p_n/q_n mit LaTeX: n>0 ist eine beste Näherung 2. Art (und daher auch eine beste Näherung 1. Art).

Für einen 0-ten Näherungsbruch gilt dies nicht immer, da dieser beispielsweise bei LaTeX: 17/10 den Wert LaTeX: 1 hat, aber die ganze Zahl LaTeX: 2 eine bessere Näherung mit Nenner LaTeX: 1 darstellt.[26]

Man kann diesen Satz im Fall von besten Näherungen 2. Art umkehren:

Satz:[27] Jede beste Näherung 2. Art einer reellen Zahl ist ein Näherungsbruch ihrer (regulären) Kettenbruchentwicklung.

Für Näherungen 1. Art gilt dies jedoch nicht, wie oben im Beispiel 17/10 dargestellt. Man kann jedoch die zusätzlich auftretenden Brüche charakterisieren: Sie entstehen als Medianten (Farey-Summen) von Näherungsbrüchen und werden Nebennäherungsbrüche genannt. Näheres dazu im nächsten Abschnitt.

Nebennäherungsbrüche in Lagranges Additions au mémoire sur la résolution des équations numériques aus dem Jahr 1770 (Seite 567)

Beispiel: Angenommen, man sucht die kleinste natürliche Zahl LaTeX: q, für die der Abstand von LaTeX: q \cdot \sqrt{2} von der nächstgelegenen ganzen Zahl kleiner als LaTeX: 1/1000 ist. Aufgrund des letzten Satzes muss LaTeX: q in der Folge der Näherungsbruch-Nenner LaTeX: q_n von LaTeX: \sqrt{2}=[1; 2, 2, \dotsc] enthalten sein. Die ersten Nenner lauten, wie schon oben ausgerechnet, LaTeX: 1, 2, 5, 12, 29. Diese lassen sich, aufgrund der periodischen Teilnenner, leicht durch die Rekursion LaTeX: q_n = 2 \cdot q_{n-1} + q_{n-2} (eine Lucas-Folge) mit LaTeX:  70, 169, 408, 985 usw. fortsetzen. Der Näherungsbruch LaTeX: p_7/q_7 ist gleich LaTeX: 577/408 und es gilt LaTeX: 408 \cdot \sqrt{2} = 576{,}99913, sodass der Abstand zu LaTeX: 577 kleiner als die geforderte Genauigkeit ist. Das gesuchte LaTeX: q ist also gleich LaTeX: 408, da die Genauigkeit von LaTeX: 1/1000 für LaTeX: p_6/q_6 gleich LaTeX: 239/169 nicht erreicht ist (LaTeX: 169 \cdot \sqrt{2} = 239{,}00209).

Die gleiche Frage für die goldene Zahl LaTeX: \phi führt zur Überprüfung von LaTeX: f_n \cdot \phi für Elemente LaTeX: f_n der Fibonacci-Folge und man erhält als Ergebnis LaTeX: q = 610, was zu dem Näherungsbruch LaTeX: p_{15}/q_{15} gehört. Bei der Kreiszahl LaTeX: \pi erfüllt bereits der dritte Näherungsbruch (LaTeX: 355/113) diese Bedingung.

Approximation von oben und unten, Nebennäherungsbrüche

Schon 1770 hatte sich Lagrange mit dem Thema beschäftigt, welche Näherungen 1. Art zusätzlich zu den Näherungsbrüchen auftreten (siehe Abbildung rechts). Er wurde zu den „fractions secondaires“ geführt, die im Deutschen Nebennäherungsbrüche genannt werden.

Es handelt sich um Medianten benachbarter Näherungsbrüche:

Definition: Für zwei positive Brüche LaTeX: a/b, LaTeX: c/d mit LaTeX: a/b < c/d heißt LaTeX: (a+c)/(b+d) der Mediant (oder die Farey-Summe) der beiden Brüche. Der Mediant hat die einfach zu zeigende Eigenschaft, dass LaTeX: a/b < (a+c)/(b+d) < c/d.

Aufgrund dieser Eigenschaft kann man die Bildung des Medianten wiederholt ausführen (iterieren) und bekommt Brüche der Form

LaTeX: \frac{a + r \cdot c}{b + r \cdot d},

die eine aufsteigende Folge bilden. Für die folgende Definition der Nebennäherungsbrüche werden also iterierte Medianten benachbarter Näherungsbrüche gebildet:

Definition: Die zu einem Kettenbruch gehörenden Brüche

LaTeX: \frac{p_{n,r}}{q_{n,r}}=\frac{r \cdot p_{n+1} + p_n}{r \cdot q_{n+1} + q_n}, \, r=1, \dotsc, b_{n+2}-1

heißen Nebennäherungsbrüche. Sie liegen zwischen dem LaTeX: n-ten und dem LaTeX: (n+2)-ten Näherungsbruch. Für gerades LaTeX: n bilden sie eine steigende Folge und für ungerades LaTeX: n eine fallende Folge.

Anmerkung: im besonderen Fall LaTeX: n={-1} verwendet man LaTeX: p_{-1} = 1, LaTeX: q_{-1} = 0 und erhält eine fallende Folge, die größer ist als LaTeX: p_1/q_1.

Satz (Lagrange 1798):[28] Jede beste Näherung 1. Art einer reellen Zahl ist ein Näherungsbruch oder ein Nebennäherungsbruch ihrer Kettenbruchentwicklung.

Eine Charakterisierung der Menge der Näherungsbrüche und Nebennäherungsbrüche kann man wie folgt erhalten:

Satz (Lagrange 1798):[29] Für jede reelle Zahl LaTeX: \alpha gilt:

a) Jeder Bruch, der zwischen LaTeX: \alpha und einem Näherungs- oder Nebennäherungsbruch liegt, hat einen größeren Nenner als dieser.

b) Ist umgekehrt ein Bruch LaTeX: a/b von der Art, dass jeder Bruch, der zwischen LaTeX: \alpha und LaTeX: a/b liegt, einen Nenner größer als LaTeX: b hat, dann ist LaTeX: a/b ein Näherungs- oder Nebennäherungsbruch.

In anderen Worten: Betrachtet man nur approximierende Brüche größer als LaTeX: \alpha (oder umgekehrt kleiner als LaTeX: \alpha), so sind die Rekordnäherungen vollständig durch die Menge der Näherungs- oder Nebennäherungsbrüche beschrieben.[30]

(Neben-)Näherungsbrüche von LaTeX: \pi (Erläuterung im Text)

In der Definition der besten Näherung 1. Art werden aber die Approximationen von oben und unten gleichzeitig betrachtet. Die Analyse dieser Situation (Verfeinerung des vorletzten Satzes) ergibt:

Satz:[31] Es sei LaTeX: m=b_{n+2}-1 die Anzahl der Nebennäherungsbrüche zwischen dem LaTeX: n-ten und dem LaTeX: (n+2)-ten Näherungsbruch. Dann gilt: Ist LaTeX: m gerade, so ergibt die zweite Hälfte der Nebennäherungsbrüche beste Näherungen 1. Art, die erste Hälfte aber nicht. Das Gleiche gilt – mit Ausnahme des mittleren Elements –, wenn LaTeX: m ungerade ist. Für den mittleren Bruch gibt es eine kompliziertere Bedingung, die wir hier nicht angeben.

Beispiele:

a) Wir betrachten das einfache Beispiel LaTeX: [1;5,2]=13/11. Die Näherungsbrüche sind LaTeX: 1/1, LaTeX: 6/5 und LaTeX: 13/11. Die Nebennäherungsbrüche für LaTeX: n={-1} sind LaTeX: 2/1, LaTeX: 3/2, LaTeX: 4/3, LaTeX: 5/4 (größer als LaTeX: 6/5) und für LaTeX: n=0 ist es der Bruch LaTeX: 7/6 (zwischen LaTeX: 1/1 und LaTeX: 13/11).

b) Für die Kreiszahl LaTeX: \pi=[3; 7, 15, 1, 292, \dotsc] lauten die ersten Näherungsbrüche LaTeX: 3/1, LaTeX: 22/7, LaTeX: 333/106 und LaTeX: 355/113. Die Nebennäherungsbrüche sind für LaTeX: n={-1} die Brüche LaTeX: 4/1, LaTeX: 7/2, LaTeX: 10/3, LaTeX: 13/4, LaTeX: 16/5, LaTeX: 19/6. Sie bilden eine fallende Folge und die letzten drei sind beste Näherungen 1. Art. (Die ersten drei sind weiter entfernt von LaTeX: \pi als der Näherungsbruch LaTeX: p_0/q_0 = 3/1). Für LaTeX: n=0 findet man die Nebennäherungsbrüche LaTeX: 25/8, LaTeX: 47/15, LaTeX: 69/22, LaTeX: 91/29, LaTeX: 113/36, LaTeX: 135/43, LaTeX: 157/50, LaTeX: 179/57, LaTeX: 201/64, LaTeX: 223/71, LaTeX: 245/78, LaTeX: 267/85, LaTeX: 289/92, LaTeX: 311/99. Diese LaTeX: 14 Brüche bilden eine steigende Folge und die letzten sieben sind beste Näherungen 1. Art.

In der Abbildung rechts sind diese (Neben-)Näherungsbrüche illustriert: Auf der LaTeX: y-Achse ist LaTeX: \log_{10} |\pi-p/q| gegen LaTeX: q auf der LaTeX: x-Achse abgetragen. Außer den Näherungen von unten (rot) und von oben (blau) enthält die Graphik noch die Schranke LaTeX: 1 / (\sqrt{5} \cdot q^2), deren Bedeutung im nächsten Abschnitt klar wird.[32] Gut zu sehen ist, dass nur die zweite Hälfte der Nebennäherungsbrüche für LaTeX: n = 0 eine bessere Näherung liefert als LaTeX: 22/7. Außerdem sieht man, dass die Näherung durch LaTeX: 355/113 außergewöhnlich gut ist (Grund dafür: Der nächste Teilnenner ist mit LaTeX: 292 sehr groß).

Sätze über quadratische Approximierbarkeit

In diesem Abschnitt stellen wir Ergebnisse vor, die zum Thema „Diophantische Approximation“ überleiten.

Aus Gleichung (3) folgt wegen LaTeX: q_{n+1} > q_n: Zu jeder irrationalen Zahl LaTeX: \alpha gibt es unendlich viele Brüche LaTeX: a/b mit[33]

LaTeX: \left|\alpha-\frac{a}{b}\right| < \frac{1}{b^2}.

Umgekehrt gilt für jede reelle Zahl LaTeX: \alpha:

Satz (Legendre):[34] Erfüllt ein Bruch LaTeX: a/b die Ungleichung LaTeX: \left|\alpha-\tfrac{a}{b}\right| < \tfrac{1}{2b^2}, so ist LaTeX: a/b ein Näherungsbruch von LaTeX: \alpha.

Diese Ungleichung wird jedoch nicht von jedem Näherungsbruch erfüllt. Es gilt aber:

Satz (Vahlen, 1895):[35] Von jeweils zwei aufeinanderfolgenden Näherungsbrüchen der reellen Zahl LaTeX: \alpha erfüllt mindestens einer die Ungleichung

LaTeX: \left|\alpha-\frac{p_n}{q_n}\right| < \frac{1}{2\,q_n^2}.

Insbesondere gibt es auch hier für irrationales LaTeX: \alpha unendlich viele Brüche mit dieser Eigenschaft.

Bezieht man drei Näherungsbrüche in die Auswahl ein, so gilt sogar:

Satz (Émile Borel, 1903):[36] Von jeweils drei aufeinanderfolgenden Näherungsbrüchen der reellen Zahl LaTeX: \alpha erfüllt mindestens einer die Ungleichung

LaTeX: \left|\alpha-\frac{p_n}{q_n}\right| < \frac{1}{\sqrt{5}\, q_n^2}.

Insbesondere gibt es für irrationales LaTeX: \alpha unendlich viele Brüche mit dieser Eigenschaft.

Man könnte angesichts dieser Ergebnisse vermuten, dass man die Bedingung durch Einbeziehen von vier oder mehr aufeinanderfolgenden Näherungsbrüche weiter verschärfen kann. Dies ist aber nicht der Fall:

Satz (Hurwitz, 1891,[37] siehe auch Satz von Hurwitz): Sei LaTeX: \phi = [1; 1, \dotsc] die goldene Zahl. Dann gibt es für jede reelle Zahl LaTeX: c mit LaTeX: c > \sqrt{5} nur endliche viele Brüche LaTeX: a/b mit

LaTeX: \left|\phi-\frac{a}{b}\right| < \frac{1}{c\ b^2}.

Eine Verschärfung lässt sich nun nur erreichen, wenn man die zu LaTeX: \phi äquivalenten Zahlen ausschließt:

Satz (Hurwitz, 1891):[38] Für alle irrationalen Zahlen LaTeX: \alpha, die nicht äquivalent zu LaTeX: \phi sind, gibt es unendlich viele Brüche LaTeX: a/b mit

Vorlage:NumBlk

Durch weiteres Ausschließen von Äquivalenzklassen kann man die Konstante LaTeX: c weiter vergrößern. Die dabei auftretenden Werte LaTeX: c bilden das sogenannte Lagrange-Spektrum. Sie konvergieren gegen die Zahl 3 und sind mit den Markoff-Zahlen verwandt.[39]

Eigenschaften fast aller irrationalen Zahlen

Beispiele für augenscheinliche, aber bislang nicht nachgewiesene Konvergenz gegen die Chintschin-Konstante,
Rot: LaTeX: \pi (Kreiszahl),
Blau: LaTeX: \gamma (Euler-Mascheroni-Konstante),
Grün: ∛2 (Kubikwurzel aus 2).
Schwarze Linie: Chintschin-Konstante
Nachweislich keine Konvergenz gegen die Chintschin-Konstante,
Rot: LaTeX: e (Eulersche Zahl),
Blau: √2 (Wurzel 2),
Grün: √3 (Wurzel 3).
Schwarze Linie: Chintschin-Konstante

Chintschin-Konstante

Die sogenannte metrische Kettenbruchtheorie beschäftigt sich mit Eigenschaften, die typische reelle Zahlen haben. Sie geht auf den gleichnamigen Artikel von Alexander Chintschin in der Zeitschrift Compositio Mathematica aus dem Jahr 1935 zurück,[40] aber auch Gauß beschäftigte sich schon mit ähnlichen Themen.[41] Typisch ist hier im maßtheoretischen Sinn zu verstehen: Man formuliert Eigenschaften, die, bis auf eine Nullmenge, alle reellen Zahlen besitzen. In diesem Fall sagt man, dass fast alle reellen Zahlen diese Eigenschaft haben.

Das Ergebnis von Chintschin lautet: Für fast alle reellen Zahlen konvergiert LaTeX: \textstyle\sqrt[n]{b_1 b_2 \cdots b_n} für LaTeX: n \to \infty gegen die Konstante

LaTeX: \prod_{r=1}^\infty \left(1+\frac{1}{r(r+2)}\right)^{\log_2 r} = 2{,}685452001\ \dots   (Folge A002210 in OEIS).

Das geometrische Mittel der Teilnenner fast jeder reellen Zahl konvergiert also gegen eine feste Konstante. Zu den Ausnahmen gehören alle rationalen Zahlen, da sie nur endlich viele Teilnenner besitzen – aber sie bilden eben auch nur eine Nullmenge der reellen Zahlen.

Es ist nicht bekannt, ob diese sogenannte Chintschin-Konstante rational, algebraisch irrational oder transzendent ist.

Die Kettenbruchentwicklungen von Zahlen, für die der Grenzwert nicht existiert oder ungleich der Chintschin-Konstante ist, sind meist besonders regelmäßig. Dies gilt für reelle Lösungen quadratischer Gleichungen (periodische Kettenbruchentwicklung, z. B. die Quadratwurzel von LaTeX: 2), die Eulersche Zahl LaTeX: e (Muster wurde weiter oben erwähnt) und beispielsweise alle Zahlen der Form LaTeX: e^{1/n} oder LaTeX: e^{2/n} (LaTeX: n \in \N).

Rechts sind Diagramme zu den Graphen der Funktion LaTeX: \textstyle n \mapsto \sqrt[n]{b_1 b_2 \cdots b_n} für je drei Beispiele zu sehen.

Vergleich von Kettenbruchdarstellung und Dezimaldarstellung

Der Satz von Lochs besagt folgendes: Für fast jede reelle Zahl zwischen LaTeX: 0 und LaTeX: 1 bekommt man auf lange Sicht für jedes weitere Glied eines Kettenbruchs LaTeX: \tfrac{\pi^2}{6\ln 2\ln 10} \approx 1{,}03064-viele gültige Dezimalstellen. Damit ist die Darstellung mit Kettenbrüchen (für fast alle Zahlen) nur leicht effizienter als die Dezimaldarstellung. Die Lochs-Konstante ist mit der Lévy-Konstante LaTeX: \lim_{n \to \infty}\sqrt[n]{q_n} = e^\frac{\pi^2}{12\ln 2} verwandt (sie ist das Doppelte des Zehner-Logarithmus der Lévy-Konstante).

Siehe auch

Literatur

  • Claude Brezinski: History of Continued Fractions and Padé Approximants. Springer, Berlin 1991.
  • Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-76490-8.
  • Alexander Jakowlewitsch Chintschin: Kettenbrüche. Teubner, Leipzig 1956, oder Continued Fractions. Dover Publications, 1997 (russ. Original 1935).
  • Godfrey Harold Hardy, E. M. Wright: An introduction to the theory of numbers. Oxford University Press, 2005 (1. Auflage 1938).
  • William B. Jones, W. J. Thron: Continued Fractions. Analytic Theory and Applications. Cambridge University Press, 2009.
  •  Oleg Karpenkov: Geometry of Continued Fractions (= Algorithms and Computation in Mathematics). Springer Verlag, Heidelberg, New York, Dordrecht, London 2013, ISBN 978-3-642-39367-9, doi:10.1007/978-3-642-39368-6.
  • Ivan M. Niven, Herbert S. Zuckerman: Einführung in die Zahlentheorie. 2 Bände, Bibliographisches Institut, Mannheim 1976 (engl. Original: Wiley, 1960).
  • Oskar Perron: Die Lehre von den Kettenbrüchen.1. Auflage in einem Band. Teubner, 1913, archive.org. 2. Auflage 1929, 3. Auflage in zwei Bänden, Band 1: Elementare Kettenbrüche. 1954, Band 2: Analytisch-funktionentheoretische Kettenbrüche. 1957.
  • Oskar Perron: Irrationalzahlen. Göschens Lehrbücherei, Band 1. Walter de Gruyter, Berlin/Leipzig 1921, archive.org. 2. Auflage 1939, 3. Auflage 1947.
  • Andrew M. Rockett, Peter Szüsz: Continued fractions. World Scientific, 1992.
  • Joachim Stiller: Endliche und unendliche Algorithmen und Kettenbrüche PDF

Weblinks

Commons-logo.png Commons: Kettenbruch - Weitere Bilder oder Audiodateien zum Thema

Einzelnachweise

  1. Oskar Perron spricht von „regelmäßigen Kettenbrüchen“. Die Bezeichnung der regelmäßigen Kettenbrüche als „einfache Kettenbrüche“ (eng. simple continued fractions) findet man zum Beispiel schon in Carl Douglas Old: „Continued fractions“, Mathematical Association of America, 1963. Siehe auch Jörg Arndt, Christoph Haenel: „Pi. Algorithmen, Computer, Arithmetik.“ 2. Auflage. Springer Verlag, 2000, S. 65.
  2. Bei Oskar Perron werden noch weitere Klassen von Kettenbrüchen systematisch behandelt.
  3. Zur Anwendung in der Kryptographie siehe z. B. das Buch „Solving the Pell Equation“ von M. Jacobson und Hugh C. Williams und zur algebraischen Geometrie den Artikel The geometry of continued fractions and the topology of surface singularities von Patrick Popescu-Pampu, math.univ-lille1.fr (PDF; 676 kB), in dem auch die geometrische Darstellung von H. J. S. Smith (1876) und Felix Klein (1895) und die Hirzebruch-Jung-Kettenbrüche erläutert werden (diese ähneln regulären Kettenbrüchen, wobei hier statt Addition die Subtraktion verwendet wird. Der Bruch LaTeX: 5/3 wird so beispielsweise als LaTeX: 2-1/3 geschrieben.) Für die Anwendung in der Funktionentheorie siehe das Buch von H. S. Wall und bei chaotischen Systemen die Webseite von John D. Barrow, Chaos in Numberland.
  4. Dass dieser Kettenbruch gleich der Quadratwurzel von 2 ist, wird im Abschnitt Periodische Kettenbrüche gezeigt.
  5. Lamberts Kettenbruchdarstellung der Tangensfunktion, siehe dafür Ebbinghaus u. a.: Zahlen. 3. Auflage, Springer, 1992, S. 122.
  6. Die Angabe des relativen Fehlers ist hier nicht sinnvoll, da sich die Approximationseigenschaften einer Zahl nicht durch Addition von ganzen Zahlen ändern.
  7. Leonhard Euler und Chr. Goldbach, Briefwechsel.
  8.  André Weil: Number Theory. Birkhäuser Verlag, Boston 1984, ISBN 0-8176-4565-9.
  9.  Winfried Scharlau, Hans Opolka: Von Fermat bis Minkowski. Springer, 1980, ISBN 3-540-10086-5.
  10.  Moritz Abraham Stern: Theorie der Kettenbrüche und ihre Anwendung. In: Journal für die reine und angewandte Mathematik. Volume 1833, Issue 10, 1833, S. 1–22, doi:10.1515/crll.1833.10.1. Es gibt auch eine Zusammenfassung mehrerer Artikel dieser Zeitschrift in Buchform aus dem Jahr 1834.
  11. In der älteren Literatur werden LaTeX: a_i und LaTeX: b_i oft vertauscht, sodass die Teilnenner LaTeX: a_i heißen.
  12.  Oskar Perron: Die Lehre von den Kettenbrüchen. Band I: Elementare Kettenbrüche. Wissenschaftliche Buchgesellschaft, Darmstadt 1977, S. 1.
  13. Außer den hier angegebenen Schreibweisen gibt es noch LaTeX: b_0+\tfrac{1}{b_1+{}} \tfrac{1}{b_2+{}} \tfrac{1}{b_3+{}}\cdots (zum Beispiel in Conway, Guy: The book of numbers. Springer, 1996), LaTeX: \langle b_0, b_1, b_2, b_3, \dotsc \rangle (z. B. im Buch von Niven/Zuckerman) sowie LaTeX: b_0 + /\!/b_1, b_2, b_3, \dotsc/\!/ (z. B. in Donald Knuth: The Art of Computer Programming. (Band 2), Addison-Wesley, 1997).
  14. Siehe Alf van der Poorten: Symmetry and folding of continued fractions. Journal de Théorie des Nombres de Bordeaux 14 (2), 603–611 (2002).
  15. Für eine aktuelle Verwendung dieser Veranschaulichung siehe Dusa McDuff: Symplectic embeddings and continued fractions: a survey. Japanese Journal of Mathematics, 4(2), 2009.
  16. Das wäre zum Beispiel nicht der Fall, wenn als Teilnenner beliebige positive reelle Zahlen zugelassen wären. In diesem Fall gilt: Der Kettenbruch LaTeX: [b_0; b_1, \dotsc] konvergiert genau dann, wenn die Summe LaTeX: \textstyle \sum_{i=0}^\infty b_i divergiert.
  17. A. Hurwitz: Ueber die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche. In: Mathematische Annalen. Band 39, 1891, S. 284. Siehe auch Hardy/Wright, Kapitel 10.11.
  18. Siehe Perron (1929), 2. Kapitel, Satz 23 (Seite 63).
  19. Siehe etwa Artikel Konvergenzkriterium von Pringsheim!
  20. Eine ausführliche Behandlung dieses Themas wurde insbesondere von Oskar Perron vorgenommen in Band II seiner Lehre von den Kettenbrüchen.
  21.  Leonhard Euler: Einleitung in die Analysis des Unendlichen. Springer Verlag, 1983, S. 302.
  22. Joseph-Louis Lagrange: Additions au mémoire sur la résolution des équations numériques. Œuvres complètes, tome 2, 581–652 (1770).
  23. Siehe Perron (1913), 3. Kapitel, Satz 9 – Internet Archive.
  24. Als Quelle siehe Eulers De usu novi algorithmi in problemate Pelliano solvendo. Ganz unten erkennt man auch die Zahl LaTeX: 61. Die Kettenbruchentwicklung ihrer Quadratwurzel hat Periode LaTeX: 11: LaTeX: \sqrt{61}=[7;\overline{1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14}] und Euler rechnet sie als nächstes Beispiel aus. Einige Seiten später findet man eine komplette Liste der periodischen Kettenbrüche für LaTeX: d bis 120.
  25. Siehe Chintschin, Satz 17.
  26. Es gibt noch einen Ausnahmefall für rationale Zahlen LaTeX: \alpha, der aber vermieden werden kann, wenn man nur solche Kettenbrüche erlaubt, deren letzter Teilnenner größer als LaTeX: 1 ist. Es handelt sich um LaTeX: \alpha = b_0+1/2. Diese kann man als LaTeX: [b_0;2] oder als LaTeX: [b_0;1,1] schreiben. Im letzten Fall ist LaTeX: p_1/q_1 = b_0+1 und dieser Näherungsbruch hat den gleichen Abstand zu LaTeX: \alpha wie der 0-te Näherungsbruch LaTeX: b_0. Siehe Hardy/Wright, Seite 194.
  27. Siehe Chintschin, Satz 16.
  28. Siehe Chintschin, Satz 15.
  29. Siehe Perron (1913), 2. Kapitel, Sätze 20 und 21.
  30. Siehe hierfür zum Beispiel die Aufgaben zu Kapitel 7.5 im Buch von Niven/Zuckerman.
  31. Siehe Perron (1913), 2. Kapitel, Satz 22.
  32. Genauer formuliert müsste man natürlich sagen, dass die Graphik zusätzlich noch den Logarithmus dieser Schranke enthält.
  33. Siehe auch die ähnliche Aussage im Artikel Dirichletscher Approximationssatz.
  34. Legendre: Essai sur la théorie des nombres. 1798. In der Auflage von 1808 findet sich der Beweis auf Seite 21.
  35. Siehe Perron (1913), 2. Kapitel, Satz 14.
  36. Siehe Perron (1913), 2. Kapitel, Satz 15.
  37. Zum Beweis siehe zum Beispiel Albrecht Beutelspacher, Bernhard Petri: Der Goldene Schnitt. Bibliographisches Institut 1989, Seite 99.
  38. Hurwitz, 1891, Mathematische Annalen 39, Ueber die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche. S. 279–284.
  39. Siehe Michel Waldschmidt: Introduction to Diophantine methods irrationality and trancendence. (PDF; 700 kB), Seiten 24–26.
  40. A. Khintchine: Metrische Kettenbruchprobleme. (29. März 1934), Compositio Mathematica 1, 1935, S. 361–382.
  41. Der Satz von Gauß-Kusmin betrifft die Wahrscheinlichkeitsverteilung der Teilnenner reeller Zahlen (R. O. Kusmin, 1928, außerdem Paul Lévy, 1929). Es gilt nämlich für alle natürlichen Zahlen LaTeX: k: Das Maß von LaTeX: M_n(k)=\{x\in[0,1]\mid n\text{-ter Teilnenner von }x\text{ ist gleich }k\} konvergiert für LaTeX: n \to \infty gegen LaTeX: -\log_2\left[ 1-\tfrac{1}{(k+1)^2}\right]. Für LaTeX: k=1 beträgt der Grenzwert ungefähr 41 %, für LaTeX: k=2 ungefähr 17 %. Siehe hierzu das Buch von Chintschin.
Dieser Artikel wurde am 13. April 2010 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.


Dieser Artikel basiert (teilweise) auf dem Artikel Kettenbruch aus der freien Enzyklopädie Wikipedia und steht unter der Lizenz Creative Commons Attribution/Share Alike. In der Wikipedia ist eine Liste der Autoren verfügbar.