Inhomogene Rekursionsgleichung

12.05.2019, 07:29

Daniel K. M.

Inhomogene Rekursionsgleichung

Gegeben ist die folgende inhomogene Rekursion:

a_1 = 2 und a_(n+1) = a_n + n + 1 für n >= 1

Ich löse zunächst den homogenen Teil der Rekursion (a_(n+1) = a_n) und erhalte:

a_(h,n) = C_1

Für die spezielle inhomogene Lösung mache ich den Ansatz:

a_(s,n) = B_1 * n + B_0

Eingesetzt in die Rekursion liefert das

B_1 * (n + 1) + B_0 = B_1 * n + B_0 + n + 1

B_0 hebt sich auf, B_1 = n + 1

Damit lautet die spezielle inhomogene Lösung

a_(s,n) = (n + 1) * n + B_0

Damit ergibt sich für die Lösung der inhomogenen Rekursion:

a_n = a_(h,n) + a_(s,n) = C_1 + (n + 1) * n + B_0

n = 1: a1 = 2 = C_1 + 1 * 2 + B_0 und damit C_1 + B_0 = 0
n = 2: a2 = 2 + 1 + 1 = 4 = C_1 + 2 * 3 + B_0 und damit C_1 + B_0 = -2

Und das ist ein Widerspruch !

Denkfehler ? Rechenfehler ? Ansatz falsch ?

12.05.2019, 09:28

Daniel K. M.

Auf diesen Beitrag antworten »

Ich habe in der Zwischenzeit die Aufgabe direkt über die erzeugende Funktion gelöst.

Nach einiger mühsamer Rechnung erhält man das charakteristische Polynom p(x) = (1 - x)³

Man hat also eine dreifache Nullstelle für x1 = 1 und damit erhält man ein Gleichungssystem mit 3 Unbekannten. Das ist lösbar und damit kann man die explizite Darstellung der Rekursion angeben:

a_n = 1 + ((n+1) über 2)

Das sieht ja eigentlich gar nicht so schwierig aus !

Wieso also klappt mein obiger Ansatz nicht ? Wie müsste der Ansatz korrekt lauten (und warum) ? Oder ist die Aufgabe nicht über einen Ansatz lösbar ?

12.05.2019, 10:02

Helferlein

Auf diesen Beitrag antworten »

Die Tatsache, dass dein $\begin{eqnarray*} B_1 \end{eqnarray*}$ nicht konstant ist zeigt bereits, dass der Ansatz unzureichend ist.
Mit einem quadratischen Ansatz wärst Du hingekommen.

12.05.2019, 11:40

Daniel K. M.

Auf diesen Beitrag antworten »

ok ... der quadratische Ansatz funktioniert:

a_(s,n) = B_2 * n² + B_1 * n

(Das B_0 habe ich weggelassen, weil es sich in der Rekursion aufhebt).

Damit kriegt man ein sauberes Gleichungssystem ... das sich lösen lässt.

Aber woher weiß ich, dass ich hier "quadratisch" ansetzen muss ?

Bei der Rekursion a_(n+1) = a_n + n funktioniert der "lineare" Ansatz problemlos. Warum also nicht auch bei a_(n+1) = a_n + n + 1 ?

Ist das jetzt Intuition bzw. Erfahrung ... oder steckt da eine Regel dahinter ?

12.05.2019, 12:48

Finn_

Auf diesen Beitrag antworten »

Alternativer Lösungsweg

Setze $\begin{eqnarray*} x_n:=a_n \end{eqnarray*}$ und $\begin{eqnarray*} y_n:=n+1 \end{eqnarray*}$ . Es gilt dann $\begin{eqnarray*} x_{n+1}=x_n+y_n \end{eqnarray*}$ .

Die Folge $\begin{eqnarray*} (y_n) \end{eqnarray*}$ will ich nun in rekursive Form bringen. Es gilt $\begin{eqnarray*} y_{n+1}-y_n=1 \end{eqnarray*}$ und daher $\begin{eqnarray*} y_{n+1}=y_n+1 \end{eqnarray*}$ .

Setze nun $\begin{eqnarray*} z_n:=1 \end{eqnarray*}$ , dann gilt $\begin{eqnarray*} y_{n+1}=y_n+z_n \end{eqnarray*}$ . Durch diesen Trick wird die Addition in Matrizenmultiplikation überführt (homogene Koordinaten).

