Kategorie: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.

Allgemeine Theorie Eine allgemeine lineare Differenzengleichung ${\displaystyle k}$-ter Ordnung über einem Körper ${\displaystyle \mathbb {K} }$ ist von der Form

${\displaystyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n),}$

wobei ${\displaystyle a_{i}(n)\in \mathbb {K} ,a_{0}(n)\neq 0,n\in \mathbb {N} ,n\geq k}$. Die lineare Differenzengleichung wird dabei von den Koeffizienten-Funktionen ${\displaystyle a_{0},a_{1},\dots ,a_{k}\colon \mathbb {N} _{\geq k}\rightarrow \mathbb {K} }$ und der Funktion ${\displaystyle b\colon \mathbb {N} _{\geq k}\rightarrow \mathbb {K} }$ charakterisiert.

Ohne Beschränkung der Allgemeinheit kann ${\displaystyle a_{0}(n)=-1}$ angenommen werden; das sieht man, weil man alle Koeffizienten und ${\displaystyle b(n)}$ einfach durch ${\displaystyle -a_{0}(n)\neq 0}$ teilen kann. Nach Umstellen erhält man eine alternative Darstellung, die die Berechnungsvorschrift für ${\displaystyle f_{n}}$ aus den ${\displaystyle k}$ vorhergehenden Werten anschaulicher verdeutlicht:

${\displaystyle f_{n}=a_{1}(n)f_{n-1}+\dots +a_{k}(n)f_{n-k}-b(n),}$

wobei ${\displaystyle a_{i}(n)\in \mathbb {K} ,n\in \mathbb {N} ,n\geq k}$, also

${\displaystyle f_{n}=c(n)+\sum _{i=1}^{k}a_{i}(n)f_{n-i},}$

wenn man ${\displaystyle c(n):=-b(n)}$ setzt.

Eine Zahlenfolge ${\displaystyle F=(f_{0},f_{1},f_{2},\dots )}$, die für alle ${\displaystyle n\geq k}$ die Gleichung erfüllt, heißt Lösung der Differenzengleichung. Offenbar ist eine Lösung durch ihre ${\displaystyle k}$ Anfangswerte ${\displaystyle f_{0},f_{1},\dots ,f_{k-1}}$ also eindeutig bestimmt – das kann man aus der alternativen Form direkt ablesen. Ist ${\displaystyle b(n)=0}$ für alle ${\displaystyle n\geq k}$, so heißt die Gleichung Gleichungen homogen, ansonsten heißt sie inhomogen. Die Zahlenfolge ${\displaystyle f_{n}=0}$ für alle ${\displaystyle n}$ erfüllt alle homogenen Gleichungen und heißt deshalb triviale Lösung.

Rechenregeln

• Sind ${\displaystyle F}$ und ${\displaystyle G}$ Lösungen der homogenen linearen Differenzengleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=0}$, dann ist auch ${\displaystyle \alpha F+\beta G}$ für beliebige ${\displaystyle \alpha ,\beta \in \mathbb {K} }$ eine Lösung.
• Sind ${\displaystyle F}$ und ${\displaystyle G}$ Lösungen der inhomogenen linearen Differenzengleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n)}$, dann ist ${\displaystyle F-G}$ eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit ${\displaystyle b(n)=0}$ für alle ${\displaystyle n\geq k}$.
• Ist ${\displaystyle F}$ eine Lösung der inhomogenen linearen Differenzengleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n)}$ und ${\displaystyle G}$ eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit ${\displaystyle b(n)=0}$ für alle ${\displaystyle n\geq k}$, dann ist auch ${\displaystyle F+\alpha G}$ für beliebige ${\displaystyle \alpha \in \mathbb {K} }$ eine Lösung der inhomogenen linearen Differenzengleichung.

${\displaystyle [*]}$ Exzerpt aus dem Originalartikel Lineare Differenzengleichung