Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursive Funktion explizit darstellen

Rekursive Funktion explizit darstellen

Universität / Fachhochschule

angewandte lineare Algebra

Tags: explizite Darstellung, explizite Form, Matrix, Rekursion

anonymous

16:57 Uhr, 06.05.2020

Hallo, ich soll folgende rekursive Funktion:

a_{0} = 1

a_{1} = 1

a_{n + 1} = 4 a_{n} - 4 a_{n - 1}

für

n \geq 1

in eine explizite Form bringen. So weit ich weiß müsste das mit Hilfe einer Matrix gehen, ich weiß allerdings nicht wie das geht.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Funktion (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Matrizen - Determinante und inverse Matrix
Matrizen - Eigenwerte und Eigenvektoren

HAL9000

18:42 Uhr, 06.05.2020

Die charakteristische Gleichung

λ^{2} - 4 λ + 4 = 0

dieser Linearen Differenzengleichung hat die doppelte Nullstelle 2. Damit hat die explizite Formel die Gestalt

a_{n} = (A n + B) \cdot 2^{n}

mit Konstanten

A, B

, welche aus den Anfangsbedingungen ermittelbar sind.

anonymous

18:54 Uhr, 06.05.2020

Wie kommst du auf diese Formel?

HAL9000

18:56 Uhr, 06.05.2020

Ja wenn du rätst statt zu rechnen, kann auch nix gescheites rauskommen. :(

n=0:

a_{0} = 1 = (A \cdot 0 + B) \cdot 2^{0} = B

n=1:

a_{1} = 1 = (A \cdot 1 + B) \cdot 2^{1} = 2 A + 2 B

Das ist das Gleichungssystem, welches NICHT die Lösungen hast, die du da ... was weiß ich, wo du die her hast.

anonymous

18:57 Uhr, 06.05.2020

ja ich hatte eben meinen rechenfehler gefunden sorry!

michaL aktiv_icon

19:01 Uhr, 06.05.2020

Hallo,

wegen der Matrix frage ich mal zurück:
Habt ihr schon die Jordansche Normalform gehabt? (Wie HAL9000 schon schrieb, hat das char. Polynom nur eine Nullstelle. Das führt dazu, dass die "Matrix" nicht diagonalisierbar ist.)

Mfg Michael

anonymous

19:01 Uhr, 06.05.2020

von wo hast du diese formel?

anonymous

19:02 Uhr, 06.05.2020

Ja die Jordansche Normalform hatten wir schon

HAL9000

19:05 Uhr, 06.05.2020

Ja man kann die Rekursion einbetten in eine Vektorgleichung

v_{n} = T \cdot v_{n - 1}

mit

v_{n} = (\begin{array}{c} a_{n} \\ a_{n + 1} \end{array})

sowie passender 2x2-Matrix

T

. Deren Lösung ist dann

v_{n} = T^{n} \cdot v_{0}

Aber das war mir zuviel Schreibarbeit, da es mit der Theorie der oben schon genannten "Linearen Differenzengleichungen" ja auch geht. Den Weg über die Matrixpotenz wird dir dann sicher michaL erläutern. ;-)

anonymous

19:06 Uhr, 06.05.2020

Vielen Dank

michaL aktiv_icon

19:41 Uhr, 06.05.2020

Hallo,

HAL9000 deutet den Weg ja schon an.
Kannst du die Gleichung

a_{n + 1} = 4 a_{n} - 4 a_{n - 1}

(*)
als Matrixgleichung der Art

(\begin{array}{c} a_{n + 1} \\ a_{n} \end{array}) = (\begin{array}{cc} p & q \\ r & s \end{array}) \cdot (\begin{array}{c} a_{n} \\ a_{n - 1} \end{array})

schreiben?

Wenn du nicht weißt, wie das gehen kann, dann setze für

a_{n + 1}

gemäß (*) ein.

Vielleicht hilft es dir, wenn du die Ersetzung

a_{n} \to x

und

a_{n - 1} \to y

vornimmst?!

Zu bestimmen wären die Zahlen

p

q

r

und

s

.

Mfg Michael

anonymous

19:46 Uhr, 06.05.2020

ich kann es ja einfach mal einsetzen für

a_{0}, a_{1}, a_{2}, a_{3}

oder?

(\begin{matrix} p & q \\ r & s \end{matrix}) \cdot (\begin{matrix} 1 \\ 1 \end{matrix}) = (\begin{matrix} 0 \\ - 4 \end{matrix})

und

(\begin{matrix} p & q \\ r & s \end{matrix}) \cdot (\begin{matrix} 0 \\ - 4 \end{matrix}) = (\begin{matrix} - 4 \\ - 16 \end{matrix})

und wir erhalten

p = - 1, q = 1, r = - 8, s = 4

michaL aktiv_icon

19:56 Uhr, 06.05.2020

Hallo,

> ich kann es ja einfach mal einsetzen für a0,a1,a2,a3 oder?

Nö. Lies dir meinen Beitrag genau durch und führe die Ersetzung(en) durch.

Mfg Michael

anonymous

20:10 Uhr, 06.05.2020

Hm sorry, ich verstehe das nicht so ganz.

also wenn ich das mal ausmultipliziere komme ich auf

(\begin{matrix} p \cdot a_{n} + q \cdot a_{n - 1} \\ r \cdot a_{n} + s \cdot a_{n - 1} \end{matrix}) = (\begin{matrix} a_{n + 1} \\ a_{n} \end{matrix})

wäre das schon einmal ein Ansatz?

michaL aktiv_icon

20:15 Uhr, 06.05.2020

Hallo,

> ich verstehe das nicht so ganz.

Merke ich schon.

Der Anfang ist schon ganz gut.

Jetzt folgendes:
>> Wenn du nicht weißt, wie das gehen kann, dann setze für an+1 gemäß (*) ein.
>>
>> Vielleicht hilft es dir, wenn du die Ersetzung an→x und an−1→y vornimmst?!

Mfg Michael

anonymous

20:28 Uhr, 06.05.2020

so komme ich auf

(\begin{matrix} p \cdot x + q \cdot y \\ r \cdot x + s \cdot y \end{matrix}) = (\begin{matrix} 4 \cdot (x - y) \\ x \end{matrix})

stimmt das soweit?

michaL aktiv_icon

20:32 Uhr, 06.05.2020

Hallo,

korrekt.
Kannst du daraus die Werte für

p

q

r

und

s

berechnen?

Mfg Michael

anonymous

20:35 Uhr, 06.05.2020

Ja, wenn

p \cdot x + q \cdot y = 4 \cdot x - 4 \cdot y,

dann ist

p = 4, q = - 4

r \cdot x + q \cdot y = x,

dann ist

r = 1

und

s = 0

anonymous

20:39 Uhr, 06.05.2020

in der letzten Zeile sollte

s

anstatt

q

stehen^

michaL aktiv_icon

21:31 Uhr, 06.05.2020

Hallo,

so...

Dann hätten wir also:

(\begin{array}{c} a_{n + 1} \\ a_{n} \end{array}) = (\begin{array}{cc} 4 & - 4 \\ 1 & 0 \end{array}) \cdot (\begin{array}{c} a_{n} \\ a_{n - 1} \end{array})

Wir kürzen mal

A := (\begin{array}{cc} 4 & - 4 \\ 1 & 0 \end{array})

ab.

Berechne mal
*

χ_{A} (x)

* die Eigenwerte von

A

Untersuche, ob
*

χ_{A}

über

ℝ

(in Linearfaktoren) zerfällt
*

A

diagonlisierbar ist
* ggfs. die Jordansche Normalform von

A

und eine Jordanbasis dazu

Mfg Michael

anonymous

08:26 Uhr, 07.05.2020

Die Matrix ist nicht diagonalisierbar und ich komme auf folgende Jordansche Normalform

(\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix})

