Formale Definition

Groß O und klein o sind die am häufigsten verwendeten Landau-Symbole; darüber hinaus gibt es noch O, ? und T.
In der folgenden Tabelle bezeichnen ff und gg entweder
Formal lassen sich die Landau-Symbole dann mittels Limes superior und Limes inferior folgendermaßen definieren:
Notation Definition Mathematische Definition
f(x)∈O(g(x))f(x) \in \text{O}(g(x)) asymptotische obere Schranke 0≤lim sup⁡x→a∣f(x)g(x)∣<∞0 \le \limsup_{x \to a} \ntxbraceI{\dfrac{f(x)}{g(x)}} < \infty
f(x)∈o(g(x))f(x) \in \text{o}(g(x)) asymptotisch vernachlässigbar 0=lim⁡x→a∣f(x)g(x)∣0 = \lim_{x \to a} \ntxbraceI{\dfrac{f(x)}{g(x)}}
f(x)∈Ω(g(x))f(x) \in \Omega(g(x)) asymptotische untere Schranke, g(x)∈O(f(x))g(x)\in\text{O}(f(x)) 0<lim inf⁡x→a∣f(x)g(x)∣≤∞0 < \liminf_{x \to a} \ntxbraceI{\dfrac{f(x)}{g(x)}} \le \infty
f(x)∈ω(g(x))f(x) \in \omega(g(x)) asymptotisch dominant, g(x)∈o(f(x))g(x)\in\text{o}(f(x)) lim⁡x→a∣f(x)g(x)∣=∞\lim_{x \to a} \ntxbraceI{\dfrac{f(x)}{g(x)}} = \infty
f(x)∈Θ(g(x))f(x) \in \Theta(g(x)) asymptotisch scharfe Schranke, sowohl f(x)∈O(g(x))f(x)\in\text{O}(g(x)) als auch g(x)∈O(f(x))g(x)\in\text{O}(f(x)) 0<lim inf⁡x→a∣f(x)g(x)∣≤lim sup⁡x→a∣f(x)g(x)∣<∞0 < \liminf_{x \to a} \ntxbraceI{\dfrac{f(x)}{g(x)}} \le \limsup_{x \to a} \ntxbraceI{\dfrac{f(x)}{g(x)}}< \infty

Definition mittels Quantoren

