Landau Notation

Neue Frage »

09.12.2018, 13:56	landau	Auf diesen Beitrag antworten »
Landau Notation Hallo Zu zeigen ist die folgende Gleichung: $\begin{eqnarray} \frac{3n^3-2n^2+6n-1}{n^2-4n+6}=3n+O(1) \end{eqnarray}$ Ich wollte das nun einmal mit einer Grenzwertbetrachtung und einmal mit der Schranken-Quantoren-Definition versuchen. Hier sind meine Lösungsvorschläge: Durch Polynomdivision folgt $\begin{eqnarray} \frac{3n^3-2n^2+6n-1}{n^2-4n+6}=3n+10+\frac{28n-61}{n^2-4n+6} \end{eqnarray}$ und damit $\begin{eqnarray} \lim_{n \to \infty} 10+\frac{28n-61}{n^2-4n+6}=\lim_{n \to \infty} 10+\frac{28-\frac{61}{n}}{n-4+\frac{6}{n}}=10<\infty \end{eqnarray}$ , wodurch $\begin{eqnarray} 10+\frac{28n-61}{n^2-4n+6} \in O(1) \end{eqnarray}$ folgt. Mit der anderen Definition habe ich mir überlegt, dass $\begin{eqnarray} 10+\frac{28n-61}{n^2-4n+6}=10+\frac{28n-61}{(n-2)^2+2} \leq 10+\frac{28n-61}{2}=14n-20,5 \leq c \cdot 1=c>0 \ ~ \forall n \geq 2 \end{eqnarray}$ Ich bitte um Korrektur und ggf. gerne um Verbesserungsvorschläge.
09.12.2018, 14:13	URL	Auf diesen Beitrag antworten »
RE: Landau Notation Der zweite Teil ist falsch. $\begin{eqnarray} 14n-20,5\leq c \end{eqnarray}$ für alle $\begin{eqnarray} n\geq 2 \end{eqnarray}$ ? Der Term ist doch offensichtlich nicht beschränkt, wenn n groß wird.
09.12.2018, 15:27	landau	Auf diesen Beitrag antworten »
Das ist klar. Dann habe ich die Definition falsch verstanden. Ich dachte es reicht, dass es zu jedem n irgendein positives c gibt. Wenn man mal den Graphen zu $\begin{eqnarray} f(n)=10+\frac{28n-61}{n^2-4n+6} \end{eqnarray}$ betrachtet, dann sieht man ja, dass z.B. c=20 eine obere Schranke ist. Dann könnte man ja $\begin{eqnarray} 10+\frac{28n-61}{n^2-4n+6} \leq 20 \end{eqnarray}$ durch Umformungen die entstehende quadratische Ungleichung lösen. Mein Gefühl sagt mir es geht aber bestimmt bedeutend eleganter. Wie wäre denn hier eine übliche Vorgehensweise für die Anwendung der Quantoren-Definition für Landau-Symbole ?
09.12.2018, 15:34	URL	Auf diesen Beitrag antworten »
Du hast in einer Abschätzung im Nenner nur den falschen Teil weggeworfen $\begin{eqnarray} 10+\frac{28n-61}{n^2-4n+6}=10+\frac{28n-61}{(n-2)^2+2} \leq 10+\frac{28n-61}{(n-2)^2}=\ldots \end{eqnarray}$ Ich würde allerdings noch gröber vorgehen $\begin{eqnarray} 10+\frac{28n-61}{n^2-4n+6}<10+\frac{28n}{n^2-4n} = 10+\frac{28}{n-4} \leq 11 \end{eqnarray}$ für $\begin{eqnarray} n\geq 32 \end{eqnarray}$
09.12.2018, 16:25	landau	Auf diesen Beitrag antworten »
$\begin{eqnarray} ...=10+\frac{28(n-2)-5}{(n-2)^2}=10+\frac{28}{n-2}-\frac{5}{(n-2)^2} \leq 10+ \frac{28}{n-2} \leq 38 \end{eqnarray}$ für alle $\begin{eqnarray} n \geq 3 \end{eqnarray}$ Passt das so ?
09.12.2018, 16:29	URL	Auf diesen Beitrag antworten »
Kann man so machen. Man muss natürlich zeigen, dass der Term beschränkt ist, also auch nach unten beschränkt. Aber das ist hier offensichtlich. Vergessen darf man es aber trotzdem nicht.
Anzeige

09.12.2018, 22:41	landau	Auf diesen Beitrag antworten »
Alles klar, vielen Dank schon mal bis dahin. Mit dem Limes macht man sich das Leben aber glaub ich deutlich leichter. Aber zum Üben trotzdem ganz gut eigentlich. Ein paar Gleichungen habe ich noch: $\begin{eqnarray} \sqrt{1+\frac{1}{n}}=1+\frac{1}{2n}+o(\frac{1}{n}) \end{eqnarray}$ Nach Umstellen komme ich dann auf $\begin{eqnarray} \lim_{n \to \infty} \frac{\sqrt{1+\frac{1}{n}}-1-\frac{1}{2n}}{\frac{1}{n}}=\lim_{n \to \infty} n \cdot \frac{\frac{1}{n}}{\sqrt{1+\frac{1}{n}}+1}-\frac{1}{2}=\lim_{n \to \infty} \frac{1}{\sqrt{1+\frac{1}{n}}+1}-\frac{1}{2}=\frac{1}{2}-\frac{1}{2}=0 \end{eqnarray}$ Dann wäre da noch das hier: Falls $\begin{eqnarray} a_n=o(1) \ ~ \ \Rightarrow \ ~ \ \frac{1}{1+a_n}=1-a_n+o(a_n) \end{eqnarray}$ Hier bin ich so vorgegangen: $\begin{eqnarray} \lim_{n \to \infty} \frac{a_n-\frac{a_n}{a_n+1}}{a_n}=\lim_{n \to \infty} 1-\frac{1}{a_n+1}=0 \end{eqnarray}$ da $\begin{eqnarray} a_n=o(1) \Leftrightarrow \lim_{n \to \infty} a_n=0 \end{eqnarray}$ Ist das so in Ordnung ?
09.12.2018, 23:14	URL	Auf diesen Beitrag antworten »
In deinem ersten Beispiel hattest du $\begin{eqnarray} O(1) \end{eqnarray}$ , da gibt's im allgemeinen keinen Grenzwert. Sieht alles für mich richtig aus.
09.12.2018, 23:34	landau	Auf diesen Beitrag antworten »
Alles klar, danke. Bei der letzten zu zeigenden Identität hänge ich leider etwas: $\begin{eqnarray} \sqrt[n]{a}=1+o(\frac{1}{\sqrt{n}}) \ ~ \forall \ ~ \ a>0 \end{eqnarray}$ Bei der Grenzwertbetrachtung $\begin{eqnarray} \lim_{n \to \infty} \frac{\sqrt[n]{a}-1}{\frac{1}{\sqrt{n}}} \end{eqnarray}$ helfen bei mir die üblichen Vorgehensweisen wie Ausklammern, Binome, etc bisher nicht. L'Hospital kenne ich aus der Schule, war aber bisher in der Vorlesung noch nicht dran. Hat ja jemand eine Idee ?
10.12.2018, 00:10	URL	Auf diesen Beitrag antworten »
Setze $\begin{eqnarray} a_n:=\sqrt[n]{a}-1 \end{eqnarray}$ . Die Bernoullische Ungleichung liefert $\begin{eqnarray} a=(1+a_n)^n\geq 1+na_n \end{eqnarray}$ . Kommst du damit schon weiter?
10.12.2018, 00:29	landau	Auf diesen Beitrag antworten »
An die Bernoulli-Ungleichung hatte ich auch kurz gedacht. Ich komme aber leider noch nicht dahinter wie ich deinen Ansatz erfolgreich zu Ende führen kann.
10.12.2018, 00:46	URL	Auf diesen Beitrag antworten »
Für a>1 ist $\begin{eqnarray} 0 \leq a_n \leq \frac{a-1}{n} \end{eqnarray}$

Neue Frage »

Antworten »

Landau Notation

Verwandte Themen