infostudium.de

von **CrazyPumuckl** » 18.02.07 17:11

Hi,

hat sich schon jemand mit den rekursiven Funktionen, die als explizite Formeln ausgedrückt werden sollen, beschäftigt? Habe mir einige aus den Klausuren angeguckt, sind auch ganz verständlich. Nur die Aufgabe von Blatt 6 bekomme ich nicht gelößt. Kann jemand weiterhelfen?

Danke.

$f(n+2) = 3f(n) + 2f(n-1) - 9*2^n$

$AW: f(0) = f(1) = f(2) = 0$

von **SpatzenArsch** » 18.02.07 17:26

Warum ist f(2) = 0 gegeben? Wenn ich für n=0 einsetze, dann bekomme ich doch $f(0+2) = 3*0+2*0-9*2^0=-9$

von **Martin** » 18.02.07 17:37

SpatzenArsch hat geschrieben:Warum ist f(2) = 0 gegeben? Wenn ich für n=0 einsetze, dann bekomme ich doch $f(0+2) = 3*0+2*0-9*2^0=-9$

Sicher? Wie ist $f(-1)$ denn definiert?

Unabhängig davon ist es doch egal, solange in der Aufgabenstellungen steht, dass $f(2) = 0$ , dann gilt die Funktion halt erst für $n > 2$ .

von **Teq** » 18.02.07 19:02

Also was meinen die denn mit "geschlossene Formel"?

Soll man die Aufgabe so ähnlich lösen, wie auf diesem Blatt zur
"Linearen Rekursion mit Inhomogenitäten" ?
Das sieht ja sehr ähnlich aus...
(http://www.math2.rwth-aachen.de/~uebung/DISSTR/loesungrekursion.pdf)

von **CrazyPumuckl** » 18.02.07 19:35

ja, das ist das. die $-9\cdot2^n$ machen mir probleme. ich glaube das liegt daran, dass 2 eine nullstelle ist vom charakteristischen polynom. hat viell. jemand die in der kgü vorgerechnet bekommen? dann könnte er ja die lösung mal posten :-)

Thx.

von **maddinac** » 18.02.07 19:41

dadurch, dass die 2 ne nullstelle ist musst du lediglich nen anderen ansatz wählen.
--> fp(n) = n*c*a^n

in dem fall also fp(n) = -9*n*c*2^n

und der rest läuft wie wenn es keine ns wäre.

von **CrazyPumuckl** » 19.02.07 14:32

Hm, ich bekomms trotzdem nicht gelößt, weil mein $\delta$ jetzt von n abhängt (also nicht bezgl des Ansatzes, sondern wenn ich nachher $\delta$ bestimmen möchte)

Ich habe folgenden Ansatz gewählt:

$f_h(n)=(\alpha+\beta n)(-1)^n+(\gamma+\delta n)2^n$

Stimmt denn der Ansatz überhaupt?

von **p0llux** » 19.02.07 14:47

Sieht gut aus, aber warum interessiert dich das dein Deta von n abhängt? Wenn du die Anfangswerte um die Gleichungen rauszubekommen, dann bekommste doch auch nur ein Delta raus.

von **CrazyPumuckl** » 19.02.07 14:53

naja, bei allen anderen aufgaben ist es so dass die variablen nicht von n abhängen, sondern nen festen Wert aus $\mathbb{R}$ haben. daher glaube ich dass das so falsch ist wie ich das mache.

von **p0llux** » 19.02.07 15:20

CrazyPumuckl hat geschrieben:naja, bei allen anderen aufgaben ist es so dass die variablen nicht von n abhängen, sondern nen festen Wert aus $\mathbb{R}$ haben. daher glaube ich dass das so falsch ist wie ich das mache.

Ne bloss nicht, aber du solltest auf jeden Fall genug Startwerte haben um die Koeffizienten als "Zahlen" zu ermitteln. (Siehe das Ende von dem tollen Dokument das der Le[e,h]rstuhl dazu auf die noch tollere webseite gestellt hat)

