Differenzengleichung/ Rekursionsgleichung

06.03.2024, 13:35

Menelaos1

Differenzengleichung/ Rekursionsgleichung

Meine Frage:
In der linearen Algebra habe ich gelernt wie man Rekursionen der Form $\begin{eqnarray*} x_n =ax_{n-1}+bx_{n-2} \end{eqnarray*}$ mithilfe der charakteristischen Gleichung explizit darstellen kann. Nun liegt mir eine Rekursion der Form $\begin{eqnarray*} x_n =ax_{n-1}+bx_{n-2}+c \end{eqnarray*}$ vor, gibt es hier ebenso eine Variante, die Rekursion explizit darzustellen?

Meine Ideen:
Habe versucht die Gleichung in die erste Form umzuwandeln, aber kam zu keinem Ergebnis.

06.03.2024, 14:04

HAL 9000

Auf diesen Beitrag antworten »

Naja, das ist eine zugehörige inhomogene Differenzengleichung. Da könnte man jetzt auch eine entsprechende Theorie ausbreiten, ich fasse mich aber mal kurz:

Es gibt zwei prinzipiell verschiedene Fälle, nämlich $\begin{eqnarray*} a+b=1 \end{eqnarray*}$ sowie entsprechend $\begin{eqnarray*} a+b\neq 1 \end{eqnarray*}$ :

In ersterem Fall ist nämlich $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ Lösung der zugehörigen charakteristischen Gleichung $\begin{eqnarray*} \lambda^2 - a\lambda - b = 0 \end{eqnarray*}$ , in letzterem Fall nicht.

Ich bespreche jetzt erstmal nur den letzteren Fall: Hier gibt es eine konstante Lösung $\begin{eqnarray*} x_n=s \end{eqnarray*}$ dieser Gleichung, durch Einsetzen bekommt man die über $\begin{eqnarray*} s = as+bs+c \end{eqnarray*}$ , umgestellt $\begin{eqnarray*} s = \frac{c}{1-a-b} \end{eqnarray*}$ .

Verschiebt man nun die gesuchte Folge um $\begin{eqnarray*} s \end{eqnarray*}$ , d.h. man betrachtet $\begin{eqnarray*} y_n = x_n - s \end{eqnarray*}$ , so erfüllt $\begin{eqnarray*} \left(y_n\right) \end{eqnarray*}$ die zugehörige homogene Differenzengleichung $\begin{eqnarray*} y_n = ay_{n-1} + by_{n-2} \end{eqnarray*}$ , die du ja schon lösen kannst.

Über den Fall $\begin{eqnarray*} a+b=1 \end{eqnarray*}$ reden wir, wenn er akut wird, d.h. wirklich für dich von Interesse ist. Augenzwinkern

06.03.2024, 15:45

Menelaos1

Auf diesen Beitrag antworten »

Erstmal vielen Dank für die Hilfe. Tatsächlich brauche ich den ersten Fall... Speziell bin ich an der Gleichung $\begin{eqnarray*} x_n = 2x_{n-1}-x_{n-2}-1 \end{eqnarray*}$ interessiert

06.03.2024, 20:50

HAL 9000

Auf diesen Beitrag antworten »

Oje, das ist sogar der worst-case: Hier ist $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ sogar doppelte Nullstelle der charakteristischen Gleichung. Da hilft Ansatz $\begin{eqnarray*} x_n = sn^2 \end{eqnarray*}$ für eine partikuläre Lösung der Gleichung, eingesetzt ergibt sich

$\begin{eqnarray*} sn^2 = 2s(n-1)^2 - s(n-2)^2 - 1 = 2sn^2-4sn+2s -sn^2+4sn-4s-1 \end{eqnarray*}$

$\begin{eqnarray*} s = -\frac{1}{2} \end{eqnarray*}$ .

D.h. $\begin{eqnarray*} x_n = y_n - \frac{n^2}{2} \end{eqnarray*}$ mit $\begin{eqnarray*} y_n \end{eqnarray*}$ Lösung der homogenen Gleichung $\begin{eqnarray*} y_n = 2y_{n-1} - y_{n-2} \end{eqnarray*}$ , welche du ja nach eigenem Bekunden lösen kannst.

10.03.2024, 11:41

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Naja, das ist eine zugehörige inhomogene Differenzengleichung. Da könnte man jetzt auch eine entsprechende Theorie ausbreiten...

Hier eine Lösung, die mit fortgesetzten Differenzenfolgen arbeitet. Ich stelle das Nötigste bereit.

Sei $\begin{align*} V \end{align*}$ der Vektorraum der reellen Zahlenfolgen $\begin{align*} x = \left( x_n \right)_{n \geq 0} \end{align*}$ mit punktweiser Addition und skalarer Multiplikation. Auf $\begin{align*} V \end{align*}$ definieren wir den Differenzenoperator

$\begin{align*} \Delta: \, V \to V \, , \ \ \Delta x = \left( x_{n+1} - x_n \right)_{n \geq 0} \end{align*}$

Der Operator $\begin{align*} \Delta \end{align*}$ ist linear. Die $\begin{align*} k \end{align*}$ -fache Hintereinanderausführung von $\begin{align*} \Delta \end{align*}$ wird mit $\begin{align*} \Delta^k \end{align*}$ bezeichnet.

Wir wenden $\begin{align*} \Delta \end{align*}$ auf die konkret vorliegende Folge $\begin{align*} x \end{align*}$ an. Das Glied mit dem Index 0 ist

$\begin{align*} \left( \Delta x \right)_0 = x_1 - x_0 \end{align*}$

Für das Glied mit einem Index $\begin{align*} n \geq 1 \end{align*}$ gilt aufgrund der Rekursion

$\begin{align*} \left( \Delta x \right)_n = x_{n+1} - x_n = 2x_n - x_{n-1} - 1 - x_n = x_n - x_{n-1} - 1 \end{align*}$

Jetzt wird $\begin{align*} \Delta \end{align*}$ ein weiteres Mal angewandt:

$\begin{align*} \left( \Delta^2 x \right)_0 = \left( \Delta x \right)_1 - \left( \Delta x \right)_0 = x_1 - x_0 - 1 - \left( x_1 - x_0 \right) = -1 \end{align*}$

Und für $\begin{align*} n \geq 1 \end{align*}$ gilt, zuletzt wieder unter Verwendung der Rekursion:

$\begin{align*} \left( \Delta^2 x \right)_n = \left( \Delta x \right)_{n+1} - \left( \Delta x \right)_n = x_{n+1} - x_n - 1 - \left( x_n - x_{n-1} - 1 \right) = x_{n+1} - 2x_n + x_{n-1} = 2x_n - x_{n-1} - 1 - 2x_n + x_{n-1} = -1 \end{align*}$

Damit ist die Folge $\begin{align*} \Delta^2 x \end{align*}$ konstant -1. Für die Folge $\begin{align*} \Delta x \end{align*}$ heißt das: Mit dem Startglied $\begin{align*} x_1 - x_0 \end{align*}$ beginnend wird in jedem weiteren Schritt 1 subtrahiert:

$\begin{align*} x_n - x_{n-1} = x_1 - x_0 - (n-1) \, , \ \ n \geq 1 \end{align*}$

$\begin{align*} x_n - x_0 = \sum_{k=1}^n \left( x_k - x_{k-1} \right) = \sum_{k=1}^n \left( x_1 - x_0 - (k-1) \right) = \left( x_1 - x_0 \right) \cdot n - \frac{1}{2} n (n-1) \end{align*}$

Hieraus berechnet man

$\begin{align*} x_n = x_0 + \left( x_1 - x_0 + \frac{1}{2} \right) \cdot n - \frac{1}{2} n^2 \end{align*}$

Die Herleitung gilt für $\begin{align*} n \geq 1 \end{align*}$ , die Formel gilt aber auch für $\begin{align*} n=0 \end{align*}$ und liefert in den Fällen $\begin{align*} n=0 \end{align*}$ und $\begin{align*} n=1 \end{align*}$ triviale Identitäten.

Neue Frage »

Antworten »

Differenzengleichung/ Rekursionsgleichung

Verwandte Themen