______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.3.2. Kettenbrüche

_______________________________________________________________________________
Kettenbrüche als Werkzeug zur Findung geeigneter rationaler Approximationen wurden in vielen Kulturen benutzt; eine erste systematische Theorie hingegen wurde aber erst durch den Astronomen Christaan Huygens im 17. Jahrhundert gegeben, als dieser ein mechanisches Modell unseres Sonnensystems bauen wollte.

Zunächst betrachten wir den euklidischen Algorithmus, welchen wir (gemäß der Notation aus III.1.) umschreiben als

(1) Reste


für n ≤ m; dabei steht ⌊x⌋ für die größte ganze Zahl ≤ x (auch Gaußklammer bzw. Ganfteil genannt). Setzen wir an = ⌊rn−1/rn⌋, so ergibt sich

a/b

Die erste Gleichung liefert den Ganzteil von a/b; jede weitere gibt bessere und bessere Näherungen (mit den kleinst möglichen Nennern entsprechend der Approximationsqualität, wie wir unten zeigen werden). Ein Beispiel liefert das Sonnenjahr.
Der typographische Albtraum

Kettenbruch

heißt Kettenbruch (engl. continued fraction); die an nennt man Teilnenner. Wir notieren einen solchen Kettenbruch kurz mit

Teilnenner

Zunächst betrachten wir [a0,…,am] als eine formale Funktion in unabhängigen Variablen a0,…,am. Offensichtlich gilt

Entwicklung

und


[a ,a ,a ] = a2a1a0 +-a2-+-a0-. 0 1 2 a2a1 + 1
Per Induktion zeigt man

(2) [ ] [a ,a ,...,a ] = a ,a ,...,a + -1- 0 1 n 0 1 n−1 an

und

[a0,a1,...,an] = a0 + ----1------= [a0,[a1,...,an]]. [a1,...,an ]

Ein besonders interessanter Kettenbruch ergibt übrigens sich für den Quotienten aufeinanderfolgender Fibonacci-Zahlen.
Für n ≤ m nennen wir [a0,a1,…,an] den n-ten Näherungsbruch an [a0,a1,…,am]. Wir definieren desweiteren

( { p−1 = 1, p0 = a0 und pn = anpn−1 + pn−2, (3) ( q−1 = 0, q0 = 1 und qn = anqn−1 + qn−2.

Die Berechnung der Näherungsbrüche erfolgt leicht mit Hilfe von

Satz.

Für 0 ≤ n ≤ m gilt

pn-= [a0,a1,...,an]. qn
Dabei ist
pnqn −1 − pn−1qn = (− 1)n−1

und insbesondere sind pn und qn teilerfremd für ganzzahlige Teilnenner a0,a1,…,am.

Beweis per Induktion nach n. Der Fall n = 0 ist trivial. Der Fall n = 1 folgt unmittelbar aus

a1a0 + 1 p1 [a0,a1] = ---------= --. a1 q1
Angenommen die Formel ist richtig für n. In Anbetracht von (2) gilt

[ ] --1-- [a0, a1,...,an,an+1] = a0,a1,...,an + an+1 .

Mit der Rekursionsformel (3) für die pn,qn schreibt sich dies als

( ) --1- (an-+-an+1)-pn−1-+-pn−2- (an+1an-+--1)pn−1 +-an+1pn−2 -1-- = (an+1an + 1)qn−1 + an+1qn−2 an + an+1 qn−1 + qn−2 an+1pn + pn−1 pn+1 = -------------- = -----, an+1qn + qn−1 qn+1

was die Induktion und den Beweis der ersten Aussage abschließt.

Mittels (3) ist

p q − p q = (a p + p )q − p (a q + q ) n n− 1 n− 1 n n n− 1 n−2 n−1 n−1 n n−1 n−2 = − (pn−1qn−2 − pn−2qn− 1).

Wiederholen wir dieses Argument für n − 1,n − 2,…, 2, 1, so ergibt sich induktiv

(− 1 )n (p0q− 1 − p− 1q0) = (− 1)n+1

und damit die zweite Behauptung; die Teilerfremdheitsaussage ist eine einfache Schlussfolgerung. qed.

Jetzt weisen wir den Teilnennern an und somit auch dem Kettenbruch [a0,a1,…,am] numerische Werte zu. Wir fordern a0∈ℤ und an∈ℕ für 1 ≤ n < m, sowie am≥ 1. Sei jetzt α irgendeine rationale Zahl. Dann gibt es teilerfremde ganze Zahlen a und b > 0, so dass α = ab. Es folgt aus der Variation des euklidischen Algorithmus (1) angewandt auf r−1 = a und r0 = b, dass α als endlicher Kettenbruch dargestellt werden kann:
[ ] a-= [a0,a1,a2,...,am ] , wobei an = rn−1-. b rn
Diese Darstellung ist nicht eindeutig, da
[a0,a1,a2,...,am ] = [a0,a1,a2, ...,am − 1,1];
wenn wir allerdings am≥ 2 für den letzten Teilnenner fordern, so besitzt jede rationale Zahl eine eindeutige Darstellung als endlicher Kettenbruch.
Jetzt wollen wir Kettenbrüche zu nicht notwendig rationalen Zahlen bilden. Wir können den Algorithmus (1) zur Berechnung der Kettenbruchentwicklung von rationalen Zahlen umschreiben als

(4) -1--- α0 := α, αn = ⌊αn ⌋ + αn+1 f¨ur n = 0,1, ... .

Setzen wir an = ⌊αn⌋, so erhalten wir α = [a0,a1,…,an,αn+1]. Dieser Algorithmus ist der Kettenbruchalgorithmus. Ist α rational, dann bricht die Iteration nach endlich vielen Schritten ab und der Kettenbruchalgorithmus ist nichts anderes als der euklidische Algorithmus in Verkleidung. Beispiel.
Sei jetzt α irgendeine Irrationalzahl. Dann bricht die Iteration nicht ab, da ansonsten α ja eine Darstellung als endlicher Kettenbruch hätte und somit rational wäre. Also liefert die Iteration für Irrationalzahlen eine unendliche Folge endlicher Kettenbrüche:

[a ,a ,...] := lim [a ,a ,...,α ]. 0 1 m→ ∞ 0 1 m

Der Grenzwert [a0,a1,a2,…] heißt unendlicher Kettenbruch und das Erste, was wir uns zu fragen haben, ist, ob dieser unendliche Prozess konvergent ist, und wenn ja, ob der Grenzwert etwas mit α zu tun hat?

Satz.

Sei α = [a0,a1,…,an,αn+1] irrational mit Näherungsbrüchen pn/qn. Dann gilt

pn- -----(−-1)n------- α − q = q (α q + q ). n n n+1 n n−1
Insbesondere ist
(5) | | || pn-|| --1---- |α − qn | < an+1q2. n

und

pn α = lim ---= [a0,a1,a2,...]. n→∞ qn

Beweis. Zunächst bemerken wir, dass alle unsere Beobachtungen über endliche Kettenbrüche sich auf unendliche Kettenbrüche übertragen - insbesondere (3) und der vorherige Satz. Eine kurze Berechnung zeigt

pn- αn+1pn-+--pn−1 pn- -pn−1qn-−-pnqn−1-- α − q = α q + q − q = q (α q + q ). n n+1 n n−1 n n n+1 n n−1

Der vorherige Satz impliziert damit die erste Behauptung.

Wegen an+1≤ αn+1 folgt ferner

| | ||α − pn|| < --------1---------, | qn| qn(an+1qn + qn− 1)

was bereits (5) beweist. Im Falle eines irrationalen α sind die Folgen der pn und der qn jeweils streng monoton wachsend für n ≥ 2 (d.h. also pn+1> pn und qn+1> qn wie man sofort aus dem Bildungsgesetz (3) folgert). Damit ist die Folge der Näherungsbrüche pn/qn abwechselnd größer bzw. kleiner als α; die mit geradem Index n liegen links, die mit ungeradem Index rechts:

p0 p2 p3 p1 q--< q-< ...< α < ...< q--< q--. 0 2 3 1
Ferner gilt (wiederum) nach vorherigem Satz für die Distanz zweier aufeinanderfolgender Näherungsbrüche

||p p || |p q − p q | 1 ||--n− -n−1|| = --n-n−1----n−1-n- = ------, qn qn−1 qn−1qn qn−1qn

was mit qn→∞ gegen null konvergiert. Die Folge der Näherungsbrüche bildet also eine Intervallschachtelung an α. Ist α irrational, dann terminiert der Kettenbruchalgorithmus nicht und die Folge der Nenner qn der Näherungsbrüche ist unbeschränkt. Also folgt aus der ersten Behauptung, dass der Abstand aufeinanderfolgender Näherungsbrüche kleiner und kleiner wird und gegen Null konvergiert. Also konvergieren die pn/qn gegen den Grenzwert [a0,a1,…] und dieser Grenzwert ist gleich α. Der Satz ist damit vollständig bewiesen. qed.

Sehr interessant sind auch so genannte periodische Kettenbrüche.