Lineare Differenzengleichung

Lineare Differenzengleichungen (auch lineare Rekursionsgleichungen, selten C-Rekursionen oder lineare Rekurrenz von engl. linear recurrence relation) sind Beziehungen einer besonders einfachen Form zwischen den Gliedern einer Folge.

Beispiel

Ein bekanntes Beispiel einer Folge, die einer linearen Differenzengleichung genügt, ist die Fibonacci-Folge. Mit der linearen Differenzengleichung

$f_n = f_{n-1} + f_{n-2} \quad$

und den Anfangswerten f₀ = 0 und f₁ = 1 ergibt sich die Folge

0, 1, 1, 2, 3, 5, 8, 13, … .

Jedes Folgenglied (abgesehen von den beiden Anfangswerten) ist also die Summe der beiden vorherigen.

Allgemein nennt man jede Gleichung der Form

$f_n = a_1 f_{n-1} + a_2 f_{n-2}, \quad a_2 \neq 0$

eine (homogene) lineare Differenzengleichung 2. Ordnung (mit konstanten Koeffizienten). Die Koeffizienten a₁ und a₂ definieren dabei die Differenzengleichung. Eine Folge $F = f_0, f_1, f_2, \dots$ die für alle f_i,i > 1 die Gleichung erfüllt, heißt Lösung der Differenzengleichung. Diese Lösungen sind durch die zwei Anfangswerte eindeutig definiert.

Die Fibonacci-Folge ist also eine Lösung der Differenzengleichung, die durch a₁ = a₂ = 1 definiert ist. Die Folge ist durch die Anfangswerte f₀ = 0 und f₁ = 1 eindeutig bestimmt.

Allgemeine Theorie

Eine Lineare Differenzengleichung k-ter Ordnung über einem Körper $\mathbb K$ ist von der Form

$\sum_{i=0}^k a_i(n)f_{n-i} = b(n),$

wobei $a_i(n)\in \mathbb K, a_k(n) \neq 0, n \in \mathbb{N}, n \geqq k$. Die lineare Differenzengleichung wird dabei von den Koeffizienten $a_0(n), a_1(n), \dots, a_k(n)$ und der Funktion b(n) definiert. Eine Zahlenfolge $F = f_0, f_1, f_2, \dots$, die für alle $n \geqq k$ die Gleichung erfüllt, heißt Lösung der Differenzengleichung. Diese unendliche Folge ist durch ihre k Anfangswerte $f_0, f_1, \dots, f_{k-1}$ eindeutig bestimmt. Ist b(n) = 0 für alle n, so heißt die Gleichung homogen, ansonsten heißt sie inhomogen. Die Zahlenfolge f_n = 0 für alle n erfüllt alle homogenen Gleichungen und heißt deshalb triviale Lösung.

Ohne Beschränkung der Allgemeinheit kann a₀ = − 1 angenommen werden. Damit erhält man eine alternative Darstellung, die die Berechnungsvorschrift für f_n aus den k vorhergehenden Werten anschaulicher verdeutlicht:

$f_n = a_1(n) f_{n-1} + a_2(n) f_{n-2} + \dots + a_k(n) f_{n-k} - b(n) = \sum_{i=1}^k a_i(n) f_{n-i} - b(n),$

wobei $a_i(n)\in \mathbb K, a_k(n) \neq 0, n \in \mathbb{N}, n \geqq k$.

Rechenregeln

• Sind F und G Lösungen der homogenen linearen Differenzengleichung $\textstyle \sum_{i=0}^k a_i(n)f_{n-i} = 0$, dann ist auch αF + βG für beliebige $\alpha , \beta \in \mathbb{R}$ eine Lösung.

• Sind F und G Lösungen der inhomogenen linearen Differenzengleichung $\textstyle \sum_{i=0}^k a_i(n)f_{n-i} = b(n)$, dann ist F − G eine Lösung der zugehörigen homogenen linearen Differenzgenleichung mit b(n) = 0 für alle $n \in \mathbb{N}$.

• Ist F eine Lösung der inhomogenen linearen Differenzengleichung $\textstyle \sum_{i=0}^k a_i(n)f_{n-i} = b(n)$ und G eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit b(n) = 0 für alle $n \in \mathbb{N}$, dann ist auch F + αG für beliebige $\alpha \in \mathbb{R}$ eine Lösung der inhomogenen linearen Differenzengleichung.

Lösungstheorie homogener linearer Differenzengleichungen 2. Ordnung

