Landau-Symbole < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:17 Do 08.01.2009 | | Autor: | Pacapear |
Hallo zusammen.
Ich verstehe die Definition der Landau-Symbole nicht, vielleicht kann sie mir jemand erklären?
Hier mal meine Definion:
1) [mm]\ (...) = O^m :\gdw (...) \le C*h^m[/mm]
2) [mm]\ (...) = c(h) :\gdw \forall c>0 \exists h(c)>0 \forall h
Also bei Wiki hab ich gelesen, dass das große O quasi besagt, dass die Funktion (...) nicht wesentlich schneller wächst als die Funktion [mm] h^m.
[/mm]
Und das kleine O bedeutet, dass sie langsamer wächst.
Hmm, ich kann das aus diesen Definionen nicht wirklich ablesen.
Kann mir vielleicht jemand ein einfaches Beispiel dazu geben?
Aus Definition 1) lese ich nur, dass die Funktion (...) unterhalb oder auf [mm]C*h^m[/mm] liegt, also doch quasi unterhalb oder auf einer nach oben verschobenen Funktion [mm] h^m [/mm] (weil ich ja den Funktionswert [mm] h^m [/mm] mit der Konstanten C multipliziere und er ja damit auf der y-Achse nach oben wandert). Was sagt mir das über das Wachstum von (...) und [mm] h^m?
[/mm]
Und noch eine Frage:
Wenn eine Funktion f langsamer wächst als eine Funktion h, muss f dann zwingend unterhalb von h liegen, oder kann f auch darüber liegen?
Bin für jede Hilfe dankbar.
LG, Nadine
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:28 Do 08.01.2009 | | Autor: | felixf |
Hallo Nadine
> Ich verstehe die Definition der Landau-Symbole nicht,
> vielleicht kann sie mir jemand erklären?
> Hier mal meine Definion:
> 1) [mm]\ (...) = O^m :\gdw (...) \le C*h^m[/mm]
> 2) [mm]\ (...) = c(h) :\gdw \forall c>0 \exists h(c)>0 \forall h
Bist du dir sicher dass die Definitionen so stimmen? Was ist z.B. $h$?
Eine schoenere Definition der Landau-Symbole ist: $f = O(g) [mm] :\Longleftrightarrow \limsup_{x \to \infty} \frac{f(x)}{g(x)} [/mm] < [mm] \infty$ [/mm] und $f = o(g) [mm] :\Longleftrightarrow \lim_{x \to \infty} \frac{f(x)}{g(x)} [/mm] = 0$.
Beachte auch, dass man das $x [mm] \to \infty$ [/mm] z.B. gegen $x [mm] \to [/mm] 0$ ersetzen kann; was jetzt gemeint ist, haengt immer vom Kontext ab wo das Symbol vorkommt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:55 Do 08.01.2009 | | Autor: | Pacapear |
Hallo Felix.
> Bist du dir sicher dass die Definitionen so stimmen?
Also ob sie so stimmen weiß ich nicht, sie stehen auf jeden Fall so in meiner Vorlesungsmitschrift 
> Was ist z.B. [mm]h[/mm]?
Oh ja, das hab ich ganz vergessen, [mm] h\in \IR^+
[/mm]
Für Definiton 1) noch, dass [mm]h[/mm] klein.
Hmm, dann hieße das ja in der ersten Definition, dass [mm](...)[/mm] kleinergleich einer Konstanten multipliziert mit einer Konstanten, also einer größen Konstanten ist?
Also das [mm](...)[/mm] unterhalb oder auf einer Parallelen zur x-Achse liegt?
In Definition 2) ist [mm]h(c)[/mm] aber glaub ich ein anderes [mm]h[/mm], aber wissen tu ich's nicht ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
> Eine schoenere Definition der Landau-Symbole ist: [mm]f = O(g) :\Longleftrightarrow \limsup_{x \to \infty} \frac{f(x)}{g(x)} < \infty[/mm]
> und [mm]f = o(g) :\Longleftrightarrow \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0[/mm].
>
> Beachte auch, dass man das [mm]x \to \infty[/mm] z.B. gegen [mm]x \to 0[/mm]
> ersetzen kann; was jetzt gemeint ist, haengt immer vom
> Kontext ab wo das Symbol vorkommt.
Hmm, das versteh ich glaub ich noch viel weniger ![[haee]](/images/smileys/haee.gif "[haee]")
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:45 Do 08.01.2009 | | Autor: | felixf |
Hallo Nadine
> > Bist du dir sicher dass die Definitionen so stimmen?
In Definition 2 soll schon $c(h)$ stehen und nicht $o(h)$?
>
> Also ob sie so stimmen weiß ich nicht, sie stehen auf jeden
> Fall so in meiner Vorlesungsmitschrift
>
>
>
> > Was ist z.B. [mm]h[/mm]?
>
> Oh ja, das hab ich ganz vergessen, [mm]h\in \IR^+[/mm]
Sorry, aber das macht jetzt gar keinen Sinn mehr. Soll $h$ vielleihct eine Unbestimmte sein, zumindest in Definition 1? Dann waere $f = [mm] O(h^m) :\Longleftrightarrow \exists [/mm] C > 0 [mm] \forall [/mm] x [mm] \in \IR^+ [/mm] : f(x) [mm] \le [/mm] C [mm] \cdot x^m$.
[/mm]
Normalerweise ist $h$ eine Funktion mit Werten in [mm] $\IR^+$, [/mm] und der Definitionsbereich ist entweder [mm] $\IR^+$ [/mm] oder [mm] $\IN$ [/mm] (je nachdem was man tun moechte).
> Für
> Definiton 1) noch, dass [mm]h[/mm] klein.
Wie meinst du das jetzt?
> Hmm, dann hieße das ja in der ersten Definition, dass [mm](...)[/mm]
> kleinergleich einer Konstanten multipliziert mit einer
> Konstanten, also einer größen Konstanten ist?
Wenn das so waer waer der Wert von $h$ voellig egal, weil man $C$ einfach anpassen koennte.
Ich denke eher dass $h$ eine Funktion ist.
> Also das [mm](...)[/mm] unterhalb oder auf einer Parallelen zur
> x-Achse liegt?
>
> In Definition 2) ist [mm]h(c)[/mm] aber glaub ich ein anderes [mm]h[/mm],
> aber wissen tu ich's nicht
>
>
>
> > Eine schoenere Definition der Landau-Symbole ist: [mm]f = O(g) :\Longleftrightarrow \limsup_{x \to \infty} \frac{f(x)}{g(x)} < \infty[/mm]
> > und [mm]f = o(g) :\Longleftrightarrow \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0[/mm].
>
> >
> > Beachte auch, dass man das [mm]x \to \infty[/mm] z.B. gegen [mm]x \to 0[/mm]
> > ersetzen kann; was jetzt gemeint ist, haengt immer vom
> > Kontext ab wo das Symbol vorkommt.
>
> Hmm, das versteh ich glaub ich noch viel weniger
Die erste Definition [mm] $\limsup_{x \to \infty} \frac{f(x)}{g(x)} [/mm] < [mm] \infty$ [/mm] bedeutet, dass [mm] $\frac{f(x)}{g(x)}$ [/mm] beschraenkt ist. Anders gesagt $f = O(g) [mm] \Longleftrightarrow \exists [/mm] C > 0 [mm] \forall [/mm] x > 0 : f(x) [mm] \le [/mm] C [mm] \cdot [/mm] g(x)$.
Die zweite Definition sagt, dass [mm] $\frac{f(x)}{g(x)}$ [/mm] gegen 0 geht, also beliebig klein wird. Wenn es nicht beliebig klein wuerde, oder sogar gegen eine von Null verschiedene Konstante konvergieren wuerde (fuer $x [mm] \to \infty$), [/mm] dann wuerde $f$ fuer grosse $x$ sich aehnlich verhalten wie $g$ -- bis auf ein konstantes Vielfaches. (Und konstante Vielfache sind egal da's nur um das Wachstum geht.)
Alternativ koennte man auch definieren: $f = o(g) [mm] \Longleftrightarrow \forall [/mm] c > 0 [mm] \exists x_0 [/mm] > 0 [mm] \forall [/mm] x > [mm] x_0 [/mm] : f(x) [mm] \le [/mm] c [mm] \cdot [/mm] g(x)$: dies sagt gerade, dass egal wie gross oder klein man $g$ durch eine Konstante skaliert, die Funktion $f$ fuer gross genuge Werte von $x$ immer darunter liegen wird.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:21 Do 08.01.2009 | | Autor: | Pacapear |
Hallo Felix!
> In Definition 2 soll schon [mm]c(h)[/mm] stehen und nicht [mm]o(h)[/mm]?
Oh, entschuldige bitte, klar, da soll [mm]\ o(h)[/mm] stehen.
Komisch, eigentlich hatte ich es vor dem Abschicken nochmal kontrolliert, aber irgendwie sah das [mm]\ c[/mm] wie ein [mm]\ o[/mm] aus .
Also es heißt: [mm]\ (...) = o(h) :\gdw \forall c>0 \exists h(c)>0 \forall h
> Sorry, aber das macht jetzt gar keinen Sinn mehr. Soll [mm]h[/mm]
> vielleihct eine Unbestimmte sein, zumindest in Definition
> 1? Dann waere [mm]f = O(h^m) :\Longleftrightarrow \exists C > 0 \forall x \in \IR^+ : f(x) \le C \cdot x^m[/mm].
>
> Normalerweise ist [mm]h[/mm] eine Funktion mit Werten in [mm]\IR^+[/mm], und
> der Definitionsbereich ist entweder [mm]\IR^+[/mm] oder [mm]\IN[/mm] (je
> nachdem was man tun moechte).
Hmm...
Also ich schreib es jetzt nochmal im Gesamten auf, was da steht:
[mm] h\in\IR^+
[/mm]
[mm]\ (...) = O^m :\gdw (...) \le C\cdot{}h^m[/mm], h klein, C konstante
[mm]\ (...) = o(h) :\gdw \forall c>0 \exists h(c)>0 \forall h
> > Für Definiton 1) noch, dass [mm]h[/mm] klein.
> Wie meinst du das jetzt?
s.o.
> Anders gesagt [mm]f = O(g) \Longleftrightarrow \exists C > 0 \forall x > 0 : f(x) \le C \cdot g(x)[/mm].
Heißt das folgendes:
Ich habe eine Konstante C, die ist größer als Null?
Diese multipliziere ich mit allen Funktionwerten der Funktion g, deren Argument auf der positiven x-Achse liegt?
Der Funktionswert g(x) wird also größer, wandert also auf der y-Achse nach oben?
Mein Funktionswert an der Stelle f(x) liegt unterhalb oder auf dem nach oben verschobenen Funktionswert g(x)?
Im Gesamten (bzw. für die positive x-Achse) liegt die Funktion f(x) unterhalb oder auf der nach oben verschobenen Funktion g(x)?
> Alternativ koennte man auch definieren: [mm]f = o(g) \Longleftrightarrow \forall c > 0 \exists x_0 > 0 \forall x > x_0 : f(x) \le c \cdot g(x)[/mm]:
> dies sagt gerade, dass egal wie gross oder klein man [mm]g[/mm]
> durch eine Konstante skaliert, die Funktion [mm]f[/mm] fuer gross
> genuge Werte von [mm]x[/mm] immer darunter liegen wird.
Das f für große x immer unter der Funktion g liegen wird, hab ich das nicht gerade schon in der Groß-O-Notation beschrieben
Obwohl, nee, bei Groß-O ist ja schon für alle [mm]\ x>0 [/mm], oder?
Meinst du mit "groß genuge Werte von x" alle die x-Werte ab dem [mm] x_0?
[/mm]
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:38 Fr 09.01.2009 | | Autor: | fred97 |
Kurz und knapp:
Bei der Landau-Symbolik gehört imm er ein Grenzwert dazu.
Sei [mm] x_0 \in \IR \cup [/mm] { [mm] -\infty, \infty [/mm] }
1. $f= O(g)$ (x--> [mm] x_0) \gdw [/mm] f/g ist in der Nähe von [mm] x_0 [/mm] beschränkt
2. $f=o(g)$ (x--> [mm] x_0) \gdw \bruch{f(x)}{g(x)} [/mm] --> 0 für x--> [mm] x_0
[/mm]
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:05 Fr 09.01.2009 | | Autor: | Pacapear |
Danke für deine Antwort, Fred.
Aber das ist ja genau die eine Definition von Felix, die ich nicht verstanden habe :-(
Ich kann mir da irgendwie nicht wirklich was drunter vorstellen.
LG, Nadine
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:07 Fr 09.01.2009 | | Autor: | Pacapear |
Hallo Felix!
> Heißt das folgendes:
> Ich habe eine Konstante C, die ist größer als Null?
> Diese multipliziere ich mit allen Funktionwerten der
> Funktion g, deren Argument auf der positiven x-Achse
> liegt?
> Der Funktionswert g(x) wird also größer, wandert also auf
> der y-Achse nach oben?
> Mein Funktionswert an der Stelle f(x) liegt unterhalb oder
> auf dem nach oben verschobenen Funktionswert g(x)?
> Im Gesamten (bzw. für die positive x-Achse) liegt die
> Funktion f(x) unterhalb oder auf der nach oben verschobenen
> Funktion g(x)?
> Das f für große x immer unter der Funktion g liegen wird,
> hab ich das nicht gerade schon in der Groß-O-Notation
> beschrieben
> Obwohl, nee, bei Groß-O ist ja schon für alle [mm]\ x>0 [/mm],
> oder?
> Meinst du mit "groß genuge Werte von x" alle die x-Werte
> ab dem [mm]x_0?[/mm]
Ist mein Verständnis soweit richtig?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:40 Sa 10.01.2009 | | Autor: | felixf |
Hallo Nadine!
> > Heißt das folgendes:
> > Ich habe eine Konstante C, die ist größer als Null?
> > Diese multipliziere ich mit allen Funktionwerten der
> > Funktion g, deren Argument auf der positiven x-Achse
> > liegt?
> > Der Funktionswert g(x) wird also größer, wandert also
Nun, wenn $C < 1$ ist, wird er kleiner ;) Aber sagen wir mal er ist $> 1$.
> auf
> > der y-Achse nach oben?
> > Mein Funktionswert an der Stelle f(x) liegt unterhalb
> oder
> > auf dem nach oben verschobenen Funktionswert g(x)?
Der Funktionswert $g(x)$ wird nicht verschoben, sondern skaliert! Das ist ein wichtiger Unterschied!
> > Im Gesamten (bzw. für die positive x-Achse) liegt die
> > Funktion f(x) unterhalb oder auf der nach oben verschobenen
> > Funktion g(x)?
Ja (bis auf das verschoben).
> > Das f für große x immer unter der Funktion g liegen wird,
> > hab ich das nicht gerade schon in der Groß-O-Notation
> > beschrieben
Ja, aber diesmal gilt es fuer alle Konstanten $c > 0$, und nicht nur fuer eine! (Dafuer muss es nur fuer gross genuge $x$ gelten.)
> > Obwohl, nee, bei Groß-O ist ja schon für alle [mm]\ x>0 [/mm],
> > oder?
Ja. Wobei man dort auch sagen kann dass es nur fuer gross genuge $x$ gelten soll. (Ansonsten kann man unter Umstaenden Probleme bekommen; hat man nur ganzzahlige Parameter $x$ macht es keinen Unterschied, ist die Funktion aber nicht stetig oder sie ist nur auf $(0, [mm] \infty)$ [/mm] definiert und nicht $[0, [mm] \infty)$, [/mm] dann macht das schon einen Unterschied.)
> > Meinst du mit "groß genuge Werte von x" alle die
> x-Werte
> > ab dem [mm]x_0?[/mm]
Genau.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:36 Mo 19.01.2009 | | Autor: | Pacapear |
Hallo Felix.
> Der Funktionswert [mm]g(x)[/mm] wird nicht verschoben, sondern
> skaliert! Das ist ein wichtiger Unterschied!
Was genau bedeutet skaliert denn?
Ich dachte bisher immer, skalieren und verschieben wäre das gleiche...
> Ja, aber diesmal gilt es fuer alle Konstanten [mm]c > 0[/mm], und
> nicht nur fuer eine! (Dafuer muss es nur fuer gross genuge
> [mm]x[/mm] gelten.)
Wenn es für alle Konstante c gilt, warum muss es dann nur für genügend große x gelten?
Das verstehe ich nicht...
Also ich hab nochmal geguckt:
In deiner Definition steht, dass es zu jeder Konstanten c ein [mm] x_0 [/mm] gebt, so dass dann die Abschätzung für alle [mm] x>x_0 [/mm] gilt.
Meinst du das mit den genügend großen x wieder, weil es diese Grenze [mm] x_0 [/mm] gibt, ab der die Abschätzung erst gelten soll?
> Ja. Wobei man dort auch sagen kann dass es nur fuer gross
> genuge [mm]x[/mm] gelten soll. (Ansonsten kann man unter Umstaenden
> Probleme bekommen; hat man nur ganzzahlige Parameter [mm]x[/mm]
> macht es keinen Unterschied, ist die Funktion aber nicht
> stetig oder sie ist nur auf [mm](0, \infty)[/mm] definiert und nicht
> [mm][0, \infty)[/mm], dann macht das schon einen Unterschied.)
In wie fern kann ich denn bei unstetigen Funktionen, oder Funktionen, die nicht in 0 definiert sind, Probleme bekommen?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:51 Mo 19.01.2009 | | Autor: | felixf |
Hallo Nadine
> > Der Funktionswert [mm]g(x)[/mm] wird nicht verschoben, sondern
> > skaliert! Das ist ein wichtiger Unterschied!
>
> Was genau bedeutet skaliert denn?
> Ich dachte bisher immer, skalieren und verschieben wäre
> das gleiche...
Skalieren heisst mit einer Konstanten multiplizieren, Verschieben heisst eine Konstante hinzu zu addieren. Wenn du z.B. die Gerade $y = x$ skalierst, aenderst du den Winkel mit dem sie durch den Ursprung geht (insb. aendert sich die Steigung). Wenn du sie verschiebst, geht sie nicht mehr durch den Ursprung, aber die Steigung aendert sich nicht.
> > Ja, aber diesmal gilt es fuer alle Konstanten [mm]c > 0[/mm], und
> > nicht nur fuer eine! (Dafuer muss es nur fuer gross genuge
> > [mm]x[/mm] gelten.)
>
> Wenn es für alle Konstante c gilt, warum muss es dann nur
> für genügend große x gelten?
Wenn man das weglassen wuerde, muesste die eine Funktion konstant 0 sein :)
> Das verstehe ich nicht...
> Also ich hab nochmal geguckt:
> In deiner Definition steht, dass es zu jeder Konstanten c
> ein [mm]x_0[/mm] gebt, so dass dann die Abschätzung für alle [mm]x>x_0[/mm]
> gilt.
> Meinst du das mit den genügend großen x wieder, weil es
> diese Grenze [mm]x_0[/mm] gibt, ab der die Abschätzung erst gelten
> soll?
Genau, so ist das gemeint. "Gross genug" wird durch $x > [mm] x_0$ [/mm] ausgedrueckt, wobei [mm] $x_0$ [/mm] sagt, was fuer dieses $c$ gross genug ist.
> > Ja. Wobei man dort auch sagen kann dass es nur fuer gross
> > genuge [mm]x[/mm] gelten soll. (Ansonsten kann man unter Umstaenden
> > Probleme bekommen; hat man nur ganzzahlige Parameter [mm]x[/mm]
> > macht es keinen Unterschied, ist die Funktion aber nicht
> > stetig oder sie ist nur auf [mm](0, \infty)[/mm] definiert und nicht
> > [mm][0, \infty)[/mm], dann macht das schon einen Unterschied.)
>
> In wie fern kann ich denn bei unstetigen Funktionen, oder
> Funktionen, die nicht in 0 definiert sind, Probleme
> bekommen?
Wenn die Funktion stetig und bei 0 definiert ist, so ist sie auf dem kompakten Intervall $[0, [mm] x_0]$ [/mm] stetig, womit sie dort ein Minimum annimmt: da die Funktion $> 0$ ist muss das Minimum echt positiv sein. Ebenso nimmt die Funktion ein Maximum an. Zumindest kann man die eine Funktion jetzt so skalieren, dass sie immer ueber der anderen Funktion liegt, da der Skalierungsfaktor durch das Minimum der einen und das Maximum der anderen bestimmt werden kann.
Ist die Funktion unstetig oder in 0 nicht definiert, so kann es sein dass sie kein Minimum hat, aber das Infimum der Funktionswerte fuer $x [mm] \le x_0$ [/mm] gleich 0 ist. Und das Supremum kann halt [mm] $\infty$ [/mm] sein. Damit kann man i.A. die eine Funktion nicht mehr so skalieren, dass sie ueber der anderen liegt.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:53 Mo 19.01.2009 | | Autor: | felixf |
Hallo Nadine
> Wenn die Funktion stetig und bei 0 definiert ist, so ist
> sie auf dem kompakten Intervall [mm][0, x_0][/mm] stetig, womit sie
> dort ein Minimum annimmt: da die Funktion [mm]> 0[/mm] ist muss das
> Minimum echt positiv sein. Ebenso nimmt die Funktion ein
> Maximum an. Zumindest kann man die eine Funktion jetzt so
> skalieren, dass sie immer ueber der anderen Funktion liegt,
> da der Skalierungsfaktor durch das Minimum der einen und
> das Maximum der anderen bestimmt werden kann.
>
> Ist die Funktion unstetig oder in 0 nicht definiert, so
> kann es sein dass sie kein Minimum hat, aber das Infimum
> der Funktionswerte fuer [mm]x \le x_0[/mm] gleich 0 ist. Und das
> Supremum kann halt [mm]\infty[/mm] sein. Damit kann man i.A. die
> eine Funktion nicht mehr so skalieren, dass sie ueber der
> anderen liegt.
Vielleicht ein Beispiel:
$f(x) = 1/x$ und $g(x) = 1$. Dann sollte ja $f = O(g)$ sein, sogar $f = o(g)$, aber man kann $f$ nicht so skalieren, dass es immer unterhalb von $g$ liegt, da fuer sehr kleine Werte von $x$ auch [mm] $\lambda [/mm] f(x)$ beliebig gross werden kann (fuer [mm] $\lambda [/mm] > 0$), insbesondere groesser als 1.
LG Felix
|
|
|
|
