Kettenbrüche

$a_0 + \dfrac{1}{\displaystyle a_1+\dfrac{1}{\displaystyle a_2+\dfrac{1}{a_3+\cdots}}}$

$a_0 + \dfrac{b_1}{\displaystyle a_1+\dfrac{b_2}{\displaystyle a_2+\dfrac{b_3}{a_3+\cdots}}}$

Endlicher Kettenbruch

a = $q_{0} \cdot$ b + $r_{2}$

b = $q_{1} \cdot r_{2}$ + $r_{3}$

$r_{2}$ = $q_{2} \cdot r_{3}$ + $r_{4}$

.

.

$r_{n}$ = $q_{n} \cdot r_{n+1}$ + $r_{n+2}$

.

.

$r_{o}$ = $q_{o} \cdot r_{o+1}$ + 0

$a = q_0 * b + r_2 | :b$

$\dfrac{a}{b} = q_0 + \dfrac{r_2}{b} = q_0 + \dfrac{1}{\displaystyle\ \dfrac{b}{r_2}\ } = q_0 + \dfrac{1}{\displaystyle q_1 +\dfrac{r_3}{r_2}} = \dots$

$13 = 2 \cdot 5 + 3$

$5 = 1 \cdot 3 + 2$

$3 = 1 \cdot 2 + 1$

$2 = 2 \cdot 1 + 0$

$\dfrac{13}{5} = 2 + \dfrac{3}{5} = 2 + \dfrac{1}{\displaystyle\ \dfrac{5}{3}\ } = 2 + \dfrac{1}{\displaystyle 1 + \dfrac{2}{3}} = 2 + \dfrac{1}{\displaystyle 1 + \dfrac{1}{\displaystyle\ \dfrac{3}{2}\ }} = 2 + \dfrac{1}{\displaystyle 1 + \dfrac{1}{\displaystyle 1 + \dfrac{1}{2}}}$

In der alternativen Schreibweise ist $\dfrac{13}{5} = [2;1,1,2]$

Unendliche Kettenbrüche

Periodisch unendliche Kettenbrüche

$x= 1 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{\displaystyle 3 + \dfrac{1}{\displaystyle 1 + \dfrac{1}{2 + \dots }}}}$

$x= 1 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{\displaystyle 3 + \dfrac{1}{x}}} = \cdots = \dfrac{10x+3}{7x+2}$

$\sqrt{2} = 1 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{2 + \ldots}}}}\,$

Nichtperiodisch unendliche Kettenbrüche

$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1,\dots]\,$

$\pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, \dots]$

$\pi = \dfrac{4}{\displaystyle 1+\dfrac{1^2}{\displaystyle 2+\dfrac{3^2}{\displaystyle 2+\dfrac{5^2}{\cdots}}}}$

$\sqrt[3]{2} = [1; 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, \dots]$

Historisches und Anwendungen

Zur Geschichte der Kettenbrüche

$\dfrac{77 \, 708 \, 491}{2 \, 640 \, 858}$$= [29;2,2,1,5,1,6,1,1,1,1,9,1,1,14,2,2]$$= 29{,}425471\dots$

$29 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{\displaystyle 2 + \dfrac{1}{1}}} = \dfrac{206}{7} = 29{,}428571\dots$

Anwendungen

• Die Kettenbruchmethode, ein Faktorisierungsverfahren für ganze Zahlen $n$, die keine Quadratzahl sind, basiert auf der Kettenbruchzerlegung von $\sqrt{n}$.
• Kettenbrüche sind manchmal recht angenehm, um etwas zu zeigen, beispielsweise um algebraische Zahlen von transzendenten Zahlen zu unterscheiden. Am Wachstum der Folge $a _{n}$ kann man ablesen, wie gut die Zahl $\alpha$=[$a _{0};a_{1}$, ...] durch rationale Zahlen approximierbar ist; falls die Folge $a _{n}$ schnell genug wächst, ist $\alpha$ ein Liouvillesche Zahl und daher transzendent.
• Kettenbrüche werden benutzt um rationale Näherungen an eine vorgegebene reelle Zahl zu berechnen, d.h. die betreffende Zahl durch Brüche anzunähern, deren Zähler und Nenner für die erzielte Genauigkeit der Darstellung möglichst klein sind. Man kann zeigen, dass die teilweise Auswertung der Kettenbruchdarstellung einer reellen Zahl einen Bruch liefert, der in dem Sinne die genaueste mögliche rationale Annäherung an den Kettenbruch ist, als man die Annäherung nur genauer machen kann, wenn man den Nenner größer macht.

Beispiel: die oben angeführte Kettenbruchdarstellung für

$\pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, \dots]$

liefert nacheinander mit zunehmendem Nenner und zunehmender Genauigkeit für $\pi$ die Näherungswerte

$3,\, \dfrac{22}{7} \approx 3{,}143$; $\dfrac{333}{106} \approx 3{,}14151$; $\dfrac{355}{113} \approx 3{,}1415929$; $\dfrac{103 \, 993}{33 \, 102} \approx 3{,}1415926530$, usw.

Diese sind abwechselnd ein bisschen zu klein und ein bisschen zu groß, wobei der absolute Fehler immer kleiner wird.

• Kettenbrüche eignen sich aber kaum zur Berechnung, da keine schnellen Algorithmen zur Berechnung der Summe, Differenz, Produkt oder Quotient zweier Zahlen in Kettenbruchdarstellung bekannt sind, und es für die Berechnung transzendenter und algebraischer Zahlen effektivere und schneller konvergierende Verfahren gibt.

Die Logik ist die Hygiene, deren sich der Mathematiker bedient, um seine Gedanken gesund und kräftig zu erhalten.

Hermann Weyl

Zahlenbereiche

• Natürliche Zahlen
• Ganze Zahlen
• Rationale Zahlen
  • Beispiele
  • 0,9999... =1
  • Verteilung
  • Kettenbrüche
  • Irrationalitätsbeweise