Hallo zusammen!
Wir nehmen gerade das Thema O-Notation durch. Ich glaube, dass ich es
eigentlich auch soweit verstanden habe. Bei einer Aufgabe fehlt mit
allerdings der Ansatz.
Folgende Aufgabenstellung:
Zeigen Sie, dass für jedes feste k gilt, dass
aber nicht
Für diese Aufgabe können Sie die Grenzwert-Definition von O und Omega
verwenden.
So, bei O muss der Grenzwert dann kleiner unendlich sein, weshalb die
Bedingung dann so aussieht:
wenn ich aber den Grenzwert davon bilde kommt dabei aber raus:
Wenn ich mit L'Hospital drangehe wird der Ausdruck noch grausliger. Wie
kann ich also hier argumentieren?
Ich möchte hier keine vorgekaute Lösung. Vielmehr geht es mir darum,
dass mir jemand zeigen kann wie ich die Aufgabe richtig angehe und auch
mathematisch richtig argumentieren kann.
Vielen Dank für jede Hilfe!!!
Flo
Für die Grenzwert-Definition von O:
wenn du den Zähler ein wenig umformst und den konstanten Faktor ln 2
unterschlägst (darfst du im Hinblick auf die Endlichkeit ja machen),
lautet er ln (kn). Die Ableitung nach n und damit der l'Hopital verliert
doch damit ihren Schrecken.
Flo schrieb:> Wenn ich mit L'Hospital drangehe wird der Ausdruck noch grausliger. Wie> kann ich also hier argumentieren?>
Ich glaub das hat er schon versucht... ;)
Fuer O:
mehrfache Anwendung von L'Hospital.
erstes Mal:
k*(log(n)^(k-1))/n
Darauf ist L'Hospital wieder erlaubt weil...
Irgendwann ist der Zaehler konstant.
Ohne Garantie, das ist alles schon so lange her.
Gruss
josef
Hi!
Danke, für die Antworten. Mehrfach L'Hospital habe ich schon versucht
(zu erst von Hand und dann mit CAS). Zumindest bis zur 4. Ableitung. Mit
jedem Ableiten wird der Ausdruck nur noch schlimmer. Das sollte
eigentlich nur eine kleine Übungsaufgabe sein. Es muss hier einen
besonderen Kniff geben.
Ich denke der Ansatz vom Mechatroniker ist vielversprechend. Dies
versuche ich gleich mal und stells dann auch hier rein!
Flo
Beim ersten Teil ist doch die Frage, ob für jedes feste k für ein sehr
großes n gilt:
(log n)^k < n
also umgeformt
n^k < 2^n
Nun gehört es doch zu den Grundlagen, dass links (polynomiell) langsamer
wächst als rechts (exponentiell) und entsprechende formale Beweise
findet man allenthalben.
Einfach etwas kreativer an Mathematik herangehen!
Zum Gruße
Noch etwas:
Flo, so wie Du es oben gemacht hast, bildet man auch keine Grenzwerte,
also dass Du Zähler und Nenner individuell betrachtest.
Schau Dir mal ein gutes Analysis-Buch an, z.B. Königsberger etc.
ok, die 4. Anwendung von L'Hospital gibt
k*(k-1)*(k-2)*(k-3)*(log(n)^(k-4))/n
oder?
@Gustl: Bei divergentem Zaehler und Nenner und L'Hospital
betrachtet man aber schon Zaehler und Nenner extra.
@Josef: Ja, bringt aber nichts, wie wir hier sehen.
Ich persönlich finde, hier mit L'Hospital loszulegen ist wie mit Kanonen
auf Spatzen schießen. Es bedeutet, dass man irgendein Werkzeug verwendet
ohne zu verstehen, worum es in der Aufgabe geht.
Königsberger Analysis 1, S. 42:
lim_{n->\infty} n^k / z^n = 0
entspricht meiner obigen Aussage.
Beweis über Binomialentwicklung.
Es ist sowieso Grundlage zu wissen, dass Expontialfunktionen schneller
wachsen als jedes Polynom. Und wichtig ist lediglich, zu erkennen, dass
diese Aussage hinter der Aufgabe steckt.
Meine Meinung.
@der mechatroniker:
ja habe ich gesehen. Ist an meiner Ableitung was falsch?
@Gustl:
Sicher ist es besser wenn man den Grenzwert direkt bilden kann.
Wenn einem nichts mehr einfaellt versucht man es halt mit L'Hospital.
Dann haben wir jetzt ja schon zwei Loesungen.
Also, danke nochmal euch allen!!!
Ich habe jetzt nochmal ein bisschen rumgerechnet und mit L'Hospital
komme ich einfach nicht weiter! Selbst wenn ich wie der Mechatroniker im
zweiten Beitrag den Zähler so umforme:
(log2(n))^k = (C*ln(n))^k = C^k*(ln(n))^k
Dann kann ich die Umwandlungskonstante C^k von den Limes ziehen sodass
ich im Zähler nur noch
(ln(n))^k stehen habe.
Sieht einfach aus, da man denkt ln(n) abgeleitet ergibt 1/x aber durch
die Produktregel durch das ^k wird der Zähler mit jeder Ableitung immer
schlimmer, sodass ich hier nichts beweisen kann.
Ich habe es jetzt nach Gustls Methode gezeigt! Interessanter
Lösungsansatz! Muss man drauf kommen...
Allerdings dürfen wir so etwas wie n^k<2^n nicht einfach annehmen,
obwohl es eigentlich logisch ist. Das müssen wir beweisen.
Ich habe es nun folgendermaßen begründet:
Da k=const wächst der Zähler nun polynomiell, der Nenner wächst
exponentiell.
Polynom: f1(x)=a0 + a1*x + a2*x^2 + ... + an*x^x
Exponentialfunktion: f2(x)=1 + 1/(2!)*x^2 + 1/(3!)*x^3 + ...
Das Polynom hat für ein konstantes k also eine endliche Summe, die
Taylorreihenentwicklung einer Exponentialfunktion eine unendliche. Damit
wächst für sehr große n die Exponentialfunktion stärker als das Polynom.
Kann man das so schreiben?
Nochmals vielen Dank an alle!!!
Flo
Eine Frage noch. Wir sollen noch zeigen, dass die Behauptungen nicht
gelten, wenn k von n abhängt.
Wenn k=const. gilt ja wie Gustl gezeigt hat:
(log2(n))^k < n --> n^k < 2^n
Wenn k von n abhängt sage ich k=l+n. Stimmt dann meine Umformung???:
(log2(n))^(l+n) < n --> n^(l+2^n) < 2^n
Dann kann ich doch zeigen, dass sowohl die linke Basis für große n
größer der rechten Basis ist und auch der der linke exponent für große n
größer als der rechte exponent ist.
Da größer^größer > kleiner^kleiner ist ist nun die linke Seite größer.
Flo
Flo, ich habe einen Fehler gemacht... und keiner hat's gemerkt :-)
Meine erste Umformung stimmt nicht, weil ich's mir ohne Klammern auf ein
Blatt geschrieben hatte und weitergerechnet.
Entschuldigung!
Es ist zu zeigen:
(log n)^k < n für große n
heisst:
n < 2^(n^(1/k)) für große n
Grundsätzlich bleibt es aber eine "ähnliche" Situation: Nun ist links
etwas lineares und rechts (noch immer) etwas exponentielles. Wie auch
immer, der Lösungsweg über "Rechnen" ist schon richtig.
----
Zu Deiner anderen Aufgabe: Es ist die Frage, ob man zeigen soll, dass es
allgemein nicht gilt, wenn man k als Funktion von n ansetzt, also k(n).
Dann wird es komplizierter und man müsste wahrscheinlich eine
Fallunterscheidung machen, je nachdem, in welche Richtung sich k(n)
bewegt. Falls es reicht, dass Du nur ein Bsp bringst, dann nehme
k(n):=n.
Dann gilt
lim_{n->\infty} 2^(n^(1/k)) = lim... 2^(n^(1/n)) = 2, denn
lim_{n->\infty} n^{1/n} = 1
Damit wäre gezeigt, dass für diesen Fall nicht
(log n)^k = O(n) gilt.
------------
Das alles findet man aber instantan durch Denken und Nachschlagen in
Analysis 1 raus. Bitte tun!
Und Deine Argumentation bei der Reihenentwicklung scheint mir noch etwas
holprig, da man auch die Koeffizienten vor den Gliedern betrachten muss.
Richtig wär's, es ganz konkret per Ungleichung nachzuweisen.
Vielleicht ist alles etwas kompliziert, aber man lernt viel dabei.
Nun also viel Spaß beim selbstständigen Bearbeiten der Aufgabe.
Gruß
Gustl, vielen Dank für deine Bemühungen! Hast mir wirklich sehr
geholfen!
So langsam machts auch wieder Klick und ich merke wie man langsam wieder
in die Materie reinkommt! Hatte die letzten 4 Jahre mit dieser Art der
Mathe wenig zu tun und bin leider etwas aus der Übung!
Zu der Umformung, ich habe wirklich darüber nachgedacht, ob die
Umformung so stimmt, da bei der Umformung das ^k ja völlig ausser Acht
gelassen wurde. Deshalb war auch meine Frage ob diese Umformung von mir
so stimmt:
(log2(n))^(l+n) < n --> n^(l+2^n) < 2^n
Ich hatte hier irgendwie ein ungutes Gefühl konnte es aber nicht
erklären. Dank diener Hilfe kann ich es jetzt!
Naja und mathematische Beweise habe ich nie auf die richtig
mathematische Weise gelernt. Bisher hat es immer gereicht wenn wir es
"ingenieursmäßig" beweisen, mit der Fussnote, dass es mathematisch nicht
ganz korrekt ist.
Mit deiner Aussage "Vielleicht ist alles etwas kompliziert, aber man
lernt viel dabei" hast du definitiv recht. Nach 2 Tagen auf der Leitung
stehen und die verschiedenen Lösungsansätze durchrechnen merke ich
definitiv eine großen Fortschritt im Verständnis! Ich werde mich übers
WE nochmals mit der Aufgabe beschäftigen...
Flo
Thread beobachten
Seitenaufteilung abschalten