Mathematik: Allgemeine Lösung linearer Rekursionsgleichungen
Released by matroid on Do. 14. Januar 2016 22:00:22 [Statistics]
Written by trunx - 1781 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\usepackage{setspace}\)

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 f_n und entsprechend allen Koeffizienten r_i aus einem Körper \mathds{K}) lautet: f_{n+m}=\sum \limits_{i=0}^{m-1} r_i f_{n+i} + g(n) (0) mit Anfangsbedingungen f_i für i=0,\dotsc,m-1. Für g(n)=0 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 g(n)=\sum \limits_{j=1}^l p_j(n) \phi^n_j, wobei p_j(n)=\sum \limits_{k=0}^{d_j} q_{jk} n^k Polynome d_j-ten Grades in n sind (hier sind die \phi_j,q_{jk} nicht notwendig in \mathds{K}, es genügt ja, wenn dies für alle g(n) der Fall ist).

Homogener Fall g(n)=0

Es gilt also zunächst f_{n+m}=\sum \limits_{i=0}^{m-1} r_i f_{n+i} (1) mit gegebenen f_i. m ist der Grad der Rekursion. Üblicherweise wird für die Lösung von linearen Rekursionsgleichungen f_n=X^n angesetzt. Eingesetzt in die Rekursionsgleichung (1) ergibt sich das sog. charakteristische Polynom P(X)=X^m-\sum \limits_{i=0}^{m-1} r_i X^i=0 (natürlich ebenfalls m-ten Grades), dessen Nullstellen \phi_j zu ermitteln sind. Diese Nullstellen sind im allgemeinen mehrfach und nicht Elemente von \mathds{K}. Mit ihrer Hilfe lässt sich das charakteristische Polynom wie folgt darstellen: P(X)=\prod \limits_{j=1}^{m_0} (X-\phi_j)^{v_j}, wobei v_j die Vielfachheit der Nullstelle \phi_j ist und m_0 \le m die Anzahl der verschiedenen Nullstellen. Der Lösungsansatz geht jetzt zunächst weiter mit einer Linearkombination der Nullstellen-Potenzen f_n=\sum \limits_{j=1}^{m_0} A_j \phi^n_j. Dabei müssen die A_j aus den Anfangsbedingungen f_i ermittelt werden. Aber es gibt zwei Probleme damit: 1. die Vielfachheit der Nullstellen ist dabei nicht berücksichtigt, daher gibt es im allgemeinen mehr f_i als A_j, das LGS ist (noch) überbestimmt. 2. allg. gilt \phi_j \notin \mathds{K}, dh. (noch) kann nicht sicher gestellt werden, dass die so ermittelten f_n in \mathds{K} landen. Das erste Problem beheben wir durch folgende Überlegung: mit einer beliebigen Nullstelle \phi_j kann die Rekursionsgleichung (1) durch die Transformation f'_n=f_{n+1}-\phi_jf_n (2) in eine Rekursionsgleichung überführt werden, deren Grad um eins gesenkt ist. Hat man für f'_n eine Lösung, so muss nur noch die einfachere Rekursion f_{n+1}=\phi_jf_n+f'_n gelöst werden. Sei jetzt \phi einzige, aber mehrfache Nullstelle mit Vielfachheit v. Dann reduzieren wir jetzt die Rekursionsgleichung mittels (2) v-1-mal, dh. wir erhalten als Rekursion f^{(v-1)}_{n+1}=\phi f^{(v-1)}_n mit der Lösung f^{(v-1)}_n=f^{(v-1)}_0\phi^n. Jetzt machen wir die Transformationen schrittweise wieder rückgängig. Es ist f^{(v-2)}_{n+1}=\phi f^{(v-2)}_n+f^{(v-1)}_0\phi^n mit der Lösung f^{(v-2)}_n=\phi^n (f^{(v-2)}_j+n\frac{f^{(v-1)}_n}{\phi}). In der Klammer ist nun ein Polynom in n, das mit jedem weiteren Rücktransformationsschritt um einen Grad steigt. Daher setzen wir besser an: 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 (3) Jetzt sind genau m Koeffizienten A_{jk} gesucht. Bevor es ans Lösen des zugehörigen LGS geht, noch folgende Bemerkung. Genau diese Kombination aus Polynom p_j(n) und Potenz \phi^n_j, 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 A_{jk}

Wie bereits gesagt, besteht bei der Ermittlung der Koeffizienten A_{jk} das Problem, dass die \phi_j und ihre Potenzen nicht notwendig Elemente aus \mathds{K} sind, die f_n dagegen schon. Aus diesem Grund ist \mathds{K} zum Zerfällungskörper \mathds{L}=\mathds{K}(\phi_1,...,\phi_{m_0}) des charakteristischen Polynoms zu erweitern und die A_{jk} sind als Elemente dieses Zerfällungskörpers anzusetzen. Allgemein lässt sich über den Grad deg(\mathds{L}) des Zerfällungskörpers wenig sagen, sind bspw. alle \phi_j \in \mathds{K}, dann ist \mathds{L}=\mathds{K}, also deg(\mathds{L})=1. Andererseits entsteht \mathds{L} ja durch die Adjunktion aller Nullstellen, sprich durch die Verknüpfungen +,-,*,/ können weitere (endlich viele) Elemente entstehen, dh. deg(\mathds{L}) kann auch maximal m_0 ! werden. Sei nun (b_1=1,b_2,...,b_{deg(\mathds{L})}) eine Basis von \mathds{L}. Dann muss jedes A_{jk} als A_{jk}=\sum \limits_{h=1}^{deg(\mathds{L})} a_{jkh} b_h angesetzt werden. Eingesetzt in (3) ergibt 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 (4), wobei wir für n=0,...,m-1 setzen. (4) ist ein lineares Gleichungssystem für die a_{jkh}. Es entsteht nicht nur durch die m Anfangsbedingungen, sondern je auch durch die deg(\mathds{L}) Komponentenvergleiche. Es sind also m*deg(\mathds{L}) Unbekannte zu ermitteln.

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

Die Bearbeitung der so gegebenen Inhomogenitäten erweist sich als recht einfach. Es genügt, das charakteristische Polynom P(X) um die in der Inhomogenität auftauchenden \phi_j als Nullstellen mit der Vielfachheit v_j=d_j(p_j(n))+1 zu erweitern, wobei d_j der Grad des Polynoms p_j(n) ist. Es ist also P'(X)=P(X) * \prod \limits_{j=1}^l (X-\phi_j)^{v_j} War bereits in P(X) ein \phi_j 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 P'(X) gehörenden Rekursion ist m'=m+ \sum \limits_{j=1}^l v_j. Die Anzahl der Unbekannten a_{jkh} 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 f_n mit n=m,...,m'-1 (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 q_{jk} gewonnen.

Beispiele

Im Prinzip ist nun alles gesagt. Im oben angegebenen Artikel ist darüberhinaus der homogene Fall m=2 ausführlich dargestellt. Dennoch können ein paar Beispiele das Ganze vielleicht noch etwas anschaulicher machen.

1. \phi mit Vielfachheit v (homogen)

Die Rekursion lautet f_{n+v}=-\sum \limits_{i=1}^v \binom{v}{i} (-\phi)^i f_{n+d-i}, das charakteristische Polynom lautet also einfach P(X) = (X - \phi)^v und der Lösungsansatz f_n = \phi^n \sum \limits_{i=0}^{v-1} a_i n^i. Gegeben sind die ersten v f_n, also für n=0,...,d-1. Das Gleichungssystem lautet daher \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} oder in Matrixschreibweise \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) 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 x_i= i-1 ist sie regulär bzw. invertierbar. für v=m=1: a_0=f_0 für v=m=2: a_0=f_0, a_1=\frac{f_1}{\phi}-f_0 für 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) usw.

2. \phi mit einfacher Vielfachheit und inhomogen mit gleichem \phi

Die Rekursion lautet f_{n+1}=\phi f_n + \phi^n \sum \limits_{i=0}^d c_i n^i. Nehmen wir jetzt konkret \phi=1 und \sum \limits_{i=0}^d c_i n^i= n, also f_{n+1}=f_n +n an. f_0 sei gegeben. Dann ist f_1=f_0 f_2=f_0+1 f_3=f_0+1+2 also f_n=f_0 +\sum \limits_{i=0}^{n-1} i=f_0 +\frac{1}{2}n(n-1). 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 v=d+1 (für den Fall, dass die Rekursion mit Vielfachheit v' auftritt, ist v=d+v').

3. \phi mit einfacher Vielfachheit und inhomogen mit anderem \phi'

Jetzt lautet die Rekursion also f_{n+1}=\phi f_n + \phi'^n \sum \limits_{i=0}^d q_i n^i. Beim Lösungsansatz müssen natürlich \phi und \phi' mit ihrer Vielfachheit v bzw. ihrem Polynomgrad d jeweils einzeln berücksichtigt werden. Es ist also f_n=a\phi^n +\phi'^n \sum \limits_{i=0}^d a_i n^i mit unbekannten a und a_i anzusetzen. Nehmen wir konkret f_{n+1} = 2f_n + n mit \phi=2 und \phi'=1, dann muss f_n=a2^2+a_1 n+a_0 angesetzt werden. Ursprünglich ist nur f_0 gegeben, da wir jedoch drei Unbekannte haben, ermitteln wir zwei weitere Vorgaben, nämlich f_1=2f_0 und f_2=4f_0+1. Damit erhalten wir für a=f_0+1 und a_1=a_0=-1. Übrigens entspricht daher die obige inhomogene Rekursion f_{n+1} = 2f_n + n mit gegebenem f_0 der homogenen Rekursion f_{n+3}=4f_{n+2}-5f_{n+1}+2f_n mit den gegebenen/zusätzlich ermittelten f_0, f_1 und f_2.

4. Fibonacci-Folge (Körpererweiterung)

Bei den bisherigen Beispielen spielte die Körpererweiterung noch keine Rolle, weil die \phi's demselben Körper angehörten wie die Folgenglieder f_n. Ein (relativ) einfaches Beispiel bei dem dies nicht mehr der Fall ist, ist die Fibonacci-Folge. Diese lautet f_{n+2}=f_{n+1}+f_n mit f_0=f_1=1 Das charakteristische Polynom für diese Rekursion ist X^2-X-1=0 mit den Nullstellen \phi_{1,2}=\frac{1}{2}(1\pm\sqrt{5}). Alle Elemente der Fibonacci-Folge sind natürliche Zahlen, der zugehörige Körper wäre also \mathds{Q}. \sqrt{5} gehört nun nicht dazu, entsprechend muss der Körper, in dem der Lösungsansatz zu formulieren ist, erweitert werden zu \mathds{Q}[\sqrt{5}]. Der Lösungsansatz lautet daher 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), also mit A, B \in \mathds{Q}[\sqrt{5}]. Es ergeben sich durch die Anfangsbedingungen A_1+A_2\sqrt{5}+B_1+B_2\sqrt{5}=1 \frac{1}{2}((A_1+A_2\sqrt{5})(1+\sqrt{5})+(B_1+B_2\sqrt{5})(1-\sqrt{5}))=1 und daraus durch Komponentenvergleich folgende 4 Gleichungen: A_1+B_1=1 A_2+B_2=0 A_1+5A_2+B_1-5B_2=2 A_1+A_2-B_1+B_2=0 mit der Lösung A=\frac{1}{2}(1+\frac{\sqrt{5}}{5}) B=\frac{1}{2}(1-\frac{\sqrt{5}}{5}), also f_n=\frac{\sqrt{5}}{5*2^{n+1}}((1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1})

5. inhomogene Fibonacci-Folge

Schauen wir uns nun an, was passiert, wenn die Rekursion der Fibonacci-Folge inhomogen wird. Sei z.B. f'_{n+2}=f'_{n+1}+f'_n +c wieder mit f'_0=f'_1=1, sprich wir addieren stets noch eine Konstante dazu. Nach dem bisherigen kommt durch die Inhomogenität die "Nullstelle" \phi=1 hinzu, der Polynomgrad der Konstante ist d=0. Da \phi keine Nullstelle der homogenen Rekursion f_n 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 f'_2=2+c. Insgesamt haben wir also als Ansatz 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 und als Gleichungen A_1+A_2\sqrt{5}+B_1+B_2\sqrt{5}+C=1 \frac{1}{2}((A_1+A_2\sqrt{5})(1+\sqrt{5})+(B_1+B_2\sqrt{5})(1-\sqrt{5}))+C=1 \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 und daraus durch Komponentenvergleich folgende 5 Gleichungen: A_1+B_1+C=1 A_2+B_2=0 A_1+5A_2+B_1-5B_2+2C=2 A_1+A_2-B_1+B_2=0 3A_1+5A_2+C=2+c mit der Lösung f'_n = (1+c)f_n - c, wobei f_n 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 \"{x}+2\gamma\.{x}+\omega^2_0x=0 mit den Anfangsbedingungen x0 und \.x_0=v_0 wobei \gamma\ge 0 die Abklingkonstante und \omega_0 die Resonanzfrequenz des Oszillators ist. Für den Fall \gamma=0 ist der harmonische Oszillator ohne Dämpfung. Mit der Zeit t=n\tau und dem Zeitintervall \tau werden die Zeitableitungen jetzt diskretisiert, also als Differenzenquotienten geschrieben: \.{x}=\frac{x_{(n+1)\tau}-x_{n\tau}}{\tau} \"{x}=\frac{x_{(n+2)\tau}-2x_{(n+1)\tau}+x_{n\tau}}{\tau^2} Eingesetzt in die Gleichung für den harmonischen Oszillator ergibt folgende Rekursion 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 bzw. x_{(n+2)\tau}=2(1-\gamma\tau)x_{(n+1)\tau}-(1-2\gamma\tau+\omega^2_0\tau^2)x_{n\tau} Für \gamma=0, also den ungedämpften Fall haben wir einfach x_{(n+2)\tau}=2x_{(n+1)\tau}-(1+\omega^2_0\tau^2)x_{n\tau} Die Anfangsbedingungen sind x_0 und x_{\tau}=x_0+v_0\tau. Wir lösen zuerst den ungedämpften Fall. Das charakteristische Polynom lautet dafür: X^2-2X+1+\omega^2_0\tau^2=0 und hat als Nullstellen \phi_{1,2}=1\pm\omega_0\tau i, wobei i natürlich die imaginäre Einheit ist. Hier ist der Grundkörper \mathds{K}=\mathds{R}, der um i erweitert werden muss, dh. es ist \mathds{L}=\mathds{C}. Um jetzt weiter zu kommen, gehen wir von der Form z=a+bi über zur Form z=\rho e^{i\alpha}. Die Nullstellen sind folglich \phi_{1,2}=\sqrt{1+\omega^2_0\tau^2}e^{\pm arctan(\omega_0\tau) i}. Damit lautet der Ansatz für x 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}). Mit den Anfangsbedingungen werden wieder die A_i und B_i ermittelt zu A_1=B_1=\frac{x_0}{2} und 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}. Zusammen also 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)). Dies ist die exakte diskrete Lösung. Für sehr kleine \tau, also \omega_0\tau\ll1 wird diese zu x_{n\tau}=x_0 cos(\omega_0n\tau)+\frac{v_0}{\omega_0} sin(\omega_0n\tau). Setzen wir darüber hinaus wieder die Zeit als t=n\tau, erhalten wir x(t)=x_0 cos(\omega_0t)+\frac{v_0}{\omega_0} sin(\omega_0t), wie man es mit analytischen Mitteln erhalten würde. Interessant finde ich hieran, dass der exponentielle Ansatz durch die Körpererweiterung zu \mathds{C} letztlich zu einer periodischen Funktion führte. Schauen wir uns nun den gedämpften harmonischen Oszillator an. Das charakteristische Polynom lautet: X^2-2(1-\gamma\tau)X+1-2\gamma\tau+\omega^2_0\tau^2=0 mit den Nullstellen \phi_{1,2}=1-\tau (\gamma\mp\sqrt{\gamma^2-\omega^2_0}). Bekanntlich gibt es jetzt drei Fälle a) den stark gedämpften Fall \gamma > \omega_0 (Kriechfall), b) den aperiodischen Grenzfall \gamma = \omega_0 und c) den Schwingfall mit \gamma < \omega_0. Für den stark gedämpften Fall liegen beide Nullstellen in \mathds{R}, s.d. als Lösungsansatz einfach 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 in Frage kommt. Mit den Anfangsbedingungen ergibt sich a_{1,2}=\frac{x_0(\sqrt{\gamma^2-\omega^2_0}\pm\gamma)\pm v_0}{2\sqrt{\gamma^2-\omega^2_0}}, zusammen also 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 ) Wird jetzt wieder der Grenzfall für kleine \tau betrachtet, setzt man Terme der Form 1+z\tau=e^{z\tau}. Damit wird 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}} ) Mit t=n\tau erhält man daraus wieder die klassische Lösung. Für den aperiodischen Grenzfall ist \gamma = \omega_0, d.h. mathematisch, dass es nur noch eine Nullstelle, nämlich \phi=1-\tau\gamma mit zweifacher Vielfachheit gibt. Der Ansatz lautet entsprechend x_{n\tau}=(a_1+na_2)(1-\tau\gamma)^n und mit der Auswertung der Anfangsbedingungen x_{n\tau}=(x_0+\frac{n\tau(v_0+x_0\gamma)}{1-\tau\gamma})(1-\tau\gamma)^n als exakter Lösung und für kleine \tau x_{n\tau}=(x_0+n\tau(v_0+x_0\gamma))e^{-n\tau\gamma} bzw. mit t=n\tau x(t)=(x_0+(v_0+x_0\gamma)t)e^{-\gamma t} Für den letzten Fall \gamma < \omega_0 wird \sqrt{\omega^2_0 -\gamma^2}=\omega_D gesetzt. Das zugehörige charakteristische Polynom hat wieder zwei komplexe Nullstellen und wieder wird eine (diesmal gedämpfte) Schwingung mit der veränderten Frequenz \omega_D durch die Verlagerung des Problems in den Erweiterungskörper \mathds{C} 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 \mathds{L} spart man sich eine Menge Rechenarbeit. Die Rekursion sieht zunächst wie folgt aus: f_{n+3}=f_{n+2}+f_{n+1}+f_n mit gegebenen f_0, f_1 und f_2. Das charakteristische Polynom lautet X^3-X^2-X-1=0 und hat folgende Nullstellen: \phi_1=\frac{1}{3}(\sqrt[3]{19+\sqrt{297}}+1+\frac{4}{\sqrt[3]{19+\sqrt{297}}}) \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}}}) Der Lösungsansatz muss jetzt wieder im Zerfällungskörper \mathds{L} formuliert werden. Um wie gesagt Arbeit zu sparen, setzen wir als Basis von \mathds{L} B_{\mathds{L}}=(1,\phi_1,\phi_1^2,\phi_2,\phi_1\phi_2,\phi_1^2\phi_2) Der Körpergrad ist [\mathds{L}:\mathds{Q}]=6. Der Lösungsansatz lautet: f_n=\sum \limits_{i=1}^3 A_i \phi_i^n mit A_i \in \mathds{L}, also A_i=\sum \limits_{j=1}^6 a_{ij}b_j. Wir benutzen weiterhin den Satz von Vieta \phi_1+\phi_2+\phi_3=1 \phi_1\phi_2+\phi_1\phi_3+\phi_2\phi_3=-1 \phi_1\phi_2\phi_3=1 sowie \phi_i^3=\phi_i^2+\phi_i+1. Damit erhalten wir u.a. \phi_3=1-\phi_1-\phi_2 \phi_2\phi_3=\phi_1^2-\phi_1-1 \phi_2^2=1+\phi_1-\phi_1^2+\phi_2-\phi_1\phi_2 \phi_3^2=2-\phi_1-\phi_2+\phi_1\phi_2 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 a_{11}+a_{21}+a_{31}=f_0 a_{1i}+a_{2i}+a_{3i}=0 für i=2,...6 a_{13}+a_{24}-a_{25}+a_{31}-a_{33}-a_{34}+a_{35}=f_1 a_{11}+a_{13}+a_{24}-a_{26}-a_{31}+a_{32}-a_{33}-a_{34}+a_{36}=0 a_{12}+a_{13}-a_{24}-a_{32}+a_{34}=0 a_{16}+a_{21}+a_{24}-a_{26}-a_{31}=0 a_{14}+a_{16}+a_{22}-a_{24}+a_{25}-a_{26}-a_{32}=0 a_{15}+a_{16}+a_{23}-a_{25}-a_{33}=0 a_{12}+a_{13}+a_{21}-a_{22}+2a_{24}-a_{25}+2a_{31}-a_{33}-2a_{34}+a_{35}=f_2 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 a_{11}+a_{12}+2a_{13}-a_{21}-a_{24}+a_{26}-a_{32}+a_{33}+a_{34}-a_{36}=0 a_{15}+a_{16}+a_{21}-a_{23}+2a_{24}-a_{26}-a_{31}+a_{33}+a_{34}-a_{35}=0 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 a_{14}+a_{15}+2a_{16}-a_{22}-a_{25}+a_{26}+a_{32}-a_{34}=0 von dieser Koeffizientenmatrix müsste nun das Inverse gebildet werden, ich überlasse dies dem Leser: \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) Für f_0=1, f_1=3 und f_2=7 bspw. wird f_n besonders überschaubar, es ist nämlich f_n=\phi_1^{n+1}+\phi_2^{n+1}+\phi_3^{n+1}

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 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}. Diese Funktion ist gebrochen rational, daher unproblematisch differenzierbar. Es ist f_n=F^{(n)}(0), also die n-te Ableitung von F(z) an der Stelle z=0. So, das war's, viel Freude :) trunx (Jens Koch)
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
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]

 
 
Aufrufzähler 1781
 
Aufrufstatistik des Artikels
Insgesamt 529 externe Seitenaufrufe zwischen 2018.05 und 2021.11 [Anzeigen]
DomainAnzahlProz
https://google.com7013.2%13.2 %
https://startpage.com10.2%0.2 %
https://duckduckgo.com417.8%7.8 %
https://www.bing.com193.6%3.6 %
https://google.de37470.7%70.7 %
https://www.ecosia.org183.4%3.4 %
https://www.qwant.com20.4%0.4 %
https://www.startpage.com20.4%0.4 %
http://google.com10.2%0.2 %
https://blue-search.org10.2%0.2 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 24 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.11.02-2021.11.30 (24x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 488 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (355x)https://google.de/
2020-2021 (46x)https://google.com/
2020-2021 (36x)https://duckduckgo.com/
2020-2021 (18x)https://www.bing.com/
2020-2021 (17x)https://www.ecosia.org/
202110-10 (16x)https://google.de

[Top of page]

"Mathematik: Allgemeine Lösung linearer Rekursionsgleichungen" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]