Rechenregeln für die Landau-Symbole Beweisen

Question

Seien f, g, g1, g2 : I → ℝ, wobei I ⊂ ℝ ein Intervall mit 0 ∈ I ist und sei x→ 0. Zeigen Sie die folgenden Rechenregeln für die Landausymbole:

(a) f = o(g) ⇒ f = O(g)

(b) f = O(g), a ∈ ℝ ⇒ af = O(g)

(c) f₁ = O(g₁), f₂ = O(g₂) ⇒ f₁ · f₂ = O(g₁ · g₂)

Comments

Hallo

 hast du die Definitionen von o(g) und O(g) mal hingeschrieben und einfach angewendet, oder was hast du versucht?

lul

---

Ich habe aus einem Buch die Definitionen herausgefunden. In diesem Buch wird eine andere Rechenregel bewiesen und es wird dort gesagt, dass diese Rechenregeln oben analog dazu zu beweisen sind.

Dies ist mir jedoch nicht Hilfe genug, da ich nicht weiß, wie ich das Analog Anwenden kann.

Aus dem Buch wird diese Regel Bewiesen:

f1 = O(g), f2 = O(g) ⇒ f1 + f2 = O(g)

Den Beweis dazu, könnte ich eventuell bei c) analog anwenden. Bei a) und b) jedoch, stehe ich auf dem Schlauch.

---

hallo

 dann schreib mal die Definitionen auf!

---

Es seien f, g : D ⊂ ℝⁿ → ℝ, x ↦ f(x), g(x) zwei Funktionen und x, x₀ ∈ D.

(i) Die Funktion f wächst für x → x₀ ein o(g), symbolisch geschrieben als f = o(g), x → x₀

oder f (x) = o(g(x)), x → x_{0 , wenn}

lim [x → x₀ ]     ( | f(x )| ) / ( | g(x) | ) = 0    gilt

(ii) Die Funktion f wächst für x → x₀ nicht wesentlich schneller als g, oder f ist für x → x₀ ein O(g), symbolisch geschrieben als f = O(g), x → x₀ oder f(x) = O(g(x)), x → x₀, wenn

∃c > 0 ∃ε >0 :      | f(x) | ≤ c | g(x) |

für alle x mit | x → x₀| < ε gilt.

(iii) f = o(g), x → ∞ und f = O(g), x → ∞ werden analog definiert.

Answer 1

Ich definiere zwei Funktionen \(h_1\) und \(h_2\), die nach \(O(f(x))\) und \(O(g(x))\) durch \(f(x)\) bzw. \(g(x)\) und einen konstanten Faktor \(c\) beschränkt werden (Def von O):

$$h_1(x) \leq c\cdot f(x)$$
$$h_2(x) \leq c\cdot g(x)$$

So, jetzt ist das Produkt von \(h_1\) und \(h_2\) folgendes:

$$h_1(x)\cdot h_2(x) \leq c\cdot f(x)\cdot g(x)$$

Ich substituiere nun \(h_1(x)*h_2(x) = h(x)\) daraus folgt dann:

$$h(x) \leq c\cdot f(x)\cdot g(x)$$

Jetzt fällt uns auf, dass dies \(O(f(x)\cdot g(x))\) entspricht

Comments

Vielen Dank. Da diese Regel außer dem Vorzeichen, der aus dem Buchs sehr ähnelt, kann ich das gut nachvollziehen. Bei der a) jedoch habe ich einmal Definition (i) und ein mal Definition (ii). In diesem Fall weiß ich nicht, wie ich das beweisen soll.

---

Ich mache (b) mal sprachlich. Also wir haben eine Funktion f die durch g beschränkt wird f <= c*g. Also höchstens g und irgendein konstanter Faktor ist. Jetzt könnte ich f mit einem konstanten Faktor, nennen wir ihn a, multiplizieren:

f <= c*g |*a

af <= a*c*g

das tolle ist a*c ist ja wieder eine Konstante, nennen wir sie C:

af <= C*g und das ist wieder die bekannte Definition zu O

In Dirk W. Hoffman - Theo. Info. ist das sehr gut erklärt by the way!