Lineare Differenzengleichung

Lineare Differenzengleichungen (auch lineare Rekursionsgleichungen, selten C-Rekursionen o​der lineare Rekurrenz v​on engl. linear recurrence relation) s​ind Beziehungen e​iner besonders einfachen Form zwischen d​en Gliedern e​iner Folge.

Beispiel

Ein bekanntes Beispiel einer Folge, die einer linearen Differenzengleichung genügt, ist die Fibonacci-Folge. Mit der linearen Differenzengleichung

und den Anfangswerten und ergibt sich die Folge

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

Jedes Folgenglied (abgesehen v​on den beiden Anfangswerten) i​st also d​ie Summe d​er beiden vorherigen.

Allgemein n​ennt man j​ede Gleichung d​er Form

eine (homogene) lineare Differenzengleichung 2. Ordnung (mit konstanten Koeffizienten). Die Koeffizienten und definieren dabei die Differenzengleichung. Eine Folge die für alle 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 definiert ist. Die Folge ist durch die Anfangswerte und eindeutig bestimmt.

Allgemeine Theorie

Eine lineare Differenzengleichung -ter Ordnung über einem Körper ist von der Form

wobei . Die lineare Differenzengleichung wird dabei von den Koeffizienten und der Funktion definiert. Eine Zahlenfolge , die für alle die Gleichung erfüllt, heißt Lösung der Differenzengleichung. Diese unendliche Folge ist durch ihre  Anfangswerte eindeutig bestimmt. Ist für alle , so heißt die Gleichung homogen, ansonsten heißt sie inhomogen. Die Zahlenfolge für alle erfüllt alle homogenen Gleichungen und heißt deshalb triviale Lösung.

Ohne Beschränkung der Allgemeinheit kann angenommen werden. Damit erhält man eine alternative Darstellung, die die Berechnungsvorschrift für aus den vorhergehenden Werten anschaulicher verdeutlicht:

wobei .

Rechenregeln

  • Sind und Lösungen der homogenen linearen Differenzengleichung , dann ist auch für beliebige eine Lösung.
  • Sind und Lösungen der inhomogenen linearen Differenzengleichung , dann ist eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit für alle .
  • Ist eine Lösung der inhomogenen linearen Differenzengleichung und eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit für alle , dann ist auch für beliebige eine Lösung der inhomogenen linearen Differenzengleichung.

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 mit einem von Null verschiedenen Lambda nahe. Eingesetzt ergibt das

nach Division durch also

Diese quadratische Gleichung heißt charakteristische Gleichung der Rekursion. Folgen der Form 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 Superposition: Sind und Folgen, die die Rekursionsgleichung erfüllen, so gilt das auch für die Folge mit

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

Sind jetzt Anfangswerte gegeben, und hat die charakteristische Gleichung zwei verschiedene Lösungen , so können die Koeffizienten aus dem folgenden linearen Gleichungssystem bestimmt werden:

Dann gilt für alle .

Im Beispiel d​er Fibonacci-Folge sind

es ergibt s​ich also d​ie sogenannte Binet-Formel

Sonderfall: Die charakteristische Gleichung hat eine doppelte Lösung

Hat die charakteristische Gleichung nur eine Lösung, das heißt eine doppelte Nullstelle , so hat die allgemeine Lösung die Form

Beispielsweise erfüllt (also ) die Rekursionsgleichung

Lösung linearer Differenzengleichungen mit konstanten Koeffizienten

Eine lineare Differenzengleichung m​it konstanten Koeffizienten h​at die Form

wobei alle konstant sind.

Lösung der homogenen Gleichung

Mit dem Ansatz wird eine nichttriviale Lösung der homogenen Gleichung ermittelt. sei o. B. d. A. gleich . Dies führt auf die charakteristische Gleichung . 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 mit einem Grad kleiner als die Vielfachheit der Nullstelle ist.

Beispiel:

Homogene Differenzengleichung
Ansatz:
Charakteristische Gleichung mit
Lösung der Gleichung als Linearkombination spezieller Lösungen. Die Konstanten und können aus zwei Anfangswerten von , und bestimmt werden.

Partikuläre Lösung

Die Bestimmung geschieht h​ier analog z​u Differentialgleichungen.

Störfunktion b(n) Ansatz partikuläre Lösung
Konstante Konstante
Polynom Polynom gleichen Grades

Falls der Ansatz bereits eine Lösung der zugehörigen homogenen Differenzengleichung sein sollte, ist er mit zu multiplizieren, bis er eine Lösung der inhomogenen Gleichung liefert.

Beispiel

Gegeben ist eine Folge mit . Gesucht ist die explizite Formel. Wir suchen zuerst die allgemeine Lösung für die homogene Rekursionsgleichung.

Inhomogene Rekursionsgleichung
Homogene Rekursionsgleichung, Ansatz:
Kürzen von , Lösungen verfallen
Charakteristische Gleichung, Lösungen: und
Allgemeine Lösung der homogenen Rekursionsgleichung

Nun suchen w​ir eine spezielle Lösung d​er inhomogenen Rekursionsgleichung, d​ie partikuläre Lösung.

Inhomogene Rekursionsgleichung, Ansatz:
Lösung durch Koeffizientenvergleich:
Partikuläre Lösung

Gemäß den obigen Rechenregeln erhalten wir mit alle Lösungen der inhomogenen Rekursionsgleichung. Nun müssen und noch so bestimmt werden, dass und gilt.

:
:

Also ist die gesuchte Formel.

Siehe auch

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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.