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

Bearbeiten

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 von den beiden Anfangswerten) ist also die Summe der beiden vorherigen.

Allgemein nennt man jede Gleichung der 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

Bearbeiten

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

Bearbeiten
  • 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

Bearbeiten

Ansatz mit Hilfe der Exponentialfunktion e^x

Bearbeiten

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.

Ansatz mit Hilfe des Superpositionsprinzips

Bearbeiten

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 der Fibonacci-Folge sind

 

es ergibt sich also die sogenannte Binet-Formel

 

Sonderfall: Die charakteristische Gleichung hat eine doppelte Lösung

Bearbeiten

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

Bearbeiten

Eine lineare Differenzengleichung mit konstanten Koeffizienten hat die Form

 

wobei alle   konstant sind.

Lösung der homogenen Gleichung

Bearbeiten

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

Bearbeiten

Die Bestimmung geschieht hier analog zu 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

Bearbeiten

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 wir eine spezielle Lösung der inhomogenen Rekursionsgleichung, die 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

Bearbeiten

Literatur

Bearbeiten
  • 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).
Bearbeiten