Welchen Grad die Koeffizientenpolynome bei deinem Ansatz für ne Lösung (partiell oder homogen) haben hängt ja wie oben schon gesagt wurde davon ab, ob die Koeffizienten Nullstellen sind und wenn, dann welche Vielfachheit sie haben. Das steht sehr verworren auch mittig in dem PDF vom Lehrstuhl.

Gruß,
Michael.

von **CrazyPumuckl** » 19.02.07 15:50

Waaaaaah

Ja, endlich hab ichs :-)

Das $\delta$ hing tatsächlich nicht von n ab, hatte mich anscheinend verrechnet, denn jetzt hat die das n durch Abwechslung von $+$ und $-$ 'aufgelöst'.

Also, hier die Lösung:
$\delta = -1$

$f(n) = (-\frac{4}{3}+2n)(-1)^n+\frac{4}{3}2^n-n\cdot2^n$

Thx an alle!

von **Teq** » 19.02.07 16:56

Ich hab mal eine Frage zum Ansatz:

CrazyPumuckl hat geschrieben:Ich habe folgenden Ansatz gewählt:

$f_h(n)=(\alpha+\beta n)(-1)^n+(\gamma+\delta n)2^n$

Also mein char. Polynom ist ja $x^3 -3x -2 = (x-2)*(x+1)^2$ .
Demnach hab ich Nullstelle 2 (Vielfachheit 1) und Nullstelle -1 (Vielfachheit 2).
Wenn ich mich dann streng an diese Anleitung von der Website halte, dann sieht mein hom. Polynom so aus:
$f_h(n)=(\alpha+\beta n)(-1)^n+(\gamma)2^n$
(der hintere Teil hat nur Grad 0).

Könntest du auch dein $f_p(n)$ mal explizit posten?
Ich glaub ich mach das noch falsch, der Koeffizientenvergleich klappt nie..
Meins war $f_p(n) = \delta_1 * n * 2^n$ ...

von kb » 19.02.07 17:04

Die Lösung ist korrekt =]

btw, weiß jemand, wie genau der Triesch die einzelnen Schritte verlangt? Also muss da hingeschrieben werden "blabla aufteilen in homogenen und inhomogenen Teil.....ansatz...charakteristisches polynom bilden....nullstellen berechnen....ansatz für inhomogenen teil....X ist nullstelle, darum neuer grad=max(,,)...."? =)

von **CrazyPumuckl** » 19.02.07 17:08

wahrscheinlich haste das geliche problem wie ich gehabt, weil dieses -9*2^n ja -9*(Nullstelle)^n ist, da geht der Koeffizientenvergleich immer in die Hose.

f_p(n) = delta*n*2^n

=> für delta:

delta*(n+2)*2^(n+2) = 3*delta*n*2^n + 2*delta*(n-1)*2^(n-1) - 9*2^n

=> delta = -1.

Ach ja, was ich als f_h(n) bezeichnet habe ist falsch, das heißt eigentlich nur f(n) - sorry :-)

von kb » 19.02.07 17:19

also wenn du das streng nach der Anleitung machst, musst du folgende Schritte durchgehen:

inhomogener Teil: ${-9}*2^n$ ist von Grad 0 ( ${-9}*n^0*2^n$ )
Also Ansatz: . $f_p(n)=\delta (-9*2^n)$
Weil 2 jedoch Nullstelle im Homogenen Teil ist, musst du den Grad neu berechnen. Jetztige Grad ist 0, NS 2 hat Vielfachheit 1 => Grad = max(0+1, 1)
Also neuer Ansatz: $f_p(n)=(\delta_1 n + \delta_2)(-9*2^n)$
Das entsprechende Polynom im Homogenen Teil ( $\gamma$ ) hat Grad 0, also kannst du $\delta_2$ weglassen.
=> $f_p = \delta n(-9*2^n) = -9 \delta n2^n$
Das dann in die Rekursion eingesetzt ergibt $\delta = \frac{1}{9}$ und somit $f_p(n) = -n2^n$

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] 6. Übung, Aufgabe 2b (2) - Rekursive Funktionen

6. Übung, Aufgabe 2b (2) - Rekursive Funktionen