aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/040-rekursion/linear.tex
blob: a3ff0c292a06f665fe157541166a8106d74251c0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
%
% linear.tex
%
% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
%
\section{Lineare Rekursionsgleichung mit konstanten Koeffizienten
\label{buch:rekursion:section:linear}}
\rhead{Lineare Rekursionsgleichungen}
Die Funktionalgleichung der Gamma-Funktion, die im
Abschnitt~\ref{buch:rekursion:section:gamma} untersucht wurde,
hat die Form einer linearen Rekursionsgleichung
\[
\Gamma(x+1) = x\Gamma(x),\qquad \Gamma(1) = 1.
\]
Gleichungen, die Werte einer Funktion für verschiedene
Argument in Beziehung setzen, heissen {\em Funktionalgleichungen}.
\index{Funktionalgleichung}%
Es war überraschend schwierig, eine Lösung für Funktionalgleichung
der Gamma-Funktion für beliebige komplexe $x$ zu finden.
In diesem Abschnitt soll daher eine Klasse von Rekursionsgleichungen
näher untersucht werden, für die einfache Lösungen möglich sind.

\subsection{Lineare Differenzengleichungen}
Die Fibonacci-Zahlen sind definiert durch die lineare Rekursionsgleichung
\begin{equation}
F_{n+1\mathstrut} = F_{n\mathstrut} + F_{n-1\mathstrut},
\qquad
F_1=1,\quad F_0=0.
\label{buch:rekursion:eqn:fibonacci}
\end{equation}
Ganz ähnlich wie bei der Gamma-Funktion kann man auch hier die Frage
stellen, ob es eine Funktion $F(z)$ von komplexen Argument gibt derart,
dass
\begin{equation}
F(z+1) = F(z) + F(z-1), \qquad F(1)=1,\quad F(0)=0.
\label{buch:rekursion:eqn:fibonaccikomplex}
\end{equation}

\begin{aufgabe}
Gibt es eine Funktion
\[
F(z) = \sum_{k=0}^\infty a_k (z-z_0)^k
\]
derart, dass
\[
F(z+1) = F(z)+F(z-1)?
\]
\end{aufgabe}

Sind $F_1(z)$ und $F_2(z)$ Lösungen der Differenzengleichung, dann
sind beliebige Linearkombinationen $\lambda F_1(z) + \mu F_2(z)$
ebenfalls Lösungen.
Ausserdem ist $e^{2k\pi i}F(z)$ eine Lösung der Differenzengleichung,
es gibt also unendlich viele linear unabhängige Lösungen.

\subsection{Lösung mit Exponentialfunktionen}
Gesucht ist eine ganze Funktion, also eine Funktion
$F\colon\mathbb{C}\to\mathbb{C}$, die Lösung einer
Differenzengleichung
\begin{equation}
\sum_{k=0}^n a_kF(z+n)=0,
\end{equation}
mit $a_n\ne 1$.
ist.
Ein erfolgversprechender Ansatz ist $F(z)=e^{bz}=(e^b)^z$, da die
Exponentialfunktion eine ganze Funktion ist.
Die Differenzengleichung führt auf
\[
0
=
\sum_{k=0}^n
a_kF(z+n)
=
\sum_{k=0}^n
a_k e^{b(z+n)}
=
e^{bz}
\sum_{k=0}^n
a_k (e^b)^n.
\]
Gesucht ist also $a\in\mathbb{C}$ derart, dass $e^a$ eine Nullstelle
des charakteristischen Polynomes
\[
p(x) = \sum_{k=0}^n a_kx^k
\]
der Differenzengleichung ist.
Die Zahl $a$ ist nicht eindeutig, denn wenn $e^a$ eine Nullstelle ist,
dann ist $e^{a+2\pi i}=e^a$ eine Nullstelle.
Dies sind die einzigen Lösungen der Differenzengleichung.

Seien also $\lambda_j$ die Nullstellen von $p(x)$ mit $1\le j\le n$.
Dann gibt es komplexe Zahlen $b_j$ 
mit $-\pi < \operatorname{Im}b_j < \pi$ derart, dass $e^{b_j}=\lambda_j$.
Die Funktionen
\[
F_{jk}(z) = e^{2k\pi i z} e^{b_jz}
\]
sind Lösungen der Differenzengleichung.

\subsection{Komplexe Fibonacci-Zahlen}
Matt Parker vom Youtube-Kanal Stand-up Maths hat in einem
Video\footnote{\url{https://youtu.be/ghxQA3vvhsk}} die Lösungsfunktionen
für die Differenzengleichung der Fibonacci-Zahlen für beliebige
reelle und komplexe Argumente visualisiert.
Die Nullstellen des charakteristischen Polynoms
\[
\lambda^2-\lambda-1=0
\qquad
\Rightarrow
\qquad
\lambda_\pm = \begin{cases}
\displaystyle
\frac{\sqrt{5}+1}{2}=\varphi
\\[8pt]
\displaystyle
\frac{\sqrt{5}-1}{2}=\frac{1}{\varphi},
\end{cases}
\]
dabei ist $\varphi$ das Verhältnis des goldenen Schnittes.
Die Anfangsbedingungen $F(0)=0$ und $F(1)=1$ bedeutet, dass
\[
F(z) = \varphi^z - \frac{1}{\varphi^z}
\]
Dies ist die Funktion, die Matt Parker visualisiert hat.
Allerdings sind die Funktionen
\[
F_{kl}(z)
=
\varphi^ze^{2k\pi iz}
-
\frac{1}{\varphi^z} e^{2l\pi z}
\]
ebenfalls Lösungen der Differenzengleichung mit den gleichen 
Anfangswerten.