Mathekram

Mathematik rein und angewandt, erforscht und unterrichtet (ein Matheblog)

Endliche Kettenbrüche und der euklidische Algorithmus

Posted by Modulix - Mai 16, 2008

Zu Kettenbrüchen gibt es eine ausgefeilte Theorie (siehe etwa den Wikipedia-Eintrag), aber die Erstellung eines endlichen Kettenbruches erfordert keine Kenntnisse über Matrizen-Multiplikation oder ähnliches.

Wie erstelle ich etwa aus \frac{3}{11} einen Kettenbruch?

Ich wende den euklidischen Algorithmus darauf an, um den (natürlich bekannten) größten gemeinsamem Teiler zu finden:

3 = 0\cdot11+3

11=3\cdot3+2

3=1\cdot2+1

2=2\cdot1+0

Der Kettenbruch lautet damit:

\frac{3}{11}=\frac{1}{3+\frac{1}{1+\frac{1}{2}}}

Die Zahlen im Kettenbruch sind also nichts anderes als die Koeffizienten im euklidischen Algorithmus.

Ein weiteres Beispiel, bei dem der Zähler mal größer als der Nenner ist: \frac{14}{5}:

14=2\cdot5+4

5=1\cdot4+1

4=4\cdot4+0

Es folgt: \frac{14}{5}=2+\frac{1}{1+\frac{1}{4}}

Noch ein weiteres Beispiel: \frac{5}{13}:

Das ist der Quotient von zwei aufeinanderfolgenden Fibonaccizahlen. Diese Kettenbruchentwicklung deutet bereits an, dass allgemein gilt: \frac{fib_{n}}{fib_{n+1}}\rightarrow\frac{-1+\sqrt{5}}{2}, dass also die Quotienten aufeinanderfolgender Kettenbrüche gegen den goldenen Schnitt konvergieren. Dabei deutet sich auch an, dass der goldene Schnitt besonders schlecht zu approximieren ist.

8=0\cdot13+8

13=1\cdot8+5

8=1\cdot5+3

5=1\cdot3+2

3=1\cdot2+1

Es folgt: \frac{8}{13}=\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}}}.

Auf der Seite von Arndt Brünner kann man Kettenbrüche online berechnen. Dort ist auch noch einmal der Mechanismus erklärt.

 

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

 
%d Bloggern gefällt das: