Fibonacci Retracements

Fibonacci Retracements
Author D. Selzer-McKenzie
YoutubeVideo: https://youtu.be/QucObQy3fII
Fibonacci-Zahlen, Goldener Schnitt, Kettenbrüche und
Anwendungen
1.1 Einführung
Bei den Fibonaccizahlen1 waren wir in Kap. III.1.4.2 auf das rekursive Wachstumsgesetz (nach Umtaufung von an in Fn)
Fn = Fn_1 + Fn_2, n ≥ 2
gestoßen. In Turin gibt es ein sehr schönes Gebäude, die Mole Antonelliana, die auf ihrer Kuppel die Fibonacci-Zahlen zu Ehre von Fibonacci trägt, siehe Abb. 1.2
Wenn man als Anfangswerte F0 := 0, F1 := 1 vorgibt, erhält man eine Zahlenfolge, die die Fibonacci-Folge genannt wird:
0,1,1,2,3,5,8,13,21,34,F10 = 55,89,
144, 233, 377, 610, 987, 1597, 2584, 4181, F20 = 6765, 10946,
'Nach LEONARDO DA PISA, genannt FIBONACCI (etwa 1170-1250), verfasste das berühmte Buch ”liber abaci“

Abbildung 1.1: Leonardo da Pisa

Abbildung 1.2: Mole antonelliana in Turin
17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, F30 = 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
63245986, F40 = 102334155,...
Mit (Fn) bezeichnen wir jetzt stets diese Fibonacci-Folge.
Andere Anfangswerte f¨uhren auf andere Zahlenfolgen, die Lucasfolgen2 genannt werden. Z.B.
1,3,4,7,11,18,29,...
welche auch zuweilen die Lucasfolge genannt wird.
Warum sind Fibonacci-Zahlen so populär? Der eine Grund ist die enge Beziehung zum Gol¬denen Schnitt, siehe Kap. 1.2.2, der auch schon in Kap. III.1.4.2 hergestellt wurde.
Der andere ist das Auftreten in der Biologie, sei es als Anzahl der Bl¨utenblätter etwa von Gänsebl¨umchen oder als Anzahl von Spiralen (Parastichen) z.B. bei Sonnenblumen, Kiefern¬zapfen oder Ananas.
Einen kleinen ¨Uberblick findet man in meinem Vortrag auf der 25. Absolventenfeier am 8. Fe¬bruar 2006 mit dem Titel Fibonacci-Zahlen und ihr Vorkommen in der Biologie, der sehr gut als Einleitung zu dieser Vorlesung angesehen werden kann. Er war an Nicht-MathematikerInnen gerichtet.
1.1.1 Kaninchen
Leonardo da Pisa stellte folgende Frage: Wieviel Nachkommen hat ein einzelnes Kaninchenpaar nach einem Jahr?
Es ist ein sehr vereinfachendes mathematisches Modell, das diese Frage beantwortet. Ich wie¬derhole kurz die Ausf¨uhrungen aus Kap. III.1.4.2:
2EDOUARD LUCAS, 1842-1891


Abbildung 1.3: Kaninchenvermehrung
In einer Tierpopulation bezeichne Jn die Anzahl der Jungtiere und An die Anzahl der Alttiere nach n Monaten. Jungtiere können sich noch nicht fortpflanzen, während die Alttiere pro Monat ein Jungtiernachkommen zeugen3, aber nie sterben. Jungtiere werden nach einem Monat zu Alttieren. Dann gilt
An+1 = An + Jn, Jn+1 = An.
Die erste Beziehung besagt, dass Jungtiere im ”nächsten“ (dem auf n folgenden) Zeitschritt (dem n + 1-ten) Alttiere werden, die zweite Gleichung, dass es im nächsten Zeitschritt genauso viele Jungtiere wie zuvor Alttiere gibt. Dann kann man für Jn auch An_1 setzen und man erhält
An+1 = An + An_1,
die Fibonacci-Rekursion. Auch die Zahl aller Kaninchenpaare Xn := An+Jn im n-ten Monat genügt dieser Fibonacci-Rekursion.
Wenn für n = 1 gerade ein Jungtier(paar) und kein Alttier(paar) existiert, so gilt X0 = 0, X1 = J1 = 1 und man erhält für (Xn) die Fibonacci-Folge: Xn = Fn. Nach genau einem Jahr, also im 13. Monat, gibt es demnach F13 = 233 Kaninchenpaare, während es nach einem halben Jahr, also im 7. Monat, ”nur“ F7 = 13 Kaninchenpaare gibt.
In Abb. 1.3 werden die Alttiere mit einem roten Kreis und die Jungtiere mit einem weißen Quadrat markiert.
1.1.2 Pflanzenwachstum
Abb. 1.4 zeigt einen Prototyp einer Pflanze mit einer Fibonacci-Gesetzmäßigkeit, was die Sei-tentriebe betrifft.
3Genauer: Ein Geschlechterpaar zeugt ein weibliches und ein männliches Jungtier.


Abbildung 1.4: Blume mit Seitentriebe
Die ”Alttriebe“ habe ich mit roten Kreisen, die ”Jungtriebe“ mit weißen Quadraten versehen. Man erkennt sofort die Analogie zur Kaninchenvermehrung. Es gibt wirklich Blumen, die so wachsen: Achillea ptarmica — Sumpf-Schafgarbe.
1.1.3 X-Chromosome
Eine andere wenig bekannte Anwendung bezieht sich auf die Vererbung des X-Chromosoms, siehe Erbmäßig bevorzugte Vorfahrenlinien bei zweigeschlechtigen Lebewesen (Arndt Richter 1979). Wenn man unterstellt, dass jeder Mensch 2n verschiedene Ahnen in der n-ten Vorgene-ration hat (n = 1: 2 Eltern, n = 2: 4 Großeltern, etc), so kann man beispielsweise bei einem Mann nach der Anzahl der Vorfahren n-ter Stufe fragen, die einen Einfluss auf sein (einziges) X-Chromosom haben. Dabei muss man wissen, dass eine Frau ihre beiden X-Chromosome zu gleichen Teilen von Mutter und Vater erhält, während ein Mann sein X-Chromosom nur von der Mutter bekommt (das andere Y-Chromosom ist eine Kopie des Y-Chromosoms des Vaters). Wenn wir jetzt mit Mn die auf das X-Chromosom Einfluss habenden Frauen (”Mütter“) und mit Vn entsprechend die ”Väter“ bezeichnen, so haben beide Eltern einer der Mn Frauen und nur die Mutter eines der Vn Männer X-chromosomalen Einfluss. Es ergibt sich
Mn+1 = Mn + Vn, Vn+1 = Mn.
Das ist genau die Rekursion für die Kaninchenvermehrung, wenn man ”Mütter“ mit Alttieren und ”Väter“ mit Jungtieren gleichsetzt! Auch die Anfangsbedingungen sind die gleichen: V0 = 1,M0 = 0.
Die Abb. 1.5 illustriert diesen Sachverhalt.


Abbildung 1.5: X-Chromosom-Vererbung
Beispielsweise gibt es in der 6. Vorgeneration eines Mannes von insgesamt 26 = 64 Ahnen genau F7 = 13 Ahnen, die dessen X-Chromosom beinflusst haben könnten.
1.1.4 Wahrscheinlichkeiten
Wenn wir in den Stammbaum in Abb. 1.5 auch noch alle fehlenden Väter aufnehmen würden, gäbe es in der n-ten Vorgeneration 2n Personen, von denen ja Fn+1 X-chromosomalen Einfluss auf den Mann (Wurzel des Baums) hat.
Nun stellen wir uns einen Münzwurf vor, der bestimmt, wie der Baum von unten nach oben durchlaufen wird: Bei ”Wappen“ wird der Vater, bei ”Zahl“ die Mutter ausgewählt. Wir fragen nach der Wahrscheinlichkeit, dass nach n Würfen ein Vorfahr ausgelost wird, der X-chromosomalen Einfluss hat. Die Wahrscheinlichkeit ist gerade
p= Fn+1
 2n .
Jetzt fragen wir bei n Münzwürfen nach der Wahrscheinlichkeit, dass niemals k-mal hinterein¬ander Wappen geworfen wird. Für k = 2 ist dies fast die eben beschriebene Situation. Nur, dass im ersten Wurf gelost wird, ob es sich um einen Mann oder eine Frau handelt, deren Stammbaum man verfolgen will. Die Antwort ist jetzt
p= Fn+2
 2n .
Für k > 2 führt dieselbe Frage auf ”Fibonacci-k-Schritt-Zahlen“, die z.B. für k = 3 durch
= F(3)
n−1 + F(3)n−2 + F(3)
n−3,

Abbildung 1.6: Fibonacci-Rechteck
F(3)
0= 0,F1(3)= 1,F(3)
2 = 1
definiert sind (und Tribonacci-Zahlen heißen).
1.1.5 Geometrie, Spiele, Kombinatorik
Wenn man, beginnend mit einem Quadrat der Kantenlänge 1, an jedes Rechteck an deren längere Seite ein Quadrat anbaut, so erhält man Rechtecke, deren Kantenlängen benachbarte Fibonacci-Zahlen sind, siehe Abb. 1.6.
Solche Rechtecke nennt man Fibonacci-Rechtecke. Beachten Sie, dass ein solches Rechteck sich aus lauter Quadraten mit Fibonacci-Zahlen als Kantenlängen zusammensetzt. Wenn man deren Flächen betrachtet, erhält man eine der vielen Fibonacci-Formeln
Xn Fk 2= Fn·Fn+1. k=1
Mit dieser geometrischen Deutung kann man auch weitere Formeln wie
Xn F2k−1 = F2n, k=1
Xn F2k = F2n+1 − 1 k=1


Abbildung 1.7: Mauermuster
Xn Fk = Fn+2 − 1 k=1

”beg¨unden“, siehe Übungen.
Wenn man das Quadrat immer gegen oder immer mit dem Uhrzeigersinn anbaut, so erhält man eine Spirale, die, wenn das Ausganbgsrechteck golden ist, zur goldenen Spirale f¨uhrt.
Die Frage nach der Anzahl der möglichen Muster, wenn man eine Mauer der Länge n und Höhe 2 aus Ziegelsteinen mit den Kantenlängen 1 und 2 bauen will, f¨uhrt ebenfalls auf Fibonacci-Zahlen, siehe Abb. 1.7.
Bei dem Damebrettspiel, siehe Abb. 1.8 kann man die Frage stellen, ob es gelingt, durch suk¬zessives Ziehen von weißen Spielsteinen (Diagonalzug, der einen eigenen Stein ¨uberspringt und diesen ”schlägt“) die letzte Linie des Brettes zu erreichen.
Die Antwort ist ”Nein“, wie man sehen kann, wenn man die Spielfelder mit Fibonacci-Zahlen unterlegt, siehe Abb. 1.9.
Man muss nur alle Zahlen unter den auf dem Brett befindlichen Spielsteinen addieren. Zu Beginn ist diese Summe 35. Sie bleibt nach jedem Zug unverändert! Daher kann allenfalls die vorletzte Linie erreicht werden.
Eine ähnliche Überlegung findet man in BEUTELSPACHER zum Wüstenspiel, wobei aber als Ge-wichte Potenzen der kleinen Goldene-Schnitt-Zahl auftreten. Mit Seitwärts- und Vorwärtsz¨ugen soll man möglichst weit in die ”W¨uste“ vordringen.
1.1.6 Phyllotaxis
In der Phyllotaxis (Lehre von der Blattstellung, Musterbildung beim Pflanzenwachstum), z.B. dem Wachstum von Kiefernzapfen oder von Sonnenblumen hat man Fibonacci-Zahlen entdeckt, siehe die Webseite Phyllotaxis (Smith College, UK).


Abbildung 1.8: Damebrett

Abbildung 1.9: Damebrett mit Fibonacci-Zahlen


Abbildung 1.10: Spiralen bei Kiefernzapfen und Ananas
In der Abb. 1.10 sind die Anzahlen der nach links und nach rechts laufenden Spiralen Fibonacci-Zahlen.
Desgleichen bei der Sonnenblume, siehe Abb. 1.11.
Auf der Webseite Rekursionen (Mathe Prisma Wuppertal) findet sich auch ein schön darge¬stellter Zusammenhang zwischen dem Wachstum von Sonnenblumen, Fibonaccizahlen. und dem goldenen Schnitt, den wir später vertiefen werden.
Dabei verweise ich auf Kap. I.2.2, was die Definition der großen (Φ) und kleinen (ϕ) Goldenen-Schnitt-Zahl und ihre Interpretation als Teilungsverhältnis betrifft.
1.2 Erste Eigenschaften der Fibonacci-Folge
Bemerkenswert ist es nun, dass man eine ”geschlossene Formel“ für die Fibonaccifolge bei beliebigen Anfangsbedingungen angeben kann, die eine Beziehung zur Goldenen-Schnittzahl liefert.
Satz 1.1. Sei λ1 := 12(1 + v'5),λ2 := 12(1 − v'5). Dann erfüllt die Folge (an) mit den Folgen-gliedern
a1 − λ2a0 λ1a0 − a1
 λn1 + λn2,n = 0,1,2,.... (1.1)
λ1 − λ2 λ1 − λ2
die Rekursion
an+1 = an + an−1
für n ≥ 2.


