| Autor |
Beitrag |
    
Sandra (Sandra24)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 10:23: | 
|
habe eine generelle Frage zu Lösen von Rekursionsgleichungen mittels gewöhnlichen erzeugenden Funktionen
Ansatz ist klar
A(z) = Sunendl n=0 ( an *zn )
ich komme dann auf eine Reihendarstellung wie Z.B.:
A(z) = 6z [ 1/10 * Sunendl n=0(z/n)n + 1/15 * Sunendl n=0(-z/3)n
wie komme ich dann auf darstellung an = .......
klar ist mir dabei: an = 3/5 (x) n-1 + (2/5 ) (y) n-1
wobei mir x =1/2
und y = -1/3 nicht so ganz klar sind
muss ich immer für z 1 einsetzen?
Danke
Sandra |
Hans (Birdsong)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 15:22: |
|
Hallo :
Es ist schwierig zu helfen, wenn die praezise
Aufgabenstellung nicht bekannt ist. Wie lautet
die zu loesende Rekursionsgleichung ? |
Sandra (Sandra24)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 16:04: |
|
a0=0;
a1=1;
an=1/6 (an-1+an-2) für n ³2 |
Hans (Birdsong)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 19:21: |
|
Hallo :
Multipliziere die Rekursionsgleichung mit
a_(n-2)*z^(n-2)
und summiere von n=2 bis oo. Bezeichnen wir die
formale Potenzreihe Summe[n=0,oo]a_n*z^n mit A(z),
so erhalten wir wegen der Anfangsbedingungen die Gleichung
A(z) - z = (1/6){z*A(z) + z^2*A(z)}.
Nach A(z) aufgeloest ergibt dies
A(z) = 6 z /(6 -z - z^2).
Dies gilt es nun in eine formale Potenzreihe zu
entwickeln, deren Koeffizienten die gesuchten a_n
sind. Eine kleine Rechnung (Partialbruchzerlegung)
ergibt
A(z) = (6/5){(1 - z/2)^(-1) - (1 + z/3)^(-1)}
In {...} erkennt man geometrische Reihen. Ordnet
man nach Potenzen von z, so sieht man, dass der
Koeffizient von z^n
a_n = (6/5){(1/2)^n - (-1/3)^n}
lautet, und das ist die gesuchte Loesung. PrŸfe
dies bitte durch Einsetzen nach !
Bemerkung : FŸr diesen Typ von Rekursionsgleichung
ist das natŸrlich ein etwas beschwerlicher Umweg,
einfacher geht's mit der charakteristischen
Gleichung : diese lautet hier
6 r^2 - r - 1 = 0 <==> (r - 1/2)(r + 1/3) = 0,
womit schon klar ist, dass
a_n = C_1*(1/2)^n + C_2*(-1/3)^n .
Die Koeffizienten C_1 , C_2 bekommt man leicht
aus den Anfangsbedingungen (Probe !).
Gruss
Hans |
Hans (Birdsong)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 19:23: |
|
Hallo :
Multipliziere die Rekursionsgleichung mit
a_(n-2)*z^(n-2)
und summiere von n=2 bis oo. Bezeichnen wir die
formale Potenzreihe Summe[n=0,oo]a_n*z^n mit A(z),
so erhalten wir wegen der Anfangsbedingungen die Gleichung
A(z) - z = (1/6){z*A(z) + z^2*A(z)}.
Nach A(z) aufgeloest ergibt dies
A(z) = 6 z /(6 -z - z^2).
Dies gilt es nun in eine formale Potenzreihe zu
entwickeln, deren Koeffizienten die gesuchten a_n
sind. Eine kleine Rechnung (Partialbruchzerlegung)
ergibt
A(z) = (6/5){(1 - z/2)^(-1) - (1 + z/3)^(-1)}
In {...} erkennt man geometrische Reihen. Ordnet
man nach Potenzen von z, so sieht man, dass der
Koeffizient von z^n
a_n = (6/5){(1/2)^n - (-1/3)^n}
lautet, und das ist die gesuchte Loesung. PrŸfe
dies bitte durch Einsetzen nach !
Bemerkung : FŸr diesen Typ von Rekursionsgleichung
ist das natŸrlich ein etwas beschwerlicher Umweg,
einfacher geht's mit der charakteristischen
Gleichung : diese lautet hier
6 r^2 - r - 1 = 0 <==> (r - 1/2)(r + 1/3) = 0,
womit schon klar ist, dass
a_n = C_1*(1/2)^n + C_2*(-1/3)^n .
Die Koeffizienten C_1 , C_2 bekommt man leicht
aus den Anfangsbedingungen (Probe !).
Gruss
Hans |
Hans (Birdsong)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 19:33: |
|
Hallo :
Multipliziere die Rekursionsgleichung mit
a_(n-2)*z^(n-2)
und summiere von n=2 bis oo. Bezeichnen wir die
formale Potenzreihe Summe[n=0,oo]a_n*z^n mit A(z),
so erhalten wir wegen der Anfangsbedingungen die Gleichung
A(z) - z = (1/6){z*A(z) + z^2*A(z)}.
Nach A(z) aufgeloest ergibt dies
A(z) = 6 z /(6 -z - z^2).
Dies gilt es nun in eine formale Potenzreihe zu
entwickeln, deren Koeffizienten die gesuchten a_n
sind. Eine kleine Rechnung (Partialbruchzerlegung)
ergibt
A(z) = (6/5){(1 - z/2)^(-1) - (1 + z/3)^(-1)}
In {...} erkennt man geometrische Reihen. Ordnet
man nach Potenzen von z, so sieht man, dass der
Koeffizient von z^n
a_n = (6/5){(1/2)^n - (-1/3)^n}
lautet, und das ist die gesuchte Loesung. PrŸfe
dies bitte durch Einsetzen nach !
Bemerkung : FŸr diesen Typ von Rekursionsgleichung
ist das natŸrlich ein etwas beschwerlicher Umweg,
einfacher geht's mit der charakteristischen
Gleichung : diese lautet hier
6 r^2 - r - 1 = 0 <==> (r - 1/2)(r + 1/3) = 0,
womit schon klar ist, dass
a_n = C_1*(1/2)^n + C_2*(-1/3)^n .
Die Koeffizienten C_1 , C_2 bekommt man leicht
aus den Anfangsbedingungen (Probe !).
Gruss
Hans |
Sandra (Sandra24)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 20:08: |
|
vielen dank
aber meine eigentliche frage war,
wie das z verschwindet, und ob das immer zu 1 wird?
der Rest war mir schon klar |
Stefan (Stefan26)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 20:44: |
|
Hallo Hans,
ja, das stimmt so. Aber warum multiplizierst Du die Rekursionsgleichung mit a_(n-2)*z^(n-2)?
Damit komme ich nicht hin. Einfacher: Multiplikation mit z^n und Summation von n=2 bis oo liefert sofort:
A(z) - z = (1/6){z*A(z) + z^2*A(z)}.
Kannst Du bitte die einfachere Methode mit der charakteristischen Gleichung genauer erklären?
Gruß
Stefan |
Stefan (Stefan26)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 20:51: |
|
Hallo Sandra,
das ist ganz einfach: Das z verschwindet nicht und es wird auch nicht z=1 gesetzt. Du machst einfach Koeffizientenvergleich in der Gleichung mit den Potentreihen und erhälst:
a_n = (6/5){(1/2)^n - (-1/3)^n} |
Hans (Birdsong)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 22:00: |
|
Hallo Stefan :
1) Ob ich mit a_(n-2)*z^(n-2) multipliziere und von
n>=2 an summiere, oder mit a_n*z^n und ab n=0,
laeuft auf dasselbe hinaus.
2) Deine Frage betrifft die Theorie der linearen
Differenzengleichungen 2. Ordnung mit konstanten
Koeffizienten :
a_(n+2) = p*a(n+1) + q*a_n.
Die sieht formal genauso aus wie die der entsprechenden Differentialgleichungen. Klar ist :
sind (x_n), (y_n) Loesungen, so auch jede Linear-
kombination C_1*(x_n) + C_2*(y_n). Um die
allgemeine Loesung zu erhalten, braucht man also
2 linear unabhaengige Loesungen.Versucht man es
mit geometrischen Folgen, macht also den Ansatz
a_n = r^n, so muss r notwendig eine Loesung der
sog. charakteristischen Gleichung
r^2 - p*r - q = 0
sein. Sind r_1, r_2 deren Nullstellen, so ist
a_n = C_1*(r_1)^n + C_2*(r_2)^n.
Das prominenteste Beispiel ist die Fibonacci-
Folge (F(n)) :
F(n+2) = F(n+1) + F(n) , F(0)=0, F(1)=1.
Die char. Gl. lautet r^2 - r - 1 = 0, also
r_1 = (1/2)(1+sqrt(5)) , r_2 = -1/r_1. Das ergibt
die sog. Binet'sche Formel
F(n) ={(r_1)^n - (r_2)^n}/sqrt(5)
Als Informationsquelle hierzu empfehle ich Dir
das wunderbare Buch
Graham/Knuth/Patashnik : Concrete Mathematics,
Addison-Wesley 1989
Gruss
Hans |
Stefan (Stefan26)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 23:23: |
|
Hallo Hans,
vielen Dank für den Literaturhinweis.
Du meinst sicher Multiplikation der Rekursionsgleichung nur mit zn bzw. zn-2.
Denn wenn wir mit an-2zn-2 multiplizieren kommt
anan-2zn-2 = 1/6(an-1an-2 + an-22)zn-2.
Bei der Summation n=2 bis oo komme ich nicht weiter. |
Hans (Birdsong)
| | Veröffentlicht am Donnerstag, den 08. Februar, 2001 - 07:55: |
|
Ja natŸrlch, sorry fŸr den Lapsus.
Summe[n=2,oo] (a_n*z^n)=Summe{n=0,00](a_n*z^n)
- a_0*z^0 - a_1*z^1
= A(z) - z oder ? |
|