Wie geht es jetzt weiter?

HAL9000

10:02 Uhr, 07.05.2020

Ok, du hast die Jordan-Matrix

J = (\begin{array}{cc} 2 & 1 \\ 0 & 2 \end{array})

sowie eine dazu passende 2x2-Transformationsmatrix

U

bestimmt, so dass

A = U J U^{- 1}

gilt. Damit ist dann

A^{n} = U J^{n} U^{- 1}

, und das weitere kommt jetzt drauf an, ob du bereits weißt, wie man die Potenz

J^{n}

einer solchen Jordan-Matrix berechnet?

Wenn nicht, schlag es nach - zur Not könnte man auch das sich noch erarbeiten (aber da kommen wir dann langsam vom Hundertsten ins Tausendste).

anonymous

10:10 Uhr, 07.05.2020

Ja ich weiß, wie man die Potenz berechnet

HAL9000

10:12 Uhr, 07.05.2020

Na dann hast du ja alles beisammen - leg los: Berechne

J^{n}

, und damit dann

A^{n} = U J^{n} U^{- 1}

anonymous

10:43 Uhr, 07.05.2020

Also

J^{n}

{(\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix})}^{n} = (\begin{matrix} 2^{n} & \frac{2^{n} \cdot n}{2} \\ 0 & 2^{n} \end{matrix})