Abbildung 1.11: Sonnenblume
Beachten Sie, dass λ1 gerade die große Goldene-Schnitt-Zahl ist, während −λ2 die kleine Goldene-Schnitt-Zahl ist.
Beachten Sie ferner, dass man in (1.1) für n = 0 und n = 1 die Identitäten a0 = a0 und a1 = a1 erhält.
Jetzt soll der Spezialfall a0 := 0, a1 := 1, der auf die Fibonacci-Folge (Fn) führt, untersucht werden. Nach Satz 1.1 gilt
Fn =
bzw., wenn man λ1 und λ2 einsetzt:
(
1 (1 √5)n)
 Fn = √5 2 + 1 √5)n −(1 2 −1 , n = 0,1,2,.... (1.2)
2 2
oder auch (
1  Φn + (−1)nϕn)
Fn = √5 (1.3)
Formel (1.2) wird J. P. M. BINET (1786-1856) zugeschrieben und heißt daher auch Binet-Formel, ist aber wohl schon 1745 von L. EULER publiziert worden.
Wegen ϕ= 0.618.. < 1 ist ϕn ≈0 für große n. Daher gilt die Näherung
Fn = Φn
√5
Sie gilt aber auch für keine n, da (ohne Beweis)
Fn=Φn√5+0.5.

1.2.1 Lineare Differenzengleichungen
Um Satz 1.1 zu beweisen, müssen wir mehr über lineare Differenzengleichungen wissen, von denen Fn+1 = Fn + Fn−1 ein Spezialfall ist.
Definition 1.2. Eine lineare Differenzengleichung k-ter Ordnung für eine Folge (an) ist ein rekursives Bildungsgesetz der Form
an+k = αk−1an+k−1 + αk−2an+k−2 + · · · + α1an+1 + α0an, n = 0, 1, 2, ... (1.4)
mit den k Koeffizienten αj E IR, j = 0,1, ..., k − 1.
Für die Fibonacci-Rekursion ist offensichtlich k = 2 die Ordnung der Differenzengleichung, und es gilt α0 = α1 = 1.
Die Folge (an) wird offensichtlich dann eindeutig festgelegt, wenn k Startwerte a0, a1, ..., ak−1 vorgegeben werden — das kennen Sie von der Fibonacci-Folge.
Bemerkung: (1.4) bezeichnet man in engerem Sinne als homogene Differenzengleichung — im Gegensatz zu inhomogenen wie z.B. bei
an+1 = (1 + p)an + b,
wie sie z.B. als Differenzengleichung 1.Ordnung auftritt, bei Ratensparverträgen auftritt, siehe Kap.III, Übungsaufgabe 5.
Die Lösungstheorie solcher linearen Differenzengleichungen geht zunächst von dem Begriff Lösung aus: Hierunter verstehen wir eine reelle Folge (an)nEIN0, die der Rekursion (1.4) genügt. Es dürfte klar sein, dass es sehr viele verschiedene Lösungen gibt: Was ich auch immer für die Startwerte a0, a1, ..., ak−1 einsetze — ich erhalte stets eine Lösung.
Auf Grund der Linearität und der Homogenität von (1.4) sieht man sehr schnell ein:
Satz 1.3. Mit zwei Folgen ist auch stets die Summe sowie die skalaren Vielfachen hiervon eine Lösung.
Mehr noch: Die Menge aller Lösungsfolgen bildet einen Vektorraum der Dimension k, wenn man als Summe und skalares Vielfaches von Folgen das versteht, was wir in Kap. III definiert haben:
(an)n + (bn)n := (an + bn)n, λ(an)n := (λan)n.
Wir wollen diesen Satz nicht beweisen, sondern ihn an der Fibonacci-Rekursion demonstrieren: Wir erwarten einen Lösungsraum der Dimension 2. In der Tat ist jede Lösung eine Linearkom-bination der Folge (an), die der Fibonacci-Rekursion und den Anfangswerten a0 = 1 und a1 = 0 genügt, sowie der FOlge (bn), die ebenfalls der Fibonacci-Rekursion und den Anfangswerten b0 = 0, b1 = 1 genügt. Letztere ist gerade die Fibonaccifolge (Fn) := 0, 1, 1, 2, 3, 5, 8, ..., erstere ist die Folge 1, 0, 1, 1, 2, 3, 5, 8, ...., welche sich als (Fn−1) darstellen lässt, wenn man F−1 := 1 setzt. So ist die Folge (cn) := 3, 2, 5, 7, 12, 19, ... gerade das 3-fache von (an) plus das 2-fache von (bn). Daher kann man cn = 3Fn−1 + 2Fn für n > 1 gewinnen!
Letzteres kann man verallgemeinern.

Satz 1.4. Sei (cn) die durch die Fibonacci-Rekursion und die Anfangswerte c0 = A, c1 = B definierte Folge mit beliebigen (reellen!!) A und B. Dann gilt cn = AFn−1 + BFn,n > 1.
BEWEIS: Mit den eben eingeführten ”Basisfolgen“ (an) und (bn) gilt cn = A · an + B · bn und wegen an = Fn−1 und bn = Fn folgt die Behauptung.
Wenn Ihnen diese Argumentation zu abstrakt ist, schreiben Sie die ersten Folgenglieder von (cn) auf:
A,B,A+B,A+2B,2A+3B,3A+5B,5A+8B,
Erkennen Sie die Gesetzmäßigkeit?
Satz 1.4 ist sehr hilfreich zum Beweis einiger überraschender Aussagen über (Fn) wie z.B.
Fn(Fn−1 + Fn+1) = F2n,
s. Übungen.
Das Wunderbare ist nun, dass man spezielle Lösungen von (1.4) durch einen Ansatz an := λn in Form von geometrischen Folgen (exponentielles Wachstum!) mit einer unbekannten Zahl λ gewinnen kann (diese kann sogar nichtreell komplex sein!). Gehen wir mit diesem Ansatz in (1.4), so erhält man
λk = αk−1λk−1 + · · · + α1λ + α0.
Diese Gleichung ist eine polynomiale Gleichung k-ter Ordnung, sie heißt charakteristische Gleichung von (1.4).
Im Falle der Fibonacci-Rekursion ist die charakteristische Gleichung eine quadratische Glei¬chung
λ2 = λ + 1.
I.A. besitzt die charakteristische Gleichung k Lösungen λj, j = 1, 2, ..., k, die in der Regel auch eine Basis von geometrischen Folgen des Lösungsraums liefern.
Dies demonstrieren wir wieder an dem Beispiel der Fibonacci-Rekursion mit dem Ziel, den Satz 1.2 zu verstehen: Die charakteristische Gleichung lautet ja λ2 = λ + 1. Sie hat λ1 und λ2 (s. Satz 1.2) zur Lösung. Mit den Linearkoeffizienten cj, j = 1, 2 ist damit jede Folge (an) mit
an = c1λn1 + c2λn (1.5)
2
eine Lösung der Fibonacci-Rekursion. Die Fibonacci-Zahlen erhält man nun, indem man die Bedingungen a0 = 0, a1 = 1 in (1.5) einsetzt, also
0 = c1 + c2, 1 = c1λ1 + c2λ2
erhält. Dies sind zwei lineare Gleichungen für c1 und c2. Es ergibt sich
1
c1 = −c2 = 
 ,
λ1 − λ2

und die eigentliche Formel von BINET
Fn =  1 ((1 √5)n (1 √5)n)
√5 2+ 222 ,n = 0,1,2,....
.
Die Formel (1.2) in Satz 1.2 erhält man, wenn man
c1 + c2 = a0, c1λ1 + c2λ2 = a1
nach cj, j = 1, 2 auflöst.
1.2.2 Fibonaccizahlen und der Goldene Schnitt
Es gilt der folgende schon JOHANNES KEPLER (1571-1630) bekannte
Satz 1.5. Der Quotient zweier aufeinanderfolgender Fibonaccizahlen konvergiert gegen eine Goldene-Schnitt-Zahl. Genauer: Es gilt
 lim n→∞Fn Fn+1  = Φ
mit der großen Goldene-Schnitt-Zahl   
1 √
Φ = 2( 5 + 1).
Es gilt
Fn
 = ϕ
Fn+1
mit der kleinen Goldene-Schnitt-Zahl
1
√
ϕ = 2( 5 − 1).
Beweis: Offensichtlich gilt λ1 = Φ. Es ergibt sich
λn+1
1 − λn+1
2
=
Dividiert man Zähler und Nenner des Bruches durch λn1 und setzt µ := λ2
λ1 , so folgt
Fn+1  λ1 − λ2µn
 
Fn 1 − µn .
Da |µ| < 1, konvergiert die geometrische Folge (µn) gegen Null und Fn+1
Fn gegen λ1 = Φ.
Die letzte Behauptung des Satzes 1.5 folgt aus Φ = 1ϕ.
Aus der letzten Rechnung folgt wegen λ2 < 0 und daher auch µ < 0, dass die Quotienten alternierend konvergieren: Man erhält abwechselnd eine obere und eine untere Schranke für den Grenzwert Φ. Dies werden wir im Rahmen der Kettenbrüche wiederentdecken.

Kapitel 2
Drehungen
2.1 Drehungen der Ebene
Zum Verständnis des Auftretens von Fibonacci-Zahlen muss man verstehen, was eine Drehung um den goldenen Winkel und allgemein, was überhaupt Drehungen sind.
Viele Phänomene im Verbindung mit dem Auftreten von Fibonacci-Zahlen im Pflanzenwachs¬tum hängen damit zusammen, dass das Wachstum ”spiralförmig“ von innen nach außen verläuft. Zwei aufeinanderfolgende Blattansätze z.B unterscheiden sich durch einen ”Divergenzwinkel“, der sich als golden in dem Sinne herausstellt, dass er 360 · p = 222, 24 Grad bzw. dessen Kom¬plement 360·(1−p) = 137,5 (s. Abb. 2.1) Grad betragen kann. Warum diese Winkel bevorzugt werden, werden wir erklären.
2.1.1 Die Kreislinie
Im Folgenden haben wir es mit einem Kreis zu tun, genauer mit der Kreislinie1. Ein Punkt dieser Kreislinie ist alleine durch einen Winkel p bestimmt, im Bogenmaß durch p E [0, 2π). Da es im Folgenden sehr darauf ankommt, ob Winkel rationale oder irrationale Vielfache von
'Im Gegensatz zur Kreisscheibe, die auch das Innere eines Kreises enthält.

Abbildung 2.1: Goldener Winkel

π sind, mache ich einen Trick. Ich definiere die Kreislinie als
S1 := [0, 1),
indem ich jedes α ∈S1 mit einem Winkel ϕ := α•2π ”identifiziere“. Wenn man also von α = 0.5 spricht, meint man den Winkel π im Bogenmaß bzw. 180 Grad im Gradmaß.
Nun führe ich eine Addition ⊕auf S1 ein, die Sie schon in ähnlicher Form ((ZZ7,,, +7,,) in Kap. I.8.3) kennen:
α ⊕β:= (a + b) mod 1.
Man addiert ganz normal und schneidet sodann den ganzzahligen Anteil weg. Hiermit wird (S1, ⊕) eine Gruppe (siehe Def.I.8.6). Das neutrale Element ist 0, das additive Inverse von α > 0 ist 1 −α.
Übrigens kann man auf IR eine Äquivalenzrelation durch
x ∼y :⇐⇒x mod 1 = y mod 1
(in Worten: x und y sind kongruent modulo 1) einführen. S1 ist dann gewissermaßen die Menge aller Äquivalenzklassen. Jede dieser Klassen hat genau einen Vertreter in [0, 1). In diesem Sinne gilt 1 ∼0 und −ε ∼1 −ε für kleine ε > 0.
Nun kann man auf S1 auch einen Abstand definieren, der auf dem Abstandsbegriff auf der reellen Zahlengeraden basiert: Für α,β∈S1 ist der Abstand d(α, β) zwischen α und β durch die kleinste der drei Zahlen α −β, 1 + α −βund 1 +β−αdefiniert. Beachten Sie, dass
Mit dem Abstandsbegriff weiß man auch, was man unter einem (abgeschlossenen) Intervall IE mit Mittelpunkt α ∈S1 und Radius ε > 0 verstehen soll: Auf der reellen Achse wäre dies einfach IE = [α −ε, α + ε]. Doch dieses kann negative Zahlen oder Zahlen ≥1 enthalten. Doch diese kann man einfach durch ihre Vertreter aus S1 ersetzen. So ist z.B. das Intervall mit Mittelpunkt 0 und Radius ε := 0.1 die Menge I0.1 := [0.0.1]∪[0.9, 1). Um diese unübersichtliche Schreibweise zu verhindern, schreibe ich wie gewohnt I0.1 = [−0.1, 0.1] und denke mir die kleinen negativen Zahlen x mit 1 + x identifiziert. Übrigens gilt allgemein IE = β ∈S1 : d(α, β) < ε. Diese Menge nenne ich ε-Umgebung von α.
Damit wird S1 zu einem sehr vertrauten Objekt. Man kann addieren und man kennt linke und rechte Nachbarn eines Punktes α ∈S1 und kann die Nähe sogar quantifizieren. Man kann die Definition von Grenzwert und Häufungspunkt von reellen Folgen auf Folgen in S1 übertragen, vgl. Def.III.1.7 und Def.III.1.20.
Man kann auch von (irr)ationalen Winkeln sprechen! Wie in Kap. II.1.4 bemerkt, kann man jeden rationalen Winkel beliebig gut durch irrationale approximieren und umgekehrt. Genauer: Die (ir)rationalen Winkel liegen dicht in S1, d.h. für alle α ∈S1 und für alle ε > 0 gibt es es in der ε-Umgebung von α stets (ir)rationale Winkel =α.
In einem weiteren Abstraktionsschritt kann man S1S1 als Fahrradschlauch ansehen. In der Mathematik heißt diese Menge Torus.

2.1.2 Drehungen
Wir können Drehungen einer Ebene um ein Drehzentrum, in das wir den Ursprung eines kar-tesischen Koordinatensystems legen, betrachten. Dann sind Drehungen eindeutig durch ihre Drehwinkel definiert, wenn wir den Drehungen eine Richtung geben. Diese Drehrichtung soll stets die entgegen dem Uhrzeigersinn sein. Wir lösen uns von der Ebene, sondern definieren Drehungen nur mit Hilfe der abstrakten Kreislinie S1.
Definition 2.1. Sei ω E S1 ein Winkel. Die Drehung Rω um den Winkel ω ist eine Abbildung von S1 nach S1, die durch Rω(x) := x ω definiert ist.
Ich denke, die Bezeichnung Drehung ist selbsterklärend. Man spricht auch von Rotation. Jede Drehung ist offensichtlich eine Bijektion. Die Umkehrabbildung (für ω =6 0) von Rω ist R1_ω, die man auch als R_ω bezeichnen kann, wenn man auch negative Vertreter von Winkeln in S1 zulässt. Das ist auch anschaulich sehr sinnvoll, da die Umkehrabbildung einer Drehung um den Winkel ω gegen den Uhrzeigersinn natürlich eine Drehung um ω im Uhrzeigersinn ist — diese ist gerade R_ω.
Eine ganz wesentliche Aussage lautet
Rω1 o Rω2 = Rω1⊕ω2.
Das bedeutet, dass man die Addition von Winkeln auch als Verkettung von Rotationen er¬klären kann. Genauso, wie man in Kap. II.2.3.2 die Addition von Vektoren als Verkettung von Translationen verstanden hat.
Die Menge aller Drehungen ist mit der Verkettung als Verknüpfung wieder eine Gruppe, die irgendwie dieselbe Gruppe wie S1 ist. Mathematisch spricht man von isomorphen Gruppen. In den ¨Ubungen werden wir noch zwei weitere zu S1 isomorphe Gruppen kennenlernen, nämlich die Menge aller 2 x 2-”Dreh-“Matrizen (s. Kap. II.4.4)
(cos(2πα) − sin(2πα)
R(α) = sin(2πα) cos(2πα),
mit der Matrizenmultiplikation als Verknüpfung und die Menge aller komplexen Zahlen vom Betrag Eins2 mit der Multiplikation komplexer Zahlen als Verknüpfung.
2.1.3 Die goldene Drehung
Sie kennen die kleine (ϕ =12(v'5 + 1)) und die große (Φ =12(v'5 − 1)) Goldene Schnitt-Zahl. Ich verweise auf Kap. I.1.2.2, notiere nur
1
Φ = , Φ = ϕ + 1. (2.1)
ϕ
2Diese haben die Darstellung z = cos(2πα) + i sin(2πα) mit α E S1.

Eine Drehung um die kleine Goldene Schnittzahl ϕ ∈S1, im Gradmaß also um 360 •ϕ = 222,5 Grad heißt Goldene Drehung. Zuweilen wird auch die Drehung um den Komplementwinkel 1 −ϕ als Goldene Drehung bezeichnet.
Dass die Goldene Drehung eine herausragende Bedeutung für die spiralförmige, mit Fibonacci-Zahlen zusammenhängende Anordnung der Sonnenblumensamen hat, wird hoffentlich später klar.
2.2 Die Analyse von Zahlen mit Hilfe von Drehungen
Eine Zahl ω ∈[0, 1) wird offensichtlich vollständig durch ihre Drehung Rω charakterisiert. Im Folgenden werden wir diese Idee verfolgen und dabei einerseits auf eine schöne Beziehung zu den Kettenbrüchen von ω stoßen und andererseits auch das spiralförmige Wachstum von Pflanzen modellieren.
2.2.1 Ein von einer Drehung erzeugtes dynamisches System
Jetzt betrachten wir ein durch eine Drehung gegebenes dynamisches System, wie wir es in ähnli¬cher Form schon in Kap. III.1.4.5 im Rahmen eines diskreten Wachstumsmodells kennengelernt haben. Hierdurch ist eine Rekursionsvorschrift
xk+1 = Rω(xk),k =0,1,2,...
bzw.
xk+1 = xk ⊕ω,k = 0,1,2,...
zur Generierung einer Folge (xk)k in S1 gemeint. Diese Folge ist durch den Startwert x0 und natürlich durch die Drehung Rω bzw. ω selbst festgelegt. Wir werden stets x0 := 0 wählen und bezeichnen die Berechnung von xk als k-ten Iterationsschritt.
Mit der Rotation Rω : S1 →S1 ist offensichtlich die reelle, als Translation sehr vertraute Abbildung
rω : IR →IR, x →x + ω
verbunden. Betrachtet man dessen dynamisches System
ξk+1 = rω(ξk),k = 0,1,2,..., ξ0 = 0, so erhält man als explizite Darstellung die arithmetische Folge
ξk = k •ω,k = 0,1,2,....
Jetzt ergibt sich eine ganz einfache explizite Darstellung von xk. Denn es gilt3 (für x0 = 0) xk = ξk mod 1, also
xk=k •ω mod1,k =0,1,2,...,
3Allgemein xk = (k •w + x0) mod1.


Abbildung 2.2: Samen-3-Orbit
der Beweis ist eine sehr gute Übung für vollständige Induktion.
Schreibt man R:= R o R o · · · R (k-mal) für die k-fache Verkettung von R, so gilt
x= R(0),k = 0,1,2,...
Dabei ist Rselbst wieder eine Rotation um den Winkel x= k w mod 1!
Diese Sichtweise führt zu folgender Einsicht: x+entsteht, indem xum den Winkel xgedreht wird, kurz:
x+= x⊕ x, j, k E IN0.
Man nennt die Menge aller Folgenglieder xauch einen Orbit unter R. Wenn wir nur die ersten N + 1 Folgenglieder x0, x1, ..., xbetrachten, so sprechen wir von einem N-Orbit.
Im Hinblick auf die Phyllotaxis gebe ich eine Interpretation des dynamischen Systems durch eine Saatmaschine. Diese bestehe aus einem im Mittelpunkt des Kreises drehbar gelagerten Arm, an dessem Ende Samen in ein kreisförmiges Beet eingesetzt werden können. Nach jeder Drehung um den Winkel w pflanze diese Maschine einen Samen, beginnend in x0 = 0. Nach N Schritten erhalten wir dann einen ”N-Samen-Orbit“.
In Abb. 2.2 sehen Sie eine solche Saatmaschine, die den Samen Nr.3 ”ausspuckt“.
Eine wesentliche Frage ist die nach der ”Verteilung“ des Orbits auf S1. Hierbei ist es ganz entscheidend, ob der Drehwinkel rational oder irrational ist.
2.2.2 Rationaler Drehwinkel
Offensichtlich gilt für rationale Drehwinkel w = mit 0 p < q und teilerfremden natürlichen Zahlen p und q, dass x= x0, d.h. nach q Iterationsschritten befindet man sich wieder im Ausgangspunkt! (Beweis: x= q w mod 1 = p mod 1 = 0). Wir sprechen in naheliegender Weise von einer q-periodischen Folge (x), da jetzt natürlich
x+= xfür alle k

folgt.
Wenn umgekehrt x= x0 = 0, so muss wegen x= q w mod 1 das Produkt q w ganzzahlig,
etwa = p E IN sein, woraus w = folgt.
Beispiel: Eine Drehung um 220 Grad entspricht einer Drehung um w = 11
18. Das kleinste gemein-
same Vielfache von 220 und 360 ist 18 220 = 11 360. Nach 18 Drehungen um diesen Winkel
befindet man sich wieder im Ausgangspunkt. Dabei wurde der Kreis 11-mal umrundet.
Wir fassen dies zusammen:
Satz 2.2. Die folgenden Aussagen sind äquivalent:
· Der Drehwinkel w ist rational, w = (gekürzt).
· Der Orbit besteht aus q verschiedenen Punkten.
· Es gilt x= x0 und q ist mit dieser Eigenschaft minimal.
· Es gilt x+= xfür irgend ein j E IN0 und q ist mit dieser Eigenschaft minimal.
2.2.3 Irrationaler Drehwinkel
Etwas schwieriger ist der Fall eines irrationalen w. Zunächst einmal wissen wir nur, dass alle Orbitpunkte verschieden sein m¨ussen. Hier notieren wir den schönen Satz
Satz 2.3. Ist w E 81 irrational, so liegt die Folge x:= R(x−1), k = 0, 1, 2, ..., dicht in 81, d.h. für alle x E 81 und alle > 0 gibt es ein k mit der Eigenschaft, dass xin der -Umgebung von x liegt.
BEWEIS-Skizze: Dieser geht auf A.L. CAUCHY (1789-1857) zur¨uck. Wenn die Aussage falsch ist, so gibt es eine -Umgebung I eines x E 81, der frei von Orbitpunkten xist. Mache I nun so groß wie möglich, so dass das Innere orbitfrei ist. Dann sind beide Randpunkte von I Orbitpunkte. Das Bild von I unter Rmuss disjunkt zu I sein, ebenfalls ein orbitfreies Inneres und Randpunkte in Gestalt von Orbitpunkten haben. Fährt man so fort, muss man irgendwann ein Intervall erhalten, dessen Inneres mit einem seiner Vorgänger nichtleeren Schnitt hat, weil die Gesamtlänge von 81 ja Eins und der Durchmesser von I positiv ist. Dann liegt ein Randpunkt eines der Intervalle im Inneren eines anderen. Widerspruch!
F¨ur meine Saatmaschine bedeutet dieser Satz, dass die Samen (als Punkte aufgefasst!) nie ¨ubereinanderliegen, sich aber immer näher kommen und dabei die Kreislinie ”ausf¨ullen“. Die Art und Weise, wie dies jedoch geschieht, hängt ganz von w ab. F¨ur den goldenen Winkel werden wir sehen, dass die ”Packung“ f¨ur die Samen optimal ist, weil sie sich so wenig wie möglich “ins Gehege kommen“.

2.2.4 Ein spezieller Orbit
In der für das Folgende wichtigen Abb. 2.3 sehen Sie die ersten 87 Orbitpunkte für den Dreh¬winkel w = 0.529 (ca. 190 Grad). Die Null selbst ist durch ein kleines weißes Quadrat markiert. Zur Verdeutlichung habe ich einige Indizes in die Abbildung eingezeichnet, um die Lage der jeweiligen xk zu kennzeichnen.
Sie sehen 17 aus fünf bis sechs Punkten bestehende ”Inseln“ auf 81. ”Auslöser“ hierfür ist x17 = 0.993, der am dichtesten bei 0 (links davon) liegende Orbitpunkt (ein linker Nachbar). Da ξ17 = 17•w = 8.993, hat der Orbit bis zu diesem ”Zeitpunkt“ den Kreis fast 9-mal umrundet. Daher ist917= 0.529411... eine ”gute“ Näherung von 0.529 ist (Es ist 0.529 −917≤0.0004). Die rechten Nachbarn von x0 = 0 sind nacheinander x2, x19, x36, x53, x70, x87, wobei x87 = 0.023 am dichtesten bei Null liegt.
Hätte man weiteriteriert, so würden die Orbitpunkte erst nach insgesamt 138 Iterationen in etwa gleichmäßig auf 81 verteilt sein. Dabei wäre 81 wegen 138 •w = 73.002 insgesamt 73 Mal umrundet worden, x138 = 0.002 würde sich als rechter Nachbar von x0 = 0 entpuppen. Daher

ist = 0.5289855... eine sehr gute Näherung von ω = 0.529. (Es ist 17338 wegen 0.529−137
1733 883 =
0.0000145 eine noch bessere Näherung als zuvor 197).
Nach 1000 (dies ist der Nenner von ω als gekürzter Bruch) Iterationen würde man wieder beim Ausgangspunkt landen. Ab da wiederholt sich alles. Der Orbit ist 1000-periodisch.
2.2.5 Linke und rechte Nachbarn und rationale Schranken für den Drehwinkel
Wir sehen in dem eben besprochenen Beispiel, dass offensichtlich linke (rechte) Nachbarn obere (untere) rationale Schranken für ω liefern, wobei der Index k von xden Nenner des Bruches liefert. Den Zähler erhalten wir, indem wir den ganzzahligen Anteil von ξ= k •ω heranziehen. Dies geschieht mit Hilfe der ”floor“-Funktion:
Definition 2.4. Sei x ∈IR. Dann ist xdie größte ganze Zahl ≤x.
Dann gilt nämlich
x= k •ω −k •ω
und k •ωist die Anzahl der bisher erfolgten Umläufe.
Bei irrationalem ω kommt man für hinreichend viele Iterationen dem Ausgangspunkt x0 beliebig nahe, man erhält immer dichtere linke und rechte Nachbarn und immer bessere Näherungen für ω durch Brüche mit allerdings immer größerem Nenner. Dies wird jetzt genauer ausgeführt:
Wir nennen xeinen ”linken“ und x einen ”rechten“ Nachbarn von x0 = 0, wenn es keinen ”früheren“ Orbitpunkt xgibt mit x> x, k < `, bzw. 0 < x< x, k < r, gibt. Dabei schauen wir von außen auf den Kreis. Linke Nachbarn sind durch Winkel 1 −ε (∼−ε), rechte durch Winkel ε mit i.A. sehr kleinem ε > 0 charakterisiert.
Nun notieren wir uns alle Indizes ` und r, für die xbzw. x im Vergleich zu ihren Vorgängern dichteste linke bzw. rechte Nachbarn sind. Gleichzeitig notieren wir uns die zugehörigen Um-laufzahlen pund p, wobei pso gewählt wird, als ob xden letzten Umlauf nicht nur ”fast“, sondern vollständig abgeschlossen hat (Man braucht nur ` •ω bzw. r •ω auf eine ganze Zahl zu runden). Offensichtlich gilt
p:= ` •ω+ 1, p := r •ω (2.2)
Es wird sich zeigen, dass sich auf diese Weise alle Konvergenten des zugehörigen Kettenbruchs
als Brüche
p
` ,
wiederfinden lassen. Wie auch immer: Schon jetzt erkennt man, dass die beiden Brüche in (2.3) die irrationale Zahl ω umso besser approximieren, je kleiner die Abstände d(0,x) (=1 −x) bzw. d(0, x) (=x) sind. Bis zum Punkt x wurden p Umläufe geschafft plus dem Winkel d(0, x). Das heißt, dass ω einen Tick größer sein muss als :. . Analog wurden bis zu xnur fast pUmläufe geschafft, es fehlte der Winkel d(x, 0). Daher muss ω einen ”Tick“ kleiner sein als
£ . Wir notieren: 

Satz 2.5. Seien xund xlinke bzw. rechte Nachbarn von x0 = 0 und pund pihre in (2.2)
definierten Umlaufzahlen. Dann gilt
p
< ω < ` .
Merkregel: Rechte Nachbarn liefern untere, linke obere Schranken.
Die Güte der Schranken hängt offensichtlich mit den Abständen d(0, x) und d(0, x) zusammen, die sich aber ganz einfach mit Hilfe von`,p, r, pausdrücken lassen. Man beachte nur, dass x= r · ω − pund x= · ω − b` · ωc =`· ω − p+ 1.
Lemma 2.6. Es gilt
d(x, 0) = p−`· ω,
d(x, 0) = r · ω − p.
Wegen Satz 2.5 nennen wir Zahlen`einen linken Nenner und r einen rechten Nenner von ω und die zugehörigen Umlaufzahlen linke bzw. rechte Zähler von ω, wenn xbzw. xlinke bzw. rechte Nachbarn von x0 sind.
2.2.6 Orbit der goldenen Drehung
Zur Einstimmung schaue man sich Abb. 2.4 an. Hier sehen Sie den 12-Orbit der Goldenen Drehung. In Rot sind alle die Nummern notiert, die im Laufe der Drehung zu linken oder rechten Nachbarn gehören, also linke Nenner`und rechte Nenner r markieren. So ist nach 2 Schritten`= 1 und r = 2, nach einem weiteren Schritt wird`= 1 durch`= 3 abgelöst, nach zwei weiteren Schritten gibt es mit r = 5 einen neuen rechten Nachbarn von x0 = 0, der achte ”Drehschritt“ liefert einen neuen linken Nachbarn`= 8. Die Nummer 13 würde einen neuen rechten Nachbarn liefern (r = 13) — dieser Schritt ist hier nicht ausgeführt.
Fällt Ihnen etwas auf? Ja, alle roten Zahlen sind Fibonacci-Zahlen! In Abb. 2.5 wird analog ein 33-Orbit gezeigt. Der ”Samen“ Nr. 34 würde zu einem neuen rechten Nachbarn.
Wenn Sie die Umläufe mitzählen, kommen Sie im 34. Iterationsschritt auf fast genau 21 Umläufe — die rationale Zahl 21
34 ist eine untere Schranke der Goldenen-Schnittzahl ϕ. Überhaupt ist jede Umlaufzahl wieder eine Fibonacci-Zahl! Vermutung: x, ist für gerade k = 2j ein linker und für ungerade k = 2j + 1 ein rechter Nachbar, die zugehörige Umlaufzahl ist F−1. Dies ist noch eine durch Experimente erhärtete Vermutung, die später im Rahmen der Kettenbruchtheorie bewiesen wird, und führt zusammen mit Satz 2.5 zur Aussage
Mit den positiven (!) Zahlen F2
< ϕ <
F2+1 F2−1,j = 1, 2,... (2.4)
F2
d:= F2+1ϕ −F2,j = 0, 1, 2, ...


Abbildung 2.4: 12-Orbit der Goldenen Drehung


Abbildung 2.5: 33-Orbit der Goldenen Drehung

und
ei := F2i−1 − F2iϕ, j = 1, 2, ....,
erhalten wir die Abstände dieser linken und rechten Nachbarn zu x0. In den Übungen wurde gezeigt, dass diese in jedem j-Schritt auf das (1 − ϕ)-fache abnehmen, was nichts anderes heißt, als dass die Kreisbögen zwischen xF, und x0 durch den nachfolgenden Nachbarn xF,+2 golden geteilt wird.
2.2.7 Aufdatierung der linken und rechten Nenner und Zähler
Zu jedem N eines N-Orbits von Rω gibt es offensichtlich sog. aktuelle linke x£ und rechte Nachbarn xr von x0 = 0. Die Indizes (linke und rechte Nenner genannt)`und r hängen von N ab und sind dadurch festgelegt, dass für k < N kein xk dichter bei x0 = 0 liegt als x£ und xr. Wenn die Iteration fortschreitet, d.h. N wächst, wird xN irgendwann zu einem neuen rechten oder linken Nachbarn von x0 = 0. Dann kann xr = xN und r = N oder x£ = xN und`= N als neue aktuelle Werte gesetzt werden. Wir sagen, dass`oder r ”aufdatiert“ wird.
In dem Beispiel der Abb. 2.3 sind für 19 < N < 35 die aktuellen Nachbarn durch`= 17 und r = 19 gegeben. Bei wachsendem N wird nach und nach r = 36, r = 53, r = 70, r = 87. Für r = 19 ist die Umlaufzahl pr = 10. Diese erhöht sich bei jedem neuen rechten Nachbarn um pe = p17 = 9, die Umlaufzahl von x£. Schließlich ist p87 = 46 und später p138 = 73.
Im Folgenden werden wir von dieser Beobachtung ausgehend eine ganz einfache rekursive Ge-setzmäßigkeit feststellen, mit der man die nächsten Indizes rechter und linker Nachbarn (also die neuen Nenner) sowie ihre Umlaufzahlen (also die neuen Zähler) berechnen kann.
Wir behaupten, dass wir, ausgehend von aktuellen linken und rechten Nachbarn x£ und xr, als nächsten neuen linken oder rechten Nachbarn xe+r mit neuer Umlaufzahl p£ + pr erhalten, der nächste Nenner ist also`+ r, der nächste Zähler ist p£ + pr. Dies entspricht der Fibonacci-Rekursion!
Dies sieht man sofort mit Hilfe von
xe+r = xg ® xr
ein. Dieses erlaubt zwei Deutungen: xe+r entsteht aus x£ durch ”Vorwärtsdrehung“ um den (i.A. kleinen) Winkel xr, aber ebenso durch ”Rückwärtsdrehung“ von xr um den durch 1 − xe gegebenen (ebenfalls i.A. kleinen) Winkel.
In beiden Deutungen erkennt man, dass xe+r näher an der Null liegen muss als x£ und xr. Ist xe+r wieder ein rechter Nachbar von x0, so übernimmt xe+r die Rolle von xr, das neue r ist gleich`+ r. Wir sprechen von einem Wechselschritt, wenn xe+r auf der anderen Seite von x0 liegt als sein unmittelbarer Vorgänger xmax(2,r), wenn also xe+r ein linker Nachbar im Falle r >`und ein rechter im Falle`> r wird. Im ersten Fall wird p£, im zweiten Fall pr durch pe+r = pe + pr ersetzt, was sofort aus (£ + r) · ω =`· ω + r · ω folgt.
Geometrisch können wir xe+r ganz einfach konstruieren. Hierzu nehme man r >`an. Man trage von xr in Richtung x0 = 0 (also in Uhrzeigersinn) einen Kreisbogen ab, der die Länge


Abbildung 2.6: Nennerschritte
1 − xdes von x0 nach xreichenden Kreisbogens hat. x+ist dann der Endpunkt dieses Kreisbogens. Diese Konstruktion ist besonders einfach, wenn wir den Kreis begradigen, s. die farbige Abb. 2.6.
Hier hat eine schwarze Strecke die Länge α:= d(0, x), die blaue die (größere) Länge α:= d(0, x). Die schwarze Strecke passt dreimal in die blaue, so dass der vierte nachfolgende Nennerschritt ein Wechselschritt ist. x+(in der Abbildung mit ` + r bezeichnet) entsteht, indem xum den Winkel α< 0 zurück gedreht wird. Mit dieser geometrischen Veranschauli¬chung haben wir der durch den ”Rechteckalgorithmus“ für Kettenbrüche (s. Kap. 3.3.2) schon vorgegriffen.
αwerden wir später wegen Lemma 2.6 als Fehler 2.Art der Annäherung von ω durch den
Bruch r
r
Wechselschritt vorliegt. Vergleiche mit den Zahlen dund efür ω = ϕ, für die wir Formeln
hergeleitet haben.
Die obigen Ausführungen haben ergeben, dass der auf ` und r folgende Nenner ` + r mit Zähler p+pist. Die Frage ist nur, ob es sich um rechte oder linke Nenner (Zähler) handelt. Das kann man auch ohne große Rechnung klären: Wenn
p+ p< ω, ` + r
handelt es sich um einen rechten Nenner (Zähler). Wenn
p+ p
ω <  ` + r ,
um einen linken.
Wir betrachten noch einmal zur Erläuterung Abb. 2.3, also den Fall ω = 0.529. Dort hatten wir schon erkannt, dass ` := 17 ein linker Nenner mit Zähler p:= 9 ist. In der Tat gilt
9
ω = 0.529 < 17

Der Vorgänger-Nenner ist 2 mit Zähler 1 (beide sind rechte), der Bruch21ist eine untere Schranke von ω. Der auf 17 folgende Nenner ist ` + r = 17 + 2 = 19, ein rechter Nenner. Der zugehörige Zähler ist p + pr = 9 + 1 = 10. Es folgen eine Reihe von Schritten (insgesamt 8), die jeweils zu rechten Nennern und den Einschließungen

37
70 < ··· <

73
138 < ω


ω < 82
155 = 0.52903...
mit linkem Nenner 155 und Zähler 82 führt.
2.2.8 Zusammenhang mit Kettenbrüchen
Natürlich muss sich rechts und links nicht dauernd abwechseln4. Vielmehr können mehrere rechte Nenner aufeinander folgen, bevor wieder ein linker auftritt. Unter Benutzung der späte¬ren Kettenbruchnotationen (Konvergente und Koeffizient des Kettenbruchs, s. Def. 3.15) notieren wir (kann bei der ersten Durcharbeit überlesen werden):
Satz 2.7. Seien ` und r aktuelle linke und rechte Nenner mit ` > r. Der nächste Nenner ` + r sei ein rechter Nenner von ω, so dass ein Wechselschritt vorliegt. Dann istp`` eine Konvergente von ω. Wenn auf ` insgesamt a E IN rechte Nenner bis zum nächsten Wechselschritt folgen, so
ist a ein Koeffizient des Kettenbruchs von ω. Die zugehörige Konvergente ist pr+a·p`
r+a·` .
Analoges gilt, wenn r > ` und der nächste Nenner ` + r ein linker Nenner von ω ist.
2.2.9 Nenner-Algorithmus
Wir nennen den Übergang von einem Nenner von ω zum nächsten einen Nennerschritt und unterscheiden einen linken und einen rechten Nennerschritt, je nachdem, ob der neue Nenner ein linker oder ein rechter Nenner ist. Weiterhin sprechen wir von einem Wechselschritt, wenn einem linken Nenner ein rechter Nenner folgt oder umgekehrt. Dann besagt Satz 2.7, dass die Koeffizienten des Kettenbruchs von ω gerade durch die Anzahl der Nennerschritte bis zu einem Wechselschritt gegeben sind und dass die Quotienten aus Zähler und Nenner von ω vor einem Wechselschritt gerade die Konvergenten des Kettenbruchs sind.
Den bisher angedeuteten Algorithmus, den wir im Folgenden ”Nenner-Algorithmus“ nennen, kann man rekursiv formalisieren, wobei besonderes Augenmerk auf die Anzahl der Nenner-schritte bis zu einem Wechselschritt gelegt wird, da diese die Koeffizienten des Kettenbruchs ergeben:
4Das ist nur für den Goldenen Winkel der Fall, wie wir sehen werden!

Dazu beginne man (k=1) mit dem Nenner q = 1. Mit Zähler p = 0 ist dies ein rechter Nenner. Es gilt ja 0 = 01 < w. Setzt man p = 1, kann man q = 1 auch als linken Nenner auffassen (w < 11), d.h. x1 ist sowohl linker als auch rechter Nachbar von x0. Der nächste Nenner ist q = 2. Es gibt zwei Möglichkeiten: Entweder ist 2w > 1 oder es ist 2w < 1. Im ersten Fall wurde S1 einmal umlaufen, q = 2 ist rechter Nenner (mit p = 1 als Zähler), es gilt 21 < w. Im zweiten Fall ist q = 2 linker Nenner (mit p = 1 als Zähler), es gilt w < 21. In diesem Fall iterieren wir bis zur Stufe q, nach der der erste Wechselschritt erfolgt, d.h. für die
1
q + 1 q
gilt5. Nach Satz 2.7 ist 1q eine (die erste) Konvergente von w, q ist der erste Koeffizient a1 des Kettenbruchs. Die erste Konvergente nennen wir p1
q1 , q1 nennen wir den ersten Konvergenten-nenner (Wir nummerieren jetzt anders!). Damit ist der erste Wechselschritt beschrieben. Für die nachfolgende Rekursion setzen wir p0 := 0, q0 := 1 und nennen p0 0 formal ebenfalls eine q0 1
Konvergente.
Sei der k-te Wechselschritt erfolgt6. Der letzte (Konvergenten-) Nenner sei qk, der letzte Zähler pk, die vorletzten Nenner qk−1 und Zähler pk−1. (Sind die einen links, so sind die anderen rechts
und umgekehrt). Dass ein Wechselschritt vorliegt, bedeutet, dass pk−1 auf einer anderen Seite
qk−1
als pk, aber auf derselben Seite von w liegt wie pk+pk−1
qk qk+qk−1 ,.
Nun mögen ak+1 Nennerschritte durchgeführt werden, bevor wieder ein Wechselschritt erfolgt,
d.h. es lege
apk + pk−1
aqk + qk−1
für 1 ≤ a ≤ ak+1 auf einer anderen Seite von w als
(ak+1 + 1)pk + pk−1
.
(ak+1 + 1)qk + qk−1
Dann ist
qk+1 := ak+1qk + qk−1
ein Konvergentennenner, der ”entgegengesetztes Vorzeichen“ zu qk hat (d.h.: Ist der eine links, ist der andere rechts) mit dem Zähler
pk+1 = ak+1pk + pk−1.
Wir fassen den Algorithmus in einer Weise zusammen, die nicht mehr Gebrauch macht von Rotationen, sondern nur noch von Abfragen, ob gewisse Brüche kleiner oder größer als w sind. Dieser Algorithmus liefert offensichtlich rationale Approximationen der irrationalen Zahl w.
5Man kann q auch als die größte natürliche Zahl charakterisieren, die kleiner als 1ω ist, in Symbolen q = bω1i, vgl. Def. 2.4 und Lemma 3.13. Wenn man ein Rechteck mit den Kantenlängen 1 und ω betrachtet, so ist q die Anzahl der Quadrate mit Länge ω, die noch gerade in das Rechteck hineinpassen.
6Eben wurde k = 1 beschrieben.

2.2.10 Kurzform des Nenner-Algorithmus
Gegeben sei ein irrationales ω ∈ (0, 1).
· Sei a1 ∈ IN durch
1
a1 + 1 < ω <
definiert. Setze p0 := 0, p1 := 1, q0 := 1, q1 := a1.
· Seien ak,pk−1, pk, qk−1, qk für k ≥ 1 definiert mit
pk−1 pk−1 + pk  <
qk−1 qk−1 + qk pk
< ω <
qk

(dann ist qk ein linker Nenner) oder
pk pk−1 + pk
< ω <
qk qk−1 + qk pk−1< qk−1
(dann ist qk ein rechter Nenner). Dann bestimme das kleinste ak+1 ∈ IN so, dass


oder
pk−1 + (ak+1 + 1)pk pk−1 + ak+1pk
< ω <
qk−1 +(ak+1 + 1)qk qk−1 + ak+1qk
und setze
pk+1 := ak+1pk + pk−1, qk+1 := ak+1qk + qk−1. (2.5)
Die Bestimmung von ak+1, pk+1, qk+1 kann auch so beschrieben werden:
Setze pk,0 := pk, qk,0 := qk und
pk,j := pk−1 + pk,j−1, qk,j := qk−1 + qk,j−1,
solange pk,j
auf der selben Seite von ω liegt wie pk−1 k−1 . Das größte j mit dieser Eigenschaft ist
qk,j q
gerade ak+1. Setze wieder
pk+1 := ak+1pk + pk−1, qk+1 := ak+1qk + qk−1.
Bevor wir die Beziehung dieses Algorithmus zu Kettenbrüchen herstellen, bemerken wir, dass wir die Begiffe k-te Konvergente pk
qk und k-ter Koeffizent ak, die wir in Satz 2.7 verwendeten, genauso gut durch den Algorithmus, der diese liefert, hätten definieren können. Dass wir dies nicht tun, liegt daran, dass diese Begriffe mit Kettenbrüchen verbunden sind, die wir erst noch einführen. Dann werden diese Begriffe definiert werden und Sie werden sofort sehen, dass volle Übereinstimmung besteht, d.h., dass Satz 2.7 gilt.

2.2.11 Ein Beispiel
Eine Pr¨asenzaufgabe der Vorlesung lautete:
Schreiben Sie an jeden Punkt des N-Orbits (N = 25) von Rω in Abb. 2.7 den zugehörigen Index k von xk, k = 1,2, ...25, markieren Sie alle linken und rechten Nachbarn (bzw. deren Indizes ` und r) sowie die zugehörigen Umlaufzahlen p und pr und geben Sie damit Schranken
p`
< ω < `
für den Drehwinkel ω an. Bestimmen Sie ferner die Wechselschritte und ”unterstreichen“ Sie die jeweiligen Brüche vor den Wechselschritten (die sog. Konvergenten) und die Anzahl der ”Nennerschritte“ zwischen zwei Wechselschritten
Hier ist die Lösung, die auch einen Zusammenhang zu den Kettenbrüchen aufzeigt:
Der dritte Punkt unterhalb der Null erhält den Index 1. Mit den Augen geschätzt ist der Drehwinkel damit etwas größer als 0.75. Beachten Sie, dass gegen den Uhrzeigersinn gedreht wird.
x1 ist sowohl ein linker als auch ein rechter Nachbar, man erhält die triviale Einschließung
01 < ω < 11.
x2 ist der 5te Punkt unterhalb der Null. Er ist ein neuer rechter Nachbar (r = 2) mit Umlaufzahl pr = 1. Jetzt lautet die aktuelle Einschließung
2 1<ω< 11.
Diesen Schritt muss man als Wechselschritt auffassen, der Bruch des Vorgängers x1, also11 ist die erste Konvergente von ω, der zugehörige Koeffizient ist a1 = 1, da nur ein Schritt benötigt wurde.
Es folgen 6 rechte Schritte r = 3, 4, 5, 6, 7, 8 mit Umlaufzahlen 2, 3, 4, 5, 6, 7, bevor der siebte Schritt mit ` = 9 und Umlaufzahl 8 ein Wechselschritt ist. Wir erhalten die Einschließung
78 < ω <
Der letzte Bruch vor diesem Wechselschritt ist78 eine weitere Konvergente von ω mit Koeffizient a2 = 7, weil 7 Schritte bis zum Wechselschritt benötigt wurden.
Der nächste Kandidat für einen neuen Nachbarn hat den Index (Nenner) `+r = 9+8 = 17 mit Umlaufzahl (Zähler) p`+r = p17 = pL? +pr = 8 + 7 = 15. Dieser ist ein rechter Nachbar (r = 17), wir erhalten die Einschließung (pr = 15)
15
17 < ω <


Abbildung 2.7: 25-Orbit mit w=?
33


Rechnen Sie nach!
Beachten Sie die Rekursionsformeln (siehe (2.5))
pk = akpk_1 +pk_2, qk = akqk_1 +qk_2,k=2,3,4,
wenn man p0 := 0, q0 := 1 setzt. Denn:    
7 = p2 = a2p1 + p0 = 7 · 1 + 0, 8 = q2 = a2q1 + q0 = 7 · 1 + 1 = 8,
8 = p3 = a3p2 + p1 = 1 · 7 + 1, 9 = q3 = a3q2 + q1 = 1 · 8 + 1 = 9,
31 = p4 = a4p3 + p2 = 3 · 8 + 7, 35 = q4 = a4q3 + q2 = 3 · 9 + 1 = 8.
2.2.12 Nenneralgorithmus für Goldene Drehung
Kann man jetzt schon beweisen, dass alle Kettenbruchkoeffizienten ak = 1 sind, d.h., dass jeder Nennerschritt ein Wechselschritt ist, wie in Kap. 2.2.6 vermutet? Ja – wenn man die Schrankenaussage (2.4) als bewiesen ansieht. Dann ist ja jeder Nennerschritt ein Wechselschritt und die vertrauten Fibonacci-Rekursionen Fk = Fk_1 + Fk_2 sind genau die Rekursionen, die der Aufdatierung von Nennern und Zählern zu Grunde liegen.


Kapitel 3
Kettenbrüche
3.1 Einführung
Sie können zunächst alles Bisherige vergessen und ein wenig elementare Zahlentheorie betreiben. Es geht um (unkürzbare) Brüchepq mit p E IN0, q E IN bzw. um die Approximation (Annähe¬rung) irgendwelcher, auch irrationaler Zahlen durch diese. So ist z.B. 227 = 3.14285714 eine erstaunlich gute Näherung für die Kreiszahl π. Auf diese Näherung kommt man mit Hilfe von Kettenbrüchen. Die Dezimalbruchdarstellung von π hilft hier wenig.
Dabei interessieren insbesondere Näherungsbrüche mit relativ kleinem Nenner oder mit einem gewissen Höchstnenner Q.
So kann man zu vorgegebenem Höchstnenner Q nach demjenigen Bruch p0
q0 fragen, für den einerseits q0 Q und andererseits jeder andere Bruchpq mit q Q eine gegebene reelle Zahl ω schlechter annähert:
p0
ω −
q0
falls nur q Q und p0
q0 =6 pq.
~ ~~~ heißt Fehler 1.Art. Als Fehler 2.Art bezeichnet man
Der Näherungsfehler ~ω − p0
q0
|q0ω − p0|,
der mit dem Nenner multiplizierte Fehler 1.Art.
Man sucht also zu einem gegebenen Höchstnenner Q und einer Zahl ω diejenigen Brüche, die die Fehler 1. Art bzw. 2. Art minimieren. Beide Fehler werden z.B. für ω = π und Q = 105 durch227 minimiert.
Für eine Näherung p0
q0 für ω kann man zunächst als Höchstnenner Q := q0 setzen und fordern, dass es keine besseren Näherungenpq mit q q0 gibt:
Definition 3.1. p0
q0 mit q0 > 0 heißt beste Approximation erster (bzw. zweiter) Art von

ω > 0 genau dann, wenn für q ≤q0 und =o

~ ~< ω −pI
ql,
q0ω −p0< qω −p.


q0ω −p0< qω −p,
falls nur q ≤q0 und  =°
° . Nun diviediere man diese Ungleichung durch q0 und nutze °1 ≤1
aus.
Die Umkehrung ist nicht richtig. Siehe KHINTCHINE.
Wenn wir an den Nenneralgorithmus in Kap. 2 denken und hier insbesondere an Lemma 2.6, so sehen wir, dass die Abstände eines linken bzw. rechten Nachbarn von x0 = 0 gerade die Fehler 2. Art sind, mit denen ω durch die zugehörigen Brüche ` bzw. r angenähert werden. Ich nehme an, dass ` und r aktuelle linke bzw. rechte Nenner von ω ∈(0, 1) zu einem ”Zeitpunkt“ Q ≥max(e, r) sind. In Bezug auf den Fehler 2. Art ist der kleinere der beiden Abstände zu nehmen. Es ist offensichtlich, dass andere Brüche mit einem kleineren Nenner als Q für eine bessere Approximation in Bezug auf den Fehler 2.Art nicht in Frage kommen. Der nächste in Frage kommende Nenner ist ` + r. Also können sogar alle Brüche mit einem Nenner < ` + r keine besseren Approximationen in Bezug auf den Fehler 2.Art liefern. Immer dann, wenn der Übergang (Nennerschritt) von q := max(e, r) zu ` + r ein Wechselschritt ist, muss also  beste Approximation 2.Art sein, sogar in Bezug auf einen Höchstnenner Q < ` + r (wobei p der zu q gehörende Zähler ist). In der schon vorweggenommenen Konvergenten-Sprechweise des letzten Kapitels ist also jede Konvergente von ω beste Approximation 2. Art (und damit nach Satz 3.2 auch beste Approximation 1.Art). Einige, aber nicht alle Brüche zu irgendwelchen Nachbarn von x0 = 0 sind beste Approximationen 1.Art.
Damit haben wir mit dem Nenneralgorithmus eine rechnerische Möglichkeit zur Lösung obiger Approximationsaufgaben. Wir werden aber sehen, dass es effizientere Methoden gibt. Dennoch habe ich mit dem Nenneralgorithmus begonnen, weil der Rotationsaspekt für die Phyllotaxis zentral ist.
Wegen ihrer Bedeutung auch für die Kettenbrüche werde ich die Fehler 2. Art der Konvergenten von ω mit
d:= qω −p, k = 1, 2, 3, ... (3.1)
benennen und noch einmal erwähnen, dass diese gerade die Abstände d(xk, 0) der Nachbarn von x0 = 0 vor einem Wechselschritt sind.

3.2 Farey-Folgen
3.2.1 Farey-Folge und Medianten-Addition von Brüchen
Man gebe sich ein n ∈ IN vor und betrachte alle (gekürzten) Brüche in [0, 1] mit Nenner ≤ n (Höchstnenner n). Diese ordne man der Größe nach an, beginnend bei01, endend bei11. Die (endliche) Folge nennt man Farey1-Folge F. Für n = 5 haben wir z.B.
11. (3.2)


1  hat. Z.B. gilt 4 3 1
5 − 4 = 20.
Definition 3.3. Zwei Brüche 1
1 und 2
2 heißen Farey-benachbart, wenn
  p1 p2  = 1
       .
Es folgt sofort (Bruchrechnung!)  q1 q2   q1q2
sind Farey-benachbart, wenn |p1q2 − p2q1| = 1.
Dass obige Beobachtung kein Zufall ist, ist nicht so unmittelbar einsehbar. Hier hilft der auch für sich sehr interessante Medianten-Operator, der eine ganz spezielle, bei Schülern sicherlich beliebte Form der Addition von Brüchen vornimmt:

Definition 3.5. Seien 1
1

zwei Brüche. dann heißt

p1 p2
⊕
q1 q2 p1 + p2
:=
q1 + q2
ihr Mediant2.
Wenn man beginnend bei den Brüchen01 und11 fortlaufend Medianten benachbarter Brüche bilden, erhalten wir


etc. Auf diese Weise erhalten wir alle Brüche von F5 in (3.2). Man sieht darüber hinaus, dass jeder Bruch in (3.2), der nicht am Rande liegt, der Mediant seiner Nachbarn ist und dass je zwei Nachbarn von F5 Farey-benachbart sind!
1JOHN FAREY, 1766-1826
2Pennäler-Addition von Brüchen

zwei Farey-benachbarte Brüche und p3
= p1+p2 ihre Mediant.
q3 q1+q2
Der BEWEIS ergibt sich durch einfache Bruchrechnung:
p1 + p2 p1
=
q1 p2q1 − p1q2
q1 + q2   .
(q1 + q2)q1
Da p1
q1 und p2
q2 Farey-benachbart sind, ist der Zähler Eins.
Jetzt ist offensichtlich, dass der obige Algorithmus, der bei den Brüchen 01 und 11 beginnend fortlaufend Medianten berechnet, eine Folge Farey-benachbarter Brüche liefert, wenn man sie der Größe nach anordnet.
Jetzt haben wir fast den


r
−
s p
q = 1
. qs
bewiesen. Es muss nur noch gewiss sein, dass man jeden Bruch von Fn auf diese Weise der fortwährenden Mediantenbildung erhält.
Hierzu bietet sich ein BEWEIS mit vollständiger Induktion nach n an:
F1 besteht nur aus den beiden trivialen Brüchen 01 und 11. Diese sind Farey-benachbart. Nehmen wir nun an, dass alle Brüche von Fn Farey-benachbart sind. Zu zeigen ist, dass sich die Brüche aus Fn+1, die noch nicht in Fn erfasst sind, also diejenigen mit Nenner n + 1, als Medianten zweier Nachbar aus Fn (die wegen der Induktionsannahme wieder Farey-benachbart sind) ergeben, so dass Lemma 3.6 angewendet werden kann.
Dass dem so ist, besagt das nachfolgende Lemma 3.8.
Lemma 3.8. Seien p1 und p2
q1 q2
diesen beiden Brüchen einen Nenner q1 + q2. Oder anders ausgedrückt: Der Bruch mit dem kleinsten Nenner, der zwischen diesen beiden Brüchen liegt, ist ihr Mediant.
BEWEIS: Sei ohne Einschränkung p1
q1 < pq < p2
q2 . Dann gilt wegen der Farey-Nachbarschaft
p2q1 − p1q2 = 1. (3.3)
Ferner folgt aus p1
q1 < p q, dass
pq1 − p1q 1 (3.4)

und aus p
q

< p2
q2 , dass

p2q − pq2 1. (3.5)

Wenn wir die Ungleichung (3.4) mit q2 und die Ungleichung (3.5) mit q1 multiplizieren und diese dann entstehenden beiden Ungleichungen
pq1q2 − p1qq2≥q2, p2qq1 − pq1q2≥q1 (3.6)
addieren, hebt sich der Term pq1q2 weg, und es bleibt
q(p2q1 − p1q2)≥q1 + q2.
Aus (3.3) folgt jetzt die Behauptung.
In Aufgabe Ü15 tauchte die Frage auf, ob ω = 5171 der einzige Bruch mit einem Nenner ≤ 60 ist, der 256 < ω < 361 erfüllt. Jetzt wissen wir sogar, dass der Bruch mit nächstkleinerem Nenner
26 ⊕ 11 557 = 83 16 ist, dass es sogar keinen weiteren Bruch mit dieser Eigenschaft gibt, der einen
Nenner < 83 hat!
In Bezug auf den Nenneralgorithmus aus Kap. 2 ist uns der Mediantenoperator durchaus ver¬traut: Ein Nennerschritt macht aus den linken bzw. rechten Nachbarn xbzw. x mit Brüchen
e
p+ p pp
= ` ⊕ .
` + r r
Ausführlicheres findet man in Kap. 3.2.3.
3.2.2 Fibonacci-Zahlen und Fareyfolgen
Auf den ersten Blick überhaupt nicht einsichtig ist die sogenannte Simpson-Identität (auch Cassini’s Identität3):
Satz 3.9. Es gilt für alle n ≥ 1
F−1F+1 − F2= (−1)
Eine Beweis-möglichkeit ist die der vollständigen Induktion (Übungen). Wir werden jetzt einen Beweis geben, der ausnutzt, dass diese Eigenschaft mit Fareyfolgen zu tun hat. Wir betrachten die Brüche r := n−1
n . Von diesen wissen wir bereits, dass sie gegen die kleine Goldene-Schnitt-Zahl ϕ konvergieren. Wenn wir genau hinschauen (Beweis von Satz 2.4), erkennen wir, dass die Konvergenz alternierend ist4, man erhält abwechselnd untere und obere Schranken,
r1 < r3 < r5 < · · · < ϕ < · · · < r6 < r4 < r2.
In der neuen Sprechweise sehen wir
3wiederum ein Spezialfall der sog. Catalan-Identität Fn2 − Fn−rFn+r = (−1)n−rFr2 genannt. 4Dies wird sich als ein Spezialfall im Rahmen der Kettenbrüche herausstellen, siehe Satz 3.19.

Lemma 3.10. rn+1 ist Mediant von rn und rn−1.
BEWEIS: rn−1 EID rn = Fn−2 EID Fn−1 Fn−1 = Fn
Fn+1 = rn+1,
   Fn  
wie man sofort unter Ausnutzung der Fibonacci-Rekursion sieht.
Wir wollen jetzt zeigen, dass die Simpson-Identität in Satz 3.9 aus Lemma 3.6 und diesem Lemma 3.10 folgt.
Hierzu zeigen wir durch Induktion, dass zwei aufeinanderfolgende Quotienten rn+1 und rn für alle n ∈ IN Farey-benachbart sind. Für n = 1 ist dies richtig (r1 =01 und r2 = 11 sind Farey-benachbart). Wenn rn−1 und rn Farey-benachbart sind, so auch wegen Lemma 3.10 rn+1 und rn−1 bzw. rn+1 und rn.
Jetzt folgt unsere Behauptung aus Lemma 3.4. Denn es gilt für gerades n


Bildet man die Differenz rn − rn+1 der beiden Brüche, so lautet deren Zähler Fn−1Fn+1 −Fn2
und ist gleich 1. Für ungerade n erhält man analog -1. .
Später werden wir sehen, dass Satz 3.9 ein Spezialfall im Rahmen der Kettenbrüche ist, siehe (3.10).
Es gibt einen schönen geometrischen Trugschluss, der auf der Simpson-Identität beruht (Übun¬gen).
3.2.3 Beziehung zum Nenner-Algorithmus
Sehen Sie, wo im Nenneralgorithmus ein Mediant von zwei Brüchen ins Spiel kam?
Dort hatten wir zwei aufeinanderfolgende Nenner r und`einer irrationalen Zahl ω mit Zählern pr und p` betrachtet. Dies führte zu einer Einschließung von ω durch (2.5),
p`
< ω < ` .
Es wurde gezeigt, dass der nachfolgende Nenner stets`+ r mit Zähler pe + pr ist, der — wenn es sich um einen rechten (linken) Nenner handelt — zu einer unteren (oberen) Schranke
p` + pr
< (>)ω` +r
von ω führt. Die neue Schranke ist offensichtlich Mediant der Brüche pr
r und p£` !

Ein Nennerschritt des Nenner-Algorithmus ist also nichts anderes als ein Mediantenschritt! Mehr noch: Der Nenner-Algorithmus startet mit der trivialen Inklusion
01 < ω <
und kann als eine Folge von Medianten-Berechnungen aufgefasst werden, wobei jeweis durch die Abfrage
p+ p< (>)ω ` + r
eine Schranke von ω durch den Medianten abgelöst wird.
Mit dieser Einsicht kann man auch völlig losgelöst von Drehungen von einem Mediantenal-gorithmus zur Annäherung von ω durch Brüche reden.
Jetzt haben wir zusätzlich noch eine Erkenntnis über die Güte des Fehler 1. Art erhalten:
Satz 3.11. Wenn es im Zuge des Medianten- bzw. Nenneralgorithmus zu einer Einschließung des Typs
p
< ω < `
kommt, so hat das Einschließungsintervall die Länge1.
Die Eigenschaft eines Bruches, beste Approximierende 1. oder 2. Art zu sein, bleibt bis zu Nennern Q < r + ` erhalten..
BEWEIS: folgt aus der Farey-Nachbarschaft der beiden Schranken.
Dass vor einem Wechselschritt auch der Fehler 2. Art minimiert wird, haben wir schon in der Einführung zu diesem Kapitel (Kap. 3.1) gesehen.
Ich bemerke noch einmal, dass alle diese Erkenntnisse ohne Gebrauch von Kettenbrüchen ge-wonnen wurden. Das ändert sich jetzt.
3.3 Kettenbrüche
3.3.1 Einführung
Definition 3.12. Ein endlicher Kettenbruch5 der Ordnung k mit Koeffizienten a∈ IN,j = 1, 2, ...k ist die Darstellung

a2 + a3 + ...
+

einer rationalen Zahl pk
qk E (0,1).
Man sagt, dass w E (0, 1) durch einen unendlichen Kettenbruch
1
w =
 1
a1 +
 1
a2 + a3 + ...
+ ak + ...
darstellbar ist, wenn die endlichen Kettenbrüche k-ter Ordung gegen w konvergiert.
Ich beschränke mich hier auf Zahlen 0 < w < 1, um die Beziehung zu den Drehungen zu betonen. Durch ein vorgeschaltetes a0 E IN0 kann man sofort auch Darstellungen beliebiger positiver Zahlen erfassen.
Diese Form der Kettenbrüche wird zuweilen auch einfach genannt, weil es auch allgemeinere Kettenbrüche der Form
b1
w =
a1 +
a2 + a3 + ...
+ ak + ...
gibt. Diese erlauben z.B. die von L.EuLER gefundene Darstellung
2
e − 1 = 1 +  
 2 + 3
   4

3 + 4 + ...
+

k + 1
k + 1 + ...

Naheliegend ist der Vergleich mit Dezimalbrüchen
w = 0.a1a2 ···ak ···
mit Ziffern ak E {0, 1, 2, ..., 9}, die ja über
w = X∞
k=1 ak10−k

mit unendlichen Reihen zusammenhängen.
Doch zuvor werden wir eine neue Notation einführen, weil die Kettenbruch-Schreibweise zu mühsam ist: Für den endlichen Kettenbruch in (3.7) schreiben wir kurz [a1, a2, ..., ak], für den unendlichen Kettenbruch entsprechend [a1, a2, ..., ak, ....].
Um auch Kettenbrüche mit beliebigen positiven Werten zu erfassen, wird von Zahlen > 1 einfach der ganzzahlige Anteil abgezogen. Wird dieser mit a0 := Lω] bezeichnet, so schreiben wir ω = [a0; a1, a2, ....].
3.3.2 Geometrische Veranschaulichung (”Rechteckalgorithmus“)
Ich bin mir nicht sicher, ob das Folgende Allgemeingut unter ”Kettenbruchexperten“ ist. Ich bin auf diesen Punkt durch irgendeine Internetseite gestoßen. Auf diese Weise erhalten wir eine sehr einfache, und wie ich meine auch schöne geometrische Konstruktion der Kettenbruchent-wicklung, aber auch eine Veranschaulichung des Euklidischen Algorithmus zur Berechnung von ggT (m, n) zweier natürlicher Zahlen m und n.
Wir betrachten ein Rechteck R1 der Längen x1 := ω und x0 := 1. Dann ist a1 die Anzahl der Quadrate mit Kantenlänge ω, die in das Rechteck R1 hineinpassen. Was nachbleibt, ist ein Rechteck R2 mit den Längen x2 := 1−a1ω und ω, wobei man in x2 gerade den Fehler 2.Art der 1.Konvergente p1
q1 = a1 , siehe (3.1), erkennt. Dann ist a2 die Anzahl der Quadrate der Länge x2, die in dieses Rechteck R2 passen. Nun setze x3 := x1 − a2x2, usw. Diesen Algorithmus nenne ich Rechteckalgorithmus. Er liefert offensichtlich die Koeffizienten des Kettenbruchs, aber nicht direkt — wie der Nenneralgorithmus — die Konvergenten(nenner). Eine ganz ähnliche geometrische Überlegung wurde beim Nenneralgorithmus angestellt.
Man kann leicht zeigen, dass x3 = d2 und allgemein die Kantenlängen des Rechtecks Rk gerade die Fehler 2. Art der (k − 1)-ten und (k − 2)-ten Konvergente ist, ganz in Übereinstimmung mit der Nenneralgorithmus-Erkenntnis, dass ak die Anzahl der Intervalle der Länge dk−1 sind, die noch in ein Intervall der Länge dk−2 ”hineinpassen“.
Diese Beobachtung hat besondere Bedeutung für die ”optimale Packung“ der Samen bei der Saatmaschine bei einem goldenen Drehwinkel ω = ϕ (siehe Kap. 3.3.10).
Ist ω = ϕ die kleine Goldene Schnittzahl, so ist das Ausgangsrechteck ein goldenes Rechteck, das verbleibende Rechteck nach Abtrennen von einem Quadrat mit Kantenlänge ϕ ist wieder golden, da 1−ϕ
ϕ = ϕ. Daher sind alle Kettenbruchkoeffizienten von ϕ gleich 1.
Wir müssen das Folgende daraufhin überprüfen, ob diese Deutung wirklich so richtig ist. Aber schon jetzt kann man sagen: Wenn der Rechteckalgorithmus nach endlich vielen Schritten bei einem goldenen Rechteck landet, so ist die asymptotische Kettenbruchentwicklung gleich der von ϕ. Das ist wichtig für die Bedeutung von Lukasfolgen für die Anzahl der Parastichen in der Phyllotaxis! Weil dann eine Drehung um ω nach endlich vielen Schritten ebenfalls ”optimal packt“.

3.3.3 Berechnung des Kettenbruchs — Erste Beschreibung
Im Folgenden verwende ich wieder die Floor-Funktion, siehe Kap. 2.2.5. Zur Erinnerung: Für a > 0 bezeichnet adie größte Zahl n0 ∈IN0 mit n0 ≤a.
Verbindung zum Rechteckalgorithmus: aist die größte Anzahl von Quadraten der Länge 1, die in ein Rechteck mit den Kanten 1 und a hineinpassen.
Wir notieren:
Lemma 3.13. Zu ω ∈(0, 1) gibt es genau ein a1 ∈IN und ein ε1 ∈[0, 1) mit
1
ω = 
 .
a1 + ε1
Es gilt j 1 k , ε1 = 1
a1 = ω −a1.
ω
BEWEIS: Ganz einfach. Klar, dass für alle y
y = y+ ε, ε := y −y.
Nun setze y :=1ω.
Verbindung zum Rechteckalgorithmus: a1 ist die größte Anzahl von Quadraten der Länge ω, die
in ein Rechteck mit den Kanten ω und 1 hineinpassen. Das verbleibende Restrechteck hat die
Längen 1 −a1ω =  ε1
a1+ε1 und ω. Oder: a1 ist die größte Anzahl von Quadraten der Länge 1, die
in ein Rechteck mit den Kanten 1 und 1/ω hineinpassen.
a1 ist also dadurch bestimmt, dass
1
a1 + 1 < ω ≤
Genau diese Überlegung wurde in Kap. 2.2.9 im Nenneralgorithmus angestellt, um den ersten Koeffizienten zu bestimmen!
Wenn ε1= 0, ist der ”Kettenbruch“ ω = a11schon fertig, sonst wende man das Lemma auf ε1 statt auf ω an: Es gibt eine eindeutige Darstellung
1
ε1 =
 a2 + ε2
mit a2 ∈IN und ε2 ∈[0, 1). Insgesamt haben wir
ω =
a1 + 1
 a2 + ε2
Verbindung zum Rechteckalgorithmus: Das Restrechteck nach dem ersten Schritt hat die Kan-tenlängen 1 − a1ω =
ε1
a1+ε1 und ω. Wir skalieren dies durch Multiplikation mit 1ω. Dann hat das
Restrechteck R2 die Längen e1 und 1, da
ω
  = e1.
1 − a1ω
a2 ist dann die Anzahl der Quadrate mit Kantenlänge e1, die in R2 hineinpassen.
Nun können wir so fortfahren und erhalten nacheinander a3, a4, ..., bis möglicherweise das erste Mal ein ek = 0. Dann gilt
ω = [a1, a2, ..., ak].
Ein solcher Abbruch kann nur für rationale ω vorliegen.
Diesen Algorithmus wollen wir im Folgenden ausführlicher darstellen und ihn insbesondere mit dem klassischen Euklidischen Algorithmus in Beziehung setzen. Hierzu dient der folgende Einschub.
3.3.4 Euklidischer Algorithmus
Der klassische Euklidische Algorithmus (Wikipedia) berechnet den größten gemeinsamen Teiler
ggT(m, n) zweier natürlicher Zahlen m und n. Auch ihn können wir mit einem Rechteckalgo-
rithmus geometrisch interpretieren. Wir setzen n > m voraus. Nun setze r0 := m und dividiere
n durch r0, so dass man
n = q0r0 + r1, 0 < r1 < r0
mit q0, r1 E IN0 erhält. Beachten Sie, dass q0 = L r0n J.
r1 ist also der Rest bei der Division von n durch r0 = m und q0 gibt an, ”wieviele m in n
hineinpassen“(” Wie oft kann man m von n abziehen?“).
Rechteckalgorithmus: Man betrachte ein Rechteck mit den Längen m und n. Dann ist q0 die
maximale Anzahl von m-Quadraten (ein Quadrat der Kantenlänge m), die in das Rechteck
hineinpassen. Es bleibt nach ein Rechteck mit den Kantenlängen r1 = n − q0m und r0 = m.
Im nächsten Schritt dividiert man r0 durch r1 mit Rest r2:
r0 = q1r1 + r2, 0 < r2 < r1
und dann analog
r1 = q2r2 + r3, 0 < r3 < r2.
(Beachten Sie, dass q1 = Lr0
r1 J und q2 = Lr1
r2 J.
Nun fährt man solange fort, bis rk = 0. Dann gilt
rk−1 = ggT(m,n),

d.h. ggT(m, n) ist der letzte nicht verschwindende Rest beim Euklidischen Algorithmus. Man sieht unmittelbar ein, dass der letzte nicht verschwindende Rest rk−1 alle vorherigen rj (j < k −1) teilen muss, insbesondere also auch m und n. Dass er auch der größte gemeinsame Teiler ist, macht man sich schnell klar.
Rechteckalgorithmus: Dieser bricht ab, wenn das Restrechteck ein Quadrat ist.
Beispiel: n = 24,m = 18. Dann gilt 24 = 1 •18 + 6 und 18 = 3 •6 + 0. Der letzte nicht verschwindende Rest war r1 = 6 = ggT(m, n).
Die qj, j = 0, 1, 2, ... haben hier keine Bedeutung — im Gegensatz zur nachfolgenden Ket-tenbruchberechnung. Daher erhalten sie einen (vorläufigen) Namen: Quotienten von m und n.
3.3.5 Euklidischer Algorithmus zur Berechnung eines Kettenbruchs
Der Kettenbruchalgorithmus wird induktiv definiert: Gegeben sei ω ∈(0, 1). Setze k := 1 und ε1 := ω.
K-Schritt (für allgemeines k):
Setze yk := εk1,ak := ykund εk+1 := yk−ak. Bemerkung für k = 1: Nach Lemma 3.13 gilt
1
ω = .
a1+ ε1
Fall 1: εk+1 > 0. Ersetze k durch k + 1 und gehe zum K-Schritt. Fall 2: εk+1 = 0. Dann breche den Algorithmus ab.
Im letzten Fall 2 haben wir ω = [a1, a2, ..., ak] als endlichen Kettenbruch dargestellt. Falls der
Fall 2 niemals eintritt, haben wir die Darstellung ω = [a1, a2,  ] als unendlichen Kettenbruch.
Einfache Merkform des Algorithmus: Invertiere (y := 1ω), setze a1 als ganzzahligen Anteil von y (die Zahl vor dem Punkt: a1 = y), nehme den nicht ganzzahligen Anteil von y (ε :=
und mache mit ε dasselbe wie vorher mit ω. Kurz: Invertieren, vor dem Punkt (Komma) merken,
abziehen, invertieren,
Die kurze rekursive Form des Algorithmus lautet
Start: y1 := 1ω, a1 := y1.
, ak+1 := yk+1
Abgebrochen werden muss, wenn erstmals yk = ak.
Rechteckalgorithmus: yk ist das Verhältnis der längeren zur kürzeren Seite des Rechtecks Rk.
Beispiel: ω = 0.886.
1. y1 = ω1 = 1.1287, also a1 = y1= 1. Dann ε2 := y1 −a1 = 0.1287.
48

2. y2 = E12 = 7.7719, also a2 = Ly2j = 7. Dann ε3 := y2 − a2 = 0.7719.
3. y3 = E31 = 1.2955, also a3 = [y3] = 1. Dann ε4 := y3 − a3 = 0.2955.
4. y4 = E14 = 3.3846, also a4 = Ly] = 3. Dann ε5 := y4 − a4 = 0.3846.
5. y5 = E15 = 2.6000, also a5 = Ly] = 2. Dann ε6 := y5 − a5 = 0.6000.
6. y6 = E16 = 1.6667, also a6 = Ly] = 1. Dann ε7 := y6 − a6 = 0.6667.
7. y7 = E17 = 1.5000, also a7 = Ly] = 1. Dann ε8 := y7 − a7 = 0.5.
8. y8 = E18 = 2.0000, also a8 = Ly] = 2. Dann ε9 := y8 − a8 = 0. Überzeugen Sie sich, dass
1
0.886 =
 1
1 +
 1
7 +
 1
1 +
 1
3 +
 1
2 +
 1
1 + 
 1 + 1
2
Sie sehen hoffentlich, dass dieser Algorithmus in einer klaren Beziehung zum Nenneralgorithmus des letzten Kapitels steht. Man bedenke, dass ak gerade angibt, wie oft das kleinere Intervall der Länge dk := d(xqk, 0) in das größere der Länge dk−1 hineinpasst. Das yk+1 ist gerade der Quotient  dk
dk−1 , gibt also die ”Verzerrung“ oder die ”Ungleichförmigkeit“ der Partition von S1 durch den qk-Orbit an, die ja gerade nur zwei verschiedene Intervalllängen aufweist.
3.3.6 Kettenbruch einer rationalen Zahl
Wir schauen uns den rationalen Fall ω = p mit teilerfremden p und q genauer an. Dann
q
kann man zum einen die Verwandtschaft zum Euklidischen Algorithmus zur Berechnung von ggT(q,p) = 1 sehen, zum anderen sieht man auch, dass in diesem Fall der Kettenbruch-Algorithmus abbricht.
E-Schritt 1: q = a1p + r1, 0 ≤ r1 < p.
Dies ist auch der erste Schritt des Kettenbruch-Algorithmus (da a1 = Lqpi und r1 p = ε1 mit ε1 in obigem Schritt.

E-Schritt 2: p = a2r1 + r2, 0 r2 < r1.
Wieder erkennt man mit ε2 := r1p der Schritt des Kettenbruchalgorithmus ist.
Insgesamt sind die aj gerade die Quotienten des Euklidischen Algorithmus f¨ur p und q, dessen letzter Schritt wegen der Teilerfremdheit von p und q zu einem Rest r = 1 f¨uhrt. Das ist, bezogen auf den Kettenbruch-Algorithmus, der vorletzte (k −1-te) Schritt, der durch ak := rk−2 ergänzt wird (es ist rk−1 = 1 und rk = 0). Beachten Sie6, dass ak ~ 2.
Wir fassen die bisherigen Überlegungen zusammen:
Satz 3.14. Jede rationale Zahl p mit 1 p < q ist durch einen endlichen Kettenbruch [a1, ..., ak]
q
der Ordnung k mit ak ~ 2 darstellbar. Jeder endliche Kettenbruch ist eine rationale Zahl.
Die Koeffizienten aj, j = 1, 2, .., k können mit dem Euklidischen Algorithmus zur Berechnung von ggT(q, p) als Quotienten von p und q berechnet werden.
Diese Aussage ist viel einfacher als der analoge Satz bei Dezimalbr¨uchen, weil zwar endliche De-zimalbr¨uche rationale Zahlen darstellen, es aber auch unendliche (periodische) Dezimalbr¨uche gibt, die rationale Zahlen darstellen.
Beachten Sie, dass der Satz 3.14 nichts ¨uber die Ordnung des Kettenbruchs aussagt, der nur bedingt etwas mit der Größe des Nenners q zu tun hat. Aber nat¨urlich ist die Ordnung niemals größer als q.
Beispiele:
1.  17   1  
 50 =
2 +  1 
      1
      
    1 + 
      16
      
 Die Ordnung ist 3, es ist a1 = 2, a2 = 1, a3 = 16  
2.       
 8   1  
 =
13    1 
      
  1
+    
      1
      
  1 +   
       1
      
    1 + 
       1
      
      1 + 2
Die Ordnung ist 5, es ist a1 = a2 = a3 = a4 = 1, a5 = 2.
6Dann ist [a1, ..., ak] = [a1, ..., ak − 1, 1]. Jeden endlichen Kettenbruch kann man mit einem letzten Koeffizi¬enten ak ~ 2 darstellen.

3.3.7 Unendliche Kettenbrüche bei irrationalen Zahlen
Für irrationale ω bricht der Kettenbruchalgorithmus niemals ab, er liefert also einen unendlichen Kettenbruch, der im Sinne von
ω = lim [a1, a2, ..., ak] k→∞
gegen ω konvergiert. Dies ist zwar anschaulich klar, muss aber noch gezeigt werden. Hierzu vermerken wir zunächst, dass die Kettenbruch-Koeffizienten von ω durch den Algorithmus eindeutig bestimmt sind, wir können von den Kettenbruch-Koeffizienten von ω sprechen. Jeder endliche Teilbruch [a1, a2,...,ak] ist eine rationale Zahl und lässt sich daher eindeutig als
Bruch pk
qk mit teilerfremden pk und qk darstellen.
Definition 3.15. Seien ak, k = 1, 2, ..., die Kettenbruch-Koeffizienten von ω E (0, 1). Dann heißt der Bruch
pk = [a1, a2,...,ak], qk
k-te Konvergente von ω. Der Zähler pk heißt Konvergentenzähler, der Nenner qk Kon-vergentennenner.
Wir haben gesehen, dass die erste Konvergente a1 1 eine obere Schranke von ω ist. Da
1
ω =
a1 + ε
mit einem ε E (0, 1) gilt und da a2 1 eine obere Schranke von ε ist, muss
p2 1
=
q2 
 a1 + 1
a2
eine untere Schranke von ω sein. Diesen Schluss kann man induktiv fortsetzen und man erhält
Satz 3.16. Für gerade k = 2j ist die k-te Konvergente eine untere, für ungerade k = 2j − 1 eine obere Schranke von ω:
p2j p2j−1
< ω <
q2j q2j−1 ,j = 1, 2, .... (3.8)
Ist ω irrational, so steht so steht in (3.8) stets < statt <.
F2
Dies stimmt überein mit dem uns bekannten Fall ω = ϕ, siehe (2.4). Hier sind ja die Brüche  3
F23+1
obere und F23−1 untere Schranken von 9o. Die k-te Konvergente von 90 ist   k = 1, 2, 3,
F2, = ic+1
Siehe (2.4) aus Kap. 2

Wir können noch mehr herausfinden. Hierzu nehmen wir an, dass die Kettenbruchdarstellung von ω bis zum k-ten Glied erfolgt ist und noch nicht abgebrochen werden kann. Dann gibt es ein εk E (0, 1) mit
1
ω =
 1
a1 +
 1
a2 + a3 + ...
+ ak + εk
Jetzt fokussieren wir den Blick auf die Abhängigkeit dieses Kettenbruchs von εk und betrachten
1
fk : IR —* IR, ε 7—*
a1 +
 1

a2 + a3 + ...
+

1
ak + ε

Wir notieren die Spezialfälle
· k = 1:
· k = 2: 1
f1(ε) = a1 + ε,


a1 +
 a2 + ε
Es ist daher naheliegend, dass fk eine gebrochen-lineare Funktion ist gemäß
Definition 3.17. Eine reelle Funktion heißt gebrochen-linear genau dann, wenn es reelle Zahlen α, β, γ und δ =6 0 gibt mit
α + βx
f(x) = γ + δx , x =6 −γδ
und
D := αδ − βγ =6 0.
Das D kann als Determinante einer 2 x 2-Matrix aufgefasst werden. Falls D = 0, so wäre f(x) eine Konstantenfunktion.

In unserem Fall haben wir noch eine speziellere Situation: Die vier Koeffizienten α, β,γ,δ sind
aus IN0, und es ist die ”Determinante“D := αδ − βγ = ±1, genauer die Determinante von
(α β )
A :=γ δ
Solche Funktionen heißen unimodular.
Beachten Sie, dass eine gebrochen-lineare Funktion i.A. eine Polstelle in der Nullstelle z := −
des Nenners hat, d.h. dass nicht ganz IR zum Definitionsbereich zählt. Genauer: Eine gebrochen-
lineare Funktion ist eine Bijektion zwischen IR \ {− } und IR \ {− }. Die Umkehrfunktion ist
selbst wieder gebrochen-linear und hat dieselbe Determinante. Die Umkehrfunktion einer D-
Funktion ist daher selbst wieder eine D-Funktion.
Lemma 3.18. Die oben definierte Funktion fist gebrochen-linear für alle k ∈ IN mit
α, β,γ,δ ∈ IN0 und ”Determinante“ D:= aδ − βγ = (−1).
BEWEIS durch vollständige Induktion nach k:
Induktionsanfang: (k = 1) f1(x) = 1
1+hat die gewünschte Form.
Induktionsschluss: Es gilt (Innduktionsschlüssel!!)
1
f+1(x) = a1
+ ˜f(x)
mit 1
˜f(x) =   
  1
 a2 +  
    1
a3 + a4 + ...
+
a+1 + x
Nach Induktionsannahme ist αδ − βγ = (−1)+1 und ˜fgebrochen-linear und es gibt α,β,γund δ aus IN mit D:= ˜f(x)
=+x
+ 2x..


Einfaches Bruchrechnen zeigt, dass
a1γ + α + (a1δ + β)x,
mit ”Determinante“ D+1 = δ(a1γ + α) − γ(a1δ + β) = δα − βγ = −D.

Daher ist auch fk+1 gebrochen-linear und die Koeffizienten genügen den obigen Bedingungen.
Nun notieren wir die folgenden Eigenschaften von fk:
1.
fk(0) = pk
qk ,
2.
pk+1
fk( 1=
ak+1 ) qk+1
3.
fk(εk) = ω,
fk(ε) = pk−1.
qk−1
Nur die letzte Aussage bedarf einer Erklärung: Diese Aussage folgt aus
lim
ε→cx) 1 = 0.
 ak + ε