Insgesamt ergibt sich das homogene lineare System
$\begin{eqnarray*} \begin{pmatrix}x_{n+1} \\ y_{n+1}\\ z_{n+1}\end{pmatrix}=\begin{pmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix}x_n \\ y_n\\ z_n\end{pmatrix}, \end{eqnarray*}$
kurz
$\begin{eqnarray*} v_{n+1}=Av_n. \end{eqnarray*}$

Die Lösung ist dann $\begin{eqnarray*} v_n=A^n v_0 \end{eqnarray*}$ , da die Formel zur geometrischen Folge auch in diesem Fall gilt.

Das charakteristische Polynom von $\begin{eqnarray*} A \end{eqnarray*}$ lässt sich sofort ablesen, da die Matrix in Treppenstufenform vorliegt:
$\begin{eqnarray*} P(\lambda) = \det(A-\lambda E) = (1-\lambda)^3. \end{eqnarray*}$
Demnach besitzt $\begin{eqnarray*} A \end{eqnarray*}$ algebraisch den dreifachen Eigenwert $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ .

Die Matrix $\begin{eqnarray*} A \end{eqnarray*}$ ist nicht diagonalisierbar. Um einer Jordan-Zerlegung aus dem Weg zu gehen, wenden wir den Satz von Cayley-Hamilton an. Ein einfacher Korollar von Cayley-Hamilton ist, dass
$\begin{eqnarray*} A^n = pA^2+qA+rE \end{eqnarray*}$
bei einer Matrix vom Typ $\begin{eqnarray*} 3\times 3 \end{eqnarray*}$ , wobei
$\begin{eqnarray*} \lambda^n = p\lambda^2+q\lambda+r \end{eqnarray*}$
für die Eigenwerte gilt. Die Zahlen $\begin{eqnarray*} p,q,r \end{eqnarray*}$ sind zu bestimmen.

Für $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ ergibt sich zunächst
$\begin{eqnarray*} 1=p+q+r. \end{eqnarray*}$

Angenommen, wir hätten nun zwei unterschiedliche $\begin{eqnarray*} \lambda_1,\lambda_2 \end{eqnarray*}$ . Dann ergäbe sich
$\begin{eqnarray*} \lambda_1^n = p\lambda_1^2+q\lambda_1+r, \end{eqnarray*}$
$\begin{eqnarray*} \lambda_2^n = p\lambda_2^2+q\lambda_2+r. \end{eqnarray*}$
Daraus erhält man
$\begin{eqnarray*} \frac{\lambda_2^n-\lambda_1^n}{\lambda_2-\lambda_1} = p\frac{\lambda_2^2-\lambda_1^2}{\lambda_2-\lambda_1}+q. \end{eqnarray*}$
Für $\begin{eqnarray*} \lambda_2=\lambda \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_1\to\lambda \end{eqnarray*}$ ergibt sich im Grenzwertfall
$\begin{eqnarray*} \frac{\mathrm d(\lambda^n)}{\mathrm d\lambda} = p\frac{\mathrm d(\lambda^2)}{\mathrm d\lambda}+q, \end{eqnarray*}$
also
$\begin{eqnarray*} n\lambda^{n-1} = 2p\lambda+q. \end{eqnarray*}$
Für $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ ergibt sich
$\begin{eqnarray*} n=2p+q = p+(p+q) = p+(1-r). \end{eqnarray*}$

Unter Hinzunahme des dritten Eigenwerts hat man nun
$\begin{eqnarray*} n\lambda^{n-1} = 2p\lambda+q, \end{eqnarray*}$
$\begin{eqnarray*} n\lambda_3^{n-1}=2p\lambda_3+q \end{eqnarray*}$ .
Also
$\begin{eqnarray*} n\frac{\lambda_3^{n-1}-\lambda^{n-1}}{\lambda_3-\lambda} = 2p. \end{eqnarray*}$
Im Grenzwertfall $\begin{eqnarray*} \lambda_3\to\lambda \end{eqnarray*}$ muss dann
$\begin{eqnarray*} n(n-1)\lambda^{n-2} = 2p \end{eqnarray*}$
sein. Für $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ ergibt sich $\begin{eqnarray*} p=\frac{n}{2}(n-1). \end{eqnarray*}$

Folglich ist $\begin{eqnarray*} q=(2-n)n \end{eqnarray*}$ und $\begin{eqnarray*} r=\frac{n}{2}(n-3)+1 \end{eqnarray*}$ .

Man kommt zum Resultat
$\begin{eqnarray*} A^n = \frac{n}{2}(n-1)A^2+(2-n)nA+(\frac{n}{2}(n-3)+1)E. \end{eqnarray*}$

Aus der Anfangsbedingung $\begin{eqnarray*} a_1=2 \end{eqnarray*}$ folgt $\begin{eqnarray*} a_0=1 \end{eqnarray*}$ . Der Anfangszustand ist demnach
$\begin{eqnarray*} \begin{pmatrix}x_0 \\ y_0\\ z_0\end{pmatrix} = \begin{pmatrix}1 \\1 \\ 1\end{pmatrix}. \end{eqnarray*}$
Die Auswertung lässt man vom CAS durchführen und erhält
$\begin{eqnarray*} a_n=x_n=\frac{n^2}{2}+\frac{n}{2}+1 = \frac{n}{2}(n+1)+1 \end{eqnarray*}$ .

Beachte:
$\begin{eqnarray*} \binom{n+1}{2} = \frac{n}{2}(n+1). \end{eqnarray*}$

12.05.2019, 14:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Daniel K. M.
Aber woher weiß ich, dass ich hier "quadratisch" ansetzen muss ?

Weil hier mit Lösung 1 der charakteristischen Gleichung der Resonanzfall vorliegt - das ist bei solchen Differenzengleichung ganz ähnlich wie bei Differenzialgleichungen.

Bei $\begin{eqnarray*} b_{n+1} = 2b_n - b_{n-1} + n+1 \end{eqnarray*}$ hättest du sogar kubisch ansetzen müssen, da hier 1 sogar doppelte Lösung der charakteristischen Gleichung der homogenen Differenzengleichung ist.

13.05.2019, 07:18

Daniel K. M.

Auf diesen Beitrag antworten »

Was ist denn "Resonanz" ?

Ich verstehe, dass es Probleme gibt, wenn das a_(n+k) auf der linken Seite der Rekursion genauso "schnell läuft" wie die a_n, a_(n+1), ... a_(n + k - 1) auf der rechten Seite. Also etwa

a_(n+1) = a_n + 1

a_(n+2) = 2 a_(n+1) - a_n + n + 3

Ist das schon die Resonanz ? Oder gibt es da noch mehr. Es wäre nett, wenn du mir das kurz erklären könntes.

13.05.2019, 09:31

HAL 9000

Auf diesen Beitrag antworten »

Im Fall einer solchen homogenen linearen Differenzengleichung sowie Störfunktion vom Typ $\begin{eqnarray*} s(n) = p(n)\lambda^n \end{eqnarray*}$ mit Polynom $\begin{eqnarray*} p \end{eqnarray*}$ spricht man von Resonanz, falls $\begin{eqnarray*} \lambda \end{eqnarray*}$ Lösung der charakteristischen Gleichung dieser Differenzengleichung ist. Hier bei dir ist das der Fall:

Es istz $\begin{eqnarray*} s(n) = (n+1)\cdot 1^n \end{eqnarray*}$ , und 1 ist Lösung der charakteristischen Gleichung $\begin{eqnarray*} \lambda-1 = 0 \end{eqnarray*}$ .

In solchen Fällen lautet der partikuläre Lösungsansatz $\begin{eqnarray*} a_n := n^r q(n) \lambda^n \end{eqnarray*}$ , wobei $\begin{eqnarray*} r \end{eqnarray*}$ die Vielfachheit der Lösung $\begin{eqnarray*} \lambda \end{eqnarray*}$ der charakteristischen Gleichung ist, und $\begin{eqnarray*} q \end{eqnarray*}$ ein Polynomansatz vom selben Grad wie $\begin{eqnarray*} p \end{eqnarray*}$ .

Im vorliegenden Fall ist $\begin{eqnarray*} r=1 \end{eqnarray*}$ und $\begin{eqnarray*} p(n)=n+1 \end{eqnarray*}$ hat Grad 1, also lautet der Partikuläransatz $\begin{eqnarray*} a_n = n(C_1n+C_2)\cdot 1^n = C_1n^2 + C_2n \end{eqnarray*}$ .

Zitat:

Original von Daniel K. M.
Bei der Rekursion a_(n+1) = a_n + n funktioniert der "lineare" Ansatz problemlos.

Das ist falsch: Auch hier kommt ein quadratisches $\begin{eqnarray*} a_n \end{eqnarray*}$ heraus.

Neue Frage »

Antworten »

Inhomogene Rekursionsgleichung

Verwandte Themen