O-Notation

01.04.2022, 23:43

kurttt

O-Notation

Meine Frage:
Hey,

Die Aufgabe lautet: Zeigen oder widerlegen Sie, dass $\begin{eqnarray*} \sqrt{x^5 - 2x^3+1} \in O(x^2) \end{eqnarray*}$

Ich bin mir nicht ganz sicher wie man das sauber zeigt.

Meine Ideen:
Hab dann versucht das mit Abschätzungen zu zeigen:

$\begin{eqnarray*} \sqrt{x^5 - 2x^3+1} \geq \sqrt{x^5 - 2x^3} = \sqrt{x^2 \cdot (x^3-2)} \end{eqnarray*}$

$\begin{eqnarray*} = x \¢dot \sqrt{x^3-2} \geq x \cdot \sqrt{x^3 \cdot \frac{1}{2}} [latex]<br /> <br /> [latex]\geq x \cdot x^{1,5} \cdot \frac {1}{\sqrt{2}} = \frac {1}{\sqrt{2}} \cdot x^{2,5} \end{eqnarray*}$

Die Ungleichungen sind wahr für alle x > 1

Kann man das so machen ?

01.04.2022, 23:46

kurttt

Auf diesen Beitrag antworten »

RE: O Notation

Zitat:

Original von kurttt
Meine Frage:
Hey,

Die Aufgabe lautet: Zeigen oder widerlegen Sie, dass $\begin{eqnarray*} \sqrt{x^5 - 2x^3+1} \in O(x^2) \end{eqnarray*}$

Ich bin mir nicht ganz sicher wie man das sauber zeigt.

Meine Ideen:
Hab dann versucht das mit Abschätzungen zu zeigen:

$\begin{eqnarray*} \sqrt{x^5 - 2x^3+1} \geq \sqrt{x^5 - 2x^3} = \sqrt{x^2 \cdot (x^3-2)} \end{eqnarray*}$

$\begin{eqnarray*} = x \cdot \sqrt{x^3-2} \geq x \cdot \sqrt{x^3 \cdot \frac{1}{2}} \end{eqnarray*}$

$\begin{eqnarray*} \geq x \cdot x^{1,5} \cdot \frac {1}{\sqrt{2}} = \frac {1}{\sqrt{2}} \cdot x^{2,5} \end{eqnarray*}$

Die Ungleichungen sind wahr für alle x > 1

Kann man das so machen ?

01.04.2022, 23:50

kurttt

Auf diesen Beitrag antworten »

RE: O Notation
Daraus würde dann folgen, dass die Funktion nicht in O(x^2) liegt.

Sorry für das Chaos, editieren ist als Gast nicht möglich.

02.04.2022, 09:13

Leopold

Auf diesen Beitrag antworten »

Beim Ausklammern von $\begin{align*} x^2 \end{align*}$ unter der Wurzel hast du einen Fehler gemacht. Und die Abschätzung $\begin{align*} x^3-2 \geq \frac{1}{2} x^3 \end{align*}$ gilt erst ab $\begin{align*} x_0=\sqrt[3]{4} \end{align*}$ . Letzteres wäre nicht so schlimm, da man ja $\begin{align*} x \to \infty \end{align*}$ gehen läßt. Ich würde den Quotienten

$\begin{align*} \frac{\sqrt{x^5-2x^3+1}}{x^2} = \frac{\sqrt{x^5 \left( 1 - 2x^{-2} + x^{-5} \right)}}{x^2} \end{align*}$

betrachten. Vereinfache noch ein wenig und untersuche ihn für $\begin{align*} x \to \infty \end{align*}$ .

02.04.2022, 11:34

IfindU

Auf diesen Beitrag antworten »

RE: O Notation

Zitat:

Original von kurttt
[...] $\begin{eqnarray*} \sqrt{x^5 - 2x^3+1} \geq \sqrt{x^5 - 2x^3} \end{eqnarray*}$ [...]

Zusätzlich zu Leopolds Anmerkung ist der Ausdruck auf der rechten Seite hier erst ab $\begin{eqnarray*} x \geq \sqrt{2} \end{eqnarray*}$ definiert. Auch kein "echtes" Problem wie Leopold schon sagte, aber dennoch sollte man darauf achten.

02.04.2022, 22:37

kurttt

Auf diesen Beitrag antworten »

Hallo und danke euch beiden für die Hinweise,

Also wenn ich nun Leopolds Quotienten heranziehen soll, dann fiele mir nur ein Widerspruchsbeweis ein:

Wenn f(x) in O(g(x)) liegen würde, dann würde für alle x > x0 gelten:

$\begin{eqnarray*} \sqrt{x^5 -2x^3 + 1} \leq C \cdot x^2 \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow \frac{\sqrt{x^5 -2x^3 + 1}}{x^2} = \frac{\sqrt{x^5(1-2x^{-2}+x^{-5})}}{x^2} \end{eqnarray*}$

$\begin{eqnarray*} = \frac{ \sqrt{x^4\cdot x(1-2x^{-2}+x^{-5}})}{x^2} = \frac{x^2\sqrt{x\cdot(1-2x^{-2}+x^{-5}})}{x^2} = \sqrt{(x-2x^{-1}+x^{-4})} \leq C \end{eqnarray*}$

Die letzte Ungleichung kann aber nicht stimmen, da der Wurzelausdruck für x gegen unendlich ebenfalls gegen unendlich geht und somit größer als jede Konstante wird.

02.04.2022, 22:54

Leopold

Auf diesen Beitrag antworten »

Der Widerspruchsbeweis erscheint mir gekünstelt. Warum nicht direkt?

$\begin{align*} \frac{\sqrt{x^5 \left( 1 - 2x^{-2} + x^{-5} \right)}}{x^2} = \underbrace{\sqrt{x}}_{\to \infty} \cdot \underbrace{\sqrt{1 - 2x^{-2} + x^{-5}}}_{\to 1} \to \infty \ \ \mbox{für} \ \ x \to \infty \end{align*}$

Aus der Unbeschränktheit des Ausdrucks folgt:

$\begin{align*} \sqrt{x^5 - 2x^3 + 1} \not \in O \left( x^2 \right) \end{align*}$

(Richtig ist dagegen offenbar: $\begin{align*} \sqrt{x^5 - 2x^3 + 1} \in O \left( x^{2{,}5} \right) \end{align*}$ )

02.04.2022, 23:15

kurttt

Auf diesen Beitrag antworten »

Ich wollte immer die Konstante C und das "kleiner gleich" aus der Definition der O-Notation mit reinnehmen, weswegen es zugegebenermaßen ein wenig gekünstelt aussieht.

Vielen Dank für die schnelle, unkomplizierte Hilfe !

Neue Frage »

Antworten »

O-Notation

Verwandte Themen