Lineare Differenzengleichung

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Lineare Differenzengleichungen oder lineare Rekursionsgleichungen sind Beziehungen einer besonders einfachen Form zwischen den Gliedern einer Folge. Das bekannteste Beispiel ist die Fibonacci-Folge

$f_0 = 0,\quad f_1 = 1,\quad f_{n+1} = f_n + f_{n-1},$

konkret

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

Jedes Folgenglied ist also die Summe der beiden vorherigen.

Allgemein nennt man jede Gleichung der Form

a n + 1 = u a n + v a n - 1

eine (homogene) lineare Differenzengleichung 2. Ordnung (mit konstanten Koeffizienten).

Inhaltsverzeichnis

1 Lösungstheorie homogener linearer Differenzengleichungen 2. Ordnung
- 1.1 Sonderfall: die charakteristische Gleichung hat eine doppelte Lösung
2 Allgemeine Theorie
- 2.1 Rechenregeln
- 2.2 Lösung linearer Differenzengleichungen mit konstanten Koeffizienten
  - 2.2.1 Lösung der homogenen Gleichung
  - 2.2.2 Partikuläre Lösung
3 Siehe auch
4 Literatur

[Bearbeiten] 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 $a n = λ n$ nahe. Eingesetzt ergibt das

λ n + 1 = u λ n + v λ n - 1,

nach Division durch $λ n - 1$ also

λ 2 - u λ - v = 0.

Diese quadratische Gleichung heißt charakteristische Gleichung der Rekursion. Folgen der Form $a n = λ 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 Linearkombination: Sind $a n$ und $b n$ Folgen, die die Rekursionsgleichung erfüllen, so gilt das auch für

c n = x a n + y b n

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

Sind jetzt Anfangswerte $a 0, a 1$ gegeben, und hat die charakteristische Gleichung zwei verschiedene Lösungen $λ 1,λ 2$ , so können die Koeffizienten $x, y$ aus dem folgenden linearen Gleichungssystem bestimmt werden:

$a_0 = x\lambda_1^0 + y\lambda_2^0 = x + y$

$a_1 = x\lambda_1^1 + y\lambda_2^1 = x\lambda_1 + y\lambda_2$

Dann gilt $a_n = x\lambda_1^n + y\lambda_2^n$ für alle $n$ .

Im Beispiel der Fibonacci-Folge sind

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

es ergibt sich also die so genannte Binet-Formel

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

[Bearbeiten] Sonderfall: die charakteristische Gleichung hat eine doppelte Lösung

Hat die charakteristische Gleichung nur eine, doppelte Lösung, so hat die allgemeine Lösung die Form

a n = x λ n + y n λ n .

Beispielsweise erfüllt $a n = n$ (also $x = 0, y = 1,λ = 1$ ) die Rekursionsgleichung

a n + 1 = 2 a n - a n - 1 .

[Bearbeiten] Allgemeine Theorie

Eine Lineare Differenzengleichung k-ter Ordnung besitzt allgemein die Form:

$a k (n) f (n + k) + a k - 1 (n) f (n + k - 1) + ... + a 0 (n) f (n) = b (n)$

Ist die rechte Seite b(n) = 0 für alle $n \in \mathbb{N}$ , dann ist die Gleichung homogen. Ansonsten ist sie inhomogen.

[Bearbeiten] Rechenregeln

[Bearbeiten] Satz 1

Sind f₁ und f₂ Lösungen der homogenen linearen Differenzgleichung $a k (n) f (n + k) + a k - 1 (n) f (n + k - 1) + ... + a 0 (n) f (n) = 0$ , dann ist auch $α f 1 + β f 2$ für beliebige $\alpha , \beta \in \mathbb{R}$ eine Lösung.

[Bearbeiten] Satz 2

Sind f₁ und f₂ Lösungen der inhomogenen linearen Differenzgleichung $a k (n) f (n + k) + a k - 1 (n) f (n + k - 1) + ... + a 0 (n) f (n) = b (n)$ , dann ist f₁ - f₂ eine Lösung der zugehörigen homogenen linearen Differenzgleichung mit b(n) = 0 für alle $n \in \mathbb{N}$ .

[Bearbeiten] Satz 3

Ist f₁ eine Lösung der inhomogenen linearen Differenzgleichung $a k (n) f (n + k) + a k - 1 (n) f (n + k - 1) + ... + a 0 (n) f (n) = b (n)$ und f₂ eine Lösung der zugehörigen homogenen linearen Differenzgleichung mit b(n) = 0 für alle $n \in \mathbb{N}$ , dann ist auch $f 1 + α f 2$ für beliebige $\alpha \in \mathbb{R}$ eine Lösung der inhomogenen linearen Differenzgleichung.

[Bearbeiten] Lösung linearer Differenzengleichungen mit konstanten Koeffizienten

Eine lineare Differenzengleichung mit konstanten Koeffizienten hat die Form $a k f (n + k) + a k - 1 f (n + k - 1) + ... + a 0 f (n) = b (n)$ . Alle a_i sind konstant.

[Bearbeiten] Lösung der homogenen Gleichung

Mit dem Ansatz $f (n) = λ n$ wird eine Lösung der homogenen Gleichung $a k f (n + k) + a k - 1 f (n + k - 1) + ... + a 0 f (n) = 0$ ermittelt.

Dies führt auf die charakteristische Gleichung $a_k \cdot {\lambda}^k + a_{k-1} \cdot {\lambda}^{k-1} + a_{k-2} \cdot {\lambda}^{k-2} + ... + a_1 \cdot {\lambda} + a_0 = 0$

Die verschiedenen Nullstellen der Gleichung ergeben dann die linear unabhängigen Lösungsfolgen und damit eine homogene Lösung.

Sind die Nullstellen nicht verschieden, so kommt die zu dieser Nullstelle gehörende Lösungsfolge nicht mit einem konstanten Faktor in der Lösung vor, sondern als Vielfaches eines Polynoms in n, dessen Grad um 1 kleiner ist als die Vielfachheit der Nullstelle.

Beispiel:

$3 \cdot x_n + 2 \cdot x_{n-1} - 5 \cdot x_{n-2} = 0$	homogene Differenzengleichung
$3 \cdot \lambda^n + 2 \cdot \lambda^{n-1} - 5 \cdot \lambda^{n-2} = 0$	Ansatz: $x_n = c \cdot \lambda^n$
$3 \cdot \lambda^2 + 2 \cdot \lambda - 5 = 0$	charakteristische Gleichung mit $\lambda_{1/2} = - \frac{1}{3} \pm \frac{4}{3}$
$x_n = c_1 \cdot \left(-\frac{5}{3}\right)^n + c_2$	Lösung der Gleichung als Linearkombination der Lösungen, Konstanten können aus Anfangsbedingungen bestimmt werden.

[Bearbeiten] Partikuläre Lösung

Die Bestimmung geschieht hier analog zu Differentialgleichungen.

Störfunktion u(n)	Ansatz partikuläre Lösung
Konstante	Konstante
Polynom	Polynom gleichen Grades
$u n$	$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 das Einsetzen des Ansatzes in die Differenzengleichung ein Ergebnis der Art $0 = 0$ liefert, ist der Ansatz mit $n, n 2, n 3$ zu multiplizieren, bis er nicht mehr $0 = 0$ liefert.