Landau-Notation

18.11.2014, 03:53

telli

Landau-Notation

Meine Frage:
Hallo Leute,

Ich habe mal eine allgemeine Frage zu Landau-Notation:

Meine Ideen:
Ich hatte einige Informatikvorlesungen zu Komplexitätstheorie da haben wir auch die BigOH bzw. O-Notation gesehen. Die O-Notation liefert ja grob gesagt eine obere Schranke für Funktionen z.B. f(x)=3x^2-15x ist O(x^2) alles gut.

Nun in der Numerikvorlesung und einigen Mathematikpaketen wie Maple habe ich diese Notation in einer für mich nicht so verständlichen Art gesehen.

Wenn man z.B die Taylorreihe von sqrt(1+x) sucht spuckt maple etwas wie:
1 + 1/2x - 1/8x^2 + 1/16x^3 - 5/128x^4 + 7/256x^5 + O(x^6)

Das Dumme ist nun, für mich heisst O(x^6):
Es existiert eine Restfunktion f(x) so dass,
1 + 1/2x - 1/8x^2 + 1/16x^3 - 5/128x^4 + 7/256x^5 + f(x)
und für die gilt:
f(x) <= const*x^6 wobei const irgendeine Konstante ist.

Es ist aber offensichtlich, dass das nicht stimmen kann, da die Reihe mit
... + ax^6 + bx^7 + cx^8 + ...
fortgesetzt wird.

Ich komme nun zum Schluss, dass diese "beiden" O-Notationen nicht die gleiche Definition haben, was mich noch mehr verwirrt..

Kann mich jemand aufklären?
Danke!

18.11.2014, 10:00

Hausmann

Auf diesen Beitrag antworten »

RE: Landau-Notation
Guten Morgen!

Soweit ich mich erinnere, beziehen sich diese Symbole auf einen bestimmten Grenzwert. Das dürfte in dem Beispiel null sein:

Zitat:

Original von telli
Wenn man z.B die Taylorreihe von sqrt(1+x) sucht spuckt maple etwas wie:
1 + 1/2x - 1/8x^2 + 1/16x^3 - 5/128x^4 + 7/256x^5 + O(x^6)

mfG

18.11.2014, 10:11

bijektion

Auf diesen Beitrag antworten »

Zitat:

Kann mich jemand aufklären?

Ja.

Ist $\begin{eqnarray*} f\in C^{n+1} (I) \end{eqnarray*}$ mit einem abgeschlossenen Intervall $\begin{eqnarray*} I\subset \mathbb{R} \end{eqnarray*}$ , so ist das Taylorpolynom um $\begin{eqnarray*} x_0\in I \end{eqnarray*}$ gegeben durch $\begin{eqnarray*} f(x)=\sum_{k=0}^n \frac{f^{(k)}(x_0)}{k!}\cdot (x-x_0)^k + R^{n+1}_{x_0,f}(x) \end{eqnarray*}$ wobei es nun mehrere Darstellungen für den Fehler gibt.

Eine mögliche wäre z.B. $\begin{eqnarray*} R^{n+1}_{x_0,f}(x) = \frac{f^{n+1}(\xi)}{(n+1)!}\cdot (x-x_0)^{n+1} \end{eqnarray*}$ mit einem $\begin{eqnarray*} \xi \end{eqnarray*}$ zwischen $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} x_0 \end{eqnarray*}$ , insb. sicherlich $\begin{eqnarray*} |R^{n+1}_{x_0,f}(x)|\leq \frac{\max_{s\in I} |f^{n+1}(s)|}{(n+1)!}\cdot |x-x_0|^{n+1} \end{eqnarray*}$ .

Dieser Fehler ist nun in der Größenordnung $\begin{eqnarray*} \mathcal{O}(x^{n+1}) \end{eqnarray*}$ für $\begin{eqnarray*} x\to x_0 \end{eqnarray*}$ .

18.11.2014, 21:59

telli

Auf diesen Beitrag antworten »

Danke für die Antworten!

Zitat:

Soweit ich mich erinnere, beziehen sich diese Symbole auf einen bestimmten Grenzwert.

Ja was ähnliches habe ich auch gelesen aber nicht so ganz verstanden schätze ich. Könnte man denn nicht die Definition aus der Informatik, die ich verwendet habe damit in zusammenhang bringen?

Zitat:

Eine mögliche wäre z.B. $\begin{eqnarray*} R^{n+1}_{x_0,f}(x) = \frac{f^{n+1}(\xi)}{(n+1)!}\cdot (x-x_0)^{n+1} \end{eqnarray*}$

Ja das ist eben genau mein Problem. Ich verstehe nicht warum R ein Polynom vom grad n+1 sein soll? Die Taylor-Reihe ist ja unendlich d.h. der Grad des "Restpolynoms" geht an sich auch gegen unendlich? n+1 wäre doch die kleinste Potenz im Restpolynom?

Neue Frage »

Antworten »

Landau-Notation

Verwandte Themen