Limes Superior < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ordnen Sie die folgenden Funktionen aufsteigend nach der Ordnung f(n) [mm] \in [/mm] O(g(n)) und beweisen Sie die Korrektheit der Anordnung.
1: f(n) = [mm] n^{2} [/mm]
2: f(n) = n! |
Hallo,
wie oben beschrieben, soll ich die beiden Funkionen nach dem asymptotischen Wachstum ordnen und die Reihenfolge beweisen. Dazu gibt es folgende Definition:
f [mm] \in [/mm] O(g) = 0 [mm] \le \limes_{n\rightarrow\infty}sup \bruch{f(x)}{g(x)} [/mm] < [mm] \infty
[/mm]
Für f(x) habe ich nun [mm] n^{2} [/mm] eingesetzt und für g(x), n!.
Also [mm] :\bruch{n^{2}}{n!}
[/mm]
Was sich umformen lässt zu: [mm] \bruch{1}{(n-2)(1-\bruch{1}{n})}
[/mm]
Von diesem Ausdruck soll ich nun den limes lim superior berechnen. Falls dieser < [mm] \infty [/mm] ist, so gilt f [mm] \in [/mm] O(g).
Wenn ich in meine obige Gleichung 2 einsetze, erhalte ich als Ergebnis 2. Für jede größere Zahl wird das Ergebnis kleiner. Bedeutet das, dass der lim sup = 2 ist? Ich habe leider Ahnung, wie man den lim sup berechnet. Könnt ihr mir bitte helfen?
|
|
| |
|
> Ordnen Sie die folgenden Funktionen aufsteigend nach der
> Ordnung f(n) [mm]\in[/mm] O(g(n)) und beweisen Sie die Korrektheit
> der Anordnung.
>
> 1: f(n) = [mm]n^{2}[/mm]
> 2: f(n) = n!
> Hallo,
>
> wie oben beschrieben, soll ich die beiden Funkionen nach
> dem asymptotischen Wachstum ordnen und die Reihenfolge
> beweisen. Dazu gibt es folgende Definition:
>
> f [mm]\in[/mm] O(g) = 0 [mm]\le \limes_{n\rightarrow\infty}sup \bruch{f(x)}{g(x)}[/mm]
> < [mm]\infty[/mm]
>
> Für f(x) habe ich nun [mm]n^{2}[/mm] eingesetzt und für g(x), n!.
>
> Also [mm]:\bruch{n^{2}}{n!}[/mm]
>
> Was sich umformen lässt zu:
> [mm]\bruch{1}{(n-2)(1-\bruch{1}{n})}[/mm]
![[notok]](/images/smileys/notok.gif "[notok]")
Aber was Du z.B. machen kannst, ist dies:
[mm]\limsup_{n\rightarrow \infty}\frac{n^2}{n!} =\limsup_{n\rightarrow \infty}\left(\frac{1}{(n-2)!}\cdot \frac{n}{n-1}\cdot \frac{n}{n}\right)=\limsup_{n\rightarrow \infty}\left(\frac{1}{(n-2)!}\cdot\frac{1}{1-\frac{1}{n}}\right)=0[/mm]
Das letzte Gleichheitszeichen gilt, weil sogar der Limes des Arguments des vorhergehenden [mm] $\limsup$ [/mm] existiert und gleich $0$ ist.
>
> Von diesem Ausdruck soll ich nun den limes lim superior
> berechnen. Falls dieser < [mm]\infty[/mm] ist, so gilt f [mm]\in[/mm] O(g).
>
> Wenn ich in meine obige Gleichung 2 einsetze, erhalte ich
> als Ergebnis 2. Für jede größere Zahl wird das Ergebnis
> kleiner. Bedeutet das, dass der lim sup = 2 ist? Ich habe
> leider Ahnung, wie man den lim sup berechnet.
In einem Falle wie diesem, bei dem sogar der [mm] $\lim$ [/mm] existiert, ist der [mm] $\limsup$ [/mm] einfach gleich dem [mm] $\lim$.
[/mm]
Betrachte aber einen Fall, bei dem der [mm] $\lim$ [/mm] nicht existiert, wie etwa
[mm] [center]$\limsup_{n\rightarrow \infty}\left[(-1)^n\cdot \left(1+\frac{3}{n}\right)^n\right]=\mathrm{e}^3$[/center]
[/mm]
Dies gilt, weil immerhin der Limes
[mm] [center]$\lim_{n\rightarrow \infty}\left(1+\frac{3}{n}\right)^n=\mathrm{e}^3$[/center]
[/mm]
existiert und für gerade $n$ jeweils ein positives Argument des obigen [mm] $\limsup$ [/mm] resultiert. Der [mm] $\liminf$ [/mm] wäre entsprechend [mm] $-\mathrm{e}^3$.
[/mm]
|
|
|
|