Die erste Idee zur Lösung besteht in der Beobachtung, dass derartige Folgen meist exponentiell wachsen. Das legt den ersten Ansatz f_n = λⁿ mit einem von Null verschiedenen Lambda nahe. Eingesetzt ergibt das

λⁿ = a₁λ^{n − 1} + a₂λ^{n − 2},

nach Division durch λ^{n − 2} also

λ² − a₁λ − a₂ = 0.

Diese quadratische Gleichung heißt charakteristische Gleichung der Rekursion. Folgen der Form f_n = λⁿ mit einem λ, das (reelle oder komplexe) Lösung der charakteristischen Gleichung ist, erfüllen also die gewünschte Rekursionsgleichung.

Die zweite Idee ist die der Superposition: Sind F und G Folgen, die die Rekursionsgleichung erfüllen, so gilt das auch für die Folge H mit

h_n = c₁f_n + c₂g_n

für beliebige (reelle oder komplexe) Zahlen c₁,c₂. Man kann das auch so ausdrücken: Die Menge aller Folgen, die die Rekursionsgleichung erfüllen, bildet einen Vektorraum.

Sind jetzt Anfangswerte f₀,f₁ gegeben, und hat die charakteristische Gleichung zwei verschiedene Lösungen λ₁,λ₂, so können die Koeffizienten c₁,c₂ aus dem folgenden linearen Gleichungssystem bestimmt werden:

$f_0 = c_1 \lambda_1^0 + c_2 \lambda_2^0 = c_1 + c_2$

$f_1 = c_1 \lambda_1^1 + c_2 \lambda_2^1 = c_1 \lambda_1 + c_2 \lambda_2$

Dann gilt $f_n = c_1 \lambda_1^n + c_2 \lambda_2^n$ für alle n.

Im Beispiel der Fibonacci-Folge sind

$\lambda_{1/2}=\frac{1\pm\sqrt5}2,\quad c_1=\frac1{\sqrt5}=-c_2,$

es ergibt sich also die so genannte Binet-Formel

$f_n=\frac1{\sqrt5}(\lambda_1^n - \lambda_2^n).$

Sonderfall: Die charakteristische Gleichung hat eine doppelte Lösung

Hat die charakteristische Gleichung nur eine Lösung, das heißt eine doppelte Nullstelle λ, so hat die allgemeine Lösung die Form

f_n = c₁λⁿ + c₂nλⁿ.

Beispielsweise erfüllt f_n = n (also c₁ = 0,c₂ = 1,λ = 1) die Rekursionsgleichung

f_n = 2f_{n − 1} − f_{n − 2}.

Lösung linearer Differenzengleichungen mit konstanten Koeffizienten

Eine lineare Differenzengleichung mit konstanten Koeffizienten hat die Form

$\sum_{i=0}^k a_i f_{n-i} = b(n),$

wobei alle a_i konstant sind.

Lösung der homogenen Gleichung

Mit dem Ansatz f_n = λⁿ wird eine nichttriviale Lösung der homogenen Gleichung $\textstyle \sum_{i=0}^k a_i f_{n-i} = 0$ ermittelt. Mit a₀ = − 1 führt dies auf die charakteristische Gleichung $\textstyle \lambda^k - \sum_{i=1}^k a_i \lambda^{k-i} = 0$. Die verschiedenen Nullstellen der Gleichung ergeben dann linear unabhängige Lösungsfolgen und damit Lösungen der homogenen Gleichung.

Sind die Nullstellen nicht verschieden, so kommt die zu einer mehrfachen Nullstelle gehörende Lösungsfolge mit einem Faktor in der Lösung vor, der ein Polynom in n mit einem Grad kleiner als die Vielfachheit der Nullstelle ist.

Beispiel:

3fn = − 2fn − 1 + 5fn − 2	Homogene Differenzengleichung
3λn + 2λn − 1 − 5λn − 2 = 0	Ansatz: fn = λn
3λ2 + 2λ − 5 = 0	Charakteristische Gleichung mit $\textstyle \lambda_{1/2} = - \frac{1}{3} \pm \frac{4}{3} = \left\{ -\frac{5}{3}, 1 \right\}$
$\textstyle f_n = c_1 \left(-\frac{5}{3}\right)^n + c_2 1^n$	Lösung der Gleichung als Linearkombination spezieller Lösungen. Die Konstanten c1 und c2 können aus zwei Anfangswerten von F, f0 und f1 bestimmt werden.

