Limes berechnen < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:08 So 07.04.2013 | | Autor: | bandchef |
| Aufgabe | | Folgern Sie, dass eine rekursive Implementierung zur Berechnung der Fibonacci-Zahlen die Lauftzeit $T(n) = [mm] \Theta\left(\frac{1+\sqrt{5}}{2}\right)$ [/mm] hat. |
Hi Leute!
Ich hab ein Problem mit diesem Grenzwert. Die Funktion T(n) geht gegen unendlich. Das weiß man bei dieser Aufgabe, weil man das vorher beweisen sollte.
Wie aber muss ich hier nun weiter vorgehen, um den Grenzwert angeben zu können? Der l'Hospital sollte hier wohl nix bringen, weil die Variable n als Potenz im Zähler wie im Nenner mit diesem Satz hier nicht verschwinden wird!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:16 So 07.04.2013 | | Autor: | M.Rex |
Hallo
Forme mal um:
[mm] $\frac{2^n \cdot T(n)}{(1+\sqrt{5})^n}$
[/mm]
[mm] $=\frac{2^n}{(1+\sqrt{5})^n} \cdot [/mm] T(n)$
[mm] $=\left(\frac{2}{1+\sqrt{5}}\right)^n \cdot [/mm] T(n)$
Kommst du damit schon weiter?
Vielleicht hilft es wenn du beachtest, dass der Bruch [mm] \frac{2}{1+\sqrt{5}} [/mm] der Kehrwert des ![[]](/images/popup.gif) Goldenen Schitts ist.
Marius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:23 So 07.04.2013 | | Autor: | bandchef |
Danke für deine Antwort!
Ich hab's jetzt über die Definition der Potenz berechnet:
$...= [mm] \lim_{n \ to \infty}\left(\frac{e^{n\cdot ln(2)}\cdot T(n)}{e^{n\cdot ln(1+\sqrt{5})}}\right) [/mm] = ... = [mm] \lim_{n \to \infty} \left( e^{n\cdot \ln(2)} \cdot T(n)\right) \to \infty \cdot \infty \to \infty$
[/mm]
Passt das so?
|
|
|
| |
|
Nein, das paßt nicht. Wo ist denn der Nenner geblieben? Und was sollen die Pfeile am Ende bedeuten, wenn du doch das Limeszeichen hast? Grenzwerte "streben nicht". Grenzwerte "sind gleich".
[mm]\left( \frac{2}{1 + \sqrt{5}} \right)^n \cdot T(n)[/mm] ist für [mm]n \to \infty[/mm] ein unbestimmter Ausdruck vom Typ [mm]0 \cdot \infty[/mm]. Eine Aussage über seinen Grenzwert ist ohne nähere Kenntnis der Funktion [mm]T(n)[/mm] nicht möglich. Ist [mm]T(n)[/mm] vielleicht ein Polynom in [mm]n[/mm]?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:30 So 07.04.2013 | | Autor: | fred97 |
> Berechnen sie den Limes:
>
> [mm]\lim_{n \to \infty}\left( \frac{2^n \cdot T(n)}{(1+\sqrt{5})^n} \right)[/mm]
>
> Hi Leute!
>
> Ich hab ein Problem mit diesem Grenzwert. Die Funktion T(n)
> geht gegen unendlich. Das weiß man bei dieser Aufgabe,
> weil man das vorher beweisen sollte.
>
> Wie aber muss ich hier nun weiter vorgehen, um den
> Grenzwert angeben zu können? Der l'Hospital sollte hier
> wohl nix bringen, weil die Variable n als Potenz im Zähler
> wie im Nenner mit diesem Satz hier nicht verschwinden wird!
Du hast also die Folge [mm] (a_n) [/mm] mit
[mm] $a_n=\left(\frac{2}{1+\sqrt{5}}\right)^n \cdot [/mm] T(n).$
Der Faktor [mm] \left(\frac{2}{1+\sqrt{5}}\right)^n [/mm] geht gegen 0 für n [mm] \to \infty [/mm] (warum ?).
Solange wir überdas Wachstumverhalten von T(n) nix wissen, können wir über das Verhalten von [mm] (a_n) [/mm] gar nix aussagen.
Beispiele:
1. ist [mm] T(n)=(\left(\frac{2}{1+\sqrt{5}}\right)^n)^{-1}, [/mm] so strebt [mm] (a_n) [/mm] gegen 1
2. ist [mm] T(n)=9^n, [/mm] so strebt [mm] (a_n) [/mm] gegen [mm] \infty.
[/mm]
3. ist 1<q [mm] <(\frac{2}{1+\sqrt{5}})^{-1} [/mm] und [mm] T(n)=q^n, [/mm] so strebt [mm] (a_n) [/mm] gegen 0.
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:35 So 07.04.2013 | | Autor: | bandchef |
Hm, da steht jetzt noch, dass: Folgern Sie, dass eine rekursive Implementierung zur Berechnung der Fibonacci-Zahlen die Lauftzeit $T(n) = [mm] \Theta\left(\frac{1+\sqrt{5}}{2}\right)$ [/mm] hat.
Da doch die Laufzeit der Fibonacci-Zahlen insbesondere wenn man sie rekursiv berechnen lässt gegen unendlich strebt, hab ich doch die Aussage die dir gefehlt hat, oder? T(n) strebt gegen unendlich!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:28 So 07.04.2013 | | Autor: | kaju35 |
Hallo Bandchef,
ich verstehe das so : Eine rekursive Implementierung zur
Berechnung der Fibonacci-Zahlen dauert $T(n)=T(n-1)+T(n-2)$.
Um den n-ten Wert zu berechnen, muss ich zuerst die ersten
n-1 Werte plus die ersten n-2 Werte auswerten.
(Stimmt doch, oder?)
Das entspricht aber gerade der Definition der Fibonacci-Folge.
Diese lässt sich umschreiben als [mm] $F(n)=\frac{1}{\sqrt{5}}\cdot\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$.
[/mm]
Für [mm] $n\to\infty$ [/mm] geht [mm] $\left(\frac{1-\sqrt{5}}{2}\right)^n$ [/mm] gegen 0 und ist
somit zu vernachlässigen.
Ebenso ist der Faktor [mm] $\frac{1}{\sqrt{5}}$ [/mm] in der Landau-Notation
zu vernachlässigen.
Es bleibt also [mm] $T(n)=\Theta\left(\left(\frac{1+\sqrt{5}}{2}\right)^n\right)$
[/mm]
Gruß
Kai
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:48 So 07.04.2013 | | Autor: | bandchef |
Ich musste leider den Aufgabentext ändern weil ich nicht richtig gelesen habe. Entschuldigt bitte!
|
|
|
|