und

A^{n}

(\begin{matrix} 2^{n} \cdot 2^{n} \cdot n & - 2 \cdot 2^{n} \cdot n \\ \frac{2^{n} \cdot n}{2} & 2^{n} \cdot 2^{n} \cdot n \end{matrix})

stimmt das so?

HAL9000

10:49 Uhr, 07.05.2020

Kommt mir so vor, also wäre in der Matrix öfter mal ein

\cdot

gelandet, wo EIGENTLICH ein + oder - hingehört. Bisschen mehr Konzentration, bitte!

anonymous

10:56 Uhr, 07.05.2020

achso ja für A habe ich mich vertippt:

A = (\begin{matrix} 2^{n} + 2^{n} \cdot n & - 2 \cdot 2^{n} \cdot n \\ \frac{2^{n} \cdot n}{2} & 2^{n} - 2^{n} \cdot n \end{matrix})

HAL9000

12:16 Uhr, 07.05.2020

So, jetzt fehlt zur Ermittlung der expliziten

a_{n}

-Formel nur noch ein Schritt: Welcher?

anonymous

12:22 Uhr, 07.05.2020

Ich bin mir nicht sicher aber man könnte das charakteristische Polynom von allem berechnen?

HAL9000

12:28 Uhr, 07.05.2020

Da denkst du jetzt viel zu kompliziert, mit der Sache sind wir doch lange durch. Wir müssen einfach mal weit zurückblicken, was der Ausgangspunkt der ganzen Matrixgeschichte war:

Wir haben da

(\begin{array}{l} a_{n + 1} \\ a_{n} \end{array}) = A \cdot (\begin{array}{l} a_{n} \\ a_{n - 1} \end{array})

, und damit per Induktion

(\begin{array}{l} a_{n + 1} \\ a_{n} \end{array}) = A^{n} \cdot (\begin{array}{l} a_{1} \\ a_{0} \end{array})

.

Du musst also lediglich noch Anfangsvektor

(\begin{array}{l} a_{1} \\ a_{0} \end{array}) = (\begin{array}{l} 1 \\ 1 \end{array})

rechts an die Matrix

A^{n}

dranmultiplizieren und erhältst

(\begin{array}{l} a_{n + 1} \\ a_{n} \end{array})

, und das ist ja letztlich das gesuchte!

anonymous

12:36 Uhr, 07.05.2020

ok so komme ich auf

(\begin{matrix} a_{n + 1} \\ a_{n} \end{matrix}) = (\begin{matrix} 2^{n} - 2^{n} \cdot n \\ \frac{2 \cdot 2^{n} - 2^{n} \cdot n}{2} \end{matrix})

HAL9000

12:43 Uhr, 07.05.2020

Also letztlich

a_{n} = (2 - n) \cdot 2^{n - 1}

, was wir oben auch schon hatten. Aber wenn die Abkürzung über die Differenzengleichungen verpönt ist, dann muss man eben auf die Ochsentour. :-)

anonymous

12:45 Uhr, 07.05.2020

Ok vielen Dank!

anonymous

12:45 Uhr, 07.05.2020

Ok vielen Dank!

michaL aktiv_icon

12:54 Uhr, 07.05.2020

Hallo miteinander,

na also, HAL9000.
Das konntest du doch auch erklären... :-)

Mfg Michael

HAL9000

13:01 Uhr, 07.05.2020

Ja, der Inhalt war von Anfang an kein Problem, eher der oben gerade erwähnte "Ochsentour"-Charakter. :-)

Aber es hätte schlimmer kommen können, wenn nämlich auch noch die Berechnung von

J^{n}

hätte erklärt werden müssen - was ich schon befürchtet hatte...

michaL aktiv_icon

13:40 Uhr, 07.05.2020

Hallo,

> der Inhalt war von Anfang an kein Problem

Deswegen der Smiley.

> wenn nämlich auch noch die Berechnung von

J^{n}

hätte erklärt werden müssen

Tja, da muss man TinaMoe schon loben. Da hatte ich auch Befürchtungen. Das ging dann aber - mal abgesehen von kleineren Fehlern echt schnell. So schnell, dass ich nicht mal Zeit hatte, mir das live anzugucken. :-)

Mfg Michael

1501748

1501602

	Status: nicht eingeloggt	Noch nicht registriert?