Beweis für O-Notation < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:14 Sa 23.10.2004 | | Autor: | Tyvan |
Hallo, kann mir einer mal helfen und sagen wie ich dieses hier beweisen kann. Ich habe keinen Ansatz wie man sowas angeht.
Ich muss zeigen dass für f,g : [mm] \IN \to \IR+, [/mm] f(n) [mm] \not= [/mm] 0 und g(n) [mm] \not= [/mm] 0 folgendes gilt:
[mm] \limes_{n\rightarrow\infty} \bruch{f}{g} [/mm] = 0 [mm] \Rightarrow [/mm] f [mm] \in [/mm] O(g)
Weiss einer wie ich das beweisen kann?
Dank im voraus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:26 Sa 23.10.2004 | | Autor: | andreas |
hi
es gilt nach definition des grenzwertes von folgen
[m] \begin{tabular}{ccl} \lim\limits_{n \to \infty} \frac{f}{g} = 0 & \Longleftrightarrow & \forall \, \varepsilon > 0 \; \exists \, n_0 \in \mathbb{N} \; \forall \, n \geq n_0: \left| \frac{f}{g} \right| < \varepsilon \\
& \Longleftrightarrow & \forall \, \varepsilon > 0 \; \exists \, n_0 \in \mathbb{N} \; \forall \, n \geq n_0:|f| < \varepsilon |g| \end{tabular} [/m]
und damit bist du schon fertig, da letztes genau die definition für [m] f \in O(g) [/m] ist. wenn du mit sowas probleme hast (was bei der einführung der landau-symbole normal ist) schaust du dir am besten nochmal die definition an, und probierst es erstmal selbst.
wenn noch fragen aufkommen kannst du dich ja nochmal melden.
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:55 Di 26.10.2004 | | Autor: | Tyvan |
Ok danke.
Ich hab hier noch 2 wobei ich mir beim ersten unsicher bin, das zweite verstehe ich gar nicht.
[mm] \limes_{n\rightarrow\infty} \bruch{f}{g} [/mm] = c [mm] \Rightarrow [/mm] g [mm] \in [/mm] "Theta" von f.
und die zweite aufgabe ist.
g [mm] \in [/mm] O(f) [mm] \gdw [/mm] f [mm] \in [/mm] "Omega" von g
weisst du vorallem wie ich das zweite angehen kann. ich weiss das Omega(g) auf gut deutsch heisst: Die Menge aller Funktionen die mindestens so schnell wachsen wie g. Aber warum soll g [mm] \in [/mm] O(f) äquivalent zu f [mm] \in [/mm] "omega"(g) sein?
Danke nochmal 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:19 Mi 27.10.2004 | | Autor: | andreas |
hi
schreibe doch einfach mal die definitionen für die benötigten ausdrücke hin und dann sieht man meist schon recht schnell, was man machen muss um vom einen zum anderen zu kommen.
wenn nicht, kannst du eure dfeinitionen ja mal hier im forum angeben.
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:13 Mi 27.10.2004 | | Autor: | Tyvan |
welche definitionen meinst du ? ich kenne nur die eine limes definition oder was meinst. die limes def. ist ja:
[mm] \limes_{n\rightarrow\infty} a_{n} [/mm] = a [mm] \gdw \forall \varepsilon [/mm] > 0 [mm] \exists [/mm] N [mm] \in \IN \forall [/mm] n > N : [mm] |a_{n} [/mm] - a | < [mm] \varepsilon
[/mm]
Ja aber daraus kann ich das nicht entnehmen, ich glaube du meinst was anderes oder? du sprichst auch noch von definitionen (mehrere?).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:33 Mi 27.10.2004 | | Autor: | andreas |
um so eine frage beantworten zu können müsst ihr doch definitionen für [m] O(f), \Theta(f), \Omega(f) [/m] gehabt haben?
andreas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:33 Mi 27.10.2004 | | Autor: | Tyvan |
Aso du meinst diese, ok:
O(g) = [mm] \{f| \exists n_{0} \in \IN, c \in \IR, c > 0: \forall n \ge n_{0} f(n) \le cg(n) \}
[/mm]
....ist die Menge der Funktionen die höchstens so schnell wachsen wie g.
und
[mm] \Omega(n) [/mm] = [mm] \{ h| \exists c > 0: \exists n' > 0: \forall n' > n: h(n) \ge cg(n) \}
[/mm]
...ist die Menge der Funktionen die mindestens so schnell wachsen wie g.
und [mm] \Theta(n) [/mm] ist gleich die Schnittmenge der beiden obigen.
Ich seh daraus nicht gleich wie ich das angehen muss.
Wie in meinem letzten Beitrag:
Zeigen:
[mm] \limes_{n\rightarrow\infty} \bruch{f}{g} [/mm] = c [mm] \Rightarrow [/mm] g [mm] \in \Theta(f)
[/mm]
und
g [mm] \in [/mm] O(f) [mm] \gdw [/mm] f [mm] \in \Omega(g)
[/mm]
Hmm, ok jetzt macht das zweite Sinn. Denn f ist durch f [mm] \in \Omega(g) [/mm] nach unten beschränkt, und das linke wohl nach oben. Aber meine "Schwäche" ist immer ich weiss nie wann ich genau ein Beweis vor mir habe, also ob das was ich mache als Beweis ok ist. Daher würde ich gerne wissen wie ich das formal hinmache. Danke dir Andreas.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:43 Do 28.10.2004 | | Autor: | Tyvan |
Bist du noch da? Ich glaube mein letzte Posting wurde als Antwort genommen, aber da ist auch ne Frage.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:39 Do 28.10.2004 | | Autor: | andreas |
hi
erstmal: sehr gut, dass du den formeleditor verwendest, dadurch wird die sache nämlich halbwegs lesbar und man überlegt sich nicht mehrmals, ob man das nun überhaupt durchlesen soll!
was dir bei den aufgaben sehr viel weiterhelfen würde, wäre eine einheitliche notation. dann sehen deine definitionen nämlich so aus:
[mm] O(g) = \{f| \exists n_{0} \in \IN, c \in \IR, c > 0: \forall n \geq n_{0} : f(n) \leq cg(n) \} [/mm]
ist schon mal sehr schön. dann - in der selben notation - ist:
[mm]\Omega(g) = \{ f | \exists n_{0} \in \IN, c \in \IR, c > 0: \forall n \geq n_{0} : f(n) \geq cg(n) \} [/mm]
> und [mm]\Theta(g)[/mm] ist gleich die Schnittmenge der beiden obigen.
wenn man das dann mal hinschreibt und vereinfacht gilt also:
[mm]\Theta(n) = \{f| \exists n_{0} \in \IN, c_1, c_2 \in \IR, c_1, c_2 > 0: \forall n \geq n_{0}: c_1g(n) \leq f(n) \leq c_2g(n) \} [/mm]
> [mm]\limes_{n\rightarrow\infty} \bruch{f}{g} = c [/mm] [mm]\Rightarrow[/mm] [mm] g \in \Theta(f) [/mm]
ich nehme einfach mal an, dass du [m] c \not= 0 [/m] verschwiegn hast, denn sonst ist die aussage im allgemeinen falsch.
was du hier nur benötigst, ist, dass konvergente folgen nach oben beschränkt sind, d.h. [m] \exists \,k_1 \in \mathbb{R} \; \forall \, n \in \mathbb{N}: |\left| \frac{f}{g} \right| \leq k_1 [/m], sowie konvergente folgen, die nicht gegen [m] 0 [/m] konvergieren, der aussage [m] \exists \, k_2 \in \mathbb{R} \; \exists \, n_0 \in \mathbb{N} \; \forall \, n \geq n_0: \left|\frac{f}{g} \right| \geq k_2 [/m] genügen (diese beiden abschätzungen folgen direkt aus der grenzwert definition, für die zweite abschätzung wähle z.b. [m] \varepsilon := \frac{|c|}{2} [/m]). wenn du diese abschätzungen hast, bist du eigentlich schon fast fertig. probiere doch die fehlenden schritte mal - ist nicht schwer und poste hier mal eine formalisierte lösung. dann kann man dir viel besser zeigen, wo deine probleme liegen könnten.
> und
>
> g [mm]\in[/mm] O(f) [mm]\gdw[/mm] f [mm]\in \Omega(g)
[/mm]
>
>
> Hmm, ok jetzt macht das zweite Sinn. Denn f ist durch f [mm]\in \Omega(g)[/mm]
> nach unten beschränkt, und das linke wohl nach oben. Aber
> meine "Schwäche" ist immer ich weiss nie wann ich genau ein
> Beweis vor mir habe, also ob das was ich mache als Beweis
> ok ist.
probiere das doch einfach mal. schreibe die definition von [m] g \in O(f) [/m] und [m] f \in \Omega(g) [/m] hin und schaue, was du mit der definition des ersten ausdrucks machen musst, damit die zweite definition dasteht (beachte dabei z.b. [m] c > 0 \; \Longrightarrow \; \frac{1}{c} > 0[/m]).
ich hoffe du kriegst jetzt etwas hin.
wir helfen dir dann weiter, wenn du irgendwo hängen bleibst, aber jetzt will ich erstmal wieder was von dir sehen.
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:03 Fr 29.10.2004 | | Autor: | Tyvan |
Hmm, siehst du das mein ich. Ich Dödel würde nie darauf kommen das ich c > 0 [mm] \Rightarrow \bruch{1}{c} [/mm] hinschreiben könnte, denn dadurch wird natürlich die letzte Aufgabe sehr einfach. Da ich das c aus dem Bruch durch Multiplikation in der Ungleichung umstellen kann und somit in die eine Richtung zeigen kann das g [mm] \in [/mm] O(f) [mm] \gdw [/mm] f [mm] \in \Omega(g) [/mm] ist und die andere Richtung geht genauso von statten. :-/
Aber bei der Aufgabe vorher weiss immer noch nicht wie ich das machen soll. Wobei mich eines verwirrt. du schreibst [mm] |\bruch{f}{g}| \le k_{1} [/mm] und sagst aber das ich für die abschätzung z.B. [mm] \varepsilon [/mm] := [mm] \bruch{1}{c} [/mm] nehmen soll. Aber ist denn das [mm] k_{1} [/mm] nicht das epsilon schon?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:58 Fr 29.10.2004 | | Autor: | andreas |
hi Tyvan
> Hmm, siehst du das mein ich. Ich Dödel würde nie darauf
> kommen das ich c > 0 [mm]\Rightarrow \bruch{1}{c}[/mm] hinschreiben
> könnte, denn dadurch wird natürlich die letzte Aufgabe sehr
> einfach. Da ich das c aus dem Bruch durch Multiplikation in
> der Ungleichung umstellen kann und somit in die eine
> Richtung zeigen kann das g [mm]\in[/mm] O(f) [mm]\gdw[/mm] f [mm]\in \Omega(g)[/mm]
> ist und die andere Richtung geht genauso von statten. :-/
genau. eigentlich kann man das sogar alles auf einmal machen, da division durch eine zahl ungleich null eine äquivalenzumformung ist.
> Aber bei der Aufgabe vorher weiss immer noch nicht wie ich
> das machen soll.
ich gebe zu, dass ist die mit abstand schwierigste von diesen drei aufgaben. machbar ist aber auch die.
> Wobei mich eines verwirrt. du schreibst
> [mm]|\bruch{f}{g}| \le k_{1}[/mm] und sagst aber das ich für die
> abschätzung z.B. [mm]\varepsilon[/mm] := [mm]\bruch{1}{c}[/mm] nehmen soll.
> Aber ist denn das [mm]k_{1}[/mm] nicht das epsilon schon?
den letzten satz verstehe ich nicht. was willst du mir damit sagen?
meinst du, dass das [m] k_1 [/m] das [m] \varepsilon [/m] aus der konvergenzdefinition ist? das ist nicht der fall, denn dann würde da dastehenn [m] \left| \frac{f}{g} - 0 \right| < \varepsilon [/m] und die folge würde gegen $0$ und nicht gegen $c$ konvergieren!
ich nehme weiterhin an, dass [m] c \not=0 [/m]. ist dir denn die aussage klar, wenn die beiden abschätzungen bewiesen sind?
für die zweite abschätzung benutzt du einfach die definition des grenzwertes:
die folge [m] \frac{f}{g} [/m] sei gegen $c > 0$ konvergent. dann gilt
[m] \forall \, \varepsilon > 0 \; \exists \, n_0 \in \mathbb{N} \; \forall \, n \geq n_0 : \left| \frac{f}{g} - c \right| < \varepsilon [/m]
insbesondere gilt für [m] \varepsilon := \frac{c}{2} > 0 [/m]:
[m] \exists \, n_0 \in \mathbb{N} \; \forall \, n \geq n_0 : \left| \frac{f}{g} - c \right| < \frac{c}{2} [/m]
dann gilt aber für [m] n \geq n_0 [/m] mit "dreiecksungleichung nach unten" und obiger abschätzung, dass [m] \left| \frac{f(n)}{g(n)} \right| = \left| \frac{f(n)}{g(n)} - c + c \right| = \left| \left(\frac{f(n)}{g(n)} - c\right) - (-c) \right| \geq \left| \left| \frac{f(n)}{g(n)} - c\right| - \left| -c \right| \right| = \left| \frac{c}{2} - c \right| = \frac{c}{2} [/m]
also ist die folge für alle [m] n \geq n_0 [/m] durch [m] k_1 := \frac{c}{2} > 0 [/m] nach unten beschränkt und das ist die eine abschätzung die man dann für die zu beweisense aussage braucht.
kommst du damit jetzt weiter?
grüße
andreas
|
|
|
|
