O.Forster: Lineare Algebra

13. Die Fibonacci-Zahlen

Die Fibonacci-Zahlen sind rekursiv definiert durch

f_{0} = 0, f_{1} = 1, f_{n+1} = f_{n} + f_{n−1}, (n ≥ 1).

Der Anfang der Folge der Fibonacci-Zahlen ist daher

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

In Matrizen-Schreibweise lässt sich die Rekursionsformel für die Fibonacci-Zahlen so ausdrücken:

( \begin{matrix}f_{n+1} \\ f_{n} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}f_{n} \\ f_{n−1} \end{matrix} ) .

Mit der Abkürzung Q := ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) wird daher

( \begin{matrix}f_{n+1} \\ f_{n} \end{matrix} ) = Q ( \begin{matrix}f_{n} \\ f_{n−1} \end{matrix} ) = Q^{2} ( \begin{matrix}f_{n−1} \\ f_{n−2} \end{matrix} ) = … = Q^{n} ( \begin{matrix}f_{1} \\ f_{0} \end{matrix} ) ,

also

( \begin{matrix}f_{n+1} \\ f_{n} \end{matrix} ) = Q^{n} ( \begin{matrix}1 \\ 0 \end{matrix} ) .

Zur Berechnung von Q^{n} ( \begin{matrix}1 \\ 0 \end{matrix} ) ist es nützlich, die Eigenwerte und Eigenvekto-

ren von Q zu bestimmen. Dazu berechnen wir zunächst das charakteristische Polynom von Q.

χ_{Q}(λ) = det(Q − λE) = det ( \begin{matrix}1 − λ & 1 \\ 1 & −λ \end{matrix} ) = λ^{2} − λ − 1.

Die Nullstellen dieses Polynoms sind λ_{1/2} = \frac{1}{2} ± \frac{1}{2} \sqrt{5}. Wir führen folgende Bezeichnungen ein:

g := λ_{1} = \frac{1}{2} + \frac{1}{2} \sqrt{5},
g̃ := λ_{2} = \frac{1}{2} − \frac{1}{2} \sqrt{5}.

Es gilt

g + g̃ = 1 und g̃ = − \frac{1}{g} .

13. Fibonacci-Zahlen

13.1 Das Verhältnis g : 1 = 1 : (g−1) ≈ 1.618.. ist der berühmte goldene Schnitt. Die Eigenvektoren zum Eigenwert λ sind Lösungen der Gleichung (Q − λE)v = 0. Da

( \begin{matrix}1 − g & 1 \\ 1 & −g \end{matrix} ) ( \begin{matrix}g \\ 1 \end{matrix} ) = ( \begin{matrix}0 \\ 0 \end{matrix} ) und ( \begin{matrix}1 − g̃ & 1 \\ 1 & −g̃ \end{matrix} ) ( g̃ ; 1 ) = ( \begin{matrix}0 \\ 0 \end{matrix} ) ,

sind ( \begin{matrix}g \\ 1 \end{matrix} ) und ( g̃ ; 1 ) Eigenvektoren von Q zu den Eigenwerten g und g̃. Wir

stellen nun den Vektor ( \begin{matrix}1 \\ 0 \end{matrix} ) als Linearkombination der Eigenvektoren dar:

( \begin{matrix}1 \\ 0 \end{matrix} ) = c ( \begin{matrix}g \\ 1 \end{matrix} ) + c̃( g̃ ; 1 ) .

Die zweite Komponente liefert c̃ = −c. Eingesetzt in die erste Komponente ergibt sich

1 = cg − cg̃ = c(g − g̃) = c\sqrt{5} ⟹ c = \frac{1}{\sqrt{5}},

also

( \begin{matrix}1 \\ 0 \end{matrix} ) = \frac{1}{\sqrt{5}} ( \begin{matrix}g \\ 1 \end{matrix} ) − \frac{1}{\sqrt{5}} ( g̃ ; 1 ) .

Damit erhält man

( \begin{matrix}f_{n+1} \\ f_{n} \end{matrix} ) = Q^{n} ( \begin{matrix}1 \\ 0 \end{matrix} ) = \frac{1}{\sqrt{5}}(Q^{n} ( \begin{matrix}g \\ 1 \end{matrix} )−Q^{n} ( g̃ ; 1 )) = \frac{1}{\sqrt{5}}(g^{n} ( \begin{matrix}g \\ 1 \end{matrix} )−g̃^{n} ( g̃ ; 1 )).

Durch Betrachtung der zweiten Komponente dieser Gleichung ergibt sich folgende explizite Formel für die n-te Fibonacci-Zahl:

f_{n} = \frac{1}{\sqrt{5}}(g^{n} − g̃^{n}) = \frac{1}{\sqrt{5}}(g^{n} − (−1)^{n} \frac{1}{g^{n}}).

Da g ≈ 1.61.. und \sqrt{5} ≈ 2.23.., gilt für alle n ≥ 0

|\frac{1}{\sqrt{5}} · \frac{1}{g^{n}} | < \frac{1}{2} .

Da die Fibonacci-Zahlen ganz sind, können wir also auch schreiben

(∗)  f_{n} = round(\frac{g^{n}}{\sqrt{5}})

13.2 Dabei bedeutet round(x) für eine reelle Zahl x die nächstgelegene ganze Zahl. (Liegt x genau in der Mitte zwischen zwei ganzen Zahlen, so sei die Betrags-größere gewählt.) Beispielsweise ist

\frac{g^{10}}{\sqrt{5}} = 55.003636.. , \frac{g^{11}}{\sqrt{5}} = 88.997752.. ,

