Türme von Hanoi < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich soll die inhomogene Rekursionsgleichung für Türme von Hanoi mit dem "Kochrezept" für inhomogene Gleichungen lösen. Es ist keine Rekursionsgleichung vorgegeben , wir sollen diese selber rausfinden , daher :
Mein Lösungsweg:
Die inhomogene Rekursionsgleichung ist:
f(n) = 2f(n-1) + 1
[mm] x_n [/mm] = f(n)
=>
[mm] x_n [/mm] = [mm] 2x_{n-1} [/mm] + 1
x = 2
Daraus folgt:
Allgemeiner Ansatz für den homogenen Teil also für 2f(n-1) ist:
c* [mm] 2^{n} [/mm] (homogener Teil)
Ansatz für die spezielle Lösung ( also für den inhomogenen Teil )
a*n + b
also
f(n) = an+b
an+b = 2(a(n-1)+b)+1
an+b = 2an - 2a + 2b +1
= (2a+1)*n -2a +2b +1
a = (2a+1) => a = -1
b = -2a +2b +1 => b = 3
allg. Lösung der Ausgangsrekursionsgleichung:
f(n) = [mm] c*2^{n} [/mm] -n +3 ( weil wir allg. Lösung (homogen) + spezielle Lösung(inhomogen) addieren)
Es sind bei der Aufagbe keine Anker vorgegeben , also keine Randbedingungen. Es existiert aber f(1) = 1 , oder f(2) = 3 usw. Ich habe f(1) genommen , um c zu berechnen. Hier ist c [mm] \in \IR [/mm] !
Also:
f(1) = [mm] c*2^{1} [/mm] -1 +3
Also:
1 = [mm] c*2^{1} [/mm] -1 +3
c = [mm] \bruch{1}{2}
[/mm]
Also : f(n) = [mm] \bruch{1}{2} *2^{n} [/mm] -n+3
Das kann aber nicht stimmen. Wo habe ich einen Fehler gemacht ?
Ich bitte um Korrektur.
EDIT: Ich gehe davon aus , dass der Ansatz bei der speziellen Lösung falsch ist , kann es aber nicht begründen.
Vielen Dank im Voraus.
|
|
| |
|
Hallo pc_doctor,
> Hallo,
>
> ich soll die inhomogene Rekursionsgleichung für Türme von
> Hanoi mit dem "Kochrezept" für inhomogene Gleichungen
> lösen. Es ist keine Rekursionsgleichung vorgegeben , wir
> sollen diese selber rausfinden , daher :
>
> Mein Lösungsweg:
>
> Die inhomogene Rekursionsgleichung ist:
> f(n) = 2f(n-1) + 1
>
> [mm]x_n[/mm] = f(n)
> =>
> [mm]x_n[/mm] = [mm]2x_{n-1}[/mm] + 1
> x = 2
> Daraus folgt:
>
> Allgemeiner Ansatz für den homogenen Teil also für
> 2f(n-1) ist:
> c* [mm]2^{n}[/mm] (homogener Teil)
>
> Ansatz für die spezielle Lösung ( also für den
> inhomogenen Teil )
>
> a*n + b
Der Ansatz ist nicht richtig,
da der inhomogene Teil nur eine Konstante ist.
Demnach Ansatz für den inhomgenen Teil: [mm]f\left(n\right)=b[/mm]
> also
> f(n) = an+b
>
> an+b = 2(a(n-1)+b)+1
> an+b = 2an - 2a + 2b +1
> = (2a+1)*n -2a +2b +1
>
> a = (2a+1) => a = -1
>
> b = -2a +2b +1 => b = 3
>
> allg. Lösung der Ausgangsrekursionsgleichung:
> f(n) = [mm]c*2^{n}[/mm] -n +3 ( weil wir allg. Lösung (homogen)
> + spezielle Lösung(inhomogen) addieren)
>
> Es sind bei der Aufagbe keine Anker vorgegeben , also keine
> Randbedingungen. Es existiert aber f(1) = 1 , oder f(2) = 3
> usw. Ich habe f(1) genommen , um c zu berechnen. Hier ist c
> [mm]\in \IR[/mm] !
>
> Also:
> f(1) = [mm]c*2^{1}[/mm] -1 +3
> Also:
> 1 = [mm]c*2^{1}[/mm] -1 +3
> c = [mm]\bruch{1}{2}[/mm]
> Also : f(n) = [mm]\bruch{1}{2} *2^{n}[/mm] -n+3
>
>
> Das kann aber nicht stimmen. Wo habe ich einen Fehler
> gemacht ?
> Ich bitte um Korrektur.
> EDIT: Ich gehe davon aus , dass der Ansatz bei der
> speziellen Lösung falsch ist , kann es aber nicht
> begründen.
> Vielen Dank im Voraus.
Gruss
MathePower
|
|
|
| |
|
Hallo ,
danke für die Antwort.
Das hatte ich mir schon gedacht.
Wenn f(n) = b ist , so ist:
b = 2f(n-1) + 1
bzw, da f(n) = [mm] x^n [/mm] war
b = [mm] 2x^{n-1} [/mm] +1 oder ?
Und das x hatte ich ja schon berechnet , war x = 2. Jetzt einfach einsetzen , damit man b hat ?
|
|
|
| |
|
Hallo pc_doctor,
> Hallo ,
>
> danke für die Antwort.
>
> Das hatte ich mir schon gedacht.
>
> Wenn f(n) = b ist , so ist:
> b = 2f(n-1) + 1
> bzw, da f(n) = [mm]x^n[/mm] war
> b = [mm]2x^{n-1}[/mm] +1 oder ?
Nein, es gilt eben auch: [mm]f}\left(n-1\right)=b[/mm]
> Und das x hatte ich ja schon berechnet , war x = 2. Jetzt
> einfach einsetzen , damit man b hat ?
Gruss
MathePower
|
|
|
| |
|
Hallo,
ich bin ein wenig verwirrt jetzt.
Wir hatten gesagt , es gelte:
f(n) = b (Ansatz spezielle Lösung)
Die Gleichung war f(n) = 2*f(n-1)+1
Wenn f(n-1) = b gilt :
b = 2*b + 1 , oder nicht ?
Dann gilt:
b = -1
also : spezielle Lösung + homogene Lösung
f(n) = [mm] c*2^{n} [/mm] -1
f(1) einsetzen :
1 = c [mm] *2^{1} [/mm] - 1
1 = 2c -1
c = 1
Also:
f(n) = [mm] 2^{n} [/mm] -1
Ich glaube das ist jetzt richtig , diese Funktion kommt mir bekannt vor. Ist das jetzt die geschlossene Formel der Ausgangsrekursion ?
|
|
|
| |
|
Hallo pc_doctor,
> Hallo,
>
> ich bin ein wenig verwirrt jetzt.
>
> Wir hatten gesagt , es gelte:
> f(n) = b (Ansatz spezielle Lösung)
>
> Die Gleichung war f(n) = 2*f(n-1)+1
> Wenn f(n-1) = b gilt :
> b = 2*b + 1 , oder nicht ?
>
Ganz genau.
> Dann gilt:
> b = -1
> also : spezielle Lösung + homogene Lösung
>
> f(n) = [mm]c*2^{n}[/mm] -1
> f(1) einsetzen :
> 1 = c [mm]*2^{1}[/mm] - 1
> 1 = 2c -1
> c = 1
> Also:
> f(n) = [mm]2^{n}[/mm] -1
> Ich glaube das ist jetzt richtig , diese Funktion kommt
> mir bekannt vor. Ist das jetzt die geschlossene Formel der
> Ausgangsrekursion ?
Ja. ![[ok]](/images/smileys/ok.gif "[ok]")
Gruss
MathePower
|
|
|
| |
|
Hallo,
vielen Dank für die Antworten.
Ich habe kurz eine Zwischenfrage:
Wenn man sowas hier hat :
f(n) = 2f(n-2) + [mm] x^{2} [/mm] + 3
Ohne jetzt den homogenen Teil zu betrachten , was wäre der Ansatz für den inhomogenen Teil ? Jetzt haben wir ja eine quadratische Gleichung.
|
|
|
| |
|
Hallo pc_doctor,
> Hallo,
>
> vielen Dank für die Antworten.
>
> Ich habe kurz eine Zwischenfrage:
> Wenn man sowas hier hat :
>
> f(n) = 2f(n-2) + [mm]x^{2}[/mm] + 3
>
Hier meinst Du wohl:
[mm]f(n) = 2f(n-2) + \blue{n}^{2} + 3[/mm]
Dann lautet der Ansatz für den inhomogenen Teil:
[mm]a*n^{2}+b*n+c[/mm]
> Ohne jetzt den homogenen Teil zu betrachten , was wäre der
> Ansatz für den inhomogenen Teil ? Jetzt haben wir ja eine
> quadratische Gleichung.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:19 Do 16.01.2014 | | Autor: | pc_doctor |
Hallo,
ja natürlich, ich meinte [mm] n^{2}.
[/mm]
Ich habe jetzt das Prinzip für den Ansatz der speziellen Lösung verstanden.
Vielen Dank für die nette Hilfe!
|
|
|
|