Jetzt folgern wir aus der ersten und letzten Aussage, dass
pk + εpk−1
fk(ε) =
qk + εqk−1
und aus der zweiten nach Erweiterung des Bruchs mit ak+1, dass
pk+1 ak+1pk + pk−1
=
qk+1 ak+1qk + qk−1
sowie die überaus wichtige und interessante Rekursionsformel
pk+1 = ak+1pk + pk−1, qk+1 = ak+1qk + qk−1,k = 1, 2, ... (3.9)
mit der Verankerung p0 = 0, q0 = 1, p1 = 1, q1 = a1. Diese Rekursion erlaubt eine einfache Berechnung der Konvergenten aus den Koeffizienten des Kettenbruchs!
Diese Rekursion kennen Sie vom Nenneralgorithmus, s. (2.5). Dies schließt den Kreis. Der Zusammenhang mit dem Nenneralgorithmus ist jetzt klar! Statt des Nenneralgorithmus haben wir jetzt den noch einfacheren Euklidischen Algorithmus zur Berechnung von Brüchen, die die Fehler 1. und 2. Art minimieren.

3.3.8 Konvergenz der Konvergenten
Wenn ω ∈ (0, 1) irrational ist, so ist ω durch einen unendlichen Kettenbruch [a1, a2, ....] dar-stellbar, und die Konvergenten
p:= [a1, a2, ..., a], k = 1, 2, ... q
konvergieren gegen ω. Jetzt stellen wir die Frage, wie gut denn die rationalen Konvergenten die irrationale Zahl approximieren. Dabei können wir von der geometrischen Interpretation des Nenneralgorithmus, von der zahlentheoretischen Interpretation durch den Mediantenalgo-rithmus oder eben durch die Kettenbrucheigenschaft Gebrauch machen. Auch die geometrische Veranschaulichung durch den Rechteckalgorithmus in Kap. 3.3.2 kann hilfreich sein. Rechnerisch ist natürlich vor allem die Rekursion (3.9) wertvoll.
Die Medianteninterpretation liefert sofort (s. auch Satz 3.16)
Satz 3.19. Zwei aufeinander folgende Konvergenten schließen ω ein. Dabei bilden die Konver-genten mit geradem Index k eine streng monoton wachsende, die Konvergenten mit ungeradem Index eine streng monoton fallende Folge, genauer: Mit c:= k
k gilt
c2 < c4 < c6 < ·· · < c2< c2+1 < · ·· < c3 < c1.
Die Länge des Einschließungsintervalls zwischen k-ter und (k + 1)-ter Konvergente ist  1
kk+1 .
cminimiert die Fehler 1. und 2. Art in Bezug auf einen Höchstnenner Q < q+1.
Die vorletzte Eigenschaft in Satz 3.19 besagt nur, dass zwei aufeinanderfolgende Konvergenten Farey-benachbart sind, was auch durch
p+1q− pq+1 = (−1)+1 (3.10)
ausgedrückt werden kann.
Die letzte Aussage des Satzes folgt aus der Analogie zum Nenneralgorithmus, wo wir gesehen hatten, dass d= d(xk, 0) = |qω − p|.
Satz 3.20. Für den Fehler 1. Art gilt die Abschätzung
1p 1
  < Lω   <
