Landau-Symbole

20.03.2006, 15:06

xplain

Landau-Symbole

Hallo!
hätte ein paar Fragen zu Landau-Symbolen:
groß O wird ja bei der Untersuchung des asympotischen Verhaltens von Funktionen dazu verwendet, um eine "maximale Größenordnung" anzugeben. doch wie ist das zu verstehen?
ist das eine Art Fehlerterm der einfach einen unbekannten aber ungefähren richtweisenden Restwert angibt? was kann man sich denn z.b. unter O(x^2) für x --> unendlich vorstellen?

und noch zu den Rechenregeln:
warum ist z.b. O(1/x^2)+O(1/x^3) = O(1/x^2) ?
und was ist O(O (1/x) ) ?
ist O(1/x^2) dasselbe wie -O(1/x^2) ?

20.03.2006, 15:21

Auf diesen Beitrag antworten »

$\begin{eqnarray*} O(x^2) \end{eqnarray*}$ für $\begin{eqnarray*} x\to\infty \end{eqnarray*}$ heißt salopp, die betreffende Funktion $\begin{eqnarray*} g(x) \end{eqnarray*}$ wächst nicht mehr als in der Größenordnung $\begin{eqnarray*} x^2 \end{eqnarray*}$ beim Grenzübergang $\begin{eqnarray*} x\to\infty \end{eqnarray*}$ . Mathematisch exakt bedeutet dies

$\begin{eqnarray*} 0\leq \limsup\limits_{x\to\infty} \left| \frac{g(x)}{x^2} \right| < \infty \end{eqnarray*}$

siehe http://de.wikipedia.org/wiki/Landau-Symbole .

Beispiel dafür ist z.B. $\begin{eqnarray*} g(x) = -3x^2+2x+x\ln(x) \end{eqnarray*}$ zu, denn da gilt

$\begin{eqnarray*} \limsup\limits_{x\to\infty} \left| \frac{-3x^2+2x+x\ln(x)}{x^2} \right| = \lim\limits_{x\to\infty} \left( 3-\frac{2}{x}-\frac{\ln(x)}{x} \right) = 3 < \infty \end{eqnarray*}$

20.03.2006, 16:10

xplain

Auf diesen Beitrag antworten »

sehr gut, das hab ich jetzt verstanden smile

noch zu den Rechenregeln, ob ich das jetzt richtig interpretiert habe:
gilt O(1/x^2)+O(1/x^3) = O(1/x^2), weil 1/x^2 > 1/x^3 für x --> unendlich ist und damit bei der Untersuchung dieser "Größenordnung" wegfällt?
O(1/x^2) = - O(1/x^2) wegen dem Betrag oder?
was kann man sich unter solch einer Ineinanderschachtelung wie O( O(1/x) ) vorstellen?
danke Wink

20.03.2006, 16:40

Auf diesen Beitrag antworten »

Zitat:

Original von xplain
sehr gut, das hab ich jetzt verstanden smile

Ja, stimmt beides.

Zitat:

Original von xplain
was kann man sich unter solch einer Ineinanderschachtelung wie O( O(1/x) ) vorstellen?
danke Wink

Wenn man sich die obige Definition von O(..) genau anschaut, merkt man, dass mehrfache Schachtelung nix neues bringt. Also ist $\begin{eqnarray*} O(O(f(x)) \equiv O(f(x)) \end{eqnarray*}$ . Interessanter sind dann schon "Rechenoperationen" wie

$\begin{eqnarray*} x\cdot O(x^2) = O(x^3) \end{eqnarray*}$

o.ä.

22.03.2006, 16:58

xplain

Auf diesen Beitrag antworten »

genau bei den Rechenoperationen bin ich jetzt angelangt.
wie kommt man denn über die Definition zu diesen Rechenregeln wie x*(O(x^2) = O(x^3) ?
steh ich da jetzt völlig auf dem Schlauch oder ist das etwas komplizierter?
verwirrt

ich stelle mir das zumindest so vor, dass wenn ich eine Funktion der Größenordnung x^2 mit x multipliziere ja eine Funktion dritten Grades rauskommen muss. zumindest wäre das bei allen Polynomfunktionen der Fall.
und diese wäre ja durch die Beschreibung mit O(x^3) wiederum beschränkt, wenn man sie durch das Argument teilt und den Grenzwert bildet.

22.03.2006, 17:03

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x\cdot O(x^2) = O(x^3) \end{eqnarray*}$ lässt sich durch eine einfache Äquivalenz beweisen:

$\begin{eqnarray*} g(x)=O(x^2) \quad\Leftrightarrow\quad 0\leq \limsup\limits_{x\to\infty} \left| \frac{g(x)}{x^2} \right| < \infty \quad\Leftrightarrow\quad 0\leq \limsup\limits_{x\to\infty} \left| \frac{x\cdot g(x)}{x^3} \right| < \infty \quad\Leftrightarrow\quad x\cdot g(x)=O(x^3) \end{eqnarray*}$

Und so ähnlich läuft das dann auch beim beweisen etwas "allgemeinerer" Regeln.

22.03.2006, 17:07

xplain

Auf diesen Beitrag antworten »

äh ja da drauf hätt ich eigentlich auch kommen können.
dankeschön! smile

23.05.2006, 13:00

PrototypeX29A

Auf diesen Beitrag antworten »

Ich hab auch ne Frage zu den Landau-Symbolen:

Folgt aus $\begin{eqnarray*} x^{2}+3x+15 = O(x^{2}) \end{eqnarray*}$ und $\begin{eqnarray*} x^{2}+2x-27 = O(x^{2}) \end{eqnarray*}$ nicht obda $\begin{eqnarray*} x^{2}+3x-15 = x^{2}+2x+27 \end{eqnarray*}$ ?

23.05.2006, 13:01

JochenX

Auf diesen Beitrag antworten »

eigentlich steht da nicht =O(x^2) sondern ELEMENT AUS O(x^2), denn dieses O-Dingens ist an sich eine MENGE von Funktionen.

Das sieht aber umständlich aus, deswegen schreibt man meistens die einfache Variante "="

23.05.2006, 13:04

PrototypeX29A

Auf diesen Beitrag antworten »

Hmpf, solche Verbrecher! böse

Neue Frage »

Antworten »

Landau-Symbole

Verwandte Themen