Grenzwerte direkt ablesen < Folgen+Grenzwerte < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:11 Sa 14.02.2015 | | Autor: | Argot |
| Aufgabe | | Gilt [mm] n^{1/n} [/mm] = [mm] O(\frac{ln(n)}{n}) [/mm] ? |
Ich habe diese Aufgabe mit Hilfe von Lemma 1.4 aus dem Buch "Entwurf und Analyse von Algorithmen" wie folgt umgestellt:
lim n → [mm] \infty \frac{n^{1/n}}{\frac{ln(n)}{n}}. [/mm] Ich weiß, dass lim [mm] n^{1/n} [/mm] = 1 und lim [mm] \frac{ln(n)}{n} [/mm] = 0 ist. Ein Freund von mir meint, dass das ausreichend wäre um zu zeigen, dass die Behauptung der Aufgabe nicht korrekt ist, da kein Grenzwert existiert.
Wenn ich die Formel allerdings umstelle, erhalte ich lim n → [mm] \infty \frac{n^{1/n} n}{log(n)} [/mm] und kann als "Grenzwert" [mm] \infty [/mm] mit Hilfe von der Regel von L'Hospital berechnen. Damit kann ich auch zeigen, dass der Grenzwert nicht existiert.
Genügt der Vorschlag von meinem Freund oder kann nur das vollständige ausrechnen zeigen, dass die Behauptung falsch ist?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:49 Sa 14.02.2015 | | Autor: | DieAcht |
Hallo Argot!
> Gilt [mm]n^{1/n}[/mm] = [mm]O(\frac{ln(n)}{n})[/mm] ?
> Ich habe diese Aufgabe mit Hilfe von Lemma 1.4 aus dem
> Buch "Entwurf und Analyse von Algorithmen" wie folgt
> umgestellt:
>
> lim n → [mm]\infty \frac{n^{1/n}}{\frac{ln(n)}{n}}.[/mm] Ich
> weiß, dass lim [mm]n^{1/n}[/mm] = 1 und lim [mm]\frac{ln(n)}{n}[/mm] = 0
> ist. Ein Freund von mir meint, dass das ausreichend wäre
> um zu zeigen, dass die Behauptung der Aufgabe nicht korrekt
> ist, da kein Grenzwert existiert.
Bei dieser Argumentation werden die Grenzwertsätze angewendet,
allerdings sind hier nicht alle Voraussetzungen dafür gegeben!
Wegen [mm] $\ln(n)/n\to [/mm] 0$ für [mm] n\to\infty [/mm] ist nämlich der Grenzwert des Nenners
Null, so dass gilt:
[mm] \lim_{n\to\infty}\frac{n^{1/n}}{\frac{\ln(n)}{n}}\not=\frac{\lim_{n\to\infty}n^{1/n}}{\lim_{n\to\infty}\frac{\ln(n)}{n}}.
[/mm]
> Wenn ich die Formel allerdings umstelle, erhalte ich lim n
> → [mm]\infty \frac{n^{1/n} n}{log(n)}[/mm] und kann als
> "Grenzwert" [mm]\infty[/mm] mit Hilfe von der Regel von L'Hospital
> berechnen. Damit kann ich auch zeigen, dass der Grenzwert
> nicht existiert.
Mit L'Hôpital schießt du aber mit Kanonen auf Spatzen! Überlege
dir noch einmal ganz in Ruhe ein Argument für
[mm] \lim_{n\to\infty}\frac{n^{1/n}}{\frac{\ln(n)}{n}}=\infty.
[/mm]
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:40 So 15.02.2015 | | Autor: | Argot |
Vielen Dank für die Antwort. Ich sehe leider nicht, auf was Du mich hinweisen möchtest, daher zeige ich meine Umwandlungen, die ich vor L'H verwendet habe. Vielleicht ist ja dort schon der Trick zu finden, welchen ich übersehe.
$ [mm] \lim_{n\to\infty}\frac{n^{1/n}}{\frac{\ln(n)}{n}}=\lim_{n\to\infty}\frac{n^{1/n} \cdot n}{\ln(n)} [/mm] = [mm] \lim_{n\to\infty}\frac{n^{1/n+1}}{\ln(n)}$
[/mm]
Genügt möglicherweise [mm] $\lim_{n\to\infty}\frac{n^{1/n} \cdot n}{\ln(n)} [/mm] $ aus um [mm] $\infty$, [/mm] also keinen Grenzwert, zu folgern, da $n >> ln(n)$ (für positive $n$, d.h. mit [mm] $n\to\infty$ [/mm] erfüllt)?
|
|
|
| |
|
Hallo Argot,
> Vielen Dank für die Antwort. Ich sehe leider nicht, auf
> was Du mich hinweisen möchtest, daher zeige ich meine
> Umwandlungen, die ich vor L'H verwendet habe. Vielleicht
> ist ja dort schon der Trick zu finden, welchen ich
> übersehe.
>
> [mm]\lim_{n\to\infty}\frac{n^{1/n}}{\frac{\ln(n)}{n}}=\lim_{n\to\infty}\frac{n^{1/n} \cdot n}{\ln(n)} = \lim_{n\to\infty}\frac{n^{1/n+1}}{\ln(n)}[/mm]
>
> Genügt möglicherweise [mm]\lim_{n\to\infty}\frac{n^{1/n} \cdot n}{\ln(n)}[/mm]
> aus um [mm]\infty[/mm], also keinen Grenzwert, zu folgern, da [mm]n >> ln(n)[/mm]
> (für positive [mm]n[/mm], d.h. mit [mm]n\to\infty[/mm] erfüllt)?
Naja, immerhin ist [mm] n^{1/n}>1, [/mm] also auch [mm] \br{n*n^{1/n}}{\ln{n}}>\br{n}{\ln{n}}.
[/mm]
Hilft das schon weiter?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:08 Di 17.02.2015 | | Autor: | Argot |
> Naja, immerhin ist [mm]n^{1/n}>1,[/mm] also auch
> [mm]\br{n*n^{1/n}}{\ln{n}}>\br{n}{\ln{n}}.[/mm]
>
> Hilft das schon weiter?
>
> Grüße
> reverend
Auf [mm] $\frac{n}{ln(n)}$ [/mm] würde ich sofort L'H werfen und [mm] $n^2$ [/mm] erhalten, was durch einen Limes gegen [mm] $\infty$ [/mm] wie erwartet gegen [mm] $\infty$ [/mm] divergiert. Damit habe ich allerdings dann doch den L'H verwendet. Mir ist noch nicht aufgefallen wie ich das umgehen kann. Die Abschätzung macht aber die Ableitungen wesentlich einfacher.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:27 Di 17.02.2015 | | Autor: | rmix22 |
> > Naja, immerhin ist [mm]n^{1/n}>1,[/mm] also auch
> > [mm]\br{n*n^{1/n}}{\ln{n}}>\br{n}{\ln{n}}.[/mm]
> >
> > Hilft das schon weiter?
> >
> > Grüße
> > reverend
>
> Auf [mm]\frac{n}{ln(n)}[/mm] würde ich sofort L'H werfen und [mm]n^2[/mm]
> erhalten, was durch einen Limes gegen [mm]\infty[/mm] wie erwartet
> gegen [mm]\infty[/mm] divergiert. Damit habe ich allerdings dann
> doch den L'H verwendet.
Hast du nicht selbst in deiner ersten Frage geschrieben, dass du weißt, daß [mm] $\limes_{n\rightarrow\infty}\frac{ln(n)}{n}=0$ [/mm] gilt?
Damit wird der Grenzwert des Kehrwerts dann ja auch kein Mirakel mehr sein, oder?
Gruß Rmix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:32 Do 19.02.2015 | | Autor: | Argot |
Das stimmt natürlich. Danke für die vielen Beiträge.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 04:11 Mi 18.02.2015 | | Autor: | DieAcht |
> Auf [mm]\frac{n}{ln(n)}[/mm] würde ich sofort L'H werfen und [mm]n^2[/mm] erhalten
Falsch. Richtig: [mm] $n\$.
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:50 So 15.02.2015 | | Autor: | fred97 |
> Gilt [mm]n^{1/n}[/mm] = [mm]O(\frac{ln(n)}{n})[/mm] ?
> Ich habe diese Aufgabe mit Hilfe von Lemma 1.4 aus dem
> Buch "Entwurf und Analyse von Algorithmen" wie folgt
> umgestellt:
>
> lim n → [mm]\infty \frac{n^{1/n}}{\frac{ln(n)}{n}}.[/mm] Ich
> weiß, dass lim [mm]n^{1/n}[/mm] = 1 und lim [mm]\frac{ln(n)}{n}[/mm] = 0
> ist. Ein Freund von mir meint, dass das ausreichend wäre
> um zu zeigen, dass die Behauptung der Aufgabe nicht korrekt
> ist, da kein Grenzwert existiert.
???? Es geht doch nicht um die Frage, ob ein Grenzwert existiert, sondern um die Frage, ob de Folge
( [mm] \frac{n^{1/n}}{\frac{ln(n)}{n}})
[/mm]
beschränkt ist oder nicht .
FRED
>
> Wenn ich die Formel allerdings umstelle, erhalte ich lim n
> → [mm]\infty \frac{n^{1/n} n}{log(n)}[/mm] und kann als
> "Grenzwert" [mm]\infty[/mm] mit Hilfe von der Regel von L'Hospital
> berechnen. Damit kann ich auch zeigen, dass der Grenzwert
> nicht existiert.
>
> Genügt der Vorschlag von meinem Freund oder kann nur das
> vollständige ausrechnen zeigen, dass die Behauptung falsch
> ist?
|
|
|
|
