Fibonacci mit LA lösen < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:39 Do 01.11.2018 | | Autor: | Hela123 |
| Aufgabe | Diese Aufgabe zeigt ein Verfahren zum Lösen (komplizierterer) Rekursionsgleichungen mit Methoden der Linearen Algebra. Betrachten Sie die folgende Rekursionsgleichung:
[mm] f_n=f_{n-1}+f_{n-2} [/mm] mit [mm] f_0=f_1=1
[/mm]
(a) Finden Sie eine geeignete Matrix [mm]A \in \IR_{2 \times 2}[/mm] sodass:
[mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = A \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}[/mm]
(b) Beweisen Sie [mm]f_n=(1,0)A^{n-1} \begin{pmatrix} f_0 \\ f_1 \end{pmatrix} [/mm] für [mm]n \ge 1[/mm] mittels vollständiger Induktion.
(c) Berechnen Sie eine Diagonalisierung von A, d.h. berechnen Sie die Matrix [mm] S \in \IR_{2 \times 2}[/mm] und ihre Inverse [mm] S^{-1} [/mm] sodass [mm]D=S^{-1}AS[/mm] eine Diagonalmatrix mit den Eigenwerten von A auf der Diagonale ist.
(d) Leiten Sie eine geschlossene Form für [mm] f_n [/mm] her. |
Hallo Forum,
ich komme mit der Aufgabe leider nicht ganz zurecht.
Hier ist mein Ansatz:
(a) [mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = A \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}[/mm]
[mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = \begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}[/mm]
Also:
[mm]A= \begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}[/mm]
Soweit klar.
(b) Hier verstehe ich schon die Aufgabenstellung nicht. Was bedeutet (1,0)?
Wie kann ich hier mit dem beweis beginnen?
(c)(d) mache ich, wenn ich bei (b) weitergekommen bin %)
Schönen Dank im Voraus und viele Grüße
Hela123
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:57 Do 01.11.2018 | | Autor: | fred97 |
> Diese Aufgabe zeigt ein Verfahren zum Lösen
> (komplizierterer) Rekursionsgleichungen mit Methoden der
> Linearen Algebra. Betrachten Sie die folgende
> Rekursionsgleichung:
> [mm]f_n=f_{n-1}+f_{n-2}[/mm] mit [mm]f_0=f_1=1[/mm]
>
> (a) Finden Sie eine geeignete Matrix [mm]A \in \IR_{2 \times 2}[/mm]
> sodass:
> [mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = A \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}[/mm]
>
> (b) Beweisen Sie [mm]f_n=(1,0)A^{n-1} \begin{pmatrix} f_0 \\ f_1 \end{pmatrix}[/mm]
> für [mm]n \ge 1[/mm] mittels vollständiger Induktion.
>
> (c) Berechnen Sie eine Diagonalisierung von A, d.h.
> berechnen Sie die Matrix [mm]S \in \IR_{2 \times 2}[/mm] und ihre
> Inverse [mm]S^{-1}[/mm] sodass [mm]D=S^{-1}AS[/mm] eine Diagonalmatrix mit
> den Eigenwerten von A auf der Diagonale ist.
>
> (d) Leiten Sie eine geschlossene Form für [mm]f_n[/mm] her.
>
> Hallo Forum,
>
> ich komme mit der Aufgabe leider nicht ganz zurecht.
> Hier ist mein Ansatz:
>
> (a) [mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = A \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}[/mm]
>
> [mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = \begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}[/mm]
>
> Also:
>
> [mm]A= \begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}[/mm]
>
> Soweit klar.
>
> (b) Hier verstehe ich schon die Aufgabenstellung nicht. Was
> bedeutet (1,0)?
(1,0) ist ein Zeilenvektor. Der wird multipliziert mit einem Spaltenvektor
> Wie kann ich hier mit dem beweis beginnen?
Wie Du das immer bei Induktion machst.
>
> (c)(d) mache ich, wenn ich bei (b) weitergekommen bin %)
>
> Schönen Dank im Voraus und viele Grüße
> Hela123
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:17 Do 01.11.2018 | | Autor: | Hela123 |
Hallo fred97,
schönen Dank für deine schnelle und hilfreiche Antwort!
Also:
(b)
IA: n=1
[mm]f_1=(1,0) A^0 \begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm]
[mm] =(1,0) \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm]
[mm] =(1,0) \begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm]
[mm] =(f_1) [/mm]
Also erfüllt.
IV: [mm]f_n=(1,0)A^{n-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
IS: n->n+1
[mm]f_{n+1}=(1,0)A^{n}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
[mm] =(1,0)A^{n-1}A\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
[mm] =f_n A[/mm]
Ist es damit bewiesen?
Jetzt zur Teilaufgabe (c):
Hier musst du (oder jemand anders) leider auch auf die Sprünge helfen.
Was bedeutet "Diagonalmatrix mit den Eigenwerten von A auf der Diagonale"?
Schönen Dank im Voraus!
Hela123
|
|
|
| |
|
> Hallo fred97,
>
> schönen Dank für deine schnelle und hilfreiche Antwort!
>
> Also:
>
> (b)
>
> IA: n=1
> [mm]f_1=(1,0) A^0 \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
>
> [mm]=(1,0) \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
>
> [mm]=(1,0) \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
>
> [mm]=(f_1)[/mm]
>
> Also erfüllt.
>
> IV: [mm]f_n=(1,0)A^{n-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
>
> IS: n->n+1
>
> [mm]f_{n+1}=(1,0)A^{n}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
>
> [mm]=(1,0)A^{n-1}A\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
Das Letzte hast du einfach nur so ohne genaue Überlegung hingeschrieben. Du musst A und [mm] A^{n-1} [/mm] genau anders herum aufschreiben:
...[mm]=(1,0)AA^{n-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=(1,0)A\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}=(1,0)\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}[/mm][mm] =f_{n+1}
[/mm]
>
> [mm]=f_n A[/mm]
Hier stimmt auch die Schreibweise nicht.
>
> Ist es damit bewiesen?
Jetzt ja.
>
> Jetzt zur Teilaufgabe (c):
> Hier musst du (oder jemand anders) leider auch auf die
> Sprünge helfen.
> Was bedeutet "Diagonalmatrix mit den Eigenwerten von A auf
> der Diagonale"?
Jetzt wird es etwas schwierig.
Nennen wir mal [mm] e_1 [/mm] und [mm] e_2 [/mm] die Eigenwerte von A. Dann sollst du eine 2x2-Matrix S finden, so dass gilt:
D = [mm] \begin{pmatrix} e_1 & 0 \\ 0 & e_2 \end{pmatrix}=S^{-1} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} [/mm] S
Damit kann man dann die Berechnung von [mm] A^n [/mm] so vereinfachen, dass man nicht n Matrizenmultiplikationen durchführen muss, um [mm] f_n [/mm] zu ermitteln. Wieso?
Es gilt ja dann A = S D [mm] S^{-1} [/mm] und damit [mm] A^n [/mm] = (S D [mm] S^{-1})(S [/mm] D [mm] S^{-1})(S [/mm] D [mm] S^{-1})...(S [/mm] D [mm] S^{-1}) [/mm] (n-mal) =S D [mm] (S^{-1}S) [/mm] D [mm] (S^{-1}S) D(S^{-1}S) [/mm] D [mm] ...(S^{-1}S) [/mm] D [mm] S^{-1}=S D^n S^{-1}.
[/mm]
Die Vereinfachung besteht nun darin, dass [mm] D^n=\begin{pmatrix} e_1^n & 0 \\ 0 & e_2^n \end{pmatrix} [/mm] ist und sofort hingeschrieben werden kann. Und damit erhältst du
[mm] f_{n+1}=(1,0)S D^{n}S^{-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}
[/mm]
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:01 Sa 03.11.2018 | | Autor: | Hela123 |
Hallo HJKweseleit,
vielen Dank für deine Antwort!
Ich habe noch ein paar Fragen dazu:
> Das Letzte hast du einfach nur so ohne genaue Überlegung
> hingeschrieben. Du musst A und [mm]A^{n-1}[/mm] genau anders herum
> aufschreiben:
>
> ...[mm]=(1,0)AA^{n-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=(1,0)A\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}=(1,0)\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}[/mm][mm] =f_{n+1}[/mm]
Könntest du mir die Schritte etwas genauer erklären? Am besten alle (tut mir leid!)? Ich verstehe die Übergänge wirklich nicht...
> > Jetzt zur Teilaufgabe (c):
> > Hier musst du (oder jemand anders) leider auch auf die
> > Sprünge helfen.
> > Was bedeutet "Diagonalmatrix mit den Eigenwerten von A
> auf
> > der Diagonale"?
>
>
>
> Jetzt wird es etwas schwierig.
>
> Nennen wir mal [mm]e_1[/mm] und [mm]e_2[/mm] die Eigenwerte von A.
>
> Dann sollst du eine 2x2-Matrix S finden, so dass gilt:
>
> D = [mm]\begin{pmatrix} e_1 & 0 \\ 0 & e_2 \end{pmatrix}=S^{-1} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}[/mm]
> S
>
> Damit kann man dann die Berechnung von [mm]A^n[/mm] so vereinfachen,
> dass man nicht n Matrizenmultiplikationen durchführen
> muss, um [mm]f_n[/mm] zu ermitteln. Wieso?
>
> Es gilt ja dann A = S D [mm]S^{-1}[/mm] und damit [mm]A^n[/mm] = (S D
> [mm]S^{-1})(S[/mm] D [mm]S^{-1})(S[/mm] D [mm]S^{-1})...(S[/mm] D [mm]S^{-1})[/mm] (n-mal) =S D
> [mm](S^{-1}S)[/mm] D [mm](S^{-1}S) D(S^{-1}S)[/mm] D [mm]...(S^{-1}S)[/mm] D [mm]S^{-1}=S D^n S^{-1}.[/mm]
>
> Die Vereinfachung besteht nun darin, dass
> [mm]D^n=\begin{pmatrix} e_1^n & 0 \\ 0 & e_2^n \end{pmatrix}[/mm]
> ist und sofort hingeschrieben werden kann. Und damit
> erhältst du
>
> [mm]f_{n+1}=(1,0)S D^{n}S^{-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
Hier musste ich einen größeren Ausflug in die Lineare Algebra unternehmen, aber jetzt weiß ich, was ich zu tun habe, danke!
Noch mal danke und viele Grüße
Hela123
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:06 So 04.11.2018 | | Autor: | Hela123 |
Nachtrag:
> > ...[mm]=(1,0)AA^{n-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=(1,0)A\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}=(1,0)\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}[/mm][mm] =f_{n+1}[/mm]
>
> Könntest du mir die Schritte etwas genauer erklären? Am
> besten alle (tut mir leid!)? Ich verstehe die Übergänge
> wirklich nicht...
>
Also ich verstehe jetzt wieso diese Übergänge funktionieren:
[mm](1,0)A\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}=(1,0)\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}[/mm]
[mm](1,0)\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}[/mm][mm] =f_{n+1}[/mm]
Aber wie wir diesen Schritt machen, verstehe ich immer noch nicht:
[mm](1,0)AA^{n-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=(1,0)A\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}[/mm]
Könntest du mir das erklären?
Danke im Voraus und viele Grüße
Hela123
|
|
|
| |
|
Du sollst doch zeigen, das
$ [mm] f_n=(1,0)A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm] $
gilt.
Das ist übrigens bei b) falsch geschrieben, dort steht [mm] f_n=(1,0)A^{n-1} \begin{pmatrix} \red{f_0} \\ \red{f_1} \end{pmatrix}, [/mm] aber die Indices stimmen nicht mit denen aus Aufgabe a) überein und passen auch nicht zur gesuchten Matrix A aus a)
Und du hast schon in a) bewiesen, dass $ [mm] \begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} [/mm] = A [mm] \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix} [/mm] $ gilt.
Das letzte benutzt du dann für die VI. Den Induktionsanfang bekommst du mit n=1:
[mm] f_1=(1,0)A^{1-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=(1,0)E \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=(1,0) \begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm] stimmt.
Jetzt setzt du [mm] f_n=(1,0)A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm] voraus.
Dann ist [mm] f_{n+1}=(1,0) \begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}= [/mm] (1,0) A [mm] \begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} [/mm] (nach b))= [mm] (1,0)A(A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix})(nach [/mm] I-Voraussetzung)= [mm] (1,0)A^n \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}
[/mm]
Ich hoffe, es ist jetzt verständlicher.
|
|
|
| |
|
Der Induktionsbeweis muss noch korrigiert werden, weil er unsauber durchgeführt wurde.
> Du sollst doch zeigen, das
>
>
> [mm]f_n=(1,0)A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
>
> gilt.
Durch den Spaltenvektor (1,0) wird eine Zahl aus den Spaltenvektoren erzeugt, was beim Induktionsbeweis stört.
Deshalb beweise ich durch VI nun "nur":
[mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}=A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
ohne den störenden Zeilenvektor (1,0).
IAnfang: n=1 [mm] \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=E \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=A^0 \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}=A^{1-1}\begin{pmatrix} f_1 \\ f_0 \end{pmatrix} [/mm] stimmt.
IVoraussetzung:
[mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}=A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
ISchritt:
[mm]\begin{pmatrix} f_{n+1} \\ f_{n} \end{pmatrix}=
A\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}[/mm](nach a))[mm]=A(A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix})[/mm] (nach Voraussetzung)[mm]=A^n \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
Und jetzt wird erst wieder (1,0) eingebaut:
Somit [mm] f_{n+1}=(1,0)[/mm] [mm]\begin{pmatrix} f_{n+1} \\ f_{n} \end{pmatrix}=(0,1)A^n \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
Der Fehler liegt an Folgendem:
> Jetzt setzt du [mm]f_n=(1,0)A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}[/mm]
> voraus.
>
>
> Dann ist [mm]f_{n+1}=(1,0) \begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}=[/mm]
> (1,0) A [mm]\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix}[/mm] (nach b))
> = [mm](1,0)A(A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix})[/mm]
Die letzte Zeile war nun falsch: Hier will ich die Induktionsvoraussetzung einsetzen, ich ersetze den Vektor [mm] \begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} [/mm] durch Vektor [mm] A^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}, [/mm] aber das ist gar nicht die Induktionsvoraussetzung, denn die bezieht sich nur auf die Zahl [mm] f_n [/mm] und nicht auf einen Vektor.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mi 07.11.2018 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
