Die Mathe-Redaktion - 30.04.2017 22:38 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 359 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Allgemeine Lösung linearer Rekursionsgleichungen
Freigegeben von matroid am Do. 14. Januar 2016 22:00:22
Verfasst von trunx -   647 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Allgemeine Lösung linearer Rekursionsgleichungen mit konstanten Koeffizienten


Hier hatte ich bereits für relativ einfache lineare Rekursionsgleichungen (nämlich solche 2. Grades) Lösungen angegeben und in den Kommentaren weitere Lösungsideen ergänzt. Mittlerweile reicht eine solche Ergänzung nicht mehr aus, ich habe mich deshalb für einen neuen Artikel entschieden (zur Lösung einer nichtlinearen Rekursion siehe hier).

Die allgemeine Form linearer Rekursionsgleichungen (mit Elementen <math>f_n</math> und entsprechend allen Koeffizienten <math>r_i</math> aus einem Körper <math>\mathds{K}</math>) lautet:

<math>f_{n+m}=\sum \limits_{i=0}^{m-1} r_i f_{n+i} + g(n)</math> (0) mit Anfangsbedingungen <math>f_i</math> für <math>i=0,\dotsc,m-1.</math>

Für <math>g(n)=0</math> heissen die Rekursionsgleichungen homogen, andernfalls inhomogen. In diesem Artikel werden nun die Lösungen (u.a. mit Hilfe der Körpererweiterung) für sämtliche homogene und für eine bestimmte Klasse inhomogener Rekursionsgleichungen hergeleitet, nämlich für den Fall <math>g(n)=\sum \limits_{j=1}^l p_j(n) \phi^n_j</math>, wobei <math>p_j(n)=\sum \limits_{k=0}^{d_j} q_{jk} n^k</math> Polynome <math>d_j</math>-ten Grades in <math>n</math> sind (hier sind die <math>\phi_j,q_{jk}</math> nicht notwendig in <math>\mathds{K}</math>, es genügt ja, wenn dies für alle <math>g(n)</math> der Fall ist).

Homogener Fall <math>g(n)=0</math>


Es gilt also zunächst <math>f_{n+m}=\sum \limits_{i=0}^{m-1} r_i f_{n+i}</math> (1) mit gegebenen <math>f_i</math>. m ist der Grad der Rekursion.
Üblicherweise wird für die Lösung von linearen Rekursionsgleichungen <math>f_n=X^n</math> angesetzt. Eingesetzt in die Rekursionsgleichung (1) ergibt sich das sog. charakteristische Polynom <math>P(X)=X^m-\sum \limits_{i=0}^{m-1} r_i X^i=0</math> (natürlich ebenfalls m-ten Grades), dessen Nullstellen <math>\phi_j</math> zu ermitteln sind. Diese Nullstellen sind im allgemeinen mehrfach und nicht Elemente von <math>\mathds{K}</math>. Mit ihrer Hilfe lässt sich das charakteristische Polynom wie folgt darstellen:
<math>P(X)=\prod \limits_{j=1}^{m_0} (X-\phi_j)^{v_j}</math>,
wobei <math>v_j</math> die Vielfachheit der Nullstelle <math>\phi_j</math> ist und <math>m_0 \le m</math> die Anzahl der verschiedenen Nullstellen.

Der Lösungsansatz geht jetzt zunächst weiter mit einer Linearkombination der Nullstellen-Potenzen
<math>f_n=\sum \limits_{j=1}^{m_0} A_j \phi^n_j</math>. Dabei müssen die <math>A_j</math> aus den Anfangsbedingungen <math>f_i</math> ermittelt werden. Aber es gibt zwei Probleme damit:
1. die Vielfachheit der Nullstellen ist dabei nicht berücksichtigt, daher gibt es im allgemeinen mehr <math>f_i</math> als <math>A_j</math>, das LGS ist (noch) überbestimmt.
2. allg. gilt <math>\phi_j \notin \mathds{K}</math>, dh. (noch) kann nicht sicher gestellt werden, dass die so ermittelten <math>f_n</math> in <math>\mathds{K}</math> landen.

Das erste Problem beheben wir durch folgende Überlegung: mit einer beliebigen Nullstelle <math>\phi_j</math> kann die Rekursionsgleichung (1) durch die Transformation <math>f'_n=f_{n+1}-\phi_jf_n</math> (2) in eine Rekursionsgleichung überführt werden, deren Grad um eins gesenkt ist. Hat man für <math>f'_n</math> eine Lösung, so muss nur noch die einfachere Rekursion <math>f_{n+1}=\phi_jf_n+f'_n</math> gelöst werden.