also f_{10} = 55, f_{11} = 89.

Wachstum der Fibonacci-Zahlen Mit der Formel (∗) lässt sich das Wachstum der Fibonacci-Zahlen leicht abschätzen. Logarithmieren zur Basis 10 ergibt

log_{10}(f_{n}) ≈ n log_{10}(g) − \frac{1}{2} log_{10} 5 ≈ 0.209n − 0.349 .

Die Anzahl der Dezimalstellen der n-ten Fibonacci-Zahl wächst also etwa linear mit n. Dies sei durch die folgenden Werte illustriert.

f_{25} = 75025,
f_{50} = 1 25862 69025,
f_{100} = 3 54224 84817 92619 15075,
f_{200} = 28 05711 72992 51014 00376 11932 41303 86771 89525.

Die Kenntnis des Wachstums der Fibonacci-Zahlen erlaubt eine Anwendung auf den Euklidischen Algorithmus.

Komplexität des Euklidischen Algorithmus Um den größten gemeinsamen Teiler zweier ganzer Zahlen x, y zu bestimmen, (o.B.d.A. sei x > y > 0), geht man wie folgt vor (vgl. §11): Man setze a_{0} := x, a_{1} := y und führe sukzessive Divisionen mit Rest durch.

a_{0} = q_{1}a_{1} + a_{2},  0 < a_{2} < a_{1},
a_{1} = q_{2}a_{2} + a_{3},  0 < a_{3} < a_{2},
⋮
a_{n−2} = q_{n−1}a_{n−1} + a_{n}, 0 < a_{n} < a_{n−1},
a_{n−1} = q_{n}a_{n} + 0.

Dann ist gcd(x, y) = a_{n}.

13.3 Wir wählen jetzt speziell x := f_{n+1} und y := f_{n}. Der Euklidische Algorithmus für dieses Zahlenpaar hat besonders einfache Gestalt:

f_{n+1} = 1 · f_{n} + f_{n−1},
f_{n} = 1 · f_{n−1} + f_{n−2},
⋮
f_{3} = 1 · f_{2} + f_{1},
f_{2} = 1 · f_{1} + 0.

Daraus ergibt zum einen, dass gcd(f_{n+1}, f_{n}) = 1, d.h. f_{n+1} und f_{n} sind teilerfremd. Andrerseits erhält man aber auch durch Vergleich mit dem allgemeinen Fall (da alle q_{i} ≥ 1), dass x ≥ f_{n+1}, falls der Euklidische Algorithmus für x > y > 0 nach n Schritten endet. Somit folgt

\frac{g^{n}}{\sqrt{5}} < x ⟹ n < (log x + \frac{1}{2} log 5)/ log(g) ≈ 2.08 log x,

also n = O(log x), d.h. die Anzahl der Schritte, die beim Euklidischen Algorithmus nötig sind, wächst höchstens linear mit dem Logarithmus der Eingabezahlen.

Schneller Algorithmus zur Berechnung von Potenzen Will man die Fibonacci-Zahlen durch Integer-Arithmetik mit der Formel

( \begin{matrix}f_{n+1} \\ f_{n} \end{matrix} ) = Q^{n} ( \begin{matrix}1 \\ 0 \end{matrix} ) berechnen, so erfordert die naive Methode n−1 Matri-

zen-Multiplikationen. Es gibt aber eine wesentlich schnellere Methode zur Berechnung von Potenzen. Dabei ist es gleichgültig, ob es sich um Potenzen von Matrizen oder von Zahlen handelt. Wir setzen also voraus, dass x ein Element eines beliebigen Ringes ist und x^{n} berechnet werden soll. Wir unterscheiden zwei Fälle:

a) n gerade,  n = 2m  ⟹ x^{n} = x^{2m} = (x^{m})^{2},
b) n ungerade, n = 2m + 1 ⟹ x^{n} = x^{2m+1} = (x^{m})^{2}x.

Damit wird die Berechnung von x^{n} auf die Berechnung von x^{m} mit m ≤ n/2 zurückgeführt. Durch rekursive Anwendung dieses Tricks erkennt man, dass man die Potenz x^{n} mit O(log n) Multiplikationen berechnen kann. Beispiel. Berechnung von x^{100}.

x^{100} = (x^{50})^{2}, x^{50} = (x^{25})^{2}, x^{25} = (x^{12})^{2}x,
x^{12} = (x^{6})^{2}, x^{6} = (x^{3})^{2}, x^{3} = x^{2}x.

13.4 Es sind also nur 8 statt 99 Multiplikationen nötig.

Bemerkung. Zur Implementation des Algorithmus ist die Binär-Entwicklung des Exponenten n nützlich. Sei also

n = ∑_{i=0}^{k} b_{i} · 2^{k−i} mit b_{i} ∈ {0, 1}, b_{0} = 1.

Mit n_{j} := ∑_{0}^{j} b_{i} · 2^{j−i} gilt dann n_{0} = 1, n_{k} = n und

n_{j+1} = 2n_{j} + b_{j+1} für j = 0, …, k − 1.

Setzt man P_{0} := x und

P_{i+1} := \{ \begin{matrix}P_{i}^{2} & falls b_{i+1} = 0, \\ P_{i}^{2}x & falls b_{i+1} = 1 \end{matrix}

für i = 0, …, k − 1, so gilt P_{i} = x^{n_{i}} für alle i, insbesondere P_{k} = x^{n}.

Anwendung auf die Fibonacci-Zahlen ergibt, dass man f_{n} mit O(log n) Multipliktionen berechnen kann. (Allerdings werden die zu multiplizierenden Zahlen immer größer.)

13.5