Partikuläre Lösung

Die Bestimmung geschieht hier analog zu Differentialgleichungen.

Störfunktion b(n)	Ansatz partikuläre Lösung
Konstante	Konstante
Polynom	Polynom gleichen Grades
un	$k \cdot u^n$
$\sin( \alpha \cdot n) , \cos( \alpha \cdot n)$	$A \cdot \sin( \alpha \cdot n) + B \cdot \cos( \alpha \cdot n)$

Falls der Ansatz bereits eine Lösung der zugehörigen homogenen Differenzengleichung sein sollte, ist er mit n,n²,n³ zu multiplizieren, bis er eine Lösung der inhomogenen Gleichung liefert.

Beispiel

Gegeben ist eine Folge F mit $f_0 = 2,\quad f_1 = 5,\quad f_n = 5 f_{n-1} - 6 f_{n-2} + (n-2)$. Gesucht ist die explizite Formel. Wir suchen zuerst die allgemeine Lösung für die homogene Rekursionsgleichung.

$f_n - 5 f_{n-1} + 6 f_{n-2} = n-2\,$	Inhomogene Rekursionsgleichung
$f_{\mathrm{homogen},n} - 5 f_{\mathrm{homogen},n-1} + 6 f_{\mathrm{homogen},n-2} = 0\,$	Homogene Rekursionsgleichung, Ansatz: fhomogen,n = λn
$\lambda^n - 5 \lambda^{n-1} + 6 \lambda^{n-2} = \lambda^{n-2} (\lambda^2 - 5 \lambda + 6) = 0\,$	Kürzen von λn − 2, Lösungen λ = 0 verfallen
$\lambda^2 - 5 \lambda + 6= 0\,$	Charakteristische Gleichung, Lösungen: λ1 = 2 und λ2 = 3
$f_{\mathrm{homogen},n} = c_1 \cdot 2^n + c_2 \cdot 3^n\,$	Allgemeine Lösung der homogenen Rekursionsgleichung

Nun suchen wir eine spezielle Lösung der inhomogenen Rekursionsgleichung, die partikuläre Lösung.

$f_n - 5 f_{n-1} + 6 f_{n-2} = n-2\,$

Inhomogene Rekursionsgleichung, Ansatz: fpartikulaer,n = c3n + c4

$c_3 n + c_4 - 5 (c_3 (n-1) + c_4) + 6 (c_3 (n-2) + c_4) = n-2\,$

$2 c_3 n - 7 c_3 + 2 c_4 = n-2\,$	Lösung durch Koeffizientenvergleich: $\textstyle c_3 = \frac{1}{2}, c_4 = \frac{3}{4}$
$\textstyle f_{\mathrm{partikulaer},n} = \frac{1}{2}n + \frac{3}{4}$	Partikuläre Lösung

Gemäß den obigen Rechenregeln erhalten wir mit $\textstyle f_n = f_{\mathrm{homogen},n} + f_{\mathrm{partikulaer},n} = c_1 \cdot 2^n + c_2 \cdot 3^n + \frac{1}{2} n + \frac{3}{4}$ alle Lösungen der inhomogenen Rekursionsgleichung. Nun müssen c₁ und c₂ noch so bestimmt werden, dass f₀ = 2 und f₁ = 5 gilt.

	$\textstyle c_1 \cdot 2^n + c_2 \cdot 3^n + \frac 1 2 n + \frac 3 4 = f_n$
n = 0:	$\textstyle c_1 + c_2 + \frac 3 4 = 2$
n = 1:	$\textstyle c_1 \cdot 2 + c_2 \cdot 3 + \frac 5 4 = 5$
	$\textstyle \Rightarrow c_1 = 0, c_2 = \frac{5}{4}$

Also ist $\textstyle f_n = \frac 5 4 \cdot 3^n + \frac 1 2 \cdot n + \frac 3 4$ die gesuchte Formel.

Siehe auch

• Differenzengleichung
• Erzeugende Funktion
• Rekursion
• Folge
• Gewöhnliche Differentialgleichung

Literatur

• Berg, L.: Lineare Gleichungssysteme mit Bandstruktur, München-Wien: Carl Hanser, 1986
• Ian Jaques. Mathematics for Economics and Business, Fifth Edition, Prentice Hall, 2006 (Kapitel 9.1 Difference Equations)

 Wikibooks: Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen – Lern- und Lehrmaterialien