Landau-Symbolik

Neue Frage »

StrunzMagi Auf diesen Beitrag antworten »
Landau-Symbolik
Beweisen oder widerlegen sie für :

(Ein Tipp war, dass eine Richtung korrekt ist und die andere widerlegt werden muss)

Hallo, die Landau-Definition von groß O kenne ich. Aber ich hatte das noch nie in Form einer Gleichung gesehen/zu beweisen. Ich bin mir deshalb unsicher was genau zu zeigen/widerlegen ist.
Was bedeutet wenn ist?

Würd mich freuen, wenn mir da wer unter die Arme greifen könnte und mir die ersten Schritte zeigt.
IfindU Auf diesen Beitrag antworten »
RE: Landau-Symbolik
Schreiben wir das mal mit Mengeninklusionen:
Zu zeigen ist
und . Die Operationen sind elementweise zu verstehen. Sei also für die erste Inklusion . Zu zeigen ist dann, dass ist, wobei .

Äquivalent also . In Worten: Wir nehmen eine Funktion die linear abfällt, dann fällt sie nach dem Addieren von 1, quadrieren und dem abziehen von 1 sogar quadratisch.

Für die andere Richtung ist zu zeigen, dass . In Worten: Falls die Funktion quadratisch abfällt, dann gibt es eine lineare abfallende Funktion, die nach dem addieren von 1, quadrieren, subtrahieren von 1 gleich ist.

Falls die Aussage in eine Richtung falsch ist, ist natürlich zu zeigen, dass die Teilmengeninklusion nicht gilt.

Edit: Mit der elementenweise zu verstehenden Operation, kann man zeigen, dass deine binomische Formel für Mengen tatsächlich stimmt. Damit sieht man auch sofort welche Richtung wahr und welche falsch ist.
StrunzMagi Auf diesen Beitrag antworten »

Danke für deine Antwort.
Ich hab mein Bestes versucht:



Sei , d.h. es existieren Funktionen mit im Definitionsbereich von f,
d.h. für x in einer Umgebung um 0.
Dies zeigt

Genauso hab ich gezeigt wenn ist auch

Durch diese Rechnungen ist gezeigt:
StrunzMagi Auf diesen Beitrag antworten »

Achja und ich hoffe, dass man das überhaupt so machen darf bzw. es zielführend ist.
IfindU Auf diesen Beitrag antworten »

Es ist richtig. Sogar Gleichheit gilt. Damit sollte offensichtlich sein welche der Mengen der Aufgabenstellung größer ist und warum.

Edit: Kleine Verbesserung meinerseits. , da die rechte Menge nur nicht-negative Funktionen enthält.
StrunzMagi Auf diesen Beitrag antworten »

Aber die Ungleichung hab ich dann genau in die verkehrte Richtung oder? Bzw. ich kanns ja gar nicht so machen, wenn du sagst bei der anderen Gleichung die Gleichheit nicht gilt.

Warum gilt die Umkehrung auch?
ZZ.:

d.h. es existiert eine positive Konstante C und eine Umgebung um 0 s.d.

Aber wie sehen die aus?

Wenn ich zeigen wollte, dass gilt kann ich doch genauso schreiben:

d.h. es existiert eine positive Konstante C und eine Umgebung um 0 s.d.
 
 
IfindU Auf diesen Beitrag antworten »

Ohja, du hast Recht. Ich habe hier den Unterschied zwischen und einfach ignoriert.
StrunzMagi Auf diesen Beitrag antworten »

Ich verstehe nicht wieso keine Gleichheit gelten sollte, siehe oben! Ich komme mit der Umkehrung leider allgemein nicht klar...
IfindU Auf diesen Beitrag antworten »

Ich bin mir nicht sicher was du jetzt genau zeigen willst, daher mal pro forma der komplette Beweis von .


Sei , d.h. es existieren mit . Dann ist , da
.


Sei . Dann ist , da trivialerweise .

Soweit in Ordnung?
StrunzMagi Auf diesen Beitrag antworten »

Danke, ja die Umkehrung mit dem Trick der Nullfunktion war mir nicht klar.

Bei Wiki steht aber z.B bei den Rechenregel für Landau, das gilt:
O(f(n)) * O(g(n)) = O(f(n) * g(n))

Ich darf als unregistrierter User keine URL posten deshalb ohne Vorsilbe world wide web.:
wedelwiki.de/index.php/Formelsammlung_O-Notation#Rechenregeln_f.C3.BCr_O-Notationen
IfindU Auf diesen Beitrag antworten »

Ja, es gilt. Leider weiß ich nicht was du mir damit sagen willst. Natürlich folgt trivial daraus.
StrunzMagi Auf diesen Beitrag antworten »

Jetzt gilt die Gleichheit doch wieder? Ich bin etwas verwirrt...

Den Post davor schreibst du doch noch:


Verstehst du mit nicht

IfindU Auf diesen Beitrag antworten »

Genau. Wenn man es elementweise definiert, dann wäre , während . Damit .

Edit: Ich hoffe mal die Aufgabensteller meinen es genauso, ich finde beides vorstellbar.
StrunzMagi Auf diesen Beitrag antworten »

Ah daher kam das Missverständnis...!

Bleibt noch zz.: für
Es gilt für
ZZ.: mit

Wähle


Zusammenfassend:

Es gelten (1) und (2):
(1)
(2)

Nach den gezeigte Gleichungen(1)(2) gilt:

Wenn
mit

d.h.
Oder zeigt die obige Zeile das noch nicht?

Für die andere Richtung muss ich mich auf die Suche nach einen Gegenbeispiel machen oder?
IfindU Auf diesen Beitrag antworten »

Das erste stimmt leider noch nicht, das g_2 nicht in O(x) liegt. Vorhin habe ich die additive Null genommen, weil man dort unfassbar viel Freiheit hatte. Für die Multiplikation bräuchtest du das Analoge der Aufteilung aka die Wurzel (man muss ein wenig mit dem Vorzeichen aufpassen).

Für den zweiten Teil definierst du wohl , was wohl sinnvoller ist, da sonst die linke Seite der Gleichung keine negativen Funktionen enthält. Die Notation ist in dem Fall wirklich ungünstig, da quadrieren im Sinne der Mengen und die Addition der 1 elementweise gemeint ist. Da sollte man den Aufgabensteller drauf hinweisen.

Und ja, das war die leichte Richtung. Man hätte Alternativ einfach schreiben können. Die ganze Arbeit des Beweises lag in der binomischen Formel.

Und ja, ein Gegenbeispiel wäre angebracht. Und denk dabei nicht zu kompliziert. Bereits ein einfaches tut es hier.
StrunzMagi Auf diesen Beitrag antworten »

Hallo Augenzwinkern

ZZ.:

Definiere
Für mit kann ich schreiben

Für kann ich schreiben demnach


Für das Gegenbeispiel der Aussage:
Sei , trivialerweise liegt
Wenn die Aussage gelten würde müsste:
Angenommen es gelte für eine Umgebung von 0:

Für x gegen 0 geht aber die linke Seite ()gegen unendlich ist also unbeschränkt, denmach existiert die Konstante C nicht.
StrunzMagi Auf diesen Beitrag antworten »

Natürlich meine ich
IfindU Auf diesen Beitrag antworten »

Und du minetest im yweiten Fall wohl . Dann ist aber nicht definiert. Formal am besten wäre wohl und dann und . Dann braucht man auch keine Fallunterscheidung.

Und das Gegenbeispiel passt Freude

Noch ein LaTeX-Hinweis: Einen schönen Multiplikationspunkt kriegst du mit \cdot (center-dot) und Äquivalenzpfeile mit \iff (if and only if).
StrunzMagi Auf diesen Beitrag antworten »

Vielen lieben Dank für die Hilfe!!!
Liebe Grüße
IfindU Auf diesen Beitrag antworten »

Gerne. Frohes Fest Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »