homogene Rekursionsfolge < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:14 Mi 30.01.2013 | | Autor: | locke123 |
| Aufgabe | | Gegeben sei die linear homogene Rekursionsfolge [mm] x_{n}=2x_{n-1}+x_{n-2}-2x_{n-3} [/mm] für [mm] n\ge1, [/mm] wobei [mm] x_{-2}=0, x_{-1}=1, x_{0}=2 [/mm] ist. Finden Sie eine geschlossene Formel für das Folgenglied [mm] x_{n}. [/mm] |
Hallo Leute ich brauch eure Hilfe um die Aufgabe zu verstehen,
ich komme irgendwie mit den negativen Indizies nicht klar. Und zwar hatten wir dies zwar in der Vorlesung/Tutorium, aber nur mit positiven Indizies und nun komm ich ziemlich durcheinander.
Wir hatten lineare Rekursion so aufgeschrieben:
Sei [mm] x_{n}=c_{1}x_{n-1}+...+c_{k}x_{n-k} [/mm] eine rekursive Folge, wobei [mm] x_{1},...,x_{k} [/mm] bekannt.
Ich komme hier irgendwie nicht auf die c's und nicht auf die x's um die Nullstellen zu berechnen, die negativen Indizies bringen mich wie gesagt irgendwie durcheinander, kann mir da jemand einen Tipp geben?
Viele Grüße
|
|
| |
|
Hallo locke123,
negative Indices (auch: Indizes; beides mit langem "e" gesprochen, aber Betonung auf der ersten Silbe) sind absolut unüblich. Von daher ist Deine Verwirrung verständlich. Glücklicherweise kann man ihr leicht abhelfen. 
> Gegeben sei die linear homogene Rekursionsfolge
> [mm]x_{n}=2x_{n-1}+x_{n-2}-2x_{n-3}[/mm] für [mm]n\ge1,[/mm] wobei [mm]x_{-2}=0, x_{-1}=1, x_{0}=2[/mm]
> ist. Finden Sie eine geschlossene Formel für das
> Folgenglied [mm]x_{n}.[/mm]
> Hallo Leute ich brauch eure Hilfe um die Aufgabe zu
> verstehen,
>
> ich komme irgendwie mit den negativen Indizies nicht klar.
> Und zwar hatten wir dies zwar in der Vorlesung/Tutorium,
> aber nur mit positiven Indizies und nun komm ich ziemlich
> durcheinander.
>
> Wir hatten lineare Rekursion so aufgeschrieben:
>
> Sei [mm]x_{n}=c_{1}x_{n-1}+...+c_{k}x_{n-k}[/mm] eine rekursive
> Folge, wobei [mm]x_{1},...,x_{k}[/mm] bekannt.
>
> Ich komme hier irgendwie nicht auf die c's
Aber die stehen doch schon da!
> und nicht auf
> die x's um die Nullstellen zu berechnen, die negativen
> Indizies bringen mich wie gesagt irgendwie durcheinander,
> kann mir da jemand einen Tipp geben?
Wir definieren eine andere Folge [mm] a_n [/mm] mit [mm] a_n=x_{n-2}.
[/mm]
Es ist also [mm] a_0=0, a_1=1, a_2=2.
[/mm]
Für n>2 gilt: [mm] a_n=2*a_{n-1}+1*a_{n-2}-2*a_{n-3}
[/mm]
So besser?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:16 Mi 30.01.2013 | | Autor: | locke123 |
> Hallo locke123,
>
> negative Indices (auch: Indizes; beides mit langem "e"
> gesprochen, aber Betonung auf der ersten Silbe) sind
> absolut unüblich. Von daher ist Deine Verwirrung
> verständlich. Glücklicherweise kann man ihr leicht
> abhelfen.
>
> > Gegeben sei die linear homogene Rekursionsfolge
> > [mm]x_{n}=2x_{n-1}+x_{n-2}-2x_{n-3}[/mm] für [mm]n\ge1,[/mm] wobei [mm]x_{-2}=0, x_{-1}=1, x_{0}=2[/mm]
> > ist. Finden Sie eine geschlossene Formel für das
> > Folgenglied [mm]x_{n}.[/mm]
> > Hallo Leute ich brauch eure Hilfe um die Aufgabe zu
> > verstehen,
> >
> > ich komme irgendwie mit den negativen Indizies nicht klar.
> > Und zwar hatten wir dies zwar in der Vorlesung/Tutorium,
> > aber nur mit positiven Indizies und nun komm ich ziemlich
> > durcheinander.
> >
> > Wir hatten lineare Rekursion so aufgeschrieben:
> >
> > Sei [mm]x_{n}=c_{1}x_{n-1}+...+c_{k}x_{n-k}[/mm] eine rekursive
> > Folge, wobei [mm]x_{1},...,x_{k}[/mm] bekannt.
> >
> > Ich komme hier irgendwie nicht auf die c's
>
> Aber die stehen doch schon da!
Stimmt, schnell getippt
>
> > und nicht auf
> > die x's um die Nullstellen zu berechnen, die negativen
> > Indizies bringen mich wie gesagt irgendwie durcheinander,
> > kann mir da jemand einen Tipp geben?
>
> Wir definieren eine andere Folge [mm]a_n[/mm] mit [mm]a_n=x_{n-2}.[/mm]
Leider vesteh ich diesen Schritt nicht wirklich, ist auch ziemlich das erste mal, dass wir/ich mit Folgen konfrontiert werden. Klar in der Analysis werden die noch eine größere Rolle spielen, aber hab ich erst nächstes Semester.
>
> Es ist also [mm]a_0=0, a_1=1, a_2=2.[/mm]
>
> Für n>2 gilt: [mm]a_n=2*a_{n-1}+1*a_{n-2}-2*a_{n-3}[/mm]
In der Aufgabe steht, dass ich für n>1 eine geschlossene Formel finden sollte, gilt dass dann trotzdem noch?
>
> So besser?
>
> Grüße
> reverend
>
|
|
|
| |
|
Hallo nochmal,
> > Wir definieren eine andere Folge [mm]a_n[/mm] mit [mm]a_n=x_{n-2}.[/mm]
>
> Leider vesteh ich diesen Schritt nicht wirklich, ist auch
> ziemlich das erste mal, dass wir/ich mit Folgen
> konfrontiert werden. Klar in der Analysis werden die noch
> eine größere Rolle spielen, aber hab ich erst nächstes
> Semester.
Eigentlich habe ich nur den Index verschoben, so dass es keine negativen Indices mehr gibt. Damit man nicht durcheinanderkommt (eine echte Gefahr bei Indexverschiebungen), habe ich der Folge halt noch einen neuen Namen gegeben. Das ist schon alles.
> > Es ist also [mm]a_0=0, a_1=1, a_2=2.[/mm]
> >
> > Für n>2 gilt: [mm]a_n=2*a_{n-1}+1*a_{n-2}-2*a_{n-3}[/mm]
>
> In der Aufgabe steht, dass ich für n>1 eine geschlossene
> Formel finden sollte, gilt dass dann trotzdem noch?
Nein, Du solltest für [mm] n\blue{\ge}1 [/mm] eine geschlossene Formel finden.
Jetzt natürlich für [mm] n\ge{3}, [/mm] weil wir ja die ganze Folge sozusagen um zwei Glieder nach rechts verschoben haben. Ich schrieb vorher "n>2", was aber in den natürlichen Zahlen das gleiche ist...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:14 Do 31.01.2013 | | Autor: | kaju35 |
Hallo Locke123,
hattet ihr in der Vorlesung schon die Formel von
Moivre-Binet? Sie läuft darauf hinaus, die
Rekursionsfolge in ein Eigenwertproblem
umzuwandeln.
Zuerst erstellen wir die Ausgangsmatrix
[mm] $A:=\left(
\begin{array}{ccc}
0&1&0 \\
0&0&1 \\
-2&1&2
\end{array}
\right)$
[/mm]
Davon wird das charakteristische Polynom = [mm] $t^3-2t^2-t+2$ [/mm]
bestimmt. Es ist sofort ersichtlich, dass 1 ein Eigenwert
ist. Durch Polynomdivision herausdividiertes (t-1) ergibt eine
quadratische Gleichung, deren Lösungen (mit p,q-Formel
berechnet) 2 und -1 sind.
Nun diagonalisieren wir A :
[mm] $D:=\left(
\begin{array}{ccc}
1^n&0&0 \\
0&2^n&0 \\
0&0&(-1)^n
\end{array}
\right)$
[/mm]
ist die Eigenwert-Matrix.
Als nächstes stellen wir die Eigenraum-Matrix auf,
indem wir die Eigenvektoren als Spaltenvektoren
von V schreiben. Dann ist [mm] $A^n=V\circ D^n\circ V^{-1}$
[/mm]
Es ergibt sich eine 3x3-Matrix, für die gilt :
[mm] $A^n\circ \left(
\begin{array}{c}
x_{-2}\\
x_{-1}\\
x_{0}
\end{array}
\right)=\left(
\begin{array}{c}
x_{n-2}\\
x_{n-1}\\
x_{n}
\end{array}
\right)$
[/mm]
Wir sollen ja [mm] $x_n$ [/mm] in geschlossener Form angeben.
Dazu bilden wir das Skalarprodukt des ersten
Zeilenvektors von [mm] $A^n$ [/mm] mit [mm] $\left(
\begin{array}{c}
x_{-2}\\
x_{-1}\\
x_{0}
\end{array}
\right)=\alpha_{1,2}+2\alpha_{1,3}$
[/mm]
Das Ergebnis sollte [mm] $-\frac{1}{2}+\frac{2}{3}2^n-\frac{1}{6}(-1)^n [/mm] $ lauten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:45 Do 31.01.2013 | | Autor: | kaju35 |
Hallo,
$ [mm] -\frac{1}{2}+\frac{2}{3}2^n-\frac{1}{6}(-1)^n [/mm] $
ist zwar richtig, aber nur, wenn der Index um -2 verschoben
ist. Die richtige Version erhältst Du, wenn Du nicht den ersten
sondern den dritten Zeilenvektor von [mm] $A^n$ [/mm] mit
[mm] $\left( \begin{array}{c} x_{-2}\\ x_{-1}\\ x_{0} \end{array} \right)$ [/mm] multiplizierst.
Die Funktion für [mm] $x_n$ [/mm] lautet dann : [mm] -\frac{1}{2}+\frac{8}{3}2^n-\frac{1}{6}(-1)^n
[/mm]
Worauf Du aber auch einfach kommst, wenn Du in der oberen
Funktion [mm] $2^n$ [/mm] durch [mm] $2^{n+2}$ [/mm] ersetzt (Beachte : [mm] $(-1)^{n+2}=(-1)^n$).
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:45 Sa 02.02.2013 | | Autor: | kaju35 |
Hallo locke123 und reverend,
es tut mir leid, wenn ich mit meinem Artikel jemanden
überfordert haben sollte. Wie habt ihr das gemacht?
An einem alternativen Lösungsweg bin ich sehr
interessiert.
Gruß
Kai
|
|
|
|
