imported>PurpleXanadu: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-09-17T06:50:56Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

'''Lineare [[Differenzengleichung]]en''' (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 (Mathematik)|Folge]].

== Beispiel ==
Ein bekanntes Beispiel einer Folge, die einer linearen Differenzengleichung genügt, ist die [[Fibonacci-Folge]].
Mit der linearen Differenzengleichung
: <math>f_n = f_{n-1} + f_{n-2} \quad (n = 2,3,4,\dots)</math>
und den Anfangswerten <math>f_0 = 0</math> und <math>f_1 = 1</math>
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
: <math>f_n = a_1 f_{n-1} + a_2 f_{n-2}</math>
mit gegebenen Koeffizienten <math>a_1</math> und <math>a_2</math> eine (homogene) ''lineare Differenzengleichung 2. Ordnung'' (mit konstanten Koeffizienten). Eine Folge <math>F = (f_0, f_1, f_2, \dots),</math> welche die Gleichung für <math>n = 2,3,4,\dots</math> 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 <math>a_1 = a_2 = 1</math> definiert ist. Die Folge ist durch die Anfangswerte <math>f_0 = 0</math> und <math>f_1 = 1</math> eindeutig bestimmt.

== Allgemeine Theorie ==
Eine allgemeine lineare Differenzengleichung <math>k</math>-ter Ordnung über einem Körper <math>\mathbb K</math> ist von der Form
: <math> \sum_{i=0}^k a_i(n)f_{n-i} = b(n),</math>
wobei <math>a_i(n)\in \mathbb K, a_0(n) \neq 0, n \in \mathbb{N}, n \geq k</math>. Die lineare Differenzengleichung wird dabei von den Koeffizienten-Funktionen <math>a_0, a_1, \dots, a_k\colon\mathbb{N}_{\geq k}\rightarrow\mathbb{K}</math> und der Funktion <math>b\colon\mathbb{N}_{\geq k}\rightarrow\mathbb{K}</math> charakterisiert.

[[Ohne Beschränkung der Allgemeinheit]] kann <math>a_0(n) = -1</math> angenommen werden; das sieht man, weil man alle Koeffizienten und <math>b(n)</math> einfach durch <math>-a_0(n)\neq0</math> teilen kann. Nach Umstellen erhält man eine alternative Darstellung, die die Berechnungsvorschrift für <math>f_n</math> aus den <math>k</math> vorhergehenden Werten anschaulicher verdeutlicht:
: <math>f_n = a_1(n) f_{n-1} + \dots + a_k(n) f_{n-k} - b(n),</math>
wobei <math>a_i(n)\in \mathbb K, n \in \mathbb{N}, n \geq k</math>, also
: <math>f_n = c(n) + \sum_{i=1}^k a_i(n) f_{n-i},</math>
wenn man <math>c(n):=-b(n)</math> setzt.