Sei jetzt <math>\phi</math> einzige, aber mehrfache Nullstelle mit Vielfachheit <math>v</math>. Dann reduzieren wir jetzt die Rekursionsgleichung mittels (2) <math>v-1</math>-mal, dh. wir erhalten als Rekursion <math>f^{(v-1)}_{n+1}=\phi f^{(v-1)}_n</math> mit der Lösung <math>f^{(v-1)}_n=f^{(v-1)}_0\phi^n</math>.

Jetzt machen wir die Transformationen schrittweise wieder rückgängig. Es ist <math>f^{(v-2)}_{n+1}=\phi f^{(v-2)}_n+f^{(v-1)}_0\phi^n</math> mit der Lösung <math>f^{(v-2)}_n=\phi^n (f^{(v-2)}_j+n\frac{f^{(v-1)}_n}{\phi})</math>. In der Klammer ist nun ein Polynom in n, das mit jedem weiteren Rücktransformationsschritt um einen Grad steigt.

Daher setzen wir besser an:
<math>f_n=\sum \limits_{j=1}^{m_0} (\sum \limits_{k=0}^{v_j-1} A_{jk}n^k )\phi^n_j=\sum \limits_{j=1}^{m_0} p_j(n) \phi^n_j</math> (3)
Jetzt sind genau m Koeffizienten <math>A_{jk}</math> gesucht.

Bevor es ans Lösen des zugehörigen LGS geht, noch folgende Bemerkung. Genau diese Kombination aus Polynom <math>p_j(n)</math> und Potenz <math>\phi^n_j</math>, die hier als Lösungsansatz benutzt wird, wird später auch angesetzt als (lösbare) Inhomogenität. Wer also eine entsprechende Rekursion zu lösen hat, sollte das im Hinterkopf behalten, es ist nämlich nicht nötig erst das homogene und dann das inhomogene LGS zu lösen.

Ermittlung der Koeffizienten <math>A_{jk}</math>


Wie bereits gesagt, besteht bei der Ermittlung der Koeffizienten <math>A_{jk}</math> das Problem, dass die <math>\phi_j</math> und ihre Potenzen nicht notwendig Elemente aus <math>\mathds{K}</math> sind, die <math>f_n</math> dagegen schon. Aus diesem Grund ist <math>\mathds{K}</math> zum Zerfällungskörper <math>\mathds{L}=\mathds{K}(\phi_1,...,\phi_{m_0})</math> des charakteristischen Polynoms zu erweitern und die <math>A_{jk}</math> sind als Elemente dieses Zerfällungskörpers anzusetzen. Allgemein lässt sich über den Grad <math>deg(\mathds{L})</math> des Zerfällungskörpers wenig sagen, sind bspw. alle <math>\phi_j \in \mathds{K}</math>, dann ist <math>\mathds{L}=\mathds{K}</math>, also
<math>deg(\mathds{L})=1</math>. Andererseits entsteht <math>\mathds{L}</math> ja durch die Adjunktion aller Nullstellen, sprich durch die Verknüpfungen +,-,*,/ können weitere (endlich viele) Elemente entstehen, dh. deg(<math>\mathds{L}</math>) kann auch maximal <math>m_0 !</math> werden.

Sei nun <math>(b_1=1,b_2,...,b_{deg(\mathds{L})})</math> eine Basis von <math>\mathds{L}</math>. Dann muss jedes <math>A_{jk}</math> als <math>A_{jk}=\sum \limits_{h=1}^{deg(\mathds{L})} a_{jkh} b_h</math> angesetzt werden. Eingesetzt in (3) ergibt
<math>f_n=\sum \limits_{j=1}^{m_0} \sum \limits_{k=0}^{d_j-1} \sum \limits_{h=1}^{deg(\mathds{L})} a_{jkh} b_h n^k \phi^n_j</math> (4), wobei wir für <math>n=0,...,m-1</math> setzen.
(4) ist ein lineares Gleichungssystem für die <math>a_{jkh}</math>. Es entsteht nicht nur durch die m Anfangsbedingungen, sondern je auch durch die <math>deg(\mathds{L})</math> Komponentenvergleiche. Es sind also <math>m*deg(\mathds{L})</math> Unbekannte zu ermitteln.

Inhomogenität <math>g(n)=\sum \limits_{j=1}^lp_j(n)\phi^n_j</math>


Die Bearbeitung der so gegebenen Inhomogenitäten erweist sich als recht einfach. Es genügt, das charakteristische Polynom <math>P(X)</math> um die in der Inhomogenität auftauchenden <math>\phi_j</math> als Nullstellen mit der Vielfachheit <math>v_j=d_j(p_j(n))+1</math> zu erweitern, wobei <math>d_j</math> der Grad des Polynoms <math>p_j(n)</math> ist.

Es ist also <math>P'(X)=P(X) * \prod \limits_{j=1}^l (X-\phi_j)^{v_j}</math>

War bereits in <math>P(X)</math> ein <math>\phi_j</math> als Nullstelle vorhanden, dann erhöht sich nur deren Vielfachheit. Im Lösungsansatz ist dies durch eine entsprechende Erhöhung des Grades des zugehörigen Polynoms zu berücksichtigen. Der Grad der zu <math>P'(X)</math> gehörenden Rekursion ist <math>m'=m+ \sum \limits_{j=1}^l v_j</math>.

Die Anzahl der Unbekannten <math>a_{jkh}</math> steigt durch die Inhomogenität; die Anzahl der Anfangsbedingungen bleibt jedoch zunächst unverändert. Die zusätzlichen Gleichungen des LGS werden nun entweder
1. durch Erzeugung weiterer Anfangsbedingungen, also der nächsten Folgenglieder <math>f_n</math> mit <math>n=m,...,m'-1</math> (dadurch wird der inhomogene Fall komplett auf den homogenen Fall zurück geführt) oder
2. durch Einsetzen von (4) in (0) und durch Komponentenvergleich unter Ausnutzung der homogenen Anteile der Gleichungen aus den <math>q_{jk}</math> gewonnen.

Beispiele


Im Prinzip ist nun alles gesagt. Im oben angegebenen Artikel ist darüberhinaus der homogene Fall <math>m=2</math> ausführlich dargestellt.

Dennoch können ein paar Beispiele das Ganze vielleicht noch etwas anschaulicher machen.

1. <math>\phi</math> mit Vielfachheit v (homogen)


Die Rekursion lautet <math>f_{n+v}=-\sum \limits_{i=1}^v \binom{v}{i} (-\phi)^i f_{n+d-i}</math>, das charakteristische Polynom lautet also einfach <math>P(X) = (X - \phi)^v</math> und der Lösungsansatz <math>f_n = \phi^n \sum \limits_{i=0}^{v-1} a_i n^i</math>. Gegeben sind die ersten v <math>f_n</math>, also für <math>n=0,...,d-1</math>.

Das Gleichungssystem lautet daher

<math>\begin{matrix}
a_0 &  &  &  &  & = & f_0 \\
a_0 & +a_1 & +a_2 & +... & +a_{v-1} & = & \frac{f_1}{\phi} \\
a_0 & +2a_1 & +4a_2 & +... & +2^{v-1} a_{v-1} & = & \frac{f_2}{\phi^2} \\
. & . & . & . & . & . & . \\
a_0 & +(v-1) a_1 & +(v-1)^2a_2 & +... & +(v-1)^{v-1} a_{v-1} & = & \frac{f_{v-1}}{\phi^{v-1}}
\end{matrix}</math>

oder in Matrixschreibweise

<math>\left(
\begin{array}{ccccc}
1 & 0 & 0 & ... & 0 \\
1 & 1 & 1 & ... & 1 \\
1 & 2 & 4 & ... & 2^{v-1} \\
. & . & . & . & . \\
1 & (v-1) & (v-1)^2 & ... & (v-1)^{v-1}
\end{array}
\right) * \left(
\begin{array}{c}
a_0 \\
a_1 \\
a_2 \\
... \\
a_{d-1}
\end{array}
\right) = \left(
\begin{array}{c}
f_0 \\
\frac{f_1}{\phi} \\
\frac{f_2}{\phi^2} \\
... \\
\frac{f_{d-1}}{\phi^{v-1}}
\end{array}
\right)</math>

wobei die Matrix eine Vandermonde-Matrix ist. Verwunderlich ist dies nicht, schliesslich dient das Gleichungssystem ja vor allem dem Finden der Koeffizienten eines Polynoms. Mit den je verschiedenen Einträgen <math>x_i= i-1</math> ist sie regulär bzw. invertierbar.

für <math>v=m=1: a_0=f_0</math>
für <math>v=m=2: a_0=f_0, a_1=\frac{f_1}{\phi}-f_0</math>
für <math>v=m=3: a_0=f_0, a_1=-\frac{1}{2} (\frac{f_2}{\phi^2}-4\frac{f_1}{\phi}+3f_0), a_2=\frac{1}{2} (\frac{f_2}{\phi^2}-2\frac{f_1}{\phi}+f_0)</math>
usw.

2. <math>\phi</math> mit einfacher Vielfachheit und inhomogen mit gleichem <math>\phi</math>


Die Rekursion lautet <math>f_{n+1}=\phi f_n + \phi^n \sum \limits_{i=0}^d c_i n^i</math>.
Nehmen wir jetzt konkret <math>\phi=1</math> und <math>\sum \limits_{i=0}^d c_i n^i= n</math>, also <math>f_{n+1}=f_n +n</math> an. <math>f_0</math> sei gegeben. Dann ist
<math>f_1=f_0</math>
<math>f_2=f_0+1</math>
<math>f_3=f_0+1+2</math>
also <math>f_n=f_0 +\sum \limits_{i=0}^{n-1} i=f_0 +\frac{1}{2}n(n-1)</math>. Man kann gut erkennen, warum der Grad des Lösungspolynoms um eins höher ist als das Polynom der Inhomogenität. Entsprechend ist der allgemeine Lösungsansatz für 2. genau der gleiche wie für 1 mit <math>v=d+1</math> (für den Fall, dass die Rekursion mit Vielfachheit v' auftritt, ist <math>v=d+v'</math>).

3. <math>\phi</math> mit einfacher Vielfachheit und inhomogen mit anderem <math>\phi'</math>


Jetzt lautet die Rekursion also
<math>f_{n+1}=\phi f_n + \phi'^n \sum \limits_{i=0}^d q_i n^i</math>.
Beim Lösungsansatz müssen natürlich <math>\phi</math> und <math>\phi'</math> mit ihrer Vielfachheit v bzw. ihrem Polynomgrad d jeweils einzeln berücksichtigt werden.

Es ist also <math>f_n=a\phi^n +\phi'^n \sum \limits_{i=0}^d a_i n^i</math> mit unbekannten a und <math>a_i</math> anzusetzen.
Nehmen wir konkret <math>f_{n+1} = 2f_n + n</math> mit <math>\phi=2</math> und <math>\phi'=1</math>, dann muss <math>f_n=a2^2+a_1 n+a_0</math> angesetzt werden. Ursprünglich ist nur <math>f_0</math> gegeben, da wir jedoch drei Unbekannte haben, ermitteln wir zwei weitere Vorgaben, nämlich <math>f_1=2f_0</math> und <math>f_2=4f_0+1</math>. Damit erhalten wir für <math>a=f_0+1</math> und <math>a_1=a_0=-1</math>.

Übrigens entspricht daher die obige inhomogene Rekursion <math>f_{n+1} = 2f_n + n</math> mit gegebenem <math>f_0</math> der homogenen Rekursion <math>f_{n+3}=4f_{n+2}-5f_{n+1}+2f_n</math> mit den gegebenen/zusätzlich ermittelten <math>f_0</math>, <math>f_1</math> und <math>f_2</math>.

4. Fibonacci-Folge (Körpererweiterung)


Bei den bisherigen Beispielen spielte die Körpererweiterung noch keine Rolle, weil die <math>\phi</math>'s demselben Körper angehörten wie die Folgenglieder <math>f_n</math>. Ein (relativ) einfaches Beispiel bei dem dies nicht mehr der Fall ist, ist die Fibonacci-Folge. Diese lautet
<math>f_{n+2}=f_{n+1}+f_n</math> mit <math>f_0=f_1=1</math>
Das charakteristische Polynom für diese Rekursion ist <math>X^2-X-1=0</math> mit den Nullstellen <math>\phi_{1,2}=\frac{1}{2}(1\pm\sqrt{5})</math>.

Alle Elemente der Fibonacci-Folge sind natürliche Zahlen, der zugehörige Körper wäre also <math>\mathds{Q}</math>. <math>\sqrt{5}</math> gehört nun nicht dazu, entsprechend muss der Körper, in dem der Lösungsansatz zu formulieren ist, erweitert werden zu <math>\mathds{Q}[\sqrt{5}]</math>.

Der Lösungsansatz lautet daher
<math>f_n=\frac{1}{2^n}(A(1+\sqrt{5})^n+B(1-\sqrt{5})^n)=\frac{1}{2^n}((A_1+A_2\sqrt{5})(1+\sqrt{5})^n+(B_1+B_2\sqrt{5})(1-\sqrt{5})^n)</math>, also mit <math>A, B \in \mathds{Q}[\sqrt{5}]</math>.

Es ergeben sich durch die Anfangsbedingungen
<math>A_1+A_2\sqrt{5}+B_1+B_2\sqrt{5}=1</math>
<math>\frac{1}{2}((A_1+A_2\sqrt{5})(1+\sqrt{5})+(B_1+B_2\sqrt{5})(1-\sqrt{5}))=1</math>
und daraus durch Komponentenvergleich folgende 4 Gleichungen:
<math>A_1+B_1=1</math>
<math>A_2+B_2=0</math>
<math>A_1+5A_2+B_1-5B_2=2</math>
<math>A_1+A_2-B_1+B_2=0</math>

mit der Lösung
<math>A=\frac{1}{2}(1+\frac{\sqrt{5}}{5})</math>
<math>B=\frac{1}{2}(1-\frac{\sqrt{5}}{5})</math>, also

<math>f_n=\frac{\sqrt{5}}{5*2^{n+1}}((1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1})</math>

5. inhomogene Fibonacci-Folge


Schauen wir uns nun an, was passiert, wenn die Rekursion der Fibonacci-Folge inhomogen wird. Sei z.B.
<math>f'_{n+2}=f'_{n+1}+f'_n +c</math> wieder mit <math>f'_0=f'_1=1</math>, sprich wir addieren stets noch eine Konstante dazu.

Nach dem bisherigen kommt durch die Inhomogenität die "Nullstelle" <math>\phi=1</math> hinzu, der Polynomgrad der Konstante ist <math>d=0</math>. Da <math>\phi</math> keine Nullstelle der homogenen Rekursion <math>f_n</math> ist, wird im Lösungsansatz einfach noch eine Unbekannte addiert. Ausserdem bedarf es noch einer zusätzlichen Anfangsbedingung, sie lautet nach Einsetzen in die Rekursion <math>f'_2=2+c</math>.

Insgesamt haben wir also als Ansatz
<math>f'_n=\frac{1}{2^n}((A_1+A_2\sqrt{5})(1+\sqrt{5})^n+(B_1+B_2\sqrt{5})(1-\sqrt{5})^n)+C</math>

und als Gleichungen
<math>A_1+A_2\sqrt{5}+B_1+B_2\sqrt{5}+C=1</math>
<math>\frac{1}{2}((A_1+A_2\sqrt{5})(1+\sqrt{5})+(B_1+B_2\sqrt{5})(1-\sqrt{5}))+C=1</math>
<math>\frac{1}{4}((A_1+A_2\sqrt{5})(1+\sqrt{5})^2+(B_1+B_2\sqrt{5})(1-\sqrt{5})^2)+C=2+c</math>
und daraus durch Komponentenvergleich folgende 5 Gleichungen:
<math>A_1+B_1+C=1</math>
<math>A_2+B_2=0</math>
<math>A_1+5A_2+B_1-5B_2+2C=2</math>
<math>A_1+A_2-B_1+B_2=0</math>
<math>3A_1+5A_2+C=2+c</math>

mit der Lösung <math>f'_n = (1+c)f_n - c</math>, wobei <math>f_n</math> das n-te Glied der homogenen Fibonacci-Folge ist.

6. harmonischer Oszillator ohne und mit Dämpfung


Besonders eindrucksvoll zeigt sich die Leistungsfähigkeit des hier vorgestellten Ansatzes bei der Lösung von diskretisierten Differentialgleichungen. Als Beispiel sei der harmonische Oszillator ohne und mit Dämpfung gewählt. Für diesen gilt
<math>\"{x}+2\gamma\.{x}+\omega^2_0x=0</math> mit den Anfangsbedingungen x0 und <math>\.x_0=v_0</math>

wobei <math>\gamma\ge 0</math> die Abklingkonstante und <math>\omega_0</math> die Resonanzfrequenz des Oszillators ist. Für den Fall <math>\gamma=0</math> ist der harmonische Oszillator ohne Dämpfung.

Mit der Zeit <math>t=n\tau</math> und dem Zeitintervall <math>\tau</math> werden die Zeitableitungen jetzt diskretisiert, also als Differenzenquotienten geschrieben:
<math>\.{x}=\frac{x_{(n+1)\tau}-x_{n\tau}}{\tau}</math>
<math>\"{x}=\frac{x_{(n+2)\tau}-2x_{(n+1)\tau}+x_{n\tau}}{\tau^2}</math>

Eingesetzt in die Gleichung für den harmonischen Oszillator ergibt folgende Rekursion
<math>x_{(n+2)\tau}-2x_{(n+1)\tau}+x_{n\tau}+2\gamma\tau(x_{(n+1)\tau}-x_{n\tau})+\omega^2_0\tau^2x_{n\tau}=0</math> bzw.

<math>x_{(n+2)\tau}=2(1-\gamma\tau)x_{(n+1)\tau}-(1-2\gamma\tau+\omega^2_0\tau^2)x_{n\tau}</math>

Für <math>\gamma=0</math>, also den ungedämpften Fall haben wir einfach
<math>x_{(n+2)\tau}=2x_{(n+1)\tau}-(1+\omega^2_0\tau^2)x_{n\tau}</math>

Die Anfangsbedingungen sind <math>x_0</math> und <math>x_{\tau}=x_0+v_0\tau</math>.

Wir lösen zuerst den ungedämpften Fall. Das charakteristische Polynom lautet dafür:
<math>X^2-2X+1+\omega^2_0\tau^2=0</math> und hat als Nullstellen
<math>\phi_{1,2}=1\pm\omega_0\tau i</math>, wobei i natürlich die imaginäre Einheit ist. Hier ist der Grundkörper <math>\mathds{K}=\mathds{R}</math>, der um i erweitert werden muss, dh. es ist <math>\mathds{L}=\mathds{C}</math>.

Um jetzt weiter zu kommen, gehen wir von der Form <math>z=a+bi</math> über zur Form <math>z=\rho e^{i\alpha}</math>. Die Nullstellen sind folglich <math>\phi_{1,2}=\sqrt{1+\omega^2_0\tau^2}e^{\pm arctan(\omega_0\tau) i}</math>. Damit lautet der Ansatz für x
<math>x_{n\tau}=(1+\omega^2_0\tau^2)^{\frac{n}{2}}((A_1+A_2 i)e^{arctan(\omega_0\tau)n i}+(B_1+B_2 i)e^{-arctan(\omega_0\tau)n i})</math>.

Mit den Anfangsbedingungen werden wieder die <math>A_i</math> und <math>B_i</math> ermittelt zu <math>A_1=B_1=\frac{x_0}{2}</math> und
<math>A_2=-B_2=-\frac{v_0\tau\sqrt{1+\omega^2_0\tau^2}+x_0(\sqrt{1+\omega^2_0\tau^2}-1)}{2\omega_0\tau}</math>.

Zusammen also
<math>x_{n\tau}=x_0 cos(n*arctan(\omega_0\tau))+\frac{v_0\tau\sqrt{1+\omega^2_0\tau^2}+x_0(\sqrt{1+\omega^2_0\tau^2}-1)}{\omega_0\tau} sin(n*arctan(\omega_0\tau))</math>.

Dies ist die exakte diskrete Lösung. Für sehr kleine <math>\tau</math>, also <math>\omega_0\tau\ll1</math> wird diese zu
<math>x_{n\tau}=x_0 cos(\omega_0n\tau)+\frac{v_0}{\omega_0} sin(\omega_0n\tau)</math>. Setzen wir darüber hinaus wieder die Zeit als <math>t=n\tau</math>, erhalten wir
<math>x(t)=x_0 cos(\omega_0t)+\frac{v_0}{\omega_0} sin(\omega_0t)</math>, wie man es mit analytischen Mitteln erhalten würde.

Interessant finde ich hieran, dass der exponentielle Ansatz durch die Körpererweiterung zu <math>\mathds{C}</math> letztlich zu einer periodischen Funktion führte.

Schauen wir uns nun den gedämpften harmonischen Oszillator an. Das charakteristische Polynom lautet: <math>X^2-2(1-\gamma\tau)X+1-2\gamma\tau+\omega^2_0\tau^2=0</math> mit den Nullstellen
<math>\phi_{1,2}=1-\tau (\gamma\mp\sqrt{\gamma^2-\omega^2_0})</math>.

Bekanntlich gibt es jetzt drei Fälle
a) den stark gedämpften Fall <math>\gamma > \omega_0</math> (Kriechfall),
b) den aperiodischen Grenzfall <math>\gamma = \omega_0</math> und
c) den Schwingfall mit <math>\gamma < \omega_0</math>.

Für den stark gedämpften Fall liegen beide Nullstellen in <math>\mathds{R}</math>, s.d. als Lösungsansatz einfach
<math>x_{n\tau}=a_1 (1-\tau (\gamma-\sqrt{\gamma^2-\omega^2_0}))^n +a_2 (1-\tau (\gamma+\sqrt{\gamma^2-\omega^2_0}))^n</math> in Frage kommt. Mit den Anfangsbedingungen ergibt sich
<math>a_{1,2}=\frac{x_0(\sqrt{\gamma^2-\omega^2_0}\pm\gamma)\pm v_0}{2\sqrt{\gamma^2-\omega^2_0}}</math>, zusammen also

<math>x_{n\tau}=\frac{x_0}{2} ((1+\frac{\gamma+v_0 /x_0}{\sqrt{\gamma^2-\omega^2_0}})(1-\tau (\gamma-\sqrt{\gamma^2-\omega^2_0}))^n +(1-\frac{\gamma+v_0 /x_0}{\sqrt{\gamma^2-\omega^2_0}}) (1-\tau (\gamma+\sqrt{\gamma^2-\omega^2_0}))^n )</math>

Wird jetzt wieder der Grenzfall für kleine <math>\tau</math> betrachtet, setzt man Terme der Form <math>1+z\tau=e^{z\tau}</math>. Damit wird
<math>x_{n\tau}=\frac{x_0}{2}e^{-\gamma n\tau} ((1+\frac{\gamma+v_0 /x_0}{\sqrt{\gamma^2-\omega^2_0}})e^{n\tau\sqrt{\gamma^2-\omega^2_0}}+(1-\frac{\gamma+v_0 /x_0}{\sqrt{\gamma^2-\omega^2_0}})e^{-n\tau\sqrt{\gamma^2-\omega^2_0}} )</math>
Mit <math>t=n\tau</math> erhält man daraus wieder die klassische Lösung.

Für den aperiodischen Grenzfall ist <math>\gamma = \omega_0</math>, d.h. mathematisch, dass es nur noch eine Nullstelle, nämlich <math>\phi=1-\tau\gamma</math> mit zweifacher Vielfachheit gibt. Der Ansatz lautet entsprechend

<math>x_{n\tau}=(a_1+na_2)(1-\tau\gamma)^n</math> und mit der Auswertung der Anfangsbedingungen
<math>x_{n\tau}=(x_0+\frac{n\tau(v_0+x_0\gamma)}{1-\tau\gamma})(1-\tau\gamma)^n</math> als exakter Lösung und für kleine <math>\tau</math>
<math>x_{n\tau}=(x_0+n\tau(v_0+x_0\gamma))e^{-n\tau\gamma}</math> bzw. mit <math>t=n\tau</math>
<math>x(t)=(x_0+(v_0+x_0\gamma)t)e^{-\gamma t}</math>

Für den letzten Fall <math>\gamma < \omega_0</math> wird <math>\sqrt{\omega^2_0 -\gamma^2}=\omega_D</math> gesetzt. Das zugehörige charakteristische Polynom hat wieder zwei komplexe Nullstellen und wieder wird eine (diesmal gedämpfte) Schwingung mit der veränderten Frequenz <math>\omega_D</math> durch die Verlagerung des Problems in den Erweiterungskörper <math>\mathds{C}</math> ermittelt. Dies sei dem Leser als Übung überlassen.

7. 3-fach Fibonacci-Folge


Das folgende Beispiel wurde wegen seiner algebraischen Stärke ausgewählt. Durch die geschickte Wahl der Basis von <math>\mathds{L}</math> spart man sich eine Menge Rechenarbeit. Die Rekursion sieht zunächst wie folgt aus:

<math>f_{n+3}=f_{n+2}+f_{n+1}+f_n</math> mit gegebenen <math>f_0</math>, <math>f_1</math> und <math>f_2</math>.

Das charakteristische Polynom lautet <math>X^3-X^2-X-1=0</math> und hat folgende Nullstellen:
<math>\phi_1=\frac{1}{3}(\sqrt[3]{19+\sqrt{297}}+1+\frac{4}{\sqrt[3]{19+\sqrt{297}}})</math>
<math>\phi_{2,3}=-\frac{1}{6}(\sqrt[3]{19+\sqrt{297}}-2+\frac{4}{\sqrt[3]{19+\sqrt{297}}}\pm i\sqrt{3\sqrt[3]{(19+\sqrt{297})^2}-24+\frac{48}{\sqrt[3]{(19+\sqrt{297})^2}}})</math>

Der Lösungsansatz muss jetzt wieder im Zerfällungskörper <math>\mathds{L}</math> formuliert werden. Um wie gesagt Arbeit zu sparen, setzen wir als Basis von <math>\mathds{L}</math>
<math>B_{\mathds{L}}=(1,\phi_1,\phi_1^2,\phi_2,\phi_1\phi_2,\phi_1^2\phi_2)</math>
Der Körpergrad ist <math>[\mathds{L}:\mathds{Q}]=6</math>.

Der Lösungsansatz lautet:
<math>f_n=\sum \limits_{i=1}^3 A_i \phi_i^n</math> mit <math>A_i \in \mathds{L}</math>, also <math>A_i=\sum \limits_{j=1}^6 a_{ij}b_j</math>.
Wir benutzen weiterhin den Satz von Vieta
<math>\phi_1+\phi_2+\phi_3=1</math>
<math>\phi_1\phi_2+\phi_1\phi_3+\phi_2\phi_3=-1</math>
<math>\phi_1\phi_2\phi_3=1</math>
sowie
<math>\phi_i^3=\phi_i^2+\phi_i+1</math>.

Damit erhalten wir u.a.
<math>\phi_3=1-\phi_1-\phi_2</math>
<math>\phi_2\phi_3=\phi_1^2-\phi_1-1</math>
<math>\phi_2^2=1+\phi_1-\phi_1^2+\phi_2-\phi_1\phi_2</math>
<math>\phi_3^2=2-\phi_1-\phi_2+\phi_1\phi_2</math>
und können nun ein (relativ einfaches, wenn auch immer noch umfangreiches) LGS für die 18 aij aufstellen.

Im einzelnen sind dies folgende 18 Gleichungen
<math>a_{11}+a_{21}+a_{31}=f_0</math>
<math>a_{1i}+a_{2i}+a_{3i}=0</math> für i=2,...6
<math>a_{13}+a_{24}-a_{25}+a_{31}-a_{33}-a_{34}+a_{35}=f_1</math>
<math>a_{11}+a_{13}+a_{24}-a_{26}-a_{31}+a_{32}-a_{33}-a_{34}+a_{36}=0</math>
<math>a_{12}+a_{13}-a_{24}-a_{32}+a_{34}=0</math>
<math>a_{16}+a_{21}+a_{24}-a_{26}-a_{31}=0</math>
<math>a_{14}+a_{16}+a_{22}-a_{24}+a_{25}-a_{26}-a_{32}=0</math>
<math>a_{15}+a_{16}+a_{23}-a_{25}-a_{33}=0</math>
<math>a_{12}+a_{13}+a_{21}-a_{22}+2a_{24}-a_{25}+2a_{31}-a_{33}-2a_{34}+a_{35}=f_2</math>
<math>a_{12}+2a_{13}+a_{21}-a_{23}+a_{24}+a_{25}-a_{26}-a_{31}+2a_{32}-a_{33}-a_{34}-a_{35}+a_{36}=0</math>
<math>a_{11}+a_{12}+2a_{13}-a_{21}-a_{24}+a_{26}-a_{32}+a_{33}+a_{34}-a_{36}=0</math>
<math>a_{15}+a_{16}+a_{21}-a_{23}+2a_{24}-a_{26}-a_{31}+a_{33}+a_{34}-a_{35}=0</math>
<math>a_{15}+2a_{16}-a_{21}+a_{22}-a_{23}-a_{24}+2a_{25}-a_{26}+a_{31}-a_{32}+a_{33}+a_{34}-a_{36}=0</math>
<math>a_{14}+a_{15}+2a_{16}-a_{22}-a_{25}+a_{26}+a_{32}-a_{34}=0</math>

von dieser Koeffizientenmatrix müsste nun das Inverse gebildet werden, ich überlasse dies dem Leser:
<math>\left(
\begin{array}{cccccccccccccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 &-1 & 0 & 1 & 0 &-1 &-1 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 &-1 &-1 & 1 &-1 &-1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &-1 & 0 & 0 & 0 &-1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 &-1 &-1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 &-1 & 1 &-1 & 0 &-1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 &-1 & 0 & 0 & 0 &-1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 &-1 & 0 & 2 &-1 & 0 & 2 & 0 &-1 &-2 & 1 & 0 \\
0 & 1 & 2 & 0 & 0 & 0 & 1 & 0 &-1 & 1 & 1 &-1 &-1 & 2 &-1 &-1 &-1 & 1 \\
1 & 1 & 2 & 0 & 0 & 0 &-1 & 0 & 0 &-1 & 0 & 1 & 0 &-1 & 1 & 1 & 0 &-1 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 &-1 & 2 & 0 &-1 &-1 & 0 & 1 & 0 &-1 & 0 \\
0 & 0 & 0 & 0 & 1 & 2 &-1 & 1 &-1 &-1 & 2 &-1 & 1 &-1 & 1 & 1 & 0 &-1 \\
0 & 0 & 0 & 1 & 1 & 2 & 0 &-1 & 0 & 0 &-1 & 1 & 0 & 1 & 0 &-1 & 0 & 0 \\
\end{array}
\right)</math>

Für <math>f_0=1</math>, <math>f_1=3</math> und <math>f_2=7</math> bspw. wird <math>f_n</math> besonders überschaubar, es ist nämlich

<math>f_n=\phi_1^{n+1}+\phi_2^{n+1}+\phi_3^{n+1}</math>

Erzeugenden Funktion und Schluss


Ohne Herleitung sei hier noch die Erzeugenden Funktion der Lösungen für alle hier behandelten linearen Rekursionen angegeben, also auch für den inhomogenen Fall, da dieser ja komplett auf den homogenen zurück geführt werden kann (in diesem Fall ist dann m durch m' usw. zu ersetzen).

Es ist <math>F(z)=\sum \limits_{n=0}^{\infty} f_n z^n=\frac{\sum \limits_{i=0}^{m-1} (f_i - \sum \limits_{j=1}^i r_{m-j}f_{j-1})z^i}{1-\sum \limits_{i=1}^m r_{m-i} z^i}</math>.

Diese Funktion ist gebrochen rational, daher unproblematisch differenzierbar. Es ist
<math>f_n=F^{(n)}(0)</math>, also die n-te Ableitung von <math>F(z)</math> an der Stelle <math>z=0</math>.

So, das war's, viel Freude :)
trunx (Jens Koch)

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Allgemeine Lösung linearer Rekursionsgleichungen [von trunx]  
mit konstanten Koeffizienten Hier hatte ich bereits für relativ einfache lineare Rekursionsgleichungen (nämlich solche 2. Grades) Lösungen angegeben und in den Kommentaren weitere Lösungsideen ergänzt. Mittlerweile reicht eine solche Ergänzung nicht
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 647
 
Aufrufstatistik des Artikels
Insgesamt 1 externer Besuch in 2017.04 [Anzeigen]
DomainAnzahlProz
http://matheplanet.de1100%100 %

[Seitenanfang]

" Mathematik: Allgemeine Lösung linearer Rekursionsgleichungen" | 0 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]