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 𝕂}$ ist von der Form

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

wobei ${\displaystyle a_i(n)\in 𝕂,a_0(n)\ne 0,n\in \mathbb{N},n\ge k}$. Die lineare Differenzengleichung wird dabei von den Koeffizienten-Funktionen ${\displaystyle a_0,a_1,\dots ,a_k:{\mathbb{N}}_{\ge k}\to 𝕂}$ und der Funktion ${\displaystyle b:{\mathbb{N}}_{\ge k}\to 𝕂}$ 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)\ne 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 𝕂,n\in \mathbb{N},n\ge 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\ge 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\ge 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 {\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 𝕂}$ eine Lösung.
• Sind ${\displaystyle F}$ und ${\displaystyle G}$ Lösungen der inhomogenen linearen Differenzengleichung ${\displaystyle {\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\ge k}$.
• Ist ${\displaystyle F}$ eine Lösung der inhomogenen linearen Differenzengleichung ${\displaystyle {\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\ge k}$, dann ist auch ${\displaystyle F+\alpha G}$ für beliebige ${\displaystyle \alpha \in 𝕂}$ eine Lösung der inhomogenen linearen Differenzengleichung.

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