Eine Zahlenfolge <math>F = (f_0, f_1, f_2, \dots)</math>, die für alle <math>n \geq k</math> die Gleichung erfüllt, heißt ''Lösung der Differenzengleichung.'' Offenbar ist eine Lösung durch ihre <math>k</math> Anfangswerte <math>f_0, f_1, \dots, f_{k-1}</math> also eindeutig bestimmt – das kann man aus der alternativen Form direkt ablesen. Ist <math>b(n) = 0</math> für alle <math>n \geq k</math>, so heißt die Gleichung ''[[Gleichung#Homogene Gleichungen|homogen]],'' ansonsten heißt sie ''inhomogen.'' Die Zahlenfolge <math>f_n = 0</math> für alle <math>n</math> erfüllt alle homogenen Gleichungen und heißt deshalb ''triviale Lösung.''

=== Rechenregeln ===
* Sind <math>F</math> und <math>G</math> Lösungen der ''homogenen'' linearen Differenzengleichung <math>\textstyle \sum_{i=0}^k a_i(n)f_{n-i} = 0</math>, dann ist auch <math>\alpha F + \beta G</math> für beliebige <math>\alpha , \beta \in \mathbb{K}</math> eine Lösung.
* Sind <math>F</math> und <math>G</math> Lösungen der ''inhomogenen'' linearen Differenzengleichung <math>\textstyle \sum_{i=0}^k a_i(n)f_{n-i} = b(n)</math>, dann ist <math>F - G</math> eine Lösung der zugehörigen ''homogenen'' linearen Differenzengleichung mit <math>b(n) = 0</math> für alle <math>n \geq k</math>.
* Ist <math>F</math> eine Lösung der ''inhomogenen'' linearen Differenzengleichung <math>\textstyle \sum_{i=0}^k a_i(n)f_{n-i} = b(n)</math> und <math>G</math> eine Lösung der zugehörigen ''homogenen'' linearen Differenzengleichung mit <math>b(n) = 0</math> für alle <math>n \geq k</math>, dann ist auch <math>F + \alpha G</math> für beliebige <math>\alpha \in \mathbb{K}</math> eine Lösung der ''inhomogenen'' linearen Differenzengleichung.

== Lösungstheorie homogener linearer Differenzengleichungen 2. Ordnung mit konstanten Koeffizienten ==
=== Ansatz mit einer geometrischen Folge ===
Die erste Idee zur Lösung besteht in der Beobachtung, dass derartige Folgen meist [[exponentiell]] wachsen. Das legt den ersten Ansatz <math> f_n = \lambda^n </math> mit einem festen <math>\lambda \in \mathbb K</math> nahe. Eingesetzt ergibt das
: <math>\lambda^{n} = a_1 \lambda^{n-1} + a_2 \lambda^{n-2} \quad (n = 2,3,4,\dots),</math>
d. h.
: <math>\lambda^2 - a_1\lambda - a_2 = 0.</math>
Diese [[quadratische Gleichung]] heißt ''charakteristische Gleichung'' der [[Rekursion]]. Folgen der Form <math>f_n = \lambda^n</math> mit einem <math>\lambda</math>, das Lösung der charakteristischen Gleichung ist, erfüllen also die gewünschte Rekursionsgleichung.

=== Ansatz mit Hilfe des Superpositionsprinzips ===
Die zweite Idee ist die der [[Superposition (Mathematik)|Superposition]]: Sind <math>F</math> und <math>G</math> Folgen, die die Rekursionsgleichung erfüllen, so gilt das auch für die Folge <math>H</math> mit
: <math>h_n = c_1 f_n + c_2 g_n</math>
mit beliebigen Konstanten <math>c_1, c_2 \in \mathbb K</math>. Man kann das auch so ausdrücken: Die Menge aller Folgen, die die Rekursionsgleichung erfüllen, bildet einen [[Vektorraum]] über <math>\mathbb K</math>.

Sind jetzt Anfangswerte <math>f_0, f_1</math> gegeben, und hat die charakteristische Gleichung zwei verschiedene Lösungen <math>\lambda_1, \lambda_2</math>, so können die Koeffizienten <math>c_1, c_2</math> aus dem folgenden [[Lineares Gleichungssystem|linearen Gleichungssystem]] bestimmt werden:
: <math>f_0 = c_1 \lambda_1^0 + c_2 \lambda_2^0 = c_1 + c_2</math>
: <math>f_1 = c_1 \lambda_1^1 + c_2 \lambda_2^1 = c_1 \lambda_1 + c_2 \lambda_2</math>
Dann gilt <math>f_n = c_1 \lambda_1^n + c_2 \lambda_2^n</math> für alle <math>n</math>.

Im Beispiel der Fibonacci-Folge sind
: <math>\lambda_{1/2}=\frac{1\pm\sqrt5}2,\quad c_1=\frac1{\sqrt5}=-c_2,</math>
es ergibt sich also die sogenannte Binet-Formel
: <math>f_n=\frac1{\sqrt5}(\lambda_1^n - \lambda_2^n).</math>

=== Sonderfall: Die charakteristische Gleichung hat eine doppelte Lösung ===
Hat die charakteristische Gleichung nur eine Lösung, das heißt eine doppelte Nullstelle <math>\lambda,</math> so wird die homogene Differenzengleichung auch von der Folge <math>\big(n\lambda^{n-1}\big)</math> gelöst (diese beginnt mit <math>0\lambda^{-1} = 0,</math> was für <math>\lambda = 0</math> noch so festgelegt sei). Die allgemeine Lösung hat die Form
:<math>f_n = c_1 \lambda^n + c_2 n \lambda^{n-1}.</math>
Beispielsweise erfüllt <math>f_n = n</math> (also <math>c_1=0, c_2=1,\lambda=1</math>) die Rekursionsgleichung
: <math>f_n = 2 f_{n-1} - f_{n-2}.</math>

== Lösung linearer Differenzengleichungen mit konstanten Koeffizienten ==
Eine lineare Differenzengleichung mit konstanten Koeffizienten hat die Form
:<math>\sum_{i=0}^k a_i f_{n-i} = b(n),</math>
wobei alle <math>a_i</math> konstant sind.

=== Lösung der homogenen Gleichung ===
Mit dem Ansatz <math>f_n = \lambda^n</math> wird eine nichttriviale Lösung der homogenen Gleichung
<math>\textstyle \sum_{i=0}^k a_i f_{n-i} = 0</math> ermittelt. <math>a_0</math> sei [[o. B. d. A.]] gleich <math>-1</math>. Dies führt auf die charakteristische Gleichung <math>\textstyle \lambda^n - \sum_{i=1}^k a_i \lambda^{n-i} = 0</math>. Die verschiedenen [[Nullstelle]]n 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 <math>n</math> mit einem Grad kleiner als die Vielfachheit der Nullstelle ist.

''Beispiel:''
{| cellpadding="5"
|-
|<math>3 f_n = -2 f_{n-1} + 5 f_{n-2}</math>
| Homogene Differenzengleichung
|-
|<math>3 \lambda^n + 2 \lambda^{n-1} - 5 \lambda^{n-2} = 0</math>
| Ansatz: <math>f_j = \lambda^j</math>
|-
|<math>3 \lambda^2 + 2 \lambda - 5 = 0</math>
| Charakteristische Gleichung mit <math>\textstyle \lambda_{1{,}2} = - \frac{1}{3} \pm \frac{4}{3} \in \left\{ -\frac{5}{3}, 1 \right\}</math>
|-
|<math>\textstyle f_n = c_1 \left(-\frac{5}{3}\right)^n + c_2 1^n</math>
| Lösung der Gleichung als Linearkombination spezieller Lösungen. Die Konstanten <math>c_1</math> und <math>c_2</math> können aus zwei Anfangswerten von <math>F</math>, <math>f_0</math> und <math>f_1</math> bestimmt werden.
|}

=== Partikuläre Lösung ===
Die Bestimmung geschieht hier analog zu Differentialgleichungen.

{| class="wikitable"
|-
! Störfunktion b(n)
! Ansatz partikuläre Lösung
|-
| Konstante
| Konstante
|-
| Polynom
| Polynom gleichen Grades
|-
| <math>u^n</math>
| <math>k \cdot u^n</math>
|-
| <math>\sin( \alpha \cdot n) , \cos( \alpha \cdot n)</math>
| <math>A \cdot \sin( \alpha \cdot n) + B \cdot \cos( \alpha \cdot n)</math>
|}

In der letzten Zeile wird <math>\mathbb K = \mathbb R</math> angenommen. Falls der Ansatz bereits eine Lösung der zugehörigen homogenen Differenzengleichung sein sollte, ist er mit <math>n, n^2, n^3</math> zu multiplizieren, bis er eine Lösung der inhomogenen Gleichung liefert.

=== Beispiel ===
Gegeben ist eine Folge <math>F</math> mit <math>f_0 = 2,\quad f_1 = 5,\quad f_n = 5 f_{n-1} - 6 f_{n-2} + (n-2)</math>. Gesucht ist die explizite Formel.
Wir suchen zuerst die allgemeine Lösung für die ''homogene'' Rekursionsgleichung.
{| cellpadding="5"
|-
| <math>f_n - 5 f_{n-1} + 6 f_{n-2} = n-2</math>
| Inhomogene Rekursionsgleichung
|-
| <math>f_{\mathrm{homogen},n} - 5 f_{\mathrm{homogen},n-1} + 6 f_{\mathrm{homogen},n-2} = 0</math>
| Homogene Rekursionsgleichung, Ansatz: <math>f_{\mathrm{homogen},n} = \lambda^n</math>
|-
| <math>\lambda^n - 5 \lambda^{n-1} + 6 \lambda^{n-2} = \lambda^{n-2} (\lambda^2 - 5 \lambda + 6) = 0</math>
| Kürzen von <math>\lambda^{n-2}</math>, Lösungen <math>\lambda = 0</math> verfallen
|-
| <math>\lambda^2 - 5 \lambda + 6= 0</math>
| Charakteristische Gleichung, Lösungen: <math>\lambda_1 = 2</math> und <math>\lambda_2 = 3</math>
|-
| <math>f_{\mathrm{homogen},n} = c_1 \cdot 2^n + c_2 \cdot 3^n</math>
| Allgemeine Lösung der homogenen Rekursionsgleichung
|}
Nun suchen wir eine ''spezielle'' Lösung der inhomogenen Rekursionsgleichung, die partikuläre Lösung.
{| cellpadding="5"
|-
| <math>f_n - 5 f_{n-1} + 6 f_{n-2} = n-2</math>
| Inhomogene Rekursionsgleichung, Ansatz: <math>f_{\mathrm{partikulaer},n} = c_3 n + c_4</math>
|}
: <math>c_3 n + c_4 - 5 (c_3 (n-1) + c_4) + 6 (c_3 (n-2) + c_4) = n-2</math>
{| cellpadding="5"
|-
| <math>2 c_3 n - 7 c_3 + 2 c_4 = n-2</math>
| Lösung durch Koeffizientenvergleich: <math>\textstyle c_3 = \frac{1}{2}, c_4 = \frac{3}{4}</math>
|-
| <math>\textstyle f_{\mathrm{partikulaer},n} = \frac{1}{2}n + \frac{3}{4}</math>
| Partikuläre Lösung
|}
Gemäß den obigen Rechenregeln erhalten wir mit <math>\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}</math> alle Lösungen der inhomogenen Rekursionsgleichung. Nun müssen <math>c_1</math> und <math>c_2</math> noch so bestimmt werden, dass <math>f_0 = 2</math> und <math>f_1 = 5</math> gilt.
{| cellpadding="5"
|-
|
| <math>\textstyle c_1 \cdot 2^n + c_2 \cdot 3^n + \frac 1 2 n + \frac 3 4 = f_n</math>
|-
| <math>n = 0</math>:
| <math>\textstyle c_1 + c_2 + \frac 3 4 = 2</math>
|-
| <math>n = 1</math>:
| <math>\textstyle c_1 \cdot 2 + c_2 \cdot 3 + \frac 5 4 = 5</math>
|-
|
| <math>\textstyle \Rightarrow c_1 = 0, c_2 = \frac{5}{4}</math>
|}
Also ist <math>\textstyle f_n = \frac 5 4 \cdot 3^n + \frac 1 2 \cdot n + \frac 3 4</math> die gesuchte Formel.

== Siehe auch ==
* [[Inhomogene lineare Differentialgleichung]]
* [[Erzeugende Funktion]]
* [[Gewöhnliche Differentialgleichung]]

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

== Weblinks ==
{{Wikibooks|Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen}}

[[Kategorie:Folgen und Reihen]]

Lineare Differenzengleichung - Versionsgeschichte

imported>PurpleXanadu: /* growthexperiments-addlink-summary-summary:1|0|0 */