Rekursion lösen mit charakteristischem Polynom

10.09.2009, 10:44

donvito

Rekursion lösen mit charakteristischem Polynom

Hallo,

ich habe hier im Skript etwas gefunden, das ich nicht so ganz kapiere: Das "einfache" Lösen von Rekursionsgleichungen mithilfe eines charakteristischen Polynoms. Das scheint neben der Methode mit erzeugenden Funktionen die einzige Methode zu sein.

Zuerst einmal was ich kapiert habe:
Ich habe eine Rekursion gegeben, z.B. $\begin{eqnarray*} a_{n+2} = 5a_{n+1} - 6a_n, a_0=2, a_1 = 3 \end{eqnarray*}$

Dann gehe ich wie folgt vor:

Ich stelle eine Gleichung auf, die den Grad der Rekursion haben muss, in diesem Fall hier also Grad = 2
Diese Gleichung in zwei (?) Klammern zerlegen
Aus den Klammern kann man nun irgendwie die Basis ablesen
Dann stelle ich ein LGS auf und setze dabei n=0 bzw. 1
Wie man ein LGS löst ist aus der Oberstufe bekannt.

Unklar ist mir, in wieviele Klammern man zerlegen muss. In der Praxis kommen wohl nur Rekursionen von Grad 2 oder maximal Grad 3 dran, da es sonst etwas kompliziert wird.
Mein größtes Problem ist aber, wie man die Basis abliest. Bei obigen Beispiel ist es ja noch sehr einleuchtend, einfach die Nullstellen von (x-2)(x-3) also 2^n und 3^n nehmen.

Bei der Rekursion $\begin{eqnarray*} a_{n+3} = -12 A_n+8A_{n+1}+A_{n+2} \end{eqnarray*}$ erhalte ich als Gleichung $\begin{eqnarray*} (x-2)^2(x+3) \end{eqnarray*}$ . Soweit so gut. Doch wie komme ich nun auf die Basis $\begin{eqnarray*} 2^n, n 2^n, 3^n \end{eqnarray*}$ ??

13.09.2009, 16:08

Abakus

Auf diesen Beitrag antworten »

RE: Rekursion lösen mit charakteristischem Polynom

Zitat:

Original von donvito
Zuerst einmal was ich kapiert habe:
Ich habe eine Rekursion gegeben, z.B. $\begin{eqnarray*} a_{n+2} = 5a_{n+1} - 6a_n, a_0=2, a_1 = 3 \end{eqnarray*}$

Dann gehe ich wie folgt vor:

Ich stelle eine Gleichung auf, die den Grad der Rekursion haben muss, in diesem Fall hier also Grad = 2
Diese Gleichung in zwei (?) Klammern zerlegen
Aus den Klammern kann man nun irgendwie die Basis ablesen
Dann stelle ich ein LGS auf und setze dabei n=0 bzw. 1
Wie man ein LGS löst ist aus der Oberstufe bekannt.

Da du hier konstante Koeffizienten hast, ist das Vorgehen ähnlich wie auch bei DGLen.

Du setzt an: $\begin{eqnarray*} x_n = m^n \end{eqnarray*}$ und setzt das einmal in die Rekursion ein:

$\begin{eqnarray*} x_{n+2} - 5x_{n+1} + 6x_n = m^n \cdot (m^2 - 5m + 6) = 0 \end{eqnarray*}$

Wenn jetzt m nicht gleich Null ist, muss also gelten: $\begin{eqnarray*} m^2 - 5m + 6 = 0 \end{eqnarray*}$ . Das ist das charakt. Polynom der Rekursion.

Jetzt nimmst du die Nullstellen als Basis $\begin{eqnarray*} m_1 = 2 \end{eqnarray*}$ und $\begin{eqnarray*} m_2 = 3 \end{eqnarray*}$ . Damit ist klar, wie man darauf kommt. Abhängig von der Diskriminante des Polynoms hast du 3 mögliche Fälle: zwei reelle Nullstellen (der Fall hier), eine doppelte reelle Nullstelle (in dem Fall ist $\begin{eqnarray*} m^n \end{eqnarray*}$ und $\begin{eqnarray*} n \cdot m^n \end{eqnarray*}$ die Basis), oder zwei komplexe Nullstellen (in dem Fall bekommst du einen Kosinus- und einen Sinusteil dazu).

Zitat:

Bei der Rekursion $\begin{eqnarray*} a_{n+3} = -12 A_n+8A_{n+1}+A_{n+2} \end{eqnarray*}$ erhalte ich als Gleichung $\begin{eqnarray*} (x-2)^2(x+3) \end{eqnarray*}$ . Soweit so gut. Doch wie komme ich nun auf die Basis $\begin{eqnarray*} 2^n, n 2^n, 3^n \end{eqnarray*}$ ??

Genauso. Du hast erstmal $\begin{eqnarray*} (-3)^n \end{eqnarray*}$ und $\begin{eqnarray*} 2^n \end{eqnarray*}$ . Und weil 2 doppelte Nullstelle ist, kommt noch $\begin{eqnarray*} n \cdot 2^n \end{eqnarray*}$ dazu.

Grüße Abakus smile

Neue Frage »

Antworten »

Rekursion lösen mit charakteristischem Polynom

Verwandte Themen