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}}

und den Anfangswerten f_{0}=0 und f_{1}=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

{\displaystyle 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_{1} und a_2 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_{1}=a_{2}=1 definiert ist. Die Folge ist durch die Anfangswerte f_{0}=0 und f_{1}=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\geq 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 \geq 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_{0}=-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\geq k.

Rechenregeln

Lösungstheorie homogener linearer Differenzengleichungen 2. Ordnung mit konstanten Koeffizienten

Die erste Idee zur Lösung besteht in der Beobachtung, dass derartige Folgen meist exponentiell wachsen. Das legt den ersten Ansatz f_{n}=\lambda ^{n} mit einem von Null verschiedenen Lambda nahe. Eingesetzt ergibt das

{\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+a_{2}\lambda ^{n-2},}

nach Division durch \lambda ^{{n-2}} also

{\displaystyle \lambda ^{2}-a_{1}\lambda -a_{2}=0.}

Diese quadratische Gleichung heißt charakteristische Gleichung der Rekursion. Folgen der Form f_{n}=\lambda ^{n} mit einem \lambda , 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

{\displaystyle h_{n}=c_{1}f_{n}+c_{2}g_{n}}

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

Sind jetzt Anfangswerte f_{0},f_{1} gegeben, und hat die charakteristische Gleichung zwei verschiedene Lösungen \lambda_1, \lambda_2, so können die Koeffizienten c_1, c_2 aus dem folgenden linearen Gleichungssystem bestimmt werden:

{\displaystyle f_{0}=c_{1}\lambda _{1}^{0}+c_{2}\lambda _{2}^{0}=c_{1}+c_{2}}
{\displaystyle f_{1}=c_{1}\lambda _{1}^{1}+c_{2}\lambda _{2}^{1}=c_{1}\lambda _{1}+c_{2}\lambda _{2}}

Dann gilt {\displaystyle 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 {\sqrt  5}}2},\quad c_{1}={\frac  1{{\sqrt  5}}}=-c_{2},

es ergibt sich also die sogenannte Binet-Formel

f_{n}={\frac  1{{\sqrt  5}}}(\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 \lambda , so hat die allgemeine Lösung die Form

{\displaystyle f_{n}=c_{1}\lambda ^{n}+c_{2}n\lambda ^{n-1}.}

Beispielsweise erfüllt f_{n}=n (also c_{1}=0,c_{2}=1,\lambda =1) die Rekursionsgleichung

{\displaystyle 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_{j}=\lambda ^{j} wird eine nichttriviale Lösung der homogenen Gleichung \textstyle \sum _{{i=0}}^{k}a_{i}f_{{n-i}}=0 ermittelt. a_{0} sei o. B. d. A. gleich -1. Dies führt auf die charakteristische Gleichung {\displaystyle \textstyle \lambda ^{n}-\sum _{i=1}^{k}a_{i}\lambda ^{n-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:

3f_{n}=-2f_{{n-1}}+5f_{{n-2}} Homogene Differenzengleichung
3\lambda ^{n}+2\lambda ^{{n-1}}-5\lambda ^{{n-2}}=0 Ansatz: f_{j}=\lambda ^{j}
3\lambda ^{2}+2\lambda -5=0 Charakteristische Gleichung mit \textstyle \lambda _{{1{,}2}}=-{\frac  {1}{3}}\pm {\frac  {4}{3}}\in \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 c_{1} und c_{2} können aus zwei Anfangswerten von F, f_{0} und f_{1} 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
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 der Ansatz bereits eine Lösung der zugehörigen homogenen Differenzengleichung sein sollte, ist er mit {\displaystyle n,n^{2},n^{3}} zu multiplizieren, bis er eine Lösung der inhomogenen Gleichung liefert.

Beispiel

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

{\displaystyle f_{n}-5f_{n-1}+6f_{n-2}=n-2} Inhomogene Rekursionsgleichung
{\displaystyle f_{\mathrm {homogen} ,n}-5f_{\mathrm {homogen} ,n-1}+6f_{\mathrm {homogen} ,n-2}=0} Homogene Rekursionsgleichung, Ansatz: f_{{{\mathrm  {homogen}},n}}=\lambda ^{n}
{\displaystyle \lambda ^{n}-5\lambda ^{n-1}+6\lambda ^{n-2}=\lambda ^{n-2}(\lambda ^{2}-5\lambda +6)=0} Kürzen von \lambda ^{{n-2}}, Lösungen \lambda =0 verfallen
{\displaystyle \lambda ^{2}-5\lambda +6=0} Charakteristische Gleichung, Lösungen: \lambda _{1}=2 und \lambda _{2}=3
{\displaystyle 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.

{\displaystyle f_{n}-5f_{n-1}+6f_{n-2}=n-2} Inhomogene Rekursionsgleichung, Ansatz: f_{{{\mathrm  {partikulaer}},n}}=c_{3}n+c_{4}
{\displaystyle c_{3}n+c_{4}-5(c_{3}(n-1)+c_{4})+6(c_{3}(n-2)+c_{4})=n-2}
{\displaystyle 2c_{3}n-7c_{3}+2c_{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_{1} und c_{2} noch so bestimmt werden, dass f_{1}=5 gilt.

  \textstyle c_{1}\cdot 2^{n}+c_{2}\cdot 3^{n}+{\frac  12}n+{\frac  34}=f_{n}
n = 0: \textstyle c_{1}+c_{2}+{\frac  34}=2
n=1: \textstyle c_{1}\cdot 2+c_{2}\cdot 3+{\frac  54}=5
  \textstyle \Rightarrow c_{1}=0,c_{2}={\frac  {5}{4}}

Also ist \textstyle f_{n}={\frac  54}\cdot 3^{n}+{\frac  12}\cdot n+{\frac  34} die gesuchte Formel.

Siehe auch

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 18.06. 2018