Äquivalent zur Definition mit Limessymbolen können für einen metrischen Raum XX, insbesondere also für die Fälle X=RX=\R und X=NX=\N folgende Definitionen mit Quantoren verwendet werden:
Notation x→a<∞x\to a<\infty
f(x)∈O(g(x))f(x) \in \text{O}(g(x)) ∃ c>0 ∃ ϵ>0 ∀ x∈{x:∥x−a∥<ϵ}:∣f(x)∣≤c⋅∣g(x)∣\exists\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \|x-a\|<\epsilon\rbrace : |f(x)| \le c\cdot |g(x)|
f(x)∈o(g(x))f(x) \in \text{o}(g(x)) ∀ c>0 ∃ ϵ>0 ∀ x∈{x:∥x−a∥<ϵ}:∣f(x)∣<c⋅∣g(x)∣\forall\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \|x-a\|<\epsilon\rbrace : |f(x)| < c\cdot |g(x)|
f(x)∈Ω(g(x))f(x) \in \Omega(g(x)) ∃ c>0 ∃ ϵ>0 ∀ x∈{x:∥x−a∥<ϵ}:∣f(x)∣≥c⋅∣g(x)∣\exists\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \|x-a\|<\epsilon\rbrace : |f(x)| \ge c\cdot |g(x)|
f(x)∈ω(g(x))f(x) \in \omega(g(x)) ∀ c>0 ∃ ϵ>0 ∀ x∈{x:∥x−a∥<ϵ}:∣f(x)∣>c⋅∣g(x)∣\forall\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \|x-a\|<\epsilon\rbrace : |f(x)| > c\cdot |g(x)|
f(x)∈Θ(g(x))f(x) \in \Theta(g(x)) ∃ c0>0 ∃ c1>0 ∃ ϵ>0 ∀ x∈{x:∥x−a∥<ϵ}:c0⋅∣g(x)∣≤∣f(x)∣≤c1⋅∣g(x)∣\exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \|x-a\|<\epsilon\rbrace : c_0\cdot |g(x)|\le|f(x)| \le c_1\cdot |g(x)|
Notation x→∞x\to\infty
f(x)∈O(g(x))f(x) \in \text{O}(g(x)) ∃ c>0 ∃ x0 ∀ x>x0:∣f(x)∣≤c⋅∣g(x)∣\exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| \le c\cdot |g(x)|
f(x)∈o(g(x))f(x) \in \text{o}(g(x)) ∀ c>0 ∃ x0 ∀ x>x0:∣f(x)∣<c⋅∣g(x)∣\forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| < c\cdot |g(x)|
f(x)∈Ω(g(x))f(x) \in \Omega(g(x)) ∃ c>0 ∃ x0 ∀ x>x0:∣f(x)∣≥c⋅∣g(x)∣\exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| \ge c\cdot |g(x)|
f(x)∈ω(g(x))f(x) \in \omega(g(x)) ∀ c>0 ∃ x0 ∀ x>x0:∣f(x)∣>c⋅∣g(x)∣\forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| > c\cdot |g(x)|
f(x)∈Θ(g(x))f(x) \in \Theta(g(x)) ∃ c0>0 ∃ c1>0 ∃ x0 ∀ x>x0:c0⋅∣g(x)∣≤∣f(x)∣≤c1⋅∣g(x)∣\exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ x_0\ \forall\ x > x_0: c_0\cdot |g(x)|\le|f(x)| \le c_1\cdot |g(x)|
Analoge Definitionen lassen sich auch für den Fall x→−∞x\to -\infty sowie für einseitige Grenzwerte geben.

Notationsfallen

Symbolisches Gleichheitszeichen

Üblicherweise wird in der Mathematik bei der Landau-Notation das Gleichheitszeichen verwendet. Es handelt sich dabei aber um eine rein symbolische Schreibweise und nicht um eine Gleichheitsaussage, auf die beispielsweise die Gesetze der Transitivität oder der Symmetrie anwendbar wäre: In einer Aussage wie f(x)=O(g(x))f(x)=\mathrm{O}(g(x)) ist keine Seite der "Gleichung" durch die andere bestimmt. Aus f1(x)=O(g(x))f_1(x)=\mathrm{O}(g(x)) und f2(x)=O(g(x))f_2(x)=\mathrm{O}(g(x)) folgt nicht, dass f1f_1 und f2f_2 gleich sind, genausowenig kann man aus f(x)=O(g1(x))f(x)=\mathrm{O}(g_1(x)) und f(x)=O(g2(x))f(x)=\mathrm{O}(g_2(x)) schließen, dass O(g1(x))\mathrm{O}(g_1(x)) und O(g2(x))\mathrm{O}(g_2(x)) dieselbe Klasse sind oder die eine in der anderen enthalten ist.

Vergessener Grenzwert

Eine weitere Falle besteht darin, dass oft nicht angegeben wird, auf welchen Grenzwert sich das Landausymbol bezieht. Der Grenzwert ist aber wesentlich; so ist beispielsweise 1x∈o(1x)\dfrac{1}{x}\in\text{o}\braceNT{\dfrac{1}{\sqrt{x}}} für x→∞x\to\infty, nicht aber für den einseitigen Grenzwert x↓0x\downarrow 0. Normalerweise wird der betrachtete Grenzwert aber aus dem Zusammenhang klar, sodass hier Mehrdeutigkeiten nur selten auftreten.
 
 

Es ist unmöglich, die Schönheiten der Naturgesetze angemessen zu vermitteln, wenn jemand die Mathematik nicht versteht. Ich bedaure das, aber es ist wohl so.

Richard Feynman

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Landau-Symbole aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Differentialrechnung