Rekursion - offene Form < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:22 Fr 24.01.2014 | | Autor: | shadee |
| Aufgabe | | Gegeben sei die folgende Rekursionsgleichung: [mm] m_k [/mm] = [mm] 3*m_{k-1}+1 [/mm] für k > 1, m(1) = 2. Geben sie die explizite Form an. |
Ich hab ein paar Schwierigkeiten damit, weil ich nicht genau weiß wie genau ich anfangen soll. Wie berechnet man denn eine explizite Form einer Rekursionsgleichung. Ich habe gelesen, dass das über eine erzeugenden Funktion geht oder über die Ableitung der Differenzen der Folgeglieder und dann Konvergenzradius berechnen. Kann mir jemand ein Schema präsentieren, nach dem ich das lösen kann?
Vielen Dank
|
|
| |
|
Hallo shadee,
> Gegeben sei die folgende Rekursionsgleichung: [mm]m_k[/mm] =
> [mm]3*m_{k-1}+1[/mm] für k > 1, m(1) = 2. Geben sie die explizite
> Form an.
> Ich hab ein paar Schwierigkeiten damit, weil ich nicht
> genau weiß wie genau ich anfangen soll. Wie berechnet man
> denn eine explizite Form einer Rekursionsgleichung. Ich
> habe gelesen, dass das über eine erzeugenden Funktion geht
> oder über die Ableitung der Differenzen der Folgeglieder
> und dann Konvergenzradius berechnen. Kann mir jemand ein
> Schema präsentieren, nach dem ich das lösen kann?
>
Schau mal hier:
![[]](/images/popup.gif) Lösung linearer Differenzengleichungen mit konstanten Koeffizienten
> Vielen Dank
Gruss
MathePower
|
|
|
| |
|
Wenn der Summand +1 fehlte, wäre sofort klar, wie das k-te Glied aussehen würde. Deshalb versuchst du, diesen Summanden so wegzutransformieren, dass er verschwindet. (Das geht immer so mit alle Rekursionsgleichungen, die linear sind.)
Ansatz: [mm] m_k =x_k [/mm] + a, a fest, noch unbekannt, wird später passend gemacht.
Dann folgt aus [mm] m_k [/mm] = 3 [mm] m_{k-1}+1 [/mm]
die Gleichung [mm] x_k+a [/mm] = [mm] 3(x_{k-1}+a)+1
[/mm]
und daraus [mm] x_k+a [/mm] = [mm] 3x_{k-1}+3a+1 [/mm]
oder [mm] x_k [/mm] = [mm] 3x_{k-1}+2a+1
[/mm]
Wähle nun a so, dass 2a+1=0 ist, also a= - 1/2.
Nun [mm] gilt:x_k [/mm] = [mm] 3x_{k-1} [/mm] und damit [mm] x_k [/mm] = [mm] A*3^k.
[/mm]
Zurücktransformiert erhältst du [mm] x_k=m_k-a [/mm] = [mm] m_k+1/2 [/mm] und damit
[mm] m_k [/mm] +1/2= [mm] A*3^k [/mm] oder [mm] m_k [/mm] = [mm] A*3^k [/mm] -1/2.
Mit [mm] m_1=A*3-1/2=2 [/mm] erhältst du noch A=1/2 und damit endgültig
[mm] m_k [/mm] = [mm] (1/2)*3^k [/mm] -1/2 = [mm] (3^k-1)/2.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:09 Fr 24.01.2014 | | Autor: | shadee |
Die Schritte sind soweit nachvollziehbar. Aber wenn ich mal für k =3 die rekursive Variante berechne komme ich auf m(3) = 3*m(2) + 1 = 3*(3*m(1)+1) + 1 = 3*(3*2+1) + 1 = 22. Und die offene Darstellung wäre dann m(3) = [mm] (3^3-1)/2 [/mm] = 13. Da kommen zwei verschiedene Werte raus?
|
|
|
| |
|
Hallo shadee,
> Die Schritte sind soweit nachvollziehbar. Aber wenn ich mal
> für k =3 die rekursive Variante berechne komme ich auf
> m(3) = 3*m(2) + 1 = 3*(3*m(1)+1) + 1 = 3*(3*2+1) + 1 = 22.
> Und die offene Darstellung wäre dann m(3) = [mm](3^3-1)/2[/mm] =
> 13. Da kommen zwei verschiedene Werte raus?
Der erstere Wert [mm]m_{3}=22[/mm] ist richtig.
Die berechnete Konstante A ist nicht richtig.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:04 Fr 24.01.2014 | | Autor: | Sax |
Hi,
da du von "erzeugenden Funktionen" schriebst, lass mich dir diese Methode kurz vorstellen, auch wenn sie wesentlich komplizierter ist als der von HJKweseleit aufgezeigte Weg.
Lass uns der Einfachheit halber die Zählung bei 0 beginnen, wir betrachten also die Rekursion [mm] a_0=2 [/mm] und [mm] a_{n+1}=3*a_n+1 [/mm] für [mm] n\in\IN_0.
[/mm]
Als erzeugende Funktion betrachtet man nun die Potenzreihe $ [mm] f(x)=\summe_{n=0}^{\infty}a_n*x^n [/mm] $.
Die Idee besteht darin, eine geschlossene Form für die Funktion f zu finden, diese in eine Potenzreihe zu verwandeln und durch Koeffizientenvergleich eine explizite Darstellung der [mm] a_n [/mm] zu gewinnen.
f(x) = [mm] \summe_{n=0}^{\infty}a_n*x^n
[/mm]
= [mm] a_0 [/mm] + [mm] \summe_{n=1}^{\infty}a_n*x^n
[/mm]
= [mm] a_0 [/mm] + [mm] \summe_{n=0}^{\infty}a_{n+1}*x^{n+1}
[/mm]
= [mm] a_0 [/mm] + [mm] x*\summe_{n=0}^{\infty}a_{n+1}*x^n
[/mm]
= [mm] a_0 [/mm] + [mm] x*\summe_{n=0}^{\infty}(3*a_n+1)*x^n
[/mm]
= [mm] a_0 [/mm] + [mm] 3x*\summe_{n=0}^{\infty}a_n*x^n [/mm] + [mm] x*\summe_{n=0}^{\infty}x^n
[/mm]
= [mm] a_0 [/mm] + $ 3x*f(x) $ + [mm] \bruch{x}{1-x}
[/mm]
[mm] \Rightarrow [/mm] $ f(x)*(1-3x) = [mm] a_0 [/mm] + [mm] \bruch{x}{1-x} [/mm] $
f(x) = [mm] \bruch{a_0}{1-3x} [/mm] + [mm] \bruch{x}{(1-x)*(1-3x)} [/mm] = [mm] \bruch{a_0}{1-3x} [/mm] + [mm] (\bruch{-\bruch{1}{2}}{1-x} [/mm] + [mm] \bruch{\bruch{1}{2}}{1-3x} [/mm] ) (Partialbruchzerlegung)
= [mm] \bruch{a_0+\bruch{1}{2}}{1-3x} [/mm] - [mm] \bruch{\bruch{1}{2}}{1-x}
[/mm]
= [mm] \summe_{n=0}^{\infty}((a_0+\bruch{1}{2})*(3x)^n [/mm] - [mm] \bruch{1}{2}*x^n) [/mm] (geometrische Reihe)
= [mm] \summe_{n=0}^{\infty}((a_0+\bruch{1}{2})*3^n [/mm] - [mm] \bruch{1}{2})*x^n
[/mm]
Somit ist [mm] a_n [/mm] = [mm] (a_0+\bruch{1}{2})*3^n [/mm] - [mm] \bruch{1}{2} [/mm] = [mm] \bruch{5}{2}*3^n [/mm] - [mm] \bruch{1}{2} [/mm] = [mm] \bruch{5*3^n-1}{2}
[/mm]
Zurücktransformiert auf deine Bezeichnungen erhälst du also
m(k) = [mm] \bruch{5*3^{k-1}-1}{2}
[/mm]
Gruß Sax.
|
|
|
|
