infostudium.de

von **Teq** » 19.02.07 17:28

kb hat geschrieben: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$

Ja exakt, habs genauso gemacht.
Dann Koeff.-vergleich:
$\delta (n+2) 2^{n+2} = 3 \delta n 2^n + 2 \delta (n-1) 2^{n-1} - 9n 2^n$

$4\delta(n+2)2^n = 3\delta n2^n + \delta (n-1) 2^n - 9n 2^n$

$4 \delta (n+2) = 3 \delta n + \delta (n-1) - 9n$

$4 \delta n + 8 \delta - 3 \delta n - \delta n + \delta + 9n = 0$

$0 \delta n + 9 \delta + 9n = 0$

$9*( \delta + n ) = 0$

Absturz...mir fehlt ein n am delta zum ausklammern.
Dann hätte ich ja auch -1 raus.

Aber danke auf jeden Fall, da der Rest ja richtig zu sein scheint, definier ich mir $\delta = -1$

von **CrazyPumuckl** » 19.02.07 17:41

wenn ich heute abend zeit haben sollte, tex ich de komplette lösung mal hier rein - hab aber leider nicht viel erfahrung mit latex, daher ist das für mich sehr aufwendig. mal sehen was sich ergibt... (falls es noch bedarf gibt)

von kb » 19.02.07 17:47

also da machst du was falsch. wenn du da das so wie ich hast, lautet die Formel nach Einsetzen in Rekursion:
${-9}\delta (n+2)2^{n+2} = {-9}\delta (3n2^n + 2(n-1)2^{n-1}) -9*2^n$
ganz wichtig, am Ende kommt ${-9}*2^n$ und nicht ${-9}n*2^n$ ! Da lag wahrscheinilch dein Fehler.

Wenn du das nun weiterrechnest, erhälst du $\delta = \frac{1}{9}$ und somit $f_p(n) = -n2^n$ .

Allerdings hast du auch nicht meinen Ansatz mit -9.. gewählt, sondern ohne die -9. (also $f_p(n)=\delta n2^n$ . Damit gehts auch, und du erhälst $\delta = -1$ und somit ebenfalls $f_p(n) = -n2^n$ .
Du darfst eben nicht den o.g. Fehler machen und inhomogenen Teil der "original-Rekursion" falsch hinschreiben ;]

--edit--
btw ist es eigentlich völlig blödsinnig, die "-9" mitzunehmen.
${-9}*2^n = (-9*n^0)*2^n$ und somit braucht mans nicht vors Delta. Hab mich heute erst damit beschäftigt, und das grad erst gesehen. Also deine Rechnung oben ist wie gesagt korrekt teq, und wenn du statt "9n" einfach "9" hinschreibst, bekommst du auch die -1 fürs Delta ;]

von **Teq** » 19.02.07 17:58

Hm, ja Tatsache, das ist es wohl!
Danke

von **der-cain** » 22.02.07 17:50

CrazyPumuckl hat geschrieben:wenn ich heute abend zeit haben sollte, tex ich de komplette lösung mal hier rein - hab aber leider nicht viel erfahrung mit latex, daher ist das für mich sehr aufwendig. mal sehen was sich ergibt... (falls es noch bedarf gibt)

*bedarf anmeldet*
ja das wär doch mal was. Ich versteh das noch nicht so ganz mit dem inhomogenen teil. In der Musterlösung der anderen Rekursion (in der gleichen Aufgabe) nimmt man doch auch die 6 nicht mit in die Gleichung mit dem delta??

von kb » 22.02.07 18:31

also hier der inhomogene Teil:

${-9}\cdot 2^n$ ist der inhomogene Teil. Das lässt sich als Polynom vor dem $2^n$ so schreiben: ${-9}\cdot n^0\cdot 2^n$ .
${-9}\cdot n^0$ ist das Polynom, und es hat Grad 0. Also ist dein Ansatz auch eins, mit Grad 0.
Also Ansatz: $f_p(n)=\delta2^n$
2 ist jedoch Nullstelle im Homogenen Teil. Also musst du den Grad neu berechnen. Jetztige Grad ist 0, Nullstelle 2 hat Vielfachheit 1
=> Grad = max(0+1, 1) [ max(Grad+1, Vielfachheit_der_NS) ]

Also neuer Ansatz, mit Polynom vom Grad 1: $f_p(n)=(\delta_1 n + \delta_2)2^n$
Das entsprechende Polynom im Homogenen Teil (das ist das, was vor der $2^n$ steht, also $\gamma$ ) hat Grad 0, also kannst du alle Polynome bis Grad 0 weglassen. Das wäre hier $\delta_2$ .

=> $f_p = \delta n\cdot 2^n$
Das dann in die Rekursion eingesetzen.
Also:
$f_p(n+2) = 3f_p(n) + 2f_p(n-1) -9\cdot 2^n \\<br />\Rightarrow \delta (n+2) 2^{n+2} = 3\delta n2^n + 2\delta (n-1)2^{n-1} - 9\cdot 2^n \\<br />\Leftrightarrow \delta 2^n(4n+8) = \delta 2^n(3n) + \delta 2^n(n-1) - 9\cdot 2^n \\<br />\Leftrightarrow 9 = \delta(-4n - 8 + 3n + n - 1) \\<br />\Leftrightarrow \delta = -1$

Somit hast du dann $f_p(n) = -n2^n$

Hoffe das hat geholfen =] Nun musst du nur noch die Startwerte einsetzen und ausrechnen.

von **der-cain** » 22.02.07 19:32

ja, das ist schon sehr aufschlussreich, nur warum bzw wann kannst du die -9 weglassen und wann muss man die wieder hinzunehmen?

von kb » 22.02.07 20:01

man hat ja im inhomogenen Teil folgende Form:
(ich machs mal wie in der Anleitung beschrieben)
$\sum_{j=0}^{l}p_j(n)\cdot N_j^n$

$p_j(n)$ ist ein Polynom, und N eine natürliche Zahl.
du ersetzt im Grunde nur die Polynome, durch andere Polynome ( $\delta$ usw).

also ${-9}\cdot 2^n$ ist nichts anderes als $(0\cdot n^0)\cdot 1^n + (-9\cdot n^0) \cdot 2^n$
Das zu ersetzende Polynom ist ${-9}\cdot n^0$ . Deshalb fällt die -9 weg. Hinzunehmen musst du die gar nicht mehr, nur wenn du z.B. $f_p(n)$ in die Startrekursion einsetzt, darfst du sie nicht weglassen, weil sie eben zu der Startrekursion dazugehört

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

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