für den Fehler 2. Art 1 1
  < |qω−p| <
(a+1 + 2)q a+1q

Dieser Satz ist mit Genuss zu interpretieren. Er besagt, dass die Güte der Näherung der k-ten Konvergente für ω ganz wesentlich von dem Konvergentennenner qk und vom nächsten Ketten-bruchkoeffizienten ak+1 abhängt. Wenn letzterer sehr groß ist, besagt dies, dass die Näherung sehr gut ist, auch wenn qk relativ klein.
BEWEIS von Satz 3.20
Wir lassen die Indizes weg und setzen
p
q pk :=
qk  r
s := pk−1
  ,    . qk−1
Per vollständiger Induktion kann man zeigen, dass die letzte Konvergente p dichter an ω liegt
q
als die vorletzte Konvergente rs. Mit a := ak+1 ist (siehe (3.9))
pk+1 := ap + r, qk+1 = aq + s. Die Mediantendeutung liefert, dass
np + r
b(n) := nq + q,n = 1, 2, ..., a
auf der p
q entgegengesetzten Seite von ω liegt, während b(a+1) (Wechselschritt!) auf der gleichen
Seite liegt, aber näher an ω als p q. Beachten Sie, dass b(n) der Mediant von b(n − 1) und p q ist, so dass zwei aufeinanderfolgende Brüche b(n − 1) und b(n) Farey-benachbart sind.
Mit einem kleinen Einschub kann man auf Grund dieser Farey-Nachbarschaft sehen, dass
g(n) := b(n) − b(n − 1)
streng monoton fällt.
Ohne Einschränkung nehmen wir an, dass
r p
< ω < .
s q
Dann haben wir also

