Auswahl Schwarzes Brett Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
Autor |
Wachstum einer Folge bestimmen |
|
Dreadwar
Aktiv  Dabei seit: 19.04.2019 Mitteilungen: 102
 |
Hallo Leute,
ich soll entscheiden, ob die folgenden Folgen exponentiell oder polynomial wachsen bzw.fallen:
 
((\alpha_n))_n = (n*2^n+n^2)/(3^n+n) ((\beta_n))_n = (sum(1/k,k=1,n)) ((\gamma_n)) = n! ((\delta_n)) = sqrt(n^4+n^3)-sqrt(n^4+1) Meine Idee war, mir entsprechende Vergleichsfolgen zu suchen und mithilfe der Landau-Notation das Wachstum der Folgen zu beschreiben. Mein Problem ist allerdings, das mir die Laundau-Notation ja nur sagt, wie das Verhältnis des Wachstums aussieht, nicht aber die Art des Wachstums. In unserem Skript steht :''Typische Referenzfolgen: n^+-m , m\el\ \IN - Polynomiales Wachstum/Abfall , M^n, M>1 - exponentielles Wachstum bzw. q^n, 0<q<1- exponentieller Abfall. Die Info ist schön und gut, jedoch weiß ich nicht so recht wie ich das verwenden soll bzw. was mir das Ergebnis genau sagen soll wenn ich verglichen habe. z.B möchte ich \alpha_n mit b_n =(1/2)^n vergleichen: Ich kürze das wegen der Schreibarbeit mal ab, ich bekomme für lim(n->\inf,\alpha_n/b_n ) = 0 heraus. Das sagt mir ja erstmal nur, dass \alpha_n langsamer wächst als (1/2)^n bzw. das \alpha_n \el\ o(b_n) ist. Über die Art des Wachstums kann ich persönlich hieraus jetzt keine Erkenntnis gewinnen. Ich hoffe ihr könnt mir einen Denkanstoß geben und entschuldigt bitte den Umfang der Frage, bin bissl am vezweifeln weil ich alle Werkzeuge habe, aber sie nicht einzusetzen weiß. Danke schonmal und liebe Grüße
|
Profil
Quote
Link |
ochen
Senior  Dabei seit: 09.03.2015 Mitteilungen: 2549
Aus: der Nähe von Schwerin
 |     Beitrag No.1, eingetragen 2019-11-11
|
Hallo,
was darfst du verwenden? Wir beginnen mal mit der b).
Es gilt einerseits
\[\sum_{k=1}^n\frac 1k=\int_{1}^{n+1}\frac{1}{[x]}\,\mathrm dx\geq \int_{1}^{n+1}\frac{1}{x}\,\mathrm dx = \ln(n+1)\]
und andererseits
\[\sum_{k=1}^n\frac 1k=1+\int_{1}^{n}\frac{1}{1+[x]}\,\mathrm dx\leq 1+\int_{1}^{n}\frac{1}{x}\,\mathrm dx = 1 + \ln(n).\]
Was bedeutet das jetzt?
Für die d) verwende die dritte binomische Formel.
|
Profil
Quote
Link |
Dreadwar
Aktiv  Dabei seit: 19.04.2019 Mitteilungen: 102
 |     Beitrag No.2, vom Themenstarter, eingetragen 2019-11-11
|
Hallo Ochen, danke für die Antwort!
Ich darf leider keine Differential- und Integralrechnung verwenden, den ln "kennen wir noch nicht". Aber trotzdem danke für die Hilfe!
Liebe Grüße
|
Profil
Quote
Link |
ochen
Senior  Dabei seit: 09.03.2015 Mitteilungen: 2549
Aus: der Nähe von Schwerin
 |     Beitrag No.3, eingetragen 2019-11-11
|
Hm, ok, habt ihr denn den Logarithmus definiert?
Wenn es nur um Polynome geht, so gilt ganz offenbar $b_n\leq n$ für alle natürlichen Zahlen $n$.
|
Profil
Quote
Link |
Dreadwar
Aktiv  Dabei seit: 19.04.2019 Mitteilungen: 102
 |     Beitrag No.4, vom Themenstarter, eingetragen 2019-11-11
|
Den Logarithmus haben wir noch nicht definiert, ich soll das irgendwie mit dieser Landau-Notation zeigen, sehe aber den Wald vor lauter Bäumen nicht mehr.
Liebe Grüße
|
Profil
Quote
Link |
ochen
Senior  Dabei seit: 09.03.2015 Mitteilungen: 2549
Aus: der Nähe von Schwerin
 |     Beitrag No.5, eingetragen 2019-11-11
|
Ja, was sollst du denn zeigen? Die Landau-Notation ist nur eine Kurzschreibweise :)
Sollst du $b_n\in O(n)$ beweisen? Das ist ganz einfach, denn dann genügt es $b_n\leq n$ zu zeigen. Auch $b_n\in o(n)$ kannst du nachrechnen :)
Kannst du bitte mal den Originalwortlaut der Aufgabenstellung posten? Und vielleicht auch wie ihr polynomielles und exponentielles Wachstum definiert habt?
|
Profil
Quote
Link |
Dreadwar
Aktiv  Dabei seit: 19.04.2019 Mitteilungen: 102
 |     Beitrag No.6, vom Themenstarter, eingetragen 2019-11-11
|
Hallo Ochen,
die Aufgabenstellung lautet:
Untersuchen Sie für jede der angegebenen Folgen, ob sie polynomial oder exponentiell wächst bzw. fällt.
Wir haben im Zuge der Landau-Notation definiert:
Referenzfolgen:
 
exponentielles Wachstum: (M^n)_n , M>1 exponentielles Fallen: ((q)^n)_n , 0<q<1 polynomiales Wachstum: (n^m)_n , m\el\ \IN polynomiales Fallen: (n^(-m))_n, m\el\ \IN Das hilft mir wie gesagt nicht viel. Eine Idee bei der a) wäre zu sagen, dass (n*2^n+n^2)/(3^n+n) = n*2^n/3^n , da ja die Polynome unwichtig werden mit größerwerdendem n. Das hätte dann die Form von n*(2/3)^n und stimmt dadurch mit der Bedingung q^n , 0<q<1 überein. Ob man das so machen kann weiß ich allerdings nicht.
Liebe Grüße
|
Profil
Quote
Link |
|