Asymptotische Beschränkung < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Seien f,g,h: [mm] \IN \to \IR_{\ge0} [/mm] die wie folgt definierten Funktionen:
f(n):= [mm] (n^{5}+n^{4}+7)/(n^3+n+1),
[/mm]
g(n):= [mm] n^{2}/3 [/mm] und
h(n):= [mm] 8n^{2}+9.
[/mm]
Zeigen Sie, dass f [mm] \in [/mm] O(g), g [mm] \in [/mm] O(h) und h [mm] \in [/mm] O(g) gelten. |
Wir haben f [mm] \in [/mm] O(g) so definiert:
f [mm] \in [/mm] O(g) [mm] \gdw \exists [/mm] c [mm] \in \IR_{\ge 0} [/mm] : [mm] \exists [/mm] m [mm] \in \IN [/mm] : [mm] \forall [/mm] n [mm] \in \IN_{\ge m}:f(n)\le [/mm] c*g(n)
Ich meine es gilt, wenn c=5 und m=2.
Aber dies habe ich nur herrausgefunden durch anschauen und rumprobieren.
Jetzt die eigentliche Frage: Wie finde ich die Werte rechnerisch raus bzw. wie führe ich für sowas ein beweis?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:32 Sa 21.01.2012 | | Autor: | fred97 |
> Seien f,g,h: [mm]\IN \to \IR_{\ge0}[/mm] die wie folgt definierten
> Funktionen:
> f(n):= [mm](n^{5}+n^{4}+7)/(n^3+n+1),[/mm]
> g(n):= [mm]n^{2}/3[/mm] und
> h(n):= [mm]8n^{2}+9.[/mm]
> Zeigen Sie, dass f [mm]\in[/mm] O(g), g [mm]\in[/mm] O(h) und h [mm]\in[/mm] O(g)
> gelten.
> Wir haben f [mm]\in[/mm] O(g) so definiert:
> f [mm]\in[/mm] O(g) [mm]\gdw \exists[/mm] c [mm]\in \IR_{\ge 0}[/mm] : [mm]\exists[/mm] m [mm]\in \IN[/mm]
> : [mm]\forall[/mm] n [mm]\in \IN_{\ge m}:f(n)\le[/mm] c*g(n)
>
> Ich meine es gilt, wenn c=5 und m=2.
> Aber dies habe ich nur herrausgefunden durch anschauen und
> rumprobieren.
>
> Jetzt die eigentliche Frage: Wie finde ich die Werte
> rechnerisch raus bzw. wie führe ich für sowas ein
> beweis?
>
>
Es gilt: [mm] \bruch{f(n)}{g(n)} \to [/mm] 3 für n [mm] \to \infty
[/mm]
Sei nun c>3. Dann gibt es ein m [mm] \in \IN [/mm] mit:
[mm] \bruch{f(n)}{g(n)} \le [/mm] c für n [mm] \ge [/mm] m
FRED
|
|
|
| |
|
> Es gilt: [mm]\bruch{f(n)}{g(n)} \to[/mm] 3 für n [mm]\to \infty[/mm]
>
> Sei nun c>3. Dann gibt es ein m [mm]\in \IN[/mm] mit:
>
> [mm]\bruch{f(n)}{g(n)} \le[/mm] c für n [mm]\ge[/mm] m
>
> FRED
Also muss man erst schauen wo sich [mm] \bruch{f(n)}{g(n)} [/mm] annähert um c zufinden.
Und dann ist c [mm] \ge [/mm] m?
Im graphen sieht es so aus als wäre m der schnittpunkt von
[mm] \bruch{f(n)}{g(n)} [/mm] und f(n). Also hier Schnittpunkt von [mm] \bruch{f(n)}{g(n)} [/mm] und f(n) ist (1,73|3.98) da uns nur der "x" wert interessiert müsste m = 2 sein, da m ja aus den Natürlichen Zahlen kommt. Ist das so richtig oder ist das grade nur Zufall?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:15 Sa 21.01.2012 | | Autor: | leduart |
Hallo
Nein , nicht wo sie sich annähern, sonder wo der Quotient fr große n hingeht.
wichtig ist, dass man dran denkt: man muss nicht das kleinst mögliche c finden. falls das kleist mögliche etwa 5 ist wäre auch c=20 oder c=1000 eine richtige mögliche lösung. deshalb kann man grob abschätzen. z_Bsp
$ [mm] (n^{5}+n^{4}+7)/(n^3+n+1),<(n^5+n^5+n^5)/n^3 [/mm] für n>1$
(Zähler vergrößert Nenner verkleinert
als [mm] f(n)
entsprechend
[mm] 8n^2+9<8n^2+n^2 [/mm] für n>3 dann hat man c=?
Gruss leduart
|
|
|
| |
|
Also gut, somit finde ich also meine m und c werte raus.
Nun habe ich für:
f [mm] \in [/mm] O(g), c= 4 m=5.
Das heißt ich muss aber immer noch Zeigen,
dass [mm] \forall [/mm] n [mm] \in \IN_{\ge 5}: [/mm] f(n) [mm] \le [/mm] 4*g(n) gilt.
Wie geht man an sowas ran?
Durch einsetzen erhalte ich schonaml f(5)~28,7 [mm] \le [/mm] 33,3 ~ 4*g(n), das ist natürlich wahr. Aber muss ich nicht irgendwas allgemeines als Beweis haben, das mir sagt, dass es nicht doch irgendwo bei 1235543 f(n) > 4*g(n) gilt?
Wie macht man soeinen Beweis?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:39 Sa 21.01.2012 | | Autor: | leduart |
Hallo
ich dachte das hab ich geschrieben ? lies meinen post bitte genau. was brauchst du mehr?
Gruss leduart
|
|
|
|
