TU Wien:Analysis VU (diverse)/Übungen 2024S/Beispiel 100

Man untersuche, welche o-, O- und ~-Beziehungen zwischen den Folgen $a_n$, $b_n$ und $c_n$ bestehen.

$a_n=2n$, $b_n=\frac{n^2}{2}$, $c_n=\frac{3n^4}{6n^2+1}$

Dieses Beispiel ist als verified_by_prof markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Hilfreiches

Landau-Symbole

Seien $(a_n{)}_{n\ge 0}$ und $(b_n{)}_{n\ge 0}$ Folgen. Dann schreibt man für $n\to \mathrm{\infty }$:

1. (i) $a_n=O(b_n)$, falls es eine Konstante C>0 gibt, so dass $\left|\frac{a_n}{b_n}\right|\le C$ für fast alle $n\in \mathbb{N}$ gilt.
2. (ii) $a_n=o(b_n)$, falls $\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=0$ gilt.
3. (iii) $a_n\sim b_n$, falls $\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=1$ gilt.

  (Definition 4.62)

Lösung

Siehe Beispiel 498 von https://web.archive.org/web/*/www.informatik-forum.at/attachment.php?attachmentid=1097&d=1052595529

Lösung von Kallisto

Wie man im Buch Seite 174 oder oben in der "Hilfreiches"-Section nachlesen kann, handelt es sich bei dieser Art von Beispielen um ein stumpfes miteinander dividieren der gegebenen Terme sowie einer anschließenden Interpretation der Ergebnisse.

Beziehung zwischen $a_n$ und $b_n$:

$\left|\frac{a_n}{b_n}\right|=\left|\frac{2n}{\frac{n^2}{2}}\right|=\left|\frac{2n\cdot 2}{n^2}\right|=\left|\frac{4n}{n^2}\right|=\left|\frac{4}{n}\right|\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\left|\frac{a_n}{b_n}\right|=\underset{n\to \mathrm{\infty }}{lim}\left|\frac{4}{n}\right|=0$

$\left|\frac{b_n}{a_n}\right|=\left|\frac{\frac{n^2}{2}}{2n}\right|=\left|\frac{n}{4}\right|\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\left|\frac{b_n}{a_n}\right|=\underset{n\to \mathrm{\infty }}{lim}\left|\frac{n}{4}\right|=\mathrm{\infty }$

Wir können daraus folgern, dass $a_n$ langsamer wächst als $b_n$, also $a_n=o(b_n)$. Offensichtlich folgt daraus auch $a_n=O(b_n)$.

Beziehung zwischen $a_n$ und $c_n$:

$\left|\frac{a_n}{c_n}\right|=\left|\frac{2n}{\frac{3n^4}{6n^2+1}}\right|=\left|\frac{2n\cdot (6n^2+1)}{3n^4}\right|=\left|\frac{2\cdot (6n^2+1)}{3n^3}\right|=\left|\frac{12n^2+2}{3n^3}\right|=\left|\frac{n^2(12+\frac{2}{n^2})}{n^2(3n)}\right|=\left|\frac{12+\frac{2}{n^2}}{3n}\right|\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\left|\frac{a_n}{c_n}\right|=\underset{n\to \mathrm{\infty }}{lim}\left|\frac{12+\frac{2}{n^2}}{3n}\right|=0$

$\left|\frac{c_n}{a_n}\right|=\left|\frac{\frac{3n^4}{6n^2+1}}{2n}\right|=\left|\frac{3n}{12+\frac{2}{n^2}}\right|\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\left|\frac{c_n}{a_n}\right|=\underset{n\to \mathrm{\infty }}{lim}\left|\frac{3n}{12+\frac{2}{n^2}}\right|=\mathrm{\infty }$

Wir können daraus folgern, dass $a_n$ langsamer wächst als $c_n$, also $a_n=o(c_n)$. Offensichtlich folgt daraus auch $a_n=O(c_n)$.

Beziehung zwischen $b_n$ und $c_n$:

$\left|\frac{b_n}{c_n}\right|=\left|\frac{\frac{n^2}{2}}{\frac{3n^4}{6n^2+1}}\right|=\left|\frac{n^2\cdot (6n^2+1)}{2\cdot (3n^4)}\right|=\left|\frac{6n^4+n^2}{6n^4}\right|=\left|\frac{n^4(6+\frac{1}{n^2})}{n^4(6)}\right|=\left|\frac{6+\frac{1}{n^2}}{6}\right|\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\left|\frac{b_n}{c_n}\right|=\underset{n\to \mathrm{\infty }}{lim}\left|\frac{6+\frac{1}{n^2}}{6}\right|=\left|\frac{6+0}{6}\right|=1$

$\left|\frac{c_n}{b_n}\right|=\left|\frac{\frac{3n^4}{6n^2+1}}{\frac{n^2}{2}}\right|=\left|\frac{6}{6+\frac{1}{n^2}}\right|\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\left|\frac{c_n}{b_n}\right|=\underset{n\to \mathrm{\infty }}{lim}\left|\frac{6}{6+\frac{1}{n^2}}\right|=1$

Wir können daraus folgern, dass $b_n$ gleich schnell wächst wie $c_n$, also $b_n\sim c_n$. Offensichtlich folgt daraus auch $c_n\sim b_n$ sowie $b_n=O(c_n)$ und $c_n=O(b_n)$.