Landau-Notation und Taylorreihen
-
Bashar schrieb:
Gregor schrieb:
Aus meiner Sicht ist O(x^2) eine Menge von Funktionen. Und nach der Definition stecken da auch die Funktionen f(x)=x und g(x)=1 drin. Das heisst unter anderem auch, dass O(x) eine Teilmenge von O(x^2) ist.
Soweit richtig.
Wie gesagt kommt es darauf an, gegen was x strebt.
Im Zusammenhang einer Taylorreihenentwicklung macht das so aber keinen Sinn. Dort will ich ja angeben, dass jeder weitere Term mindestens n-ter Ordnung und nicht maximal n-ter Ordnung ist.
Nein, das will man nicht sagen
Eigentlich schon
das O macht eine Aussage über Beschränktheit. Auch sin(x) ist O(x^2)
sin ist sogar in O(1) für x gegen unendlich.
obwohl da ganz viele höhere Potenzen in der Taylorentwicklung vorkommen.
Das eine hat nichts mit dem anderen zu tun. Gregor meint nicht, dass man Funktionen gemäß ihrer Taylorentwicklung in Komplexitätsklassen einteilt, sondern dass als Restglied eine Klasse angegeben wird.
-
Michael E. schrieb:
Du betrachtest lediglich die Definition für x gegen unendlich. Im Abschnitt "Formal definition" steht aber auch die Definition für x gegen eine beliebige Zahl.
Ah, ok. Das war der Punkt.
Danke!
Dann werden durch die O-Notation also bezueglich unterschiedlicher Bezugspunkte unterschiedliche Funktionenmengen festgelegt.
-
Michael E. schrieb:
Bashar schrieb:
Gregor schrieb:
Aus meiner Sicht ist O(x^2) eine Menge von Funktionen. Und nach der Definition stecken da auch die Funktionen f(x)=x und g(x)=1 drin. Das heisst unter anderem auch, dass O(x) eine Teilmenge von O(x^2) ist.
Soweit richtig.
Wie gesagt kommt es darauf an, gegen was x strebt.
Wenn nichts anderes gesagt ist, gegen unendlich.
Im Zusammenhang einer Taylorreihenentwicklung macht das so aber keinen Sinn. Dort will ich ja angeben, dass jeder weitere Term mindestens n-ter Ordnung und nicht maximal n-ter Ordnung ist.
Nein, das will man nicht sagen
Eigentlich schon
Nein.
obwohl da ganz viele höhere Potenzen in der Taylorentwicklung vorkommen.
Das eine hat nichts mit dem anderen zu tun. Gregor meint nicht, dass man Funktionen gemäß ihrer Taylorentwicklung in Komplexitätsklassen einteilt, sondern dass als Restglied eine Klasse angegeben wird.
Da das Restglied auch bloß eine Funktion ist, ist das ja wohl dasselbe.
BTW ist Komplexität wohl der falsche Ausdruck. Nur weil man mit der O-Notation unter anderem die Komplexität von Algorithmen angibt, macht das nicht jede O-Menge zu einer Komplexitätsklasse.
Gregor schrieb:
Ah, ok. Das war der Punkt.
Wirklich? Du hattest gar kein konkretes Beispiel angegeben, sondern "sieht man oft etwas in der Art" geschrieben. Ich vermute ganz stark, dass dort in den meisten Fällen x -> unendlich gemeint war.
-
Bashar schrieb:
Michael E. schrieb:
Bashar schrieb:
Gregor schrieb:
Aus meiner Sicht ist O(x^2) eine Menge von Funktionen. Und nach der Definition stecken da auch die Funktionen f(x)=x und g(x)=1 drin. Das heisst unter anderem auch, dass O(x) eine Teilmenge von O(x^2) ist.
Soweit richtig.
Wie gesagt kommt es darauf an, gegen was x strebt.
Wenn nichts anderes gesagt ist, gegen unendlich.
Naja, da es hier explizit um die Abschätzung von Restgliedern bei der Taylorentwicklung geht, ist eigentlich aus dem Kontext klar, dass diese Definition nicht gemeint sein kann.
Im Zusammenhang einer Taylorreihenentwicklung macht das so aber keinen Sinn. Dort will ich ja angeben, dass jeder weitere Term mindestens n-ter Ordnung und nicht maximal n-ter Ordnung ist.
Nein, das will man nicht sagen
Eigentlich schon
Nein.
Genau genommen will man sagen, dass man den Fehler nach oben durch ein Monom von Grad n bis auf einen konstanten Faktor abschätzen kann. Passt also eigentlich zu obigem Zitat.
Gregor meint nicht, dass man Funktionen gemäß ihrer Taylorentwicklung in Komplexitätsklassen einteilt, sondern dass als Restglied eine Klasse angegeben wird.
Da das Restglied auch bloß eine Funktion ist, ist das ja wohl dasselbe.
Nein.
Wirklich? Du hattest gar kein konkretes Beispiel angegeben, sondern "sieht man oft etwas in der Art" geschrieben. Ich vermute ganz stark, dass dort in den meisten Fällen x -> unendlich gemeint war.
Er schreibt doch, dass er sich auf Taylorentwicklungen bezieht...
-
Michael E. schrieb:
Bashar schrieb:
Wenn nichts anderes gesagt ist, gegen unendlich.
Naja, da es hier explizit um die Abschätzung von Restgliedern bei der Taylorentwicklung geht, ist eigentlich aus dem Kontext klar, dass diese Definition nicht gemeint sein kann.
Wieso nicht? Natürlich interessiert man sich für den Fehler, der entsteht, wenn man sich vom Entwicklungspunkt wegbewegt.
Gegen einen beliebigen festen Punkt innerhalb des Konvergenzbereiches ist das sogar völlig uninteressant, da wir es hier ja mit stetigen Funktionen zu tun haben. Dann kannst du nämlich für g(x) alles (was nicht gerade dort 0 wird) einsetzen, f(x)/g(x) ist immer etwas endliches, also ist f(x) in O(g(x)).[Kontext:
Im Zusammenhang einer Taylorreihenentwicklung macht das so aber keinen Sinn. Dort will ich ja angeben, dass jeder weitere Term mindestens n-ter Ordnung und nicht maximal n-ter Ordnung ist.
]
Genau genommen will man sagen, dass man den Fehler nach oben durch ein Monom von Grad n bis auf einen konstanten Faktor abschätzen kann. Passt also eigentlich zu obigem Zitat.Nein, es passt nicht. Dass der Fehler durch x^n beschränkt ist heißt nicht, dass der Fehler keinen Term x^m mit m>n enthalten darf. Das ist nämlich das, was das Zitat behauptet.
Gregor meint nicht, dass man Funktionen gemäß ihrer Taylorentwicklung in Komplexitätsklassen einteilt, sondern dass als Restglied eine Klasse angegeben wird.
Da das Restglied auch bloß eine Funktion ist, ist das ja wohl dasselbe.
Nein.
Doch, natürlich. f(x) = p(x) + O(g(x)) bedeutet f(x) = p(x) + R(x) mit R(x) in O(g(x)), also kannst du gleich über R(x) in O(g(x)) nachdenken, ohne den Kontext zu berücksichtigen.
-
Bashar schrieb:
Michael E. schrieb:
Naja, da es hier explizit um die Abschätzung von Restgliedern bei der Taylorentwicklung geht, ist eigentlich aus dem Kontext klar, dass diese Definition nicht gemeint sein kann.
Wieso nicht? Natürlich interessiert man sich für den Fehler, der entsteht, wenn man sich vom Entwicklungspunkt wegbewegt.
Gegen einen beliebigen festen Punkt innerhalb des Konvergenzbereiches ist das sogar völlig uninteressant, da wir es hier ja mit stetigen Funktionen zu tun haben. Dann kannst du nämlich für g(x) alles (was nicht gerade dort 0 wird) einsetzen, f(x)/g(x) ist immer etwas endliches, also ist f(x) in O(g(x)).Die Taylorentwicklung benutzt man als lokale Approximation, nicht als globale. Warum sollte ich mir dann also den globalen Fehler anschauen?
f(x) / g(x) ist zwar endlich für festes x, aber nicht beschränkt. Betrachte f(x) = x, g(x) = x^2. Dann ist lim_{x -> 0} f(x)/g(x) = lim 1/x = unendlich. Also ist x nicht in O(x^2) bzgl. x gegen 0.
[Kontext:
Im Zusammenhang einer Taylorreihenentwicklung macht das so aber keinen Sinn. Dort will ich ja angeben, dass jeder weitere Term mindestens n-ter Ordnung und nicht maximal n-ter Ordnung ist.
]
Genau genommen will man sagen, dass man den Fehler nach oben durch ein Monom von Grad n bis auf einen konstanten Faktor abschätzen kann. Passt also eigentlich zu obigem Zitat.Nein, es passt nicht. Dass der Fehler durch x^n beschränkt ist heißt nicht, dass der Fehler keinen Term x^m mit m>n enthalten darf. Das ist nämlich das, was das Zitat behauptet.
Das Zitat sagt doch gerade, dass alle Fehlerterme (gleich "jeder weitere Term") mindestens n-ter Ordnung sind
Doch, natürlich. f(x) = p(x) + O(g(x)) bedeutet f(x) = p(x) + R(x) mit R(x) in O(g(x)), also kannst du gleich über R(x) in O(g(x)) nachdenken, ohne den Kontext zu berücksichtigen.
Das ist klar, aber nicht der Punkt. Ich zitiere nochmal den Ausgangspunkt:
Bashar schrieb:
Nein, das will man nicht sagen, das O macht eine Aussage über Beschränktheit. Auch sin(x) ist O(x^2) [oder frag einen Informatiker, der wird dir ln(x) in O(x) bestätigen], obwohl da ganz viele höhere Potenzen in der Taylorentwicklung vorkommen.
Wie habe ich diesen Satz zu verstehen? Du sagst, dass sin(x) in O(x^2) liegt, obwohl eine Taylorentwicklung höhere Potenzen beinhaltet. Das verstehe ich so, dass du denkst, dass Gregor zwischen diesen beiden Dingen einen Zusammenhang sieht. Er bezieht sich allerdings gar nicht darauf, in welche Klasse die zu taylornde Funktion gesteckt werden soll, sonden in welche Klasse das Restglied gesteckt werden soll.
-
Michael E. schrieb:
Die Taylorentwicklung benutzt man als lokale Approximation, nicht als globale. Warum sollte ich mir dann also den globalen Fehler anschauen?
f(x) / g(x) ist zwar endlich für festes x, aber nicht beschränkt. Betrachte f(x) = x, g(x) = x^2. Dann ist lim_{x -> 0} f(x)/g(x) = lim 1/x = unendlich. Also ist x nicht in O(x^2) bzgl. x gegen 0.
OK, erwischt. BTW, hast du dir das zusammengereimt, oder weißt du, dass man das so macht? Gibt man das explizit an, oder geht man bei Fehlerabschätzungen immer explizit von "x gegen den Entwicklungspunkt" aus?
edit: Die Nachfrage hat sich wohl erledigt: http://en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
Das Zitat sagt doch gerade, dass alle Fehlerterme (gleich "jeder weitere Term") mindestens n-ter Ordnung sind
Wir reden wohl über unterschiedliche Teile des Zitats, ich über das "nicht maximal n-ter Ordnung ist", du über "dass jder weitere Term mindesens n-ter Ordnung ist". Also aus Sicht von Gregor im Anfangsposting ich über den als sinnlos angesehenen ist-Zustand, du über den soll-Zustand.
Doch, natürlich. f(x) = p(x) + O(g(x)) bedeutet f(x) = p(x) + R(x) mit R(x) in O(g(x)), also kannst du gleich über R(x) in O(g(x)) nachdenken, ohne den Kontext zu berücksichtigen.
Das ist klar, aber nicht der Punkt. Ich zitiere nochmal den Ausgangspunkt:
Bashar schrieb:
Nein, das will man nicht sagen, das O macht eine Aussage über Beschränktheit. Auch sin(x) ist O(x^2) [oder frag einen Informatiker, der wird dir ln(x) in O(x) bestätigen], obwohl da ganz viele höhere Potenzen in der Taylorentwicklung vorkommen.
Wie habe ich diesen Satz zu verstehen? Du sagst, dass sin(x) in O(x^2) liegt, obwohl eine Taylorentwicklung höhere Potenzen beinhaltet. Das verstehe ich so, dass du denkst, dass Gregor zwischen diesen beiden Dingen einen Zusammenhang sieht.
So hab ich sein Posting verstanden, dass er ein Problem darin sieht, dass die "weiteren Terme" der Taylorreihe, die man in dem O(x^2) zusammenfasst, höhere Ordnungen als x^2 haben. Nochmal zitiert: "Dort will ich ja angeben, dass jeder weitere Term mindestens n-ter Ordnung und nicht maximal n-ter Ordnung ist."
Ich sehe mittlerweile ein, dass ich wahrscheinlich vorschnell die Möglichkeit verworfen habe, dass es um x gegen den Entwicklungspunkt gehen kann. Da Gregor das aber auch nicht klar war, scheine ich ihn aber doch richtig verstanden zu haben.
Er bezieht sich allerdings gar nicht darauf, in welche Klasse die zu taylornde Funktion gesteckt werden soll, sonden in welche Klasse das Restglied gesteckt werden soll.
Ich verstehe nicht, wieso das einen Unterschied machen soll.
-
Bashar schrieb:
Wir reden wohl über unterschiedliche Teile des Zitats, ich über das "nicht maximal n-ter Ordnung ist", du über "dass jder weitere Term mindesens n-ter Ordnung ist". Also aus Sicht von Gregor im Anfangsposting ich über den als sinnlos angesehenen ist-Zustand, du über den soll-Zustand.
OK, Missverständnis
Er bezieht sich allerdings gar nicht darauf, in welche Klasse die zu taylornde Funktion gesteckt werden soll, sonden in welche Klasse das Restglied gesteckt werden soll.
Ich verstehe nicht, wieso das einen Unterschied machen soll.
Beispiel: e^x. Diese Funktion ist in keiner Klasse O(x^n) für beliebige n (bzgl. x gegen unendlich). Hier betrachte ich e^x global. Führe ich aber eine Taylorentwicklung an einer bestimmten Stelle x_0 durch, interessiert mich das globale Verhalten der Funktion nicht mehr, sondern ich schaue, wie schnell das Taylorpolynom gegen e^x konvergiert, wenn ich mich x_0 nähere. Je nachdem, wie weit ich die Taylor-Entwicklung fortführe, liegt das Restglied in Θ(x^2), Θ(x^3), Θ(x^4) etc (bzgl. x gegen x_0). Das ist dann aber keine Eigenschaft der Funktion e^x.
-
Michael E. schrieb:
Er bezieht sich allerdings gar nicht darauf, in welche Klasse die zu taylornde Funktion gesteckt werden soll, sonden in welche Klasse das Restglied gesteckt werden soll.
Ich verstehe nicht, wieso das einen Unterschied machen soll.
Beispiel: e^x. Diese Funktion ist in keiner Klasse O(x^n) für beliebige n (bzgl. x gegen unendlich). Hier betrachte ich e^x global. Führe ich aber eine Taylorentwicklung an einer bestimmten Stelle x_0 durch, interessiert mich das globale Verhalten der Funktion nicht mehr, sondern ich schaue, wie schnell das Taylorpolynom gegen e^x konvergiert, wenn ich mich x_0 nähere. Je nachdem, wie weit ich die Taylor-Entwicklung fortführe, liegt das Restglied in Θ(x^2), Θ(x^3), Θ(x^4) etc (bzgl. x gegen x_0). Das ist dann aber keine Eigenschaft der Funktion e^x.
Das liegt daran, dass e^x zufällig nie Restglied sein kann. Wenn du aber z.B. sin(x)+1 per Taylor approximieren willst und dich schon mit sin(x)+1 = 1 + r(x) zufrieden gibst, dann ist sin(x) genau dein Restglied, und die Betrachtung über das Verhalten des Restgliedes ist genau dasselbe wie die Betrachtung der Taylorentwicklung von sin(x). Mit dem Sinus hatte ich jetzt Glück, aber darauf sollte gar nicht hinauslaufen, sondern darauf, dass das Restglied im Allgemeinen kein Polynom ist, und deshalb der Schluss "x^m ist nicht in O(x^n) (bzgl x --> oo und m>n), deshalb ist mein Restglied, das x^m enthält, auch nicht in O(x^n)" im Allgemeinen nicht richtig.
-
Bashar schrieb:
Das liegt daran, dass e^x zufällig nie Restglied sein kann. Wenn du aber z.B. sin(x)+1 per Taylor approximieren willst und dich schon mit sin(x)+1 = 1 + r(x) zufrieden gibst, dann ist sin(x) genau dein Restglied, und die Betrachtung über das Verhalten des Restgliedes ist genau dasselbe wie die Betrachtung der Taylorentwicklung von sin(x). Mit dem Sinus hatte ich jetzt Glück, aber darauf sollte gar nicht hinauslaufen, sondern darauf, dass das Restglied im Allgemeinen kein Polynom ist, und deshalb der Schluss "x^m ist nicht in O(x^n) (bzgl x --> oo und m>n), deshalb ist mein Restglied, das x^m enthält, auch nicht in O(x^n)" im Allgemeinen nicht richtig.
Das stimmt. Ich sehe zwar auf Anhieb nicht, wo Gegenteiliges behauptet wird, aber wenn wir eh einer Meinung sind, brauchen wir auch nicht weiterzudiskutieren
-
Michael E. schrieb:
Je nachdem, wie weit ich die Taylor-Entwicklung fortführe, liegt das Restglied in Θ(x^2), Θ(x^3), Θ(x^4) etc (bzgl. x gegen x_0).
Ist die Θ-Notation bei Taylorreihen eigentlich auch üblich? Irgendwie habe ich das noch nie in dem Zusammenhang gesehen.
-
Gregor schrieb:
Michael E. schrieb:
Je nachdem, wie weit ich die Taylor-Entwicklung fortführe, liegt das Restglied in Θ(x^2), Θ(x^3), Θ(x^4) etc (bzgl. x gegen x_0).
Ist die Θ-Notation bei Taylorreihen eigentlich auch üblich? Irgendwie habe ich das noch nie in dem Zusammenhang gesehen.
Ich hab Taylor eigentlich nur als Hilfsmittel für Beweise in Analysis in Erinnerung. Bei diesen geht es immer nur darum, eine obere Schranke einzuhalten. Die genaue Größenordnung interessiert dabei nicht. Ich habs also auch noch nicht gesehen, aber auch noch nicht viel Erfahrung.