asymptotische Notation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:19 Do 12.03.2009 | | Autor: | csak1162 |
meine Fragen dazu
Aufgabe 1:
was ist bei der Frage bzgl L'Hopital gemeint, muss ich da nur sagen wann er angewendet werden kann und das mit den ableitungen?
wie kann ich (a) bis (f) zeigen, ich weiß nicht wie ich da vorgehen soll??
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:20 Do 12.03.2009 | | Autor: | Marcel |
Hallo,
> ![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang
> meine Fragen dazu
>
> Aufgabe 1:
>
> was ist bei der Frage bzgl L'Hopital gemeint, muss ich da
> nur sagen wann er angewendet werden kann und das mit den
> ableitungen?
ich denke schon. Meiner Meinung nach ist der Sinn der Frage, den Satz von Hospital genauestens zu wiederholen. Vgl. z.B. ![[]](/images/popup.gif) Wikipedia: Hospital.
Ergänzend möchte ich dazu anmerken, dass, wenn [mm] $g:=\lim_{\IR \ni x \to \infty} [/mm] h(x)$ existiert, dann auch [mm] $\lim_{\IN \ni n \to \infty} [/mm] h(n)$ existiert mit [mm] $g=\lim_{\IN \ni n \to \infty} h(n)\,.$
[/mm]
> wie kann ich (a) bis (f) zeigen, ich weiß nicht wie ich da
> vorgehen soll??
Das hängt davon ab, wie ihr die Landau-Symbole definiert habt bzw. welche Charakterisierungen ihr von [mm] $\mathcal{O}$ [/mm] etc. kennt. Z.B. scheint es mir bei Euch sinnvoll, die mathematischen Definition heranzuziehen (wenn Euch eine andere zugrundeliegt, solltest Du zunächst die jeweilige Äquivalenz der mathematischen Definition zu der Deinen beweisen). Denn dann kann man sicher auch, zumindest teilweise, Hospital verwenden.
Aber mache Dir bei jeder Aufgabe ( a) bis f) )vll. erstmal klar, was denn dort eigentlich behauptet wird. Vorher macht das Bearbeiten einer solchen Aufgabe eigentlich für Dich keinen Sinn, und die Lösung wirst Du auch nicht verstehen, wenn Du Dir die Behauptungen noch nicht klargemacht hast.
Z.B.
[mm] $n*\log(n)=\mathcal{O}(n^2)$ [/mm] (anstelle des [mm] $\in$, [/mm] wie es bei Euch steht, schreibt man oft halt auch gerne $=$)
gilt genau dann, wenn
[mm] $$\limsup_{n \to \infty} \left|\frac{n*\log(n)}{n^2}\right|=\limsup_{n \to \infty} \frac{n*\log(n)}{n^2} [/mm] < [mm] \infty\,.$$
[/mm]
Wenn Du mit dem [mm] $\limsup$ [/mm] allerdings (noch) nicht vertraut bist, dann solltest Du in obigem Wiki-Link in die Definition mit den Quantoren gucken (in die mit $x [mm] \to \infty$) [/mm] (diese Definitionen sind selbstverständlich äquivalent zueinander):
Demnach wäre [mm] $n*\log(n)=\mathcal{O}(n^2)$ [/mm] genau dann, wenn es ein $c > 0$ so gibt, dass [mm] $|n*\log(n)| \le c*|n^2|$ [/mm] für alle natürlichen $n$ ab einem gewissen [mm] $n_0\,.$
[/mm]
Ich hoffe nun, dass bei Euch [mm] $\log(.)$ [/mm] der [mm] $\ln(.)$ [/mm] ist (Logarithmus naturalis). Ansonsten müßtest Du in der folgenden Argumentation sowas wie [mm] $\log_a(.)=\frac{\ln(.)}{\ln(a)}$ [/mm] benutzen und damit müßte man das $c$ und/oder das [mm] $n_0$ [/mm] gegebenenfalls vergößern.
Es gilt jedenfalls [mm] $n*\ln(n)=\mathcal{O}(n^2)\,,$ [/mm] denn es gilt (mit (je) einem noch zu bestimmenden $c [mm] >\, [/mm] 0$ (und, später, [mm] $n_0 \in \IN$))
[/mm]
[mm] $$|n*\ln(n)| \le c*|n^2|$$
[/mm]
[mm] $$\gdw \ln(n) \le c*n\,$$
[/mm]
[mm] $$\gdw \frac{\ln(n)}{n} \le c\,.$$
[/mm]
Wegen Hospital (Fall " [mm] $\infty/\infty$ [/mm] ") strebt [mm] $\frac{\ln(n)}{n}$ [/mm] gegen den gleichen Wert, gegen den [mm] $\frac{1/n}{1}$ [/mm] bei $n [mm] \to \infty$ [/mm] strebt, insbesondere ist [mm] $\left(\frac{\ln(n)}{n}\right)_n$ [/mm] konvergent, damit beschränkt und damit auch nach oben beschränkt. Folglich existiert eine Konstante $c > 0$, so dass [mm] $\frac{\ln(n)}{n} \le [/mm] c$ für alle $n [mm] \ge n_0$ [/mm] mit einem festen [mm] $n_0 \in \IN$. [/mm] Also folgt [mm] $n*\log(n)=\mathcal{O}(n^2)\,$ [/mm] $(n [mm] \to \infty)\,.$ [/mm]
P.S.:
Alternativ:
Falls Dir die Ungleichung [mm] $\ln(x) \le [/mm] x-1$ für alle $x > 0$ bekannt ist, so folgt damit
[mm] $$\frac{\ln(n)}{n} \le \frac{n-1}{n} \le [/mm] 1$$
für alle $n [mm] \ge 1\,.$ [/mm] Du kannst hier also sogar präzise $c=1$ und dann [mm] $n_0=1$ [/mm] wählen, um [mm] $n*\ln(n)=\mathcal{O}(n^2)$ [/mm] ($n [mm] \to \infty$) [/mm] einzusehen.
Gruß,
Marcel
|
|
|
|
