Lösen von Rekursionsgleichunge < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:15 Fr 04.07.2014 | | Autor: | Marc90 |
| Aufgabe | Lösen Sie die folgende Rekursionsgleichung:
c) [mm] a_{n+2} [/mm] − [mm] 3a_{n+1} [/mm] + [mm] 2a_{n} [/mm] = 0, n ≥ 0, _{0} = 1, [mm] a_{1} [/mm] = 6 |
So ich weiß das man solche Aufgaben mit Erzeugenden Funktionen löst aber wie genau mache ich das?
Man fängt ja damit an:
[mm] A(x)=\summe_{n\ge0}^{}a_{n}x^n
[/mm]
Aber wie macht man weiter?
|
|
| |
|
Hallo,
setze an mit
[mm] a_n=z^n
[/mm]
und gehe damit in die Rekursion ein. Dies führt auf eine quadratische Gleichung in z.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:28 Fr 04.07.2014 | | Autor: | Marc90 |
Hey!
Ich habe jetzt mal im skript geschaut.. da gab es ein Schritt für Schritt Beispiel. Allerdings komme ich gerade nicht weiter. Und Zwar:
Schritt 1: Auf [mm] a_{n}=... [/mm] Form bringen
[mm] a_{n+2} [/mm] − [mm] 3a_{n+1} +2a_{n}= [/mm] 0, n ≥ 0, [mm] a_{0} [/mm] = 1, [mm] a_{1}=6
[/mm]
==> [mm] a_{n}=-\bruch{1}{2}*a_{n+2} [/mm] + [mm] \bruch{3}{2}*a_{n+1}
[/mm]
Schritt 2: Aufstellen der erzeugenden Funktion:
[mm] A(x)=\summe_{n\ge0}^{}a_{n}x^n
[/mm]
Schritt 3/4: Anwendung der Rekursionsgleichung und Umformung:
A(x)= [mm] 1+6+\summe_{n\ge2}^{}(-\bruch{1}{2}*a_{n+2} [/mm] + [mm] \bruch{3}{2}*a_{n+1})*x^n [/mm]
= [mm] 1+6+(-\bruch{1}{2})x\summe_{n\ge2}^{}a_{n+2}*x^n+ (\bruch{3}{2})x\summe_{n\ge2}^{}a_{n+1}*x^n
[/mm]
= [mm] 1+6+(-\bruch{1}{2})x\summe_{n\ge4}^{}a_{n}*x^n [/mm] + [mm] (\bruch{3}{2})x\summe_{n\ge3}^{}a_{n}*x^n
[/mm]
Danach kommen noch weitere Schritte aber ich bin mir nicht sicher ob ich bis hierhin überhaupt richtig gerechnet habe!
MfG :)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:28 Fr 04.07.2014 | | Autor: | Sax |
Hi,
ich glaube, dass du die Umformungen des Beispiels zu unreflektiert übernimmst.
Du solltest die bei jedem Schritt klar machen, wozu er dient, und bei dem, was du schreibst, darüberhinaus, ob der jeweilige Schritt überhaupt richtig ist.
Konkret :
1. Falls im Skript die Rekursion in der Form [mm] a_n+\alpha*a_{n-1}+\beta*a_{n-2}=0 [/mm] gegeben ist, ist eine Auflösung nach [mm] a_n [/mm] sinnvoll. Hier liegt die Rekursion aber als [mm] a_{n+2}+\alpha*a_{n+1}+\beta*a_{n}=0 [/mm] vor und deshalb solltest du nach [mm] a_{n+2} [/mm] auflösen, so dass ein Folgenglied durch seine Vorgänger (nicht Nachfolger) definiert wird.
2. Da die Rekursion zweigliedrig ist, werden die ersten beiden Summanden aus der Reihe herausgenommen (vergiss das x bei [mm] a_1*x [/mm] nicht). Der Laufindex wird so verschoben, dass die Rekursion eingesetzt werden kann.
3. Nach dem Aufspalten der Summe wird jeweils gerade diejenige x-Potenz ausgeklammert, sodass unter der Summe der Index bei [mm] a_i [/mm] und die Potenz bei x übereinstimmen. Das ist bei dir völlig schief gelaufen.
4. Durch eine abermalige Indexverschiebung werden beide Summen auf die Form A(x) gebracht, damit genau das A(x) eingesetzt werden kann. Die so entstehende Gleichung (im vorliegenden Fall [mm] A(x)=a_0+a_1x+3x*A(x)-3a_0x-2x^2*A(x) [/mm] ) wird nach A(x) aufgelöst.
5. Der Bruch A(x) = ... wird durch Partialbruchzerlegung in zwei Summanden aufgespalten, die anschließend in geometrische Reihen entwickelt werden.
6. Ein Koeffizientenvergleich mit der Ausgangsreihe löst die Rekursion. (Kontroll-Lösung : Hier ergibt sich [mm] a_n=-4+5*2^n [/mm] ).
7. Eine abschließende Betrachtung zur Konvergenz der benutzten Reihen rechtfertigt das ganze Verfahren im Nachhinein.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:24 Sa 05.07.2014 | | Autor: | Marc90 |
Hey vielen Dank für diese Top Antwort!
Ich hätte da aber kurz eine Nachfrage zu Schritt 2/3:
Ich habe ja:
[mm] 1+6x+3x\summe_{n\ge2}^{}a_{n-1}+x^{n-2}-2x*\summe_{n\ge?}^{}a_{n}*x^n
[/mm]
Ist das so bei der ersten Summe richtig? Und wie würde ich es bei der zweiten machen? Muss ich dann:
[mm] 1+6x+3x\summe_{n\ge2}^{}a_{n-1}+x^{n-2}-2x*\summe_{n\ge2}^{}a_{n-2}*x^{n-2}
[/mm]
?
MfG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:46 Sa 05.07.2014 | | Autor: | Sax |
Hi,
aus [mm] A(x)=\summe_{n=0}^{\infty}a_nx^n [/mm] und [mm] a_{n+2}=3a_{n+1}-2a_n [/mm] folgt
[mm] A(x)=a_0+a_1x+\summe_{n=2}^{\infty}a_nx^n=a_0+a_1x+\summe_{n=0}^{\infty}a_{n+2}x^{n+2}=a_0+a_1x+\summe_{n=0}^{\infty}(3a_{n+1}-2a_n)*x^{n+2}
[/mm]
[mm] =a_0+a_1x+3*\summe_{n=0}^{\infty}a_{n+1}x^{n+2}-2*\summe_{n=0}^{\infty}a_n*x^{n+2}=a_0+a_1x+3x*\summe_{n=0}^{\infty}a_{n+1}x^{n+1}-2x^2*\summe_{n=0}^{\infty}a_n*x^n
[/mm]
[mm] =a_0+a_1x+3x*(\summe_{n=0}^{\infty}a_nx^n\;-a_0)-2x^2*\summe_{n=0}^{\infty}a_n*x^n=a_0+a_1x+3x*(A(x)\;-a_0)-2x^2*A(x)
[/mm]
... und jetzt wird's noch komplizierter.
Wenn nicht unbedingt "erzeugende Funktion" verlangt wird, sollte man lineare Rekursionen daher unbedingt mit einem Exponentialansatz lösen.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:31 Sa 05.07.2014 | | Autor: | Marc90 |
Ah ok so sieht das ganze dann aus. Ich werde mal versuchen damit weiter zu rechnen :)
Erzeugende Funktionen werden nicht verlangt aber mein Dozent hatte nur dieses Verfahren und das Iterationsverfahren zum lösen von Rekursionsgleichungen vorgestellt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mo 07.07.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
