Rekursionsgleichungen 2.0 < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:02 Mo 22.10.2018 | | Autor: | Hela123 |
| Aufgabe | Stellen Sie für folgende Rekursionsgleichungen geschlossene Formen auf und beweisen Sie diese per Induktion:
1) [mm]T(n)=\left\{\begin{matrix}
2T(n/3)+n^2, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
2) [mm]T(n)=\left\{\begin{matrix}
4T(n/2)+n^2, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
3) [mm]T(n)=\left\{\begin{matrix}
3T(n/3)+\wurzel{n}, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
Hinweis:
Nutzen Sie z.B. iteriertes Einsetzen oder stellen Sie den Rekursionsbaum auf, um zunächst eine geschlossene Form zu erraten. Es genügt, gute obere Schranken für T(n) zu zeigen. |
Hallo Forum,
ich möchte erstmal Punk 1) lösen.
Zuerst habe ich mir angeschaut, wie die Rekursionsfolge aussieht:
T(0) = 1
T(1) = 2T(1/3) + 1 = 2T(0) + 1 = 3 (Ist es quasi wie eine Ganzzahldivision an der Stelle gedacht?)
T(2) = 2T(2/3) + 4 = 2T(0) + 4 = 6
T(3) = 2T(3/3) + 9 = 2T(1) + 9 = 15
T(4) = 22
T(5) = 31
T(6) = 48
T(7) = 61
...
Ist es korrekt?
Als nächstes habe ich die Differenzfolgen angeschaut:
2-3-9-7-9-17-13
1-6-2-2-8-4
5-4-0-6-4
...
Und ich finde keine Gesetzlichkeit. Offensichtlich, sollte man in diesem Fall einen anderen Ansatz haben.
Kann mir vielleicht jemand einen Tipp geben?
Vielen Dank im Voraus!
Hela123
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:33 Mo 22.10.2018 | | Autor: | fred97 |
> Stellen Sie für folgende Rekursionsgleichungen
> geschlossene Formen auf und beweisen Sie diese per
> Induktion:
>
> 1) [mm]T(n)=\left\{\begin{matrix}
2T(n/3)+n^2, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
>
> 2) [mm]T(n)=\left\{\begin{matrix}
4T(n/2)+n^2, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
>
> 3) [mm]T(n)=\left\{\begin{matrix}
3T(n/3)+\wurzel{n}, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
>
> Hinweis:
> Nutzen Sie z.B. iteriertes Einsetzen oder stellen
> Sie den Rekursionsbaum auf, um zunächst eine
> geschlossene Form zu erraten. Es genügt, gute obere
> Schranken für T(n) zu zeigen.
> Hallo Forum,
>
> ich möchte erstmal Punk 1) lösen.
> Zuerst habe ich mir angeschaut, wie die Rekursionsfolge
> aussieht:
>
> T(0) = 1
> T(1) = 2T(1/3) + 1 = 2T(0) + 1 = 3
Ich denke, dass nach obiger Vorschrift gilt : T (1)=1.
> (Ist es quasi wie eine
> Ganzzahldivision an der Stelle gedacht?)
> T(2) = 2T(2/3) + 4 = 2T(0) + 4 = 6
> T(3) = 2T(3/3) + 9 = 2T(1) + 9 = 15
T (3) ist auch falsch
> T(4) = 22
> T(5) = 31
> T(6) = 48
> T(7) = 61
> ...
> Ist es korrekt?
>
>
> Als nächstes habe ich die Differenzfolgen angeschaut:
> 2-3-9-7-9-17-13
> 1-6-2-2-8-4
> 5-4-0-6-4
> ...
>
> Und ich finde keine Gesetzlichkeit. Offensichtlich, sollte
> man in diesem Fall einen anderen Ansatz haben.
>
> Kann mir vielleicht jemand einen Tipp geben?
>
> Vielen Dank im Voraus!
> Hela123
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:16 Di 23.10.2018 | | Autor: | Hela123 |
Hallo fred97,
vielen Dank für deine Antwort!
Leider werde ich aus der nicht ganz schlau...
Wie kommst du darauf, dass T (1)=1?
Viele Grüße
Hela123
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:40 Di 23.10.2018 | | Autor: | fred97 |
> Hallo fred97,
>
> vielen Dank für deine Antwort!
> Leider werde ich aus der nicht ganz schlau...
>
> Wie kommst du darauf, dass T (1)=1?
Es ist doch
$ [mm] T(n)=\left\{\begin{matrix} 2T(n/3)+n^2, & \mbox{falls }n>1\mbox \\ 1, & \mbox{sonst} \end{matrix}\right. [/mm] $
D.h.: für n>1 ist [mm] T(n)=2T(n/3)+n^2 [/mm] und für n=1 ist T(1)=1.
>
> Viele Grüße
> Hela123
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:02 Di 23.10.2018 | | Autor: | Hela123 |
Hallo fred97,
vielen Dank für deine Antwort!
> > Leider werde ich aus der nicht ganz schlau...
> >
> > Wie kommst du darauf, dass T (1)=1?
>
> Es ist doch
>
> [mm]T(n)=\left\{\begin{matrix} 2T(n/3)+n^2, & \mbox{falls }n>1\mbox \\ 1, & \mbox{sonst} \end{matrix}\right.[/mm]
>
> D.h.: für n>1 ist [mm]T(n)=2T(n/3)+n^2[/mm] und für n=1 ist
> T(1)=1.
Stimmt, ich habe [mm]n \ge 1[/mm] angenommen. Danke!
Viele Grüße
Hela123
|
|
|
| |
|
Zur 1. Aufgabe
Die numerische Berechnung der Funktionswerte ist schon nicht sehr einfach, wie ich dir am Beispiel n=10 zeigen will.
Für n=10 brauchst du den Wert von 10/3, dafür aber den Wert von (10/3)/3 = 10/9 und dafür den Wert von (10/9)/3 = 10/27<1.
Für Vielfache von 3 musst du dich nur um eine Stufe "herunterschrauben", für alle anderen so lange, bis du durch Dritteln auf eine Zahl x <1 stößt. Dafür brauchst du k = [mm] aufgerundet(log_3(n)) [/mm] Schritte, für n=10 also k = 3 Schritte. Nun bist du unter 1 mit einem Bruch x, dessen Nenner [mm] 3^k [/mm] ist.
Es ist T(10/27)=1 laut Rekursionsvorschrift.
[mm] T(10/9)=2*T(10/27)+1(10/9)^2=2+100/81=262/81
[/mm]
Durch das Quadrieren erhältst du einen Nenner [mm] (3^{k-1})^2=3^{2k-2}, [/mm] hier [mm] 3^4=81.
[/mm]
T(10/3) ergibt sich zu [mm] 2*T(10/9)+(10/3)^2=524/81+100/9 [/mm] = 1424/81
und endlich [mm] T(10)=2*T(10/3)+10^2=2848/81+100=10948/81.
[/mm]
Wenn du eine geschlossene Funktionsformel suchst, wirst du wohl den abgerundeten [mm] log_3 [/mm] einbauen müssen. Mit viel Glück funktioniert diese Formel dann auch für ganzzahlige Vielfache von 3.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:58 Di 23.10.2018 | | Autor: | Hela123 |
Hallo HJKweseleit,
vielen Dank für deine Antwort! Ich habe noch ein paar Fragen dazu:
> Für n=10 brauchst du den Wert von 10/3, dafür aber den
> Wert von (10/3)/3 = 10/9 und dafür den Wert von (10/9)/3 =
> 10/27<1.
>
> Für Vielfache von 3 musst du dich nur um eine Stufe
> "herunterschrauben", für alle anderen so lange, bis du
> durch Dritteln auf eine Zahl x <1 stößt.
Das verstehe ich nicht ganz. Mit vielfachen von 3 ist klar, aber warum müssen wir solange teilen, bis x < 1 ist?
> Dafür brauchst
> du k = [mm]aufgerundet(log_3(n))[/mm] Schritte, für n=10 also k = 3
> Schritte. Nun bist du unter 1 mit einem Bruch x, dessen
> Nenner [mm]3^k[/mm] ist.
>
> Es ist T(10/27)=1 laut Rekursionsvorschrift.
> [mm]T(10/9)=2*T(10/27)+1(10/9)^2=2+100/81=262/81[/mm]
>
> Durch das Quadrieren erhältst du einen Nenner
> [mm](3^{k-1})^2=3^{2k-2},[/mm] hier [mm]3^4=81.[/mm]
>
> T(10/3) ergibt sich zu [mm]2*T(10/9)+(10/3)^2=524/81+100/9[/mm] =
> 1424/81
>
> und endlich [mm]T(10)=2*T(10/3)+10^2=2848/81+100=10948/81.[/mm]
Also, führt die Berechnung für jedes n, was nicht vielfache von 3 ist, zurück auf die Rekursionsvorschrift zurück?
Ich versuche jetzt noch mal:
T(0) = 1
T(1) = 1
T(2) = [mm] 2T(2/3)+2^2 [/mm] = 2T(0)+4 = 6
T(3) = [mm] 2T(3/3)+3^2 [/mm] = 2T(1)+9 = 11
T(4) = [mm] 2T(4/3)+4^2 [/mm] = [mm] 2(2T(4/9)+(4/3)^2)+4^2 [/mm] = 2(2*1 + 16/9) + 16 = 20+32/9 = 212/9
Ist es korrekt?
T(5) = [mm] 2T(5/3)+5^2 [/mm] = [mm] 2(2T(5/9)+(5/3)^2)+5^2 [/mm] = 2(2*1 + 25/9) + 25 = 29+50/9 = 311/9
T(6) = [mm] 2T(6/3)+6^2 [/mm] = 2T(2)+36= 2*6 + 36 = 48
T(7) = [mm] 2T(7/3)+7^2 [/mm] = [mm] 2(2T(7/9)+(7/3)^2)+49= [/mm] 2(2*1+49/9)+49 = 53+98/9 = 575/9
T(8) = [mm] 2T(8/3)+8^2 [/mm] = [mm] 2(2T(8/9)+(8/3)^2)+64= [/mm] 2(2*1+64/9)+64 = 68+128/9 = 740/9
T(9) = [mm] 2T(9/3)+9^2 [/mm] = 2T(3) + 81 = 2*11 + 81 = 103
T(10) = 10948/81 (Habe ich von dir übernommen).
> Wenn du eine geschlossene Funktionsformel suchst, wirst du
> wohl den abgerundeten [mm]log_3[/mm] einbauen müssen.
Tut mir leid, aber hier brauche ich auch Hilfe. Wie macht man das? Muss man versuchen irgendwie geschickt zu raten?
> Mit viel Glück funktioniert diese Formel dann auch für ganzzahlige
> Vielfache von 3.
Klingt ja sehr vielversprechend
Nachtrag:
Ich habe mich noch ein bisschen weiter informiert und habe noch etwas herausgefunden:
Wir können die Rekursionsgleichung wie folgt umformen:
[mm]T(n)=2T(n/3)+n^2
= 2(2T(n/9)+ (n/3)^2)+n^2 = 4T(n/9)+(2/9)n^2+n^2
= 4(2T(n/27)+(n/9)^2)+(2/9)n^2+n^2
= 8T(n/27) + (2/9)^2 * n^2 + (2/9)^1 * n^2 + (2/9)^0 * n^2 [/mm]
Hier ist ja schon eine Gesetzmäßigkeit vorhanden. Wir haben T(1) = 1 und vielleicht können wir zunächst annehmen (warum wir das dürfen verstehe ich noch nicht) dass [mm] n=3^k [/mm] (also [mm] log_3(n)=k) [/mm] ist. Dann können wir das (möglicherweise) so umschreiben:
[mm]T(n)= \summe_{i=0}^{k-1} (2/9)^i + X[/mm]
Wie man X ermittelt verstehe ich jetzt leider auch nicht.
Könntest du mir hier (auch) einen Tipp geben?
Noch mal vielen vielen Dank und viele Grüße
Hela123
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:57 Fr 26.10.2018 | | Autor: | Hela123 |
Hallo Forum,
also ich kriege langsam die Kriese mit dieser Aufgabe.
Ich bin immer noch bei Teil 1):
[mm]T(n)=\left\{\begin{matrix}
2T(n/3)+n^2, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
Wir haben T(1) = 1 und nehmen an, dass [mm] n=3^k [/mm] (also [mm] log_3(n)=k) [/mm] ist.
Dann:
[mm]T(n)= n^2 \summe_{i=0}^{k-1} (2/9)^i + 2^k[/mm]
[mm]=n^2 \summe_{i=0}^{log_3(n)-1} (2/9)^i + n^{log_3(2)}[/mm]
[mm]< n^2 \summe_{i=0}^{\infty} (2/9)^i + n^{log_3(2)}[/mm]
[mm]= n^2 * C + n^{log_3(2)}[/mm]
[mm]< n^2 * C'[/mm]
D.h. wir haben obere Schranke: [mm]T(n) \in O(n^2)[/mm]
Ist es korrekt?
Dann Induktionsbeweis:
IA: [mm]T(1) = 1 < C'*1 für C'>1[/mm] erfüllt
IV: [mm]T(n)
IS: n->n+1
[mm]T(n+1) = 2T((n+1)/3) + (n+1)^2[/mm]
[mm]= 2T((n+1)/3) + n^2 + 2n +1 [/mm]
Aber weiter komme ich leider nicht. Wie kommt man hier zur Induktionsvoraussetzung IV?
Ich wäre für einen Hinweis sehr sehr dankbar!
Viele Grüße
Hela123
|
|
|
| |
|
Ich habe mal folgenden Ansatz gemacht:
Die Anfangsbedingung wird zunächst ignoriert. Ansatz:
[mm] T(x)=a*x^k+b*x^2
[/mm]
Dann ist [mm] T(x/3)=a*(x/3)^k+b*(x/3)^2=1/3^k*ax^k+b/9x^2
[/mm]
Eingesetzt in die Rekursionsgleichung erhält man
[mm] T(x)=2T(x/3)+x^2=2/3^k*ax^k+2b/9x^2+x^2
[/mm]
Nun ist aber [mm] T(x)=a*x^k+b*x^2, [/mm] und durch Vergleich der Koeffizienten ergibt sich
[mm] 2/3^k=1, [/mm] also [mm] 3^k=2 [/mm] und damit [mm] k=log_3 [/mm] 2
sowie 2b/9+1=b, also 2b+9=9b, 9=7b, b=9/7
---------- T(x)= [mm] a*x^{log_3 2}+9/7 x^2 [/mm] ---------
Nun muss noch a ermittelt werden, und das geschieht durch die Anfangsbedingung.
[mm] T(1)=a*1^{log_3 2}+9/7 [/mm] = a+9/7= 3=21/7, also a=12/7
T(x)= [mm] 12/7*x^{log_3 2}+9/7 x^2
[/mm]
Man erhält damit die richtigen Werte
T(1)=3
T(3)=15
T(9)=111
T(27)=951
T(81)=8463
...
Die sich alle auf T(1) zurückführen lassen, womit a berechnet wurde.
ABER: T(2) ergibt hiermit den Wert 7.79753597... statt 6.
Das bedeutet: Alle Werte, die sich nicht auf T(1) rekurrieren lassen, haben ein anderes a!!!
Für x=2 erhalten wir so z.B.
[mm] T(2)=a*2^{log_3 2}+9/7 *2^2 [/mm] = 6 und daraus [mm] a=6/(7*2^{log_3 2})
[/mm]
Damit würdest du nun alle Glieder berechnen können, die auf T(2) rekurrieren. Ddie Berechnung von a müsstest du nun wiederholen für alle Glieder, die auf T(4), T(5)... rekurrieren. Am aber a daraus zu berechnen, müsstest du die Werte von T(2), T(4),... schon kennen, und hier beißt sich die Katze in den Schwanz.
Ich weiß also nicht, wie man eine geschlossene Form für diese Rekursion erstellen könnte, und erst recht nicht, was das mit der erwähnten Abschätzung zu tun haben sollte. Das einzige, was man an der in --- stehenden Form erkennt, ist, dass T(x) mindestens quadratisch zunimmt.
|
|
|
| |
|
Ich habe nun meine Überlegungen fortgeführt und eine komplette Formel für die 1. Aufgabe gefunden.
Meine letzte Aussage war die, dass man für jede Zahl n das a bestimmen müsste, und dass man dazu schon T(n) berechnet haben müsste. Das war aber genau einen Schritt zu kurz gedacht.
Ich rekurriere noch einen Schritt weiter, bis der Wert unter 1 liegt. Dann weiß ich, dass T(x)=1 ist, und daraus kann ich dann das jeweils passende a in meiner Formel
---------- T(x)= $ [mm] a\cdot{}x^{log_3 2}+9/7 x^2 [/mm] $ ---------
errechnen, wobei a=a(x) ist.
Beispiel: n=12. Die obige Formel wurde aus der Beziehung [mm] T(n)=2T(n/3)+n^2 [/mm] hergeleitet, wobei die n und n/3, die in derselben Kette liegen, also 4, 4/3, 4/9, aber auch 36,108,.. dasselbe a haben. Man muss allerdings nach unten hin bei 4/9 aufhören, da man <1 ist und hier die 'Rekursion aufhört. Bekannt ist somit, dass a für 12 und 4/9 den selben Wert hat, dass dafür die obige Gleichung gilt und dass T(4/9)=1 ist. Somit
T(4/9)= [mm] a\cdot{}(4/9)^{log_3 2}+9/7 \cdot{} (4/9)^2 [/mm] =1
Das daraus berechnete a gilt dann für n=4, 12, 36,...
Ich beschreibe nun, wie man zu jedem n [mm] \in \IN [/mm] das a und damit die obige Formel bestimmt.
Damit jetzt der Term schreibtechnisch nicht zu unübersichtlich wird, kürze ich hier einiges ab, das man aber in der Endformel wieder ausgeschrieben einsetzen kann.
DEFINITION 1: [mm] k:=log_3 [/mm] 2
Jetzt die Frage, wie oft ich n durch 3 teilen muss, um erstmalig eine Zahl <1 zu bekommen. 1 und 2 muss ich einmel durch 3 teilen, 3 bis 8 zweimal, 9 bis 26 dreimal, 27 bis 80 viermal usw.
[mm] log_3 [/mm] (n) sagt mir fast das Ergebnis:
[mm] log_3(1)=0 [/mm] statt 1
[mm] log_3(2)=0,... [/mm] statt 1
[mm] log_3(3)=1 [/mm] statt 2
[mm] log_3(4)=1,... [/mm] statt 2
....
[mm] log_3(8)=1,... [/mm] statt 2
[mm] log_3(9)=2 [/mm] statt 3
Es bietet sich an, das Ergebnis grundsätzlich nach oben aufzurunden
[mm] \left \lceil{x}\right \rceil [/mm] ist der nach oben auf die nächste ganze Zahl aufgerundete Wert von x.
Betrachten wir nun [mm] \left \lceil{log_3(n)}\right \rceil. [/mm] Damit erhalten wir
[mm] \left \lceil{log_3(1)}\right \rceil=0 [/mm] statt 1
[mm] \left \lceil{log_3(2)}\right \rceil=1
[/mm]
[mm] \left \lceil{log_3(3)}\right \rceil=1 [/mm] statt 2
[mm] \left \lceil{log_3(4)}\right \rceil=2
[/mm]
....
[mm] \left \lceil{log_3(8)}\right \rceil=2
[/mm]
[mm] \left \lceil{log_3(9)}\right \rceil=2 [/mm] statt 3
[mm] \left \lceil{log_3(10)}\right \rceil=3 [/mm]
....
[mm] \left \lceil{log_3(26)}\right \rceil=3 [/mm]
[mm] \left \lceil{log_3(27)}\right \rceil=3 [/mm] statt 4
Das passt schon gut, bis auf die vollen 3-er-Potenzen.
Da wir aber nur die Folgenwerte für natürliche Zahlen berechnen wollen und nicht für beliebige x, mogeln wir ein bisschen, indem wir einfach überall noch 1 hinzuzählen:
[mm] \left \lceil{log_3(1+1)}\right \rceil=1
[/mm]
[mm] \left \lceil{log_3(2+1)}\right \rceil=1
[/mm]
[mm] \left \lceil{log_3(3+1)}\right \rceil=2
[/mm]
[mm] \left \lceil{log_3(4+1)}\right \rceil=2
[/mm]
....
[mm] \left \lceil{log_3(8+1)}\right \rceil=2
[/mm]
[mm] \left \lceil{log_3(9+1)}\right \rceil=3
[/mm]
[mm] \left \lceil{log_3(10+1)}\right \rceil=3 [/mm]
....
[mm] \left \lceil{log_3(26+1)}\right \rceil=3 [/mm]
[mm] \left \lceil{log_3(27+1)}\right \rceil=4
[/mm]
also: Die Zahl n muss [mm] \left \lceil{log_3(n+1)}\right \rceil-mal [/mm] durch 3 dividiert werden, um zum ersten mal unter 1 zu kommen.
DEFINITION 2: r(n)= [mm] \left \lceil{log_3(n+1)}\right \rceil
[/mm]
Damit haben wir uns dann auf die Zahl [mm] x(n)=n/3^{r(n)} [/mm] unter 1 herunterrekurriert. Nun wissen wir:
[mm] T(n/3^{r(n)})=1 [/mm] und damit
[mm] a(n)*(n/3^{r(n)})^k [/mm] + [mm] 9/7*(n/3^{r(n)})^2=1
[/mm]
Daraus ergibt sich [mm] a(n)=(1-9/7*(n/3^{r(n)})^2)/(n/3^{r(n)})^k
[/mm]
sowie
[mm] T(n)=(1-9/7*(n/3^{r(n)})^2)/(n/3^{r(n)})^k [/mm] * [mm] (n)^k [/mm] + [mm] 9/7*(n)^2
[/mm]
mit r(n)= [mm] \left \lceil{log_3(n+1)}\right \rceil [/mm] und [mm] k=log_3 [/mm] 2, was man bei Bedarf auch noch in den Term einsetzen kann.
Tja, so einfach können geschlossene mathematische Formeln sein. Vielleicht findest du auf anderem Weg etwas einfacheres, dann teile das doch bitte hier mit. Ich habe die Formel bis n=12 und dann noch für 27 und 81 getestet, da stimmte sie.
Jetzt gerne noch den Beweis mit Vollst. Induktion...??
|
|
|
| |
|
> Hallo HJKweseleit,
>
> vielen Dank für deine Antwort! Ich habe noch ein paar
> Fragen dazu:
>
> > Für n=10 brauchst du den Wert von 10/3, dafür aber den
> > Wert von (10/3)/3 = 10/9 und dafür den Wert von (10/9)/3 =
> > 10/27<1.
> >
> > Für Vielfache von 3 musst du dich nur um eine Stufe
> > "herunterschrauben", für alle anderen so lange, bis du
> > durch Dritteln auf eine Zahl x <1 stößt.
> Das verstehe ich nicht ganz. Mit vielfachen von 3 ist
> klar, aber warum müssen wir solange teilen, bis x < 1
> ist?
Du musst eigentlich immer teilen, bis x<1 ist, weil erst dann die Rekursion abbricht. Bei x=9 kannst du aber auf T(3) zurückgreifen, falls du die natürlichen Zahlen der Reihe nach durchgehst und daher T(3) schon berechnet hast.
Für T(10) musst du auf T(10/3) zurückgreifen. Hättest du T(10/3) vorher schon berechnet, wür de hier auch ein einziger Schritt reichen. Da aber 10/3 keine natürliche Zahl ist, hast du diesen Wert vermutlich noch nicht berechnet.
Wenn du nur T(81) berechnen sollst und vorher noch nichts berechnet hast, musst du der Reihe nach auf T(27), T(9), T(3), T(1) und T(1/3)=1 zurückgreifen.
>
> > Dafür brauchst
> > du k = [mm]aufgerundet(log_3(n))[/mm] Schritte, für n=10 also k = 3
> > Schritte. Nun bist du unter 1 mit einem Bruch x, dessen
> > Nenner [mm]3^k[/mm] ist.
> >
> > Es ist T(10/27)=1 laut Rekursionsvorschrift.
> > [mm]T(10/9)=2*T(10/27)+1(10/9)^2=2+100/81=262/81[/mm]
> >
> > Durch das Quadrieren erhältst du einen Nenner
> > [mm](3^{k-1})^2=3^{2k-2},[/mm] hier [mm]3^4=81.[/mm]
> >
> > T(10/3) ergibt sich zu [mm]2*T(10/9)+(10/3)^2=524/81+100/9[/mm] =
> > 1424/81
> >
> > und endlich [mm]T(10)=2*T(10/3)+10^2=2848/81+100=10948/81.[/mm]
>
> Also, führt die Berechnung für jedes n, was nicht
> vielfache von 3 ist, zurück auf die Rekursionsvorschrift
> zurück?
Jedes n führt auf die Rekursionsvorschrift zurück. Bei Vielfachen von 3, sagen wir mal n=15, kommst du aber sofort im nächsten Schritt auf eine natürliche Zahl (hier 15/3 = 5), die du wahrscheinlich schon benutzt hast, wenn du die natürlichen Zahlen der Reihe nach durchgegangen bist.
>
> Ich versuche jetzt noch mal:
> T(0) = 1
>
> T(1) = 1 ![[notok]](/images/smileys/notok.gif "[notok]")
Nein: Da nicht 1<1 ist, ist [mm] T(1)=2*T(1/3)+1^2=2*1+1=3
[/mm]
Jetzt werden natürlich alle auf T(1) aufbauenden Folgeglieder falsch.
>
> T(2) = [mm]2T(2/3)+2^2[/mm] = 2T(0)+4 = 6 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> T(3) = [mm]2T(3/3)+3^2[/mm] = 2T(1)+9 = 11 T(3)=15
>
> T(4) = [mm]2T(4/3)+4^2[/mm] = [mm]2(2T(4/9)+(4/3)^2)+4^2[/mm] = 2(2*1 + 16/9)
> + 16 = 20+32/9 = 212/9
> Ist es korrekt?
>
> T(5) = [mm]2T(5/3)+5^2[/mm] = [mm]2(2T(5/9)+(5/3)^2)+5^2[/mm] = 2(2*1 + 25/9)
> + 25 = 29+50/9 = 311/9
>
> T(6) = [mm]2T(6/3)+6^2[/mm] = 2T(2)+36= 2*6 + 36 = 48
>
> T(7) = [mm]2T(7/3)+7^2[/mm] = [mm]2(2T(7/9)+(7/3)^2)+49=[/mm] 2(2*1+49/9)+49
> = 53+98/9 = 575/9
>
> T(8) = [mm]2T(8/3)+8^2[/mm] = [mm]2(2T(8/9)+(8/3)^2)+64=[/mm] 2(2*1+64/9)+64
> = 68+128/9 = 740/9
>
> T(9) = [mm]2T(9/3)+9^2[/mm] = 2T(3) + 81 = 2*11 + 81 = 103 T(9)=111
>
> T(10) = 10948/81 (Habe ich von dir übernommen)
>
> > Wenn du eine geschlossene Funktionsformel suchst, wirst du
> > wohl den abgerundeten [mm]log_3[/mm] einbauen müssen.
> Tut mir leid, aber hier brauche ich auch Hilfe. Wie macht
> man das? Muss man versuchen irgendwie geschickt zu raten?
>
> > Mit viel Glück funktioniert diese Formel dann auch für
> ganzzahlige
> > Vielfache von 3.
> Klingt ja sehr vielversprechend
>
> Nachtrag:
> Ich habe mich noch ein bisschen weiter informiert und habe
> noch etwas herausgefunden:
>
> Wir können die Rekursionsgleichung wie folgt umformen:
> [mm]T(n)=2T(n/3)+n^2
= 2(2T(n/9)+ (n/3)^2)+n^2 = 4T(n/9)+(2/9)n^2+n^2
= 4(2T(n/27)+(n/9)^2)+(2/9)n^2+n^2
= 8T(n/27) + (2/9)^2 * n^2 + (2/9)^1 * n^2 + (2/9)^0 * n^2[/mm]
>
> Hier ist ja schon eine Gesetzmäßigkeit vorhanden. Wir
> haben T(1) = 1 und vielleicht können wir zunächst
> annehmen (warum wir das dürfen verstehe ich noch nicht)
> dass [mm]n=3^k[/mm] (also [mm]log_3(n)=k)[/mm] ist. Dann können wir das
> (möglicherweise) so umschreiben:
> [mm]T(n)= \summe_{i=0}^{k-1} (2/9)^i + X[/mm]
> Wie man X ermittelt
> verstehe ich jetzt leider auch nicht.
Ich kann mir nicht vorstellen, dass eine solche Summe die gesuchte "geschlossene Form" sein soll. Das sieht ja noch komplizierter aus als die rekursive Definition.
> Könntest du mir hier (auch) einen Tipp geben?
>
> Noch mal vielen vielen Dank und viele Grüße
> Hela123
>
|
|
|
| |
|
> Hallo HJKweseleit,
>
> vielen vielen Dank für deine Antwort!
>
> > > Ich versuche jetzt noch mal:
> > > T(0) = 1
> > >
> > > T(1) = 1
> >
> > Nein: Da nicht 1<1 ist, ist [mm]T(1)=2*T(1/3)+1^2=2*1+1=3[/mm]
> > Jetzt werden natürlich alle auf T(1) aufbauenden
> > Folgeglieder falsch.
>
> Hier hatte ich mich auch vertan gehabt:
> [mm]T(n)=\left\{\begin{matrix}
2T(n/3)+n^2, & \mbox{falls }n>1\mbox \\
1, & \mbox{sonst}
\end{matrix}\right.[/mm]
>
> für alle n>1 nehmen wir die Rekursionsformel und für alle
> n<=1 (!!!) nehmen wir T(n)=1.
> Deshalb gilt auch T(1)=1. Ist doch so, oder?
Völlig korrekt!!! Ich habe nicht aufgepasst. Daher muss meine Formel (nur) so korrigiert werden, dass nun
[mm] r(n)=\lceil{log_3(n)} \rceil [/mm] statt r(n)= [mm] \left \lceil{log_3(n+1)}\right \rceil [/mm] heißen muss. Die Überlegung mit +1 fällt also weg, alles andere bleibt, wie es ist.
>
> In der Aufgabenstellung (bei "Hinweis") stand, dass es
> reicht, eine gute obere Schranke zu finden.
Das habe ich überhaupt nicht verstanden. Eine obere Schranke ist normalerweise eine feste Zahl, die von den Folgegliedern nicht überschritten wird. Diese Folge geht aber nach unendlich und hat infolge dessen gar keine obere Schranke. Die Aufgabenstellung hätte also heißen müssen:
Geben Sie eine Folge mit einem einfachen geschlossenen Term an, die T(n) nach oben hin abschätzt.
> Dies habe ich
> bei 1) und 3) in Anspruch genommen. Bei 2) war es nicht so
> schwer geschlossene Formel zu finden.
>
> Also noch mal mein Ansatz:
>
> [mm]T(n)=2T(n/3)+n^2[/mm]
>
> [mm]= 2(2T(n/9)+ (n/3)^2)+n^2 = 4T(n/9)+(2/9)n^2+n^2[/mm]
>
> [mm]= 4(2T(n/27)+(n/9)^2)+(2/9)n^2+n^2[/mm]
>
> [mm]= 8T(n/27) + (2/9)^2 * n^2 + (2/9)^1 * n^2 + (2/9)^0 * n^2[/mm]
>
> Wir haben T(1) = 1 und nehmen an, dass [mm]n=3^k[/mm] (also
> [mm]log_3(n)=k)[/mm] ist (analog zu einer Aufgabe aus der
> Vorlesung).
>
> Dann:
> [mm]T(n)= n^2 \summe_{i=0}^{k-1} (2/9)^i + 2^k[/mm] (***)
>
> [mm]=n^2 \summe_{i=0}^{log_3(n)-1} (2/9)^i + n^{log_3(2)}[/mm]
Hier hast du dich verschrieben, der letzte Summand ist [mm] 2^{log_3(n)}. [/mm] bleibe aber besser bei k, weil es ein aufgerundeter Logarithmus ist.
>
[mm]< n^2 \summe_{i=0}^{\infty} (2/9)^i + n^{log_3(2)}[/mm]
Hier auch [mm] 2^{log_3(n)}, [/mm] also
T(n)< [mm] n^2 \summe_{i=0}^{\infty} (2/9)^i [/mm] + [mm] 2^{log_3(n)} [/mm] (***)
>
> [mm]= n^2 * C + n^{log_3(2)}[/mm]
>
> [mm]\le n^2 * C'[/mm]
Vorsicht: mit n steigt auch der zweite Summand ständig an und wird nicht durch eine Konstante C' nach oben beschränkt.
>
> Jetzt Induktionsbeweis:
>
> IA: [mm]T(1) = 1 < C'*1 für C'>1[/mm] erfüllt
>
> IV: [mm]T(n)
>
> IS:
> [mm]T(n) = 2T(n/3) + (n)^2[/mm]
>
> [mm]\le 2C'(n/3)^2 + n^2[/mm]
>
> [mm]= 2/9 C'n^2 + n^2[/mm]
>
> [mm]\le C'' n^2[/mm]
Du kannst nicht eine Konstante C' durch eine andere C'' ersetzen, die vielleicht immer größer wird. Am einfachsten ist es, wenn du C' als Wert angibst. Dafaür musst du nur einen passenden Wert suchen, am einfachsten geht es mit 2/9 C'=2:
Behauptung:
T(n) < 2 [mm] n^2
[/mm]
I-Anfang: T(1)=1 < [mm] 2*1^2=2 [/mm] stimmt
I-Voraussetzung: Es gelte für 1 < i [mm] \le [/mm] n-1: [mm] T(i)<2*i^2
[/mm]
I-Schritt: [mm] T(n)=2T(n/3)+n^2 [/mm] < [mm] 2*(2*(n/3)^2) [/mm] + [mm] n^2 [/mm] = [mm] 4/9*n^2+n^2=13/9*n^2<2*n^2
[/mm]
Leider ist das aber ein Pseudo-Beweis!!!
Um zu beweisen, dass auch [mm] T(7)<2*7^2 [/mm] ist, greifst du im Induktionsschritt auf [mm] T(7/3)<2*(7/3)^2 [/mm] zurück, was aber gar nicht bewiesen ist, denn 7/3 ist keine natürliche Zahl, und du führst den Beweis ja nur für natürliche Zahlen durch, weißt also, das die Behauptung für 1,2,3,4,5 und 6 gilt, aber nicht, ob auch für 7/3, denn das hast du ja gar nicht bewiesen.
Ich möchte dir das mal an einer leichten Abwandlung der Aufgabe zeigen:
T(n)=2 T(n/3)+ [mm] n^2 [/mm] für n>1 wie bisher, aber 9/7 sonst.
Dann ist T(1)=9/7 und
[mm] T(2)=2*T(2/3)+2^2=2*9/7+4 [/mm] = 18/7+28/7=46/7
(falsche) Behauptung: [mm] T(n)=9/7*n^2
[/mm]
Beweis: T(1)=9/7 stimmt
nun gelte die Behauptung für alle [mm] 1\le [/mm] i [mm] \le [/mm] n-1. Dann ist
[mm] T(n)=2T(n/3)+n^2 [/mm] = [mm] 2(9/7*(n/3)^2)+n^2=2/7*n^2+n^2=9/7*n^2
[/mm]
Also stimmt die Formel.
Aber: Demnach wäre [mm] T(2)=9/7*2^2=36/7 [/mm] statt 46/7.
Durch die Rekursion greifen wir nämlich für n=2 auf [mm] T(2/3)=9/7*(2/3)^2 [/mm] zurück, was aber gar nicht stimmt.
Durch Vollständige Induktion lässt sich also hier gar nichts beweisen, außer für n=Dreierpotenz.
>
> Was hälst du davon? Die geschlossene Form habe ich nicht
> versucht zu suchen, weil es mir auch viel zu komliziert
> erschien...
Nein: Du hast sie gefunden, und zwar ist es die von mir mit (***) gekennzeichnete Formel. Sie lässt sich wegen der geometrischen Reihe vereinfachen zu
[mm] T(n)=n^2*(1-(2/9)^k)/(7/9) [/mm] + [mm] 2^k
[/mm]
und damit hast du eine viel einfachere Darstellung als ich gefunden!!! (k ist wieder der aufgerundete [mm] log_3(n)).
[/mm]
Diese lässt sich nun wieder wie in (***) abschätzen:
[mm] T(n)
>
> Noch mal danke und viele Grüße
> Hela123
|
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Deine Formel
$ T(n)=n^2\cdot{}(1-(2/9)^k)/(7/9) $ + $ 2^k $
stimmt übrigens mit meiner
$ T(n)=(1-9/7\cdot{}(n/3^{r(n)})^2)/(n/3^{r(n)})^k $ * $ (n)^k $ + $ 9/7\cdot{}(n)^2 $
überein, weil man meine noch vereinfachen kann. Dabei entspricht dein k meiner Funktion r(n) und mein k dem Wert log_3(2). Zum Vergleich forme ich meine Formel um zu
$ T(n)=(1-9/7\cdot{}(n/3^k})^2)/(n/3^k)^{log_3 (2)}*(n)^{log_3 (2)} $ + $ 9/7\cdot{}(n)^2 $
= (1-9/7\cdot{}(n^2/3^2^k))/(n^{log_3 (2)}/3^{log_3 (2)}^k)*(n)^{log_3 (2)} + 9/7\cdot{}(n)^2
= (1-9/7\cdot{}(n^2/9^k))*(2^k/(n^{log_3 (2)})*(n)^{log_3 (2)} + 9/7\cdot{}(n)^2
= (1-9/7\cdot{}(n^2/9^k))*(2^k) + 9/7\cdot{}(n)^2
= 2^k-9/7\cdot{}(n^2*2^k/9^k)) + 9/7\cdot{}(n)^2
= 2^k+9/7\cdot{}(n^2-n^2*(2/9)^k)
= 2^k+n^2(1-(2/9)^k)/(7/9)
Deine Herleitung ist allerdings eleganter, kürzer und im Ergebnis kompakter.
|
|
|
| |
|
Ich habe nun doch einen Beweis durch vollständige Induktion gefunden, der aber nicht über n geht.
Für beliebiges n sei k der auf eine ganze Zahl aufgerundete [mm] log_3(n). [/mm] Dann ist [mm] 1/3
Behauptung: T(n) < 9 [mm] n^2.
[/mm]
Hilfsbehauptung: Für i=0,1,2,... ist
[mm] T(n*3^i/3^k)<9*(n*3^i/3^k)^2.
[/mm]
Beweis durch VI über i (nicht über n !!!).
Induktionsanfang: i=0: [mm] T(n*3^0/3^k)=T(n/3^k)=1=9*(1/3)^2<9*(n/3^k)^2
[/mm]
Induktionsvoraussetzung: Es gelte nun für i-1: [mm] T(n*3^{i-1}/3^k)<9*(n*3^{i-1}/3^k)^2
[/mm]
Induktionsschritt: Dann ist [mm] T(n*3^i/3^k)=2*T(n*3^{i-1}/3^k)+ (n*3^i/3^k)^2<2*9*(n*3^{i-1}/3^k)^2+(n*3^i/3^k)^2=2*(n*3*3^{i-1}/3^k)^2+(n*3^i/3^k)^2=2*(n*3^i/3^k)^2+(n*3^i/3^k)^2=3(n*3^i/3^k)^2<9*(n*3^i/3^k)^2
[/mm]
Somit gilt die Behauptung für alle i, und damit insbesondere für i=k:
T(n) = [mm] T(n*3^k/3^k)<9*(n*3^k/3^k)^2 [/mm] = 9 [mm] n^2.
[/mm]
Bemerkung: Hier braucht man tatsächlich den Faktor 9 zur Abschätzung.
Beispiel: n=244, [mm] log_3(244)=5,003738..., [/mm] k=6.
Dann ist für i=0 der Wert [mm] n/3^k [/mm] = 0,3347... und somit
[mm] T(n/3^k)=1<1,008247...=9*(0,3347...)^2.
[/mm]
|
|
|
|