Es folgt
<
1+ s) aq12 ,
V3 − b(a) = q(aq  <  
q
womit die obere Schranke in Satz 3.20 gezeigt ist.
Ferner gilt
p 1 1
1
> — b(a + 1) >=
q > q(s + (a + 1)q) q(q + (a + 1)q) (a + 1)q2 .
56

Dabei habe ich von der Farey-Nachbarschaft von pq zu b(a + 1) sowie von Abschätzungen von Brüchen in dem Sinne Gebrauch gemacht, dass ein Bruch kleiner wird, wenn man den Nenner
vergr ößert. Ferner wurde s < q benutzt bzw. dass die Folge der Konvergentennenner streng
monoton wächst.
Im Beweis wurde davon Gebrauch gemacht, dass die k-te Konvergente näher an ω liegt als ihr Vorgänger, die (k − 1)-te Konvergente. Man findet in dem Beweis auch den hierzu notwendigen Induktionsschluss, da recht leicht
|ω − b(a)| < |ω − p
q
gefolgert werden kann (Man beachte, dass b(a) die (k + 1)-te Konvergente von ω ist): Es ist
|ω − b(a)| < |b(a + 1) − b(a)| <|ω −p|,
q
 da |b(a + 1) − b(a)| < p P - b(a + 1) < - C.J.
 4 q
Beispiele: 1. Ein Jahr hat J := 365.2425 Tage und ein synodischer Mondumlauf zählt M := 29.53059 Tage. Die Griechen haben so gerechnet, dass 235 Monate gerade 19 Jahre ergeben. Offensichtlich ist 21395 eine sehr gute Näherung für ω := MJ . Das kann man mit Hilfe der Kettenbrüche begründen! Denn es handelt sich um eine Konvergente von ω und der nächste Kettenbruchkoeffizient ist mit 14 recht groß.
2. Es gibt mit 315153 = 3.14159292 eine sehr gute Näherung für π. Auch das kann man mit Kettenbrüchen begründen. Der nächste Koeffizient ist 292.
3.3.9 Geometrische Konstruktion
Man nehme kariertes Papier und zeichne die Gerade y = ωx in ein Koordinatensystem, dessen Ursprung in einem ”Gitterpunkt“ liegt. Ist ω irrational, so wird sie niemals einen weiteren Gitterpunkt treffen. Man kann auch sagen, dass kein ”rationaler Punkt “ auf dieser Geraden liegt. Nun denke man sich die Konvergenten als Punkte Pk := (qk, pk) eingezeichnet. Sie liegen abwechselnd unter und über der Geraden, und zwar für gerade k oberhalb. Nun gilt ja wegen der Rekursion (3.9)
Pk+1 = ak+1Pk + Pk−1.
ak+1 ist die größte natürliche Zahl, für die Pk+1 auf der anderen Seite der Geraden liegt als Pk. Beachten Sie, dass die ”vertikalen Fehler“ gerade |qkω − pk|, also die Fehler 2. Art sind!
3.3.10 Die Goldene Drehung im Zusammenhang mit Pflanzenwachs¬tum
Jetzt geht es darum, warum die Natur den goldenen Divergenz-Winkel bevorzugt. Ausgangs¬punkt ist dabei, dass sich die entstehenden Pflanzenteile (Samen, Blütenstände, etc.) möglichst

wenig Sonnenlicht wegnehmen wollen. Wobei sie sich aber schon gegenwärtigen, dass noch andere Teile nachwachsen, also auch ihren Platz haben wollen. Die mathematische Wachstums¬annahme ist, dass für jeden Samenort ein fester Drehwinkel festgelegt wird und dass das weitere Wachsen nur radial stattfindet. Sonst könnten sich die Neuankömmlinge einfach in die Mitte ihrer Vorgänger setzen. Oder nach jedem neuen Pflanzenteil würden alle bisherigen einen neuen Platz einnehmen, so dass alle Abstände gleich wären.
Wenn das radiale Wachstum nicht sehr groß ist, kommt es ausschließlich auf die Abstände zwi¬schen benachbarten Orbitpunkten auf S1 an, von denen es kurz vor Vollendung des (k + 1)-ten Wechselschrittes zwei verschiedene, nämlich dk und dk_1 gibt. Wir versetzen uns wieder in die Lage des ”Ursamens“ x0 = 0, dessen Sonnengenuss durch seine beiden Nachbarn eingeschränkt wird. Für ihn sind nach Ansiedlung von qk Konkurrenten (der qk-te ist sein Nachbar geworden und bleibt es bis zum qk+1-ten Samen) der Abstand dk, der ja kleiner als dk_1 ist, maßgeblich. Wir interessieren uns also für die Abstände
dk := d(xqk, 0), k = 1, 2, ...,
wenn wir wieder ein dynamisches System zur Rotation Rω und die Konvergentennenner qk betrachten. Was haben diese mit Kettenbrüchen zu tun? Offensichtlich ist
dk := |qkω − pk|
der Fehler 2. Art der k-ten Konvergente von ω, siehe Lemma 2.6.
Auch ohne Kettenbrüche wissen wir, dass dk eine monoton fallende Nullfolge ist und dass ak+1 die größte natürliche Zahl ist, für die ak+1dk < dk_1 gilt. Ohne Betragstriche ist die Folge
δk := qkω − pk
oszillierend und erfüllt die Rekursion
δk+1 = ak+1δk + δk_1, δ_1 = −1, δ0 = ω.
(Dann folgt δ1 = a1ω − 1).
Rechteckalgorithmus: Die kleinere Seitenlänge des Rechtecks Rk+1 ist gerade dk, die größere Seite hat die Länge dk_1. Das Verhältnis der längeren zur kürzeren Seite von Rk+1 ist also rk. Mit Hilfe von vollständiger Induktion kann man zeigen, dass rk gerade das yk+1 im k-ten Kettenbruchalgorithmus-Schritt ist.
Ein Erklärungs-Ansatz ist es, sich für das Verhältnis
dk_1
rk := 
 ,
dk
zu interessieren, welches stets > 1 ausfällt. Unter dem Gesichtspunkt der Wachstumsinterpre¬tation und einer ”optimalen Packung“ kann man die Forderung aufstellen, dass rk nur mäßig

groß werden darf. Da ak+1 die größte natürliche Zahl ist, für die ak+1dk ≤dk−1 gilt, muss ak+1 + 1 > rk = d,−1
d, ≥ak+1 sein. Optimal im eben genannten Sinne ist also ak+1 = 1. Wir können also beim goldenen Drehwinkel ω = ϕ von einer optimalen Packung sprechen. Betrach¬ten wir die vorzeichenbehafteten
δk
Pk := δk−1 ,
so erhalten wir sofort aus der Rekursion für δk, dass
1
ek+1 = ak+1 + ,P0 = −ω.
Pk
Dann können wir leicht folgern, dass für ω = ϕ die Folge der Pk abwechselnd ϕ und −ϕ ist, d.h. dass xq,+1 den Bogen (0, xq,−1) im goldenen Schnitt teilt - was wir ja schon in Aufgabe Ü18 gesehen haben. Ferner gilt rk = Φ für alle k — beim Rechteckalgorithmus sind alle Rechtecke Rk golden.
Ein zweiter Erklärungsansatz für den goldenen Divergenzwinkel ist der Folgende: Der ”Ursa-men“ will den Nachbarabstand dk so groß, wie es bei qk Konkurrenten noch möglich erscheint, haben. Als erstes erkennt er, dass die Situation für alle Orbitpunkte gleich ist. Jeder hat einen dk-nahen Nachbarn. Daher wird er gerechterweise den Quotienten dk/qk (das ist gerade der Fehler 1. Art!) als relatives Maß nehmen und zwar für alle k = 1, 2, .... Beachten Sie, dass alle diese Zahlen von ω bzw. dessen Kettenbruchentwicklung abhängen. Nun kann man aus Satz 3.20 folgern, dass diese Quotienten bei der goldenen Drehung im Vergleich mit allen anderen Winkeln für alle k maximal sind:
Wegen ak+1 = 1 liefert Satz 3.20


Es gibt keine irrationale Zahl, die sich durch ihre Konvergenten schlechter approximieren lassen, als die kleine Goldene Schnittzahl ϕ. Man spricht von der ”irrationalsten“ Zahl.
Der goldene Winkel liefert ”zu jeder Zeit“ eine optimale Packung im Hinblick auf Nachbarschaft.
3.3.11 Kettenbrüche, Goldener Schnitt und Fibonacci-Zahlen
Der allereinfachste (periodische) Kettenbruch ist
1
ω = [1] = [1, 1, 1, ...] =
1 +
 1

1 + 1 + ...
+

1
1 + •••

mit lauter Einsen als Kettenbruchkoeffizienten. Sie wissen schon aus einem Proseminarvortrag, dass dieses w gerade die kleine Goldene-Schnitt-Zahl ist, was man sofort einsieht, wenn man
1
w =
 1 + w
aus dem Kettenbruch gewinnt und die zugehörige quadratische Gleichung
x2 + x − 1 = 0,
dessen positive Lösung gerade die kleine Goldene-Schnitt-Zahl ist, betrachtet! Betrachtet man die Rekursionsformel 3.9, so erhält man alte Bekannte:
pk+1 = pk + pk−1, qk+1 = qk + qk−1, k = 1,2,..
mit p0 = 0, q0 = 1, p1 = 1, q1 = 1. Ein Vergleich mit der Fibonacci-Rekursion
Fk+1 = Fk + Fk−1,k = 1,2,...,F0 = 0,F1 = 1
zeigt pk = Fk, qk = Fk+1, d.h. die Konvergenten von p sind die Quotienten aus Fibonacci-Zahlen, also
Fk  , k = 1, 2, ... Fk+1
von denen wir ja schon wissen, dass sie gegen p konvergieren — eine Aussage, die wir jetzt mit völlig anderen Mitteln (Kettenbrüchen) bewiesen haben, da wir ja allgemein wissen, dass Konvergenten einer irrationalen Zahl gegen diese konvergieren.
Dass die Konvergenten der kleinen Goldene-Schnitt-Zahl die Quotienten der Fibonacci-Zahlen sind, dass also
pk Fk

=
qk Fk+1
kann man auch durch vollständige Induktion nach k, ohne Bezug auf die Rekursion (3.9) be-weisen. Dass
F1
,
F2
ist der Induktionsanfang. Aus der Darstellung
pk = [1,1,...,1] qk
mit k Einsen folgt
pk+1  1
 
=
qk+1 1 + pk
qk

und unter Ausnutzung der Induktionsannahme
pk Fk

=
qk Fk+1

folgt hieraus
pk+1
=
qk+1

Fk+1
=
Fk + Fk+1

und wegen Fk+2 = Fk+1 + Fk die gesuchte Aussage7.
Wir fassen zusammen:
Satz 3.21. Für die endlichen Kettenbrüche mit lauter Einsen als Koeffizienten gilt
1 2
3 5
[1] = 2, [1,1] = 3, [1, 1, 1] = 5, [1, 1, 1, 1] = 8,
allgemein für den Kettenbruch k-ter Ordnung
Fk
[1, 1, 1, ..., 1] =
Klar dürfte sein, dass die Quotienten Fk
Fk+1 die rationalen Zahlen sind, deren Kettenbruch-
Ordnung
im Vergleich zu allen rationalen Zahlen mit einem Nenner ≤ Fk+1 maximal ist. Be¬zogen auf den Euklidischen Algorithmus bedeutet dies, dass die Anzahl der Operationen, die den größten gemeinsamen Teiler zweier Zahlen liefert, für zwei aufeinanderfolgende Fibonacci-Zahlen im Vergleich zu allen Zahlen, deren Nenner nicht größer ausfallen, maximal ist.
Der Satz 3.20 liefert jetzt sogar eine Abschätzung:
1 Fk 1
3F  <
k+1 Fk+1 < F2+1,
z.B. ist (k = 5)
 151 1
< <
192 8 64
Wenn wir wieder das dynamische System mit Rotationen betrachten, so bedeuten die Ketten-
bruchkoeffizienten Eins gerade, dass jeder Nennerschritt ein Wechselschritt ist.
Stellen Sie sich einmal vor, Sie wohnen auf S1 am Ort x = 0. Jeder Iterationsschritt
xn+1 = Rω(xn)
7Wo liegt der Induktionsschlüssel?

führt zu einem neuen Bewohner auf 81. Sie sind an Ihren im Laufe der Iteration auftauchenden nächsten (linken und rechten) Nachbarn interessiert. Ein Iterationsschritt dauere 1 Tag. Denken wir uns einmal den kontinuierlichen Vorgang, dass ein Hubschrauber mit konstanter Geschwin¬digkeit w gegen den Uhrzeigersinn um 81 kreist und jeden Tag einen neuen Kreisbürger abwirft (siehe auch die ”Saatmaschine“). Sie registrieren insbesondere den Tag, an dem wieder ein neu¬er Nachbar bei Ihnen auftaucht. Sie wissen, dass diese neuen Nachbarn Ihnen immer weiter auf die Pelle rücken.
Was Sie dann registrieren, ist, dass im Abstand von qk Tagen ein neuer Nachbar erscheint, dass der Hubschrauber Ihr Haus zwischen zwei Abwürfen pk mal (fast) überflogen hat und dass ak+1-mal der neue Nachbar auf der gleichen Seite von Ihnen auftaucht. Wenn dann das erste Mal der neue Nachbar die Seite wechselt, können Sie statt qk den neuen Tages-Rhythmus qk+1 ansetzen und mit pk+1 die Anzahl der Hubschrauberpassagen zählen, bevor der nächste Nachbar auftaucht.
Das Verhältnis der Nachbar-Abstände
dk
rk := dk−1
gibt an, um welchen Faktor sich der Abstand zu Ihrem Nachbarn verkleinert hat.
Für die kleine Goldene-Schnitt-Zahl w := p liegt eine besondere Situation vor: Nach jeweils Fk Tagen taucht ein neuer Nachbar auf, wobei der Hubschrauber den Kreis (fast) Fk−1-mal umrundet hat, immer abwechselnd ein rechter und ein linker Nachbar. Mehr noch: Qk ist stets konstant gleich der kleinen Goldene-Schnitt-Zahl! D.h., der Kreisbogen von x0 = 0 zum letzten Nachbarn wird durch einen neuen Nachbarn auf der gleichen Seite im Goldenen Schnitt geteilt!
Es gibt aber noch weitere Drehwinkel, die ebenso zu einer optimalen Packung führen, jedenfalls nach einer Einschwingphase. Man kann p und w verwandt nennen, wenn w nur endlich viele Kettenbruchkoeffizienten besitzt, die =6 1 sind. Solche mit p verwandten Drehwinkel kommen auch für eine asymptotisch optimale Packung in Frage.
3.3.12 Spiralbildung bei Sonnenblumen
Bisher ist keine Begründung dafür gegeben worden, dass die Anzahl der rechts- bzw. linksläufi¬gen Spiralen bei Sonnenblumen aufeinanderfolgende Fibonacci-Zahlen sind. Das soll hier in sehr knapper Form nachgeholt werden.
Zunächst nehme ich an, dass das Wachstum der Blüten und späteren Samen von innen nach außen erfolgt und zwar so, dass (in Polarkoordinaten) ihre Winkel unverändert bleiben und durch die Dynamik xk+1 = Rω(xk), k = 0, 1,2, ... mit einem Divergenzwinkel w gegeben sind, und dass die Abstände Rk des k-ten Samenplatzes zum Zentrum alleine von dem diskreten Zeitpunkt N abhängen, z.B. sei
√
Rk := r · N − k, k = 0, 1, 2, ..., N
mit einem r > 0.


Abbildung 3.1: Spiralbildung bei der Sonnenblume
In Abb. 3.2 werden N = 145 Samenplätze mit dem Divergenzwinkel o der kleinen Goldenen Schnittzahl auf diese Weise erzeugt. Sie enthält auch eine Nummerierung der Samenpunkte. Schaut man nur auf die Nummern (sie sind z.T. recht weit von den Punkten entfernt), so erkennt man 21 rechtsläufige und 34 linksläufige Spiralen. Der Grund ist einfach: Spiralen entstehen im Kopf, indem man benachbarte Punkte im Geiste verbindet. Diese Nachbarn haben nun Nummern, die sich um die beiden Fibonacci-Zahlen F8 = 21 und F9 = 34 unterscheiden. Das liegt daran, dass, wenn man die äußersten Punkte (etwa bis zur Nummer 34) auf eine Kreislinie projiziert, gerade xk+1 = Rω(xk), k = 0, 1, 2, ..., 34 erhält, wobei Nachbarschaft erhalten bleibt, wenn das radiale Wachstum langsam genug verläuft. Und hier wissen wir ja, dass Nachbar-Nummern sich nur um Fibonacci-Zahlen unterscheiden (man schaue nur die Nachbarn von x0 = 0 an!). Projiziert wird hier nur bis zum Samen Nr.34, um die Spiralen-Nachbarschaft auf der Kreislinie zu erhalten. Je langsamer man das radiale Wachstum modelliert, desto höher sind die ins Spiel kommende Fibonacci-Zahlen!
3.3.13 Appetitliches über Kettenbrüche
Wie schön wäre es, wenn man Kettenbrüche einfach addieren und multiplizieren könnte! Dann hätten wir heute vielleicht kein Dezimalsystem.
Wir wissen, dass periodische Dezimalbrüche rationale Zahlen darstellen. Etwas Analoges kann für Kettenbrüche nicht gelten, da rationale Zahlen gerade den endlichen Kettenbrüchen ent¬sprechen. Aber es gibt natürlich periodische Kettenbrüche, die wir analog wie bei den Dezimal¬brüchen durch
[a1, a2, .., ar, ..., ar+p] = [a1, a2, .., ar, ar+1, ..., ar+p, ar, ar+1, ..., ar+p,....]


Abbildung 3.2: Spiralbildung bei der Sonnenblume
bezeichnen und die in naheliegender Weise die Periode p besitzen.
Einen periodischen Kettenbruch der Periode 1 kennen Sie schon, nämlich ϕ = [1], die kleine Goldene-Schnitt-Zahl. Hier ist eine Bemerkung angebracht: Wir haben uns wegen der Rotatio¬nen auf Winkel w E (0, 1) beschränkt. Hätten wir beliebige positive Zahlen x > 0 zugelassen, hätten wir einen weiteren Kettenbruchkoeffizienten a0 einführen müssen:
1
x = a0 +
 1
a1 +
 1
a2 + a3 + ...
+ ak + ···
Für die große Goldene-Schnitt-Zahl Φ ist a0 = 1, da Φ = ϕ + 1, d.h., wir haben auch für diese eine wunderbare Kettenbruchdarstellung
1
Φ = 1 +
 1
1 +
 1

1 + 1 + ...
+

1
1 + ···

Welche Zahl ist nun

1
x =  ?
 

1
2 +
 1

2 + 2 + ...
+

1
2 + ···

Mit demselben Trick wie bei [1, 1, 1, ...] sehen wir, dass
1
w = 
 2 + w,

also w2 + 2w = 1 bzw. w = −1 + v'2 und
v'
2 = 1 + [2,2,2,...].
Allgemein gilt
Satz 3.22. Die periodischen Kettenbr¨uche sind gerade die positiven Lösungen quadratischer Gleichungen mit ganzzahligen Koeffizienten.
Beispiele:
· v'5 = 2 + [4]
· v'3 = 1 + [1,2]
· v'7 = 2 + [1,1,1,4]
· v'17 = 4 + [8]