+3 Daumen
329 Aufrufe

Aufgabe:

Zeigen Sie, dass für alle Funktionen ƒ, g : ℕ → ℝ >0  die folgende Äquivalenz gilt:

$$ f ( n ) \in \circ ( g ( n ) ) \Leftrightarrow \lim _ { n \rightarrow \infty } \frac { f ( n ) } { g ( n ) } = 0 $$

Der Kreis \( \circ \) steht für Verknüpfung (Komposition) von Funktionen.

Gefragt von

Mir ist nicht klar, wie man die Folge (g(n)) verknüpfen soll, dass f(n) ein Element davon sein soll. Mit sich selbst? f und g haben als Wertebereich R+ Der Definitionsbereich ist aber nur N, man kann also nicht jeden Wert aus R einsetzen.

Rechts in der Äquivalenz werden ja einzelne Folgenglieder durcheinander dividiert. 

1 Antwort

+1 Punkt

Da sollte wohl jemand mal wieder zur Vorlesung gehen. ;-)

 

Mit Kompositionen kann das kaum was zu tun haben, zumindest dann nicht, wenn das jetzt die richtige "Aufgabe" ist.

Es handelt sich wahrscheinlich eher um Aussagen der Komplexitätstheorie über das asymptotische Verhalten der Funktionen f und g.

Dann sind das allerdings keine Aufgaben, sondern Definitionen!
Man nennt f gegenüber g bei n gegen Unendlich asymptotisch vernachlässigbar, wenn gilt

limnf(n)/g(n) = 0

und schreibt dann (nach Definition!)

f(n) ∈ o(g(n))

 

Möglich ist natürlich, dass ihr diese sogenannten Landau-Symbole anders definiert habt, zum Beispiel so:

f ∈ o(g) :⇔ ∀ε<0∃n0∀n>n0: f(n) ≤ ε*g(n)

Diese Zeile ist äquivalent zu

∀ε<0∃n0∀n>n0: f(n)/g(n) ≤ ε

und mit an = f(n)/g(n) drückt das gerade die Eigenschaft der Folge (an) aus, Nullfolge zu sein.

Das ist aber gerade das, was zu beweise war.
 

Beantwortet von 10 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...