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 Inhaltsverzeichnis 1 Beispiel 2 Allgemeine Theorie 2 1 Rechenregeln 3 Losungstheorie homogener linearer Differenzengleichungen 2 Ordnung mit konstanten Koeffizienten 3 1 Sonderfall Die charakteristische Gleichung hat eine doppelte Losung 4 Losung linearer Differenzengleichungen mit konstanten Koeffizienten 4 1 Losung der homogenen Gleichung 4 2 Partikulare Losung 4 3 Beispiel 5 Siehe auch 6 Literatur 7 WeblinksBeispiel BearbeitenEin bekanntes Beispiel einer Folge die einer linearen Differenzengleichung genugt ist die Fibonacci Folge Mit der linearen Differenzengleichung f n f n 1 f n 2 displaystyle f n f n 1 f n 2 nbsp und den Anfangswerten f 0 0 displaystyle f 0 0 nbsp und f 1 1 displaystyle f 1 1 nbsp 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 f n a 1 f n 1 a 2 f n 2 a 2 0 displaystyle f n a 1 f n 1 a 2 f n 2 quad a 2 neq 0 nbsp eine homogene lineare Differenzengleichung 2 Ordnung mit konstanten Koeffizienten Die Koeffizienten a 1 displaystyle a 1 nbsp und a 2 displaystyle a 2 nbsp definieren dabei die Differenzengleichung Eine Folge F f 0 f 1 f 2 displaystyle F f 0 f 1 f 2 dots nbsp die fur alle f i i gt 1 displaystyle f i i gt 1 nbsp die Gleichung erfullt heisst Losung der Differenzengleichung Diese Losungen sind durch die zwei Anfangswerte eindeutig definiert Die Fibonacci Folge ist also eine Losung der Differenzengleichung die durch a 1 a 2 1 displaystyle a 1 a 2 1 nbsp definiert ist Die Folge ist durch die Anfangswerte f 0 0 displaystyle f 0 0 nbsp und f 1 1 displaystyle f 1 1 nbsp eindeutig bestimmt Allgemeine Theorie BearbeitenEine lineare Differenzengleichung k displaystyle k nbsp ter Ordnung uber einem Korper K displaystyle mathbb K nbsp ist von der Form i 0 k a i n f n i b n displaystyle sum i 0 k a i n f n i b n nbsp wobei a i n K a k n 0 n N n k displaystyle a i n in mathbb K a k n neq 0 n in mathbb N n geq k nbsp Die lineare Differenzengleichung wird dabei von den Koeffizienten a 0 n a 1 n a k n displaystyle a 0 n a 1 n dots a k n nbsp und der Funktion b n displaystyle b n nbsp definiert Eine Zahlenfolge F f 0 f 1 f 2 displaystyle F f 0 f 1 f 2 dots nbsp die fur alle n k displaystyle n geq k nbsp die Gleichung erfullt heisst Losung der Differenzengleichung Diese unendliche Folge ist durch ihre k displaystyle k nbsp Anfangswerte f 0 f 1 f k 1 displaystyle f 0 f 1 dots f k 1 nbsp eindeutig bestimmt Ist b n 0 displaystyle b n 0 nbsp fur alle n displaystyle n nbsp so heisst die Gleichung homogen ansonsten heisst sie inhomogen Die Zahlenfolge f n 0 displaystyle f n 0 nbsp fur alle n displaystyle n nbsp erfullt alle homogenen Gleichungen und heisst deshalb triviale Losung Ohne Beschrankung der Allgemeinheit kann a 0 1 displaystyle a 0 1 nbsp angenommen werden Damit erhalt man eine alternative Darstellung die die Berechnungsvorschrift fur f n displaystyle f n nbsp aus den k displaystyle k nbsp vorhergehenden Werten anschaulicher verdeutlicht f n a 1 n f n 1 a 2 n f n 2 a k n f n k b n i 1 k a i n f n i b n displaystyle f n a 1 n f n 1 a 2 n f n 2 dots a k n f n k b n sum i 1 k a i n f n i b n nbsp wobei a i n K a k n 0 n N n k displaystyle a i n in mathbb K a k n neq 0 n in mathbb N n geq k nbsp Rechenregeln Bearbeiten Sind F displaystyle F nbsp und G displaystyle G nbsp Losungen der homogenen linearen Differenzengleichung i 0 k a i n f n i 0 displaystyle textstyle sum i 0 k a i n f n i 0 nbsp dann ist auch a F b G displaystyle alpha F beta G nbsp fur beliebige a b R displaystyle alpha beta in mathbb R nbsp eine Losung Sind F displaystyle F nbsp und G displaystyle G nbsp Losungen der inhomogenen linearen Differenzengleichung i 0 k a i n f n i b n displaystyle textstyle sum i 0 k a i n f n i b n nbsp dann ist F G displaystyle F G nbsp eine Losung der zugehorigen homogenen linearen Differenzengleichung mit b n 0 displaystyle b n 0 nbsp fur alle n N displaystyle n in mathbb N nbsp Ist F displaystyle F nbsp eine Losung der inhomogenen linearen Differenzengleichung i 0 k a i n f n i b n displaystyle textstyle sum i 0 k a i n f n i b n nbsp und G displaystyle G nbsp eine Losung der zugehorigen homogenen linearen Differenzengleichung mit b n 0 displaystyle b n 0 nbsp fur alle n N displaystyle n in mathbb N nbsp dann ist auch F a G displaystyle F alpha G nbsp fur beliebige a R displaystyle alpha in mathbb R nbsp eine Losung der inhomogenen linearen Differenzengleichung Losungstheorie homogener linearer Differenzengleichungen 2 Ordnung mit konstanten Koeffizienten BearbeitenDie erste Idee zur Losung besteht in der Beobachtung dass derartige Folgen meist exponentiell wachsen Das legt den ersten Ansatz f n l n displaystyle f n lambda n nbsp mit einem von Null verschiedenen Lambda nahe Eingesetzt ergibt das l n a 1 l n 1 a 2 l n 2 displaystyle lambda n a 1 lambda n 1 a 2 lambda n 2 nbsp nach Division durch l n 2 displaystyle lambda n 2 nbsp also l 2 a 1 l a 2 0 displaystyle lambda 2 a 1 lambda a 2 0 nbsp Diese quadratische Gleichung heisst charakteristische Gleichung der Rekursion Folgen der Form f n l n displaystyle f n lambda n nbsp mit einem l displaystyle lambda nbsp das reelle oder komplexe Losung der charakteristischen Gleichung ist erfullen also die gewunschte Rekursionsgleichung Die zweite Idee ist die der Superposition Sind F displaystyle F nbsp und G displaystyle G nbsp Folgen die die Rekursionsgleichung erfullen so gilt das auch fur die Folge H displaystyle H nbsp mit h n c 1 f n c 2 g n displaystyle h n c 1 f n c 2 g n nbsp fur beliebige reelle oder komplexe Zahlen c 1 c 2 displaystyle c 1 c 2 nbsp Man kann das auch so ausdrucken Die Menge aller Folgen die die Rekursionsgleichung erfullen bildet einen Vektorraum Sind jetzt Anfangswerte f 0 f 1 displaystyle f 0 f 1 nbsp gegeben und hat die charakteristische Gleichung zwei verschiedene Losungen l 1 l 2 displaystyle lambda 1 lambda 2 nbsp so konnen die Koeffizienten c 1 c 2 displaystyle c 1 c 2 nbsp aus dem folgenden linearen Gleichungssystem bestimmt werden f 0 c 1 l 1 0 c 2 l 2 0 c 1 c 2 displaystyle f 0 c 1 lambda 1 0 c 2 lambda 2 0 c 1 c 2 nbsp f 1 c 1 l 1 1 c 2 l 2 1 c 1 l 1 c 2 l 2 displaystyle f 1 c 1 lambda 1 1 c 2 lambda 2 1 c 1 lambda 1 c 2 lambda 2 nbsp Dann gilt f n c 1 l 1 n c 2 l 2 n displaystyle f n c 1 lambda 1 n c 2 lambda 2 n nbsp fur alle n displaystyle n nbsp Im Beispiel der Fibonacci Folge sind l 1 2 1 5 2 c 1 1 5 c 2 displaystyle lambda 1 2 frac 1 pm sqrt 5 2 quad c 1 frac 1 sqrt 5 c 2 nbsp es ergibt sich also die sogenannte Binet Formel f n 1 5 l 1 n l 2 n displaystyle f n frac 1 sqrt 5 lambda 1 n lambda 2 n nbsp Sonderfall Die charakteristische Gleichung hat eine doppelte Losung Bearbeiten Hat die charakteristische Gleichung nur eine Losung das heisst eine doppelte Nullstelle l displaystyle lambda nbsp so hat die allgemeine Losung die Form f n c 1 l n c 2 n l n 1 displaystyle f n c 1 lambda n c 2 n lambda n 1 nbsp Beispielsweise erfullt f n n displaystyle f n n nbsp also c 1 0 c 2 1 l 1 displaystyle c 1 0 c 2 1 lambda 1 nbsp die Rekursionsgleichung f n 2 f n 1 f n 2 displaystyle f n 2f n 1 f n 2 nbsp Losung linearer Differenzengleichungen mit konstanten Koeffizienten BearbeitenEine lineare Differenzengleichung mit konstanten Koeffizienten hat die Form i 0 k a i f n i b n displaystyle sum i 0 k a i f n i b n nbsp wobei alle a i displaystyle a i nbsp konstant sind Losung der homogenen Gleichung Bearbeiten Mit dem Ansatz f n l n displaystyle f n lambda n nbsp wird eine nichttriviale Losung der homogenen Gleichung i 0 k a i f n i 0 displaystyle textstyle sum i 0 k a i f n i 0 nbsp ermittelt a 0 displaystyle a 0 nbsp sei o B d A gleich 1 displaystyle 1 nbsp Dies fuhrt auf die charakteristische Gleichung l n i 1 k a i l n i 0 displaystyle textstyle lambda n sum i 1 k a i lambda n i 0 nbsp Die verschiedenen Nullstellen der Gleichung ergeben dann linear unabhangige Losungsfolgen und damit Losungen der homogenen Gleichung Sind die Nullstellen nicht verschieden so kommt die zu einer mehrfachen Nullstelle gehorende Losungsfolge mit einem Faktor in der Losung vor der ein Polynom in n displaystyle n nbsp mit einem Grad kleiner als die Vielfachheit der Nullstelle ist Beispiel 3 f n 2 f n 1 5 f n 2 displaystyle 3f n 2f n 1 5f n 2 nbsp Homogene Differenzengleichung3 l n 2 l n 1 5 l n 2 0 displaystyle 3 lambda n 2 lambda n 1 5 lambda n 2 0 nbsp Ansatz f j l j displaystyle f j lambda j nbsp 3 l 2 2 l 5 0 displaystyle 3 lambda 2 2 lambda 5 0 nbsp Charakteristische Gleichung mit l 1 2 1 3 4 3 5 3 1 displaystyle textstyle lambda 1 2 frac 1 3 pm frac 4 3 in left frac 5 3 1 right nbsp f n c 1 5 3 n c 2 1 n displaystyle textstyle f n c 1 left frac 5 3 right n c 2 1 n nbsp Losung der Gleichung als Linearkombination spezieller Losungen Die Konstanten c 1 displaystyle c 1 nbsp und c 2 displaystyle c 2 nbsp konnen aus zwei Anfangswerten von F displaystyle F nbsp f 0 displaystyle f 0 nbsp und f 1 displaystyle f 1 nbsp bestimmt werden Partikulare Losung Bearbeiten Die Bestimmung geschieht hier analog zu Differentialgleichungen Storfunktion b n Ansatz partikulare LosungKonstante KonstantePolynom Polynom gleichen Gradesu n displaystyle u n nbsp k u n displaystyle k cdot u n nbsp sin a n cos a n displaystyle sin alpha cdot n cos alpha cdot n nbsp A sin a n B cos a n displaystyle A cdot sin alpha cdot n B cdot cos alpha cdot n nbsp Falls der Ansatz bereits eine Losung der zugehorigen homogenen Differenzengleichung sein sollte ist er mit n n 2 n 3 displaystyle n n 2 n 3 nbsp zu multiplizieren bis er eine Losung der inhomogenen Gleichung liefert Beispiel Bearbeiten Gegeben ist eine Folge F displaystyle F nbsp mit f 0 2 f 1 5 f n 5 f n 1 6 f n 2 n 2 displaystyle f 0 2 quad f 1 5 quad f n 5f n 1 6f n 2 n 2 nbsp Gesucht ist die explizite Formel Wir suchen zuerst die allgemeine Losung fur die homogene Rekursionsgleichung f n 5 f n 1 6 f n 2 n 2 displaystyle f n 5f n 1 6f n 2 n 2 nbsp Inhomogene Rekursionsgleichungf h o m o g e n n 5 f h o m o g e n n 1 6 f h o m o g e n n 2 0 displaystyle f mathrm homogen n 5f mathrm homogen n 1 6f mathrm homogen n 2 0 nbsp Homogene Rekursionsgleichung Ansatz f h o m o g e n n l n displaystyle f mathrm homogen n lambda n nbsp l n 5 l n 1 6 l n 2 l n 2 l 2 5 l 6 0 displaystyle lambda n 5 lambda n 1 6 lambda n 2 lambda n 2 lambda 2 5 lambda 6 0 nbsp Kurzen von l n 2 displaystyle lambda n 2 nbsp Losungen l 0 displaystyle lambda 0 nbsp verfallenl 2 5 l 6 0 displaystyle lambda 2 5 lambda 6 0 nbsp Charakteristische Gleichung Losungen l 1 2 displaystyle lambda 1 2 nbsp und l 2 3 displaystyle lambda 2 3 nbsp f h o m o g e n n c 1 2 n c 2 3 n displaystyle f mathrm homogen n c 1 cdot 2 n c 2 cdot 3 n nbsp Allgemeine Losung der homogenen RekursionsgleichungNun suchen wir eine spezielle Losung der inhomogenen Rekursionsgleichung die partikulare Losung f n 5 f n 1 6 f n 2 n 2 displaystyle f n 5f n 1 6f n 2 n 2 nbsp Inhomogene Rekursionsgleichung Ansatz f p a r t i k u l a e r n c 3 n c 4 displaystyle f mathrm partikulaer n c 3 n c 4 nbsp c 3 n c 4 5 c 3 n 1 c 4 6 c 3 n 2 c 4 n 2 displaystyle c 3 n c 4 5 c 3 n 1 c 4 6 c 3 n 2 c 4 n 2 nbsp 2 c 3 n 7 c 3 2 c 4 n 2 displaystyle 2c 3 n 7c 3 2c 4 n 2 nbsp Losung durch Koeffizientenvergleich c 3 1 2 c 4 3 4 displaystyle textstyle c 3 frac 1 2 c 4 frac 3 4 nbsp f p a r t i k u l a e r n 1 2 n 3 4 displaystyle textstyle f mathrm partikulaer n frac 1 2 n frac 3 4 nbsp Partikulare LosungGemass den obigen Rechenregeln erhalten wir mit f n f h o m o g e n n f p a r t i k u l a e r n c 1 2 n c 2 3 n 1 2 n 3 4 displaystyle 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 nbsp alle Losungen der inhomogenen Rekursionsgleichung Nun mussen c 1 displaystyle c 1 nbsp und c 2 displaystyle c 2 nbsp noch so bestimmt werden dass f 0 2 displaystyle f 0 2 nbsp und f 1 5 displaystyle f 1 5 nbsp gilt c 1 2 n c 2 3 n 1 2 n 3 4 f n displaystyle textstyle c 1 cdot 2 n c 2 cdot 3 n frac 1 2 n frac 3 4 f n nbsp n 0 displaystyle n 0 nbsp c 1 c 2 3 4 2 displaystyle textstyle c 1 c 2 frac 3 4 2 nbsp n 1 displaystyle n 1 nbsp c 1 2 c 2 3 5 4 5 displaystyle textstyle c 1 cdot 2 c 2 cdot 3 frac 5 4 5 nbsp c 1 0 c 2 5 4 displaystyle textstyle Rightarrow c 1 0 c 2 frac 5 4 nbsp Also ist f n 5 4 3 n 1 2 n 3 4 displaystyle textstyle f n frac 5 4 cdot 3 n frac 1 2 cdot n frac 3 4 nbsp die gesuchte Formel Siehe auch BearbeitenInhomogene lineare Differentialgleichung Erzeugende Funktion Gewohnliche DifferentialgleichungLiteratur BearbeitenL Berg Lineare Gleichungssysteme mit Bandstruktur Carl Hanser Munchen Wien 1986 Ian Jaques Mathematics for Economics and Business Fifth Edition Prentice Hall 2006 Kapitel 9 1 Difference Equations Weblinks Bearbeiten nbsp Wikibooks Lineare Rekurrenzen Potenzreihen und ihre erzeugenden Funktionen Lern und Lehrmaterialien Abgerufen von https de wikipedia org w index php title Lineare Differenzengleichung amp oldid 213860502
