Wiederholungsbeziehung - Recurrence relation

In der Mathematik ist eine Rekursionsbeziehung eine Gleichung , die rekursiv eine Folge oder ein mehrdimensionales Array von Werten definiert, sobald ein oder mehrere Anfangsterme derselben Funktion gegeben sind; jeder weitere Term der Sequenz oder des Arrays wird als Funktion der vorhergehenden Terme derselben Funktion definiert.

Der Begriff Differenzengleichung bezieht sich manchmal (und für die Zwecke dieses Artikels) auf eine bestimmte Art von Wiederholungsbeziehung. "Differenzgleichung" wird jedoch häufig verwendet, um sich auf eine beliebige Wiederholungsbeziehung zu beziehen .

Definition

Eine Rekursionsbeziehung ist eine Gleichung, die jedes Element einer Sequenz als Funktion der vorhergehenden ausdrückt. Genauer gesagt, für den Fall, dass nur das unmittelbar vorangehende Element beteiligt ist, hat eine Rekursionsbeziehung die Form

${\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{für}}\quad n>0,}$

wo

${\displaystyle \varphi :\mathbb{N} \times X\to X}$

ist eine Funktion, wobei X eine Menge ist, zu der die Elemente einer Folge gehören müssen. Für any definiert dies eine eindeutige Sequenz mit dem ersten Element, dem sogenannten Anfangswert . ${\displaystyle u_{0}\in X}$${\displaystyle u_{0}}$

Es ist einfach, die Definition für das Abrufen von Sequenzen ab dem Begriff des Index 1 oder höher zu ändern.

Dies definiert eine Rekursionsbeziehung erster Ordnung . Eine Rekursionsrelation der Ordnung k hat die Form

${\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots,u_{nk})\quad {\text{for}}\quad n\geq k ,}$

wobei eine Funktion ist, die k aufeinanderfolgende Elemente der Folge umfasst. In diesem Fall werden k Anfangswerte benötigt, um eine Sequenz zu definieren. ${\displaystyle \varphi :\mathbb{N} \times X^{k}\to X}$

Beispiele

Fakultät

Die Fakultät wird durch die Wiederholungsrelation definiert

${\displaystyle n!=n(n-1)!\quad {\text{für}}\quad n>0,}$

und die Anfangsbedingung

${\displaystyle 0!=1.}$

Logistikkarte

Ein Beispiel für eine Wiederholungsbeziehung ist die logistische Karte :

${\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}$

mit einer gegebenen Konstanten r ; bei gegebenem Anfangsterm x _{0 wird} jeder nachfolgende Term durch diese Beziehung bestimmt.

Eine Rekursionsbeziehung zu lösen bedeutet, eine geschlossene Lösung zu erhalten : eine nicht-rekursive Funktion von n .

Fibonacci-Zahlen

Die von den Fibonacci-Zahlen erfüllte Rekursion zweiter Ordnung ist das kanonische Beispiel einer homogenen linearen Rekursionsbeziehung mit konstanten Koeffizienten (siehe unten). Die Fibonacci-Folge wird mit der Rekursion

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

mit Anfangsbedingungen

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1.}$

Explizit liefert die Rekursion die Gleichungen

${\displaystyle F_{2}=F_{1}+F_{0}}$

${\displaystyle F_{3}=F_{2}+F_{1}}$

${\displaystyle F_{4}=F_{3}+F_{2}}$

etc.

Wir erhalten die Folge von Fibonacci-Zahlen, die beginnt

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Die Rekursion kann durch die unten beschriebenen Methoden gelöst werden, die die Binet-Formel ergeben , die Potenzen der beiden Wurzeln des charakteristischen Polynoms t ²  =  t  + 1 beinhaltet; die erzeugende Funktion der Folge ist die rationale Funktion

${\displaystyle {\frac {t}{1-tt^{2}}}.}$

Binomialkoeffizienten

Ein einfaches Beispiel für eine mehrdimensionale Rekursionsbeziehung sind die Binomialkoeffizienten , die die Anzahl der Möglichkeiten zur Auswahl von k Elementen aus einer Menge von n Elementen zählen. Sie können durch die Rekursionsrelation berechnet werden ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$

mit den Basisfällen . Wenn Sie diese Formel verwenden, um die Werte aller Binomialkoeffizienten zu berechnen, wird ein unendliches Array namens Pascal-Dreieck erzeugt . Dieselben Werte können auch direkt durch eine andere Formel berechnet werden, die keine Wiederholung ist, aber zur Berechnung Multiplikation und nicht nur Addition erfordert: ${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(nk)!}}.}$

Beziehung zu Differenzengleichungen eng definiert

Gegeben eine geordnete Folge von reellen Zahlen : die erste Differenz ist definiert als ${\displaystyle \left\{a_{n}\right\}_{n=1}^{\infty}}$ ${\displaystyle \Delta (a_{n})}$

${\displaystyle \Updelta (a_{n})=a_{n+1}-a_{n}.}$

Der zweite Unterschied ist definiert als ${\displaystyle \Delta^{2}(a_{n})}$

${\displaystyle \Updelta ^{2}(a_{n})=\Updelta (a_{n+1})-\Updelta (a_{n}),}$

was vereinfacht werden kann zu

${\displaystyle \Delta^{2}(a_{n})=a_{n+2}-2a_{n+1}+a_{n}.}$

Allgemeiner: die k- te Differenz der Folge a _n geschrieben als ist rekursiv definiert als ${\displaystyle \Delta^{k}(a_{n})}$

${\displaystyle \Updelta ^{k}(a_{n})=\Updelta ^{k-1}(a_{n+1})-\Updelta ^{k-1}(a_{n})=\sum _{t=0}^{k}{\binom {k}{t}}(-1)^{t}a_{n+kt}.}$

(Die Folge und ihre Differenzen werden durch eine Binomialtransformation in Beziehung gesetzt .) Die restriktivere Definition der Differenzengleichung ist eine Gleichung, die aus a _n und ihren k- ^ten Differenzen besteht. (Eine weit verbreitete breitere Definition behandelt "Differenzgleichung" als Synonym für "Wiederkehrbeziehung". Siehe zum Beispiel rationale Differenzgleichung und Matrixdifferenzgleichung .)

Eigentlich ist es leicht zu erkennen,

${\displaystyle a_{n+k}={k \choose 0}a_{n}+{k \choose 1}\Updelta (a_{n})+\cdots +{k\choose k}\Updelta ^{k }(ein}).}$

Somit kann eine Differenzengleichung als eine Gleichung definiert werden, die a _n , a _{n –1} , a _{n -2} usw. (oder äquivalent a _n , a _{n +1} , a _{n +2} usw.) umfasst.

Da Differenzengleichungen eine sehr häufige Form der Wiederholung sind, verwenden einige Autoren die beiden Begriffe synonym. Zum Beispiel die Differenzengleichung

${\displaystyle 3\Updelta ^{2}(a_{n})+2\Updelta (a_{n})+7a_{n}=0}$

entspricht der Rekursionsrelation

${\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n}.}$

So kann man viele Rekursionsbeziehungen lösen, indem man sie als Differenzengleichungen umformuliert und dann die Differenzengleichung löst, analog wie man gewöhnliche Differenzialgleichungen löst . Die Ackermann-Zahlen sind jedoch ein Beispiel für eine Rekursionsbeziehung, die sich nicht auf eine Differenzengleichung abbilden lässt, geschweige denn Punkte auf der Lösung einer Differenzialgleichung.

Siehe Zeitskalenrechnung für eine Vereinheitlichung der Theorie der Differenzengleichungen mit der der Differentialgleichungen .

Summengleichungen beziehen sich auf Differenzengleichungen, wie sich Integralgleichungen auf Differentialgleichungen beziehen.

Von Sequenzen zu Rastern

Bei eindimensionalen Rekursionsbeziehungen handelt es sich um Sequenzen (dh Funktionen, die auf eindimensionalen Gittern definiert sind). Bei multivariablen oder n-dimensionalen Rekursionsbeziehungen handelt es sich um n-dimensionale Gitter. Auf n-Gittern definierte Funktionen können auch mit partiellen Differenzengleichungen untersucht werden .

Lösen

Lösung homogener linearer Rekursionsbeziehungen mit konstanten Koeffizienten

Wurzeln des charakteristischen Polynoms

Eine homogene lineare Rekursion der Ordnung d mit konstanten Koeffizienten ist eine Gleichung der Form

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{nd},}$

wobei die d Koeffizienten c _i (für alle i ) Konstanten sind, und . ${\displaystyle c_{d}\neq 0}$

Eine konstant-rekursive Folge ist eine Folge, die eine Wiederholung dieser Form erfüllt. Es gibt d Freiheitsgrade für Lösungen dieser Rekursion, dh die Anfangswerte können als beliebige Werte angenommen werden, aber dann bestimmt die Rekursion die Reihenfolge eindeutig. ${\displaystyle a_{0},\dots ,a_{d-1}}$

Dieselben Koeffizienten ergeben das charakteristische Polynom (auch "Hilfspolynom" oder "Begleitpolynom")

${\displaystyle p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}$

deren d- Wurzeln eine entscheidende Rolle beim Finden und Verstehen der Sequenzen spielen, die die Rezidive befriedigen. Wenn die Wurzeln r ₁ , r ₂ , ... alle verschieden sind, dann hat jede Lösung der Rekursion die Form

${\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n}, }$

wobei die Koeffizienten k _i bestimmt werden, um den Anfangsbedingungen der Wiederholung zu entsprechen. Wenn dieselben Wurzeln mehrfach vorkommen, werden die Terme in dieser Formel, die dem zweiten und späteren Auftreten derselben Wurzel entsprechen, mit zunehmenden Potenzen von n multipliziert . Wenn beispielsweise das charakteristische Polynom als ( x − r ) ³ faktorisiert werden kann , wobei dieselbe Wurzel r dreimal vorkommt, dann würde die Lösung die Form . annehmen

${\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}$

Neben den Fibonacci-Zahlen umfassen andere konstant-rekursive Folgen die Lucas-Zahlen und Lucas-Folgen , die Jacobsthal-Zahlen , die Pell-Zahlen und allgemeiner die Lösungen der Pell-Gleichung .

Bei Bestellung 1 die Wiederholung

${\displaystyle a_{n}=ra_{n-1}}$

hat die Lösung a _n  =  r ⁿ mit a ₀  = 1 und die allgemeinste Lösung ist a _n  =  kr ⁿ mit a ₀  =  k . Das charakteristische Polynom gleich Null (die charakteristische Gleichung ) ist einfach t  −  r  = 0.

Lösungen für solche Rekursionsbeziehungen höherer Ordnung werden systematisch gefunden, oft unter Ausnutzung der Tatsache, dass a _n  =  r ⁿ genau dann eine Lösung für die Rekursion ist, wenn t  =  r eine Wurzel des charakteristischen Polynoms ist. Dies kann direkt oder über erzeugende Funktionen ( formale Potenzreihen ) oder Matrizen angegangen werden .

Betrachten wir zum Beispiel eine Rekursionsrelation der Form

${\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}$

Wann hat es eine Lösung der gleichen allgemeinen Form wie a _n = r ⁿ ? Setzen wir diese Vermutung ( ansatz ) in die Rekursionsrelation ein, so finden wir, dass

${\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}$

muss für alle  n  > 1 wahr sein .

Wenn wir durch r ^{n −2 dividieren} , erhalten wir, dass alle diese Gleichungen auf dasselbe reduziert werden:

${\displaystyle r^{2}=Ar+B,}$

${\displaystyle r^{2}-Ar-B=0,}$

das ist die charakteristische Gleichung der Rekursionsbeziehung. Lösen Sie nach r auf, um die beiden Wurzeln λ ₁ , λ _{2 zu erhalten} : Diese Wurzeln werden als charakteristische Wurzeln oder Eigenwerte der charakteristischen Gleichung bezeichnet. Je nach Art der Wurzeln erhält man unterschiedliche Lösungen: Sind diese Wurzeln verschieden, haben wir die allgemeine Lösung

${\displaystyle a_{n}=C\lambda_{1}^{n}+D\lambda_{2}^{n}}$

während, wenn sie identisch sind (wenn A ² + 4 B = 0 ), gilt

${\displaystyle a_{n}=C\lambda^{n}+Dn\lambda^{n}}$

Dies ist die allgemeinste Lösung; die beiden Konstanten C und D können basierend auf zwei gegebenen Anfangsbedingungen a ₀ und a _{1 gewählt werden} , um eine spezifische Lösung zu erzeugen.

Bei komplexen Eigenwerten (aus denen sich auch komplexe Werte für die Lösungsparameter C und D ergeben ) kann auf die Verwendung komplexer Zahlen verzichtet werden, indem die Lösung in trigonometrischer Form umgeschrieben wird. In diesem Fall können wir die Eigenwerte schreiben als Dann kann gezeigt werden, dass ${\displaystyle \lambda_{1},\lambda_{2}=\alpha\pm\beta i.}$

${\displaystyle a_{n}=C\lambda_{1}^{n}+D\lambda_{2}^{n}}$

kann umgeschrieben werden als

${\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\ Delta ),}$

wo

${\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha^{2}+\beta^{2}}}&\cos(\theta)={\tfrac {\alpha }{M }}&\sin(\theta)={\tfrac {\beta}{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2} }}&\cos(\delta)={\tfrac{E}{G}}&\sin(\delta)={\tfrac{F}{G}}\end{array}}}$

Dabei sind E und F (oder äquivalent G und δ) reelle Konstanten, die von den Anfangsbedingungen abhängen. Verwenden von

${\displaystyle \lambda_{1}+\lambda_{2}=2\alpha=A,}$

${\displaystyle \lambda_{1}\cdot \lambda_{2}=\alpha^{2}+\beta^{2}=-B,}$

man kann die oben gegebene Lösung vereinfachen als

${\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}$

wobei a ₁ und a ₂ die Anfangsbedingungen sind und

${\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}- Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{ausgerichtet}}}$

Auf diese Weise muss nicht nach λ ₁ und λ _{2 aufgelöst werden} .

In allen Fällen – reelle unterschiedliche Eigenwerte, reelle duplizierte Eigenwerte und komplex konjugierte Eigenwerte – ist die Gleichung stabil (d. h. die Variable a konvergiert gegen einen festen Wert [insbesondere Null]), wenn und nur dann, wenn beide Eigenwerte kleiner als eins in . sind absoluter Wert . In diesem Fall zweiter Ordnung kann gezeigt werden, dass diese Bedingung an den Eigenwerten äquivalent zu | . ist A | < 1 −  B  < 2, was | . entspricht B | < 1 und | A | < 1 −  B .

Die Gleichung im obigen Beispiel war homogen , da es keinen konstanten Term gab. Wenn man mit dem inhomogenen Rezidiv beginnt

${\displaystyle b_{n}=Ab_{n-1}+Bb_{n-2}+K}$

mit konstantem Term K kann dies wie folgt in eine homogene Form überführt werden: Der stationäre Zustand ergibt sich durch Setzen von b _n =  b _{n −1} =  b _{n −2} =  b * zu

${\displaystyle b^{*}={\frac {K}{1-AB}}.}$

Dann kann die inhomogene Rekursion in homogener Form umgeschrieben werden als

${\displaystyle [b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}],}$

was wie oben gelöst werden kann.

Die oben angeführte Stabilitätsbedingung in Form von Eigenwerten für den Fall zweiter Ordnung bleibt für den allgemeinen Fall n- ^ter Ordnung gültig : Die Gleichung ist genau dann stabil, wenn alle Eigenwerte der charakteristischen Gleichung betragsmäßig kleiner als eins sind.

Bei einer homogenen linearen Rekursion mit konstanten Koeffizienten der Ordnung d sei p ( t ) das charakteristische Polynom (auch "Hilfspolynom")

${\displaystyle t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}=0}$

so dass jedes c _i jedem c _i in der ursprünglichen Rekursionsbeziehung entspricht (siehe die allgemeine Form oben). Angenommen ist eine Wurzel von p ( t ) mit der Multiplizität r . Dies bedeutet, dass ( t −λ) ^r p ( t ) teilt . Es gelten die folgenden beiden Eigenschaften:

1. Jede der r Folgen erfüllt die Wiederholungsbeziehung.${\displaystyle \lambda^{n},n\lambda^{n},n^{2}\lambda^{n},\dots,n^{r-1}\lambda^{n}}$
2. Jede Sequenz Erfüllen der Rekursion eindeutig als eine lineare Kombination von Lösungen in Teil 1 konstruiert geschrieben werden als λ variiert über alle verschiedene Wurzeln von  P ( t ).

Als Ergebnis dieses Satzes kann eine homogene lineare Rekursionsbeziehung mit konstanten Koeffizienten wie folgt gelöst werden:

1. Finden Sie das charakteristische Polynom p ( t ).
2. Finden Sie die Wurzeln von p ( t ), indem Sie die Multiplizität zählen.
3. Schreiben Sie a _n als Linearkombination aller Nullstellen (Zählung der Multiplizität wie im obigen Satz gezeigt) mit unbekannten Koeffizienten b _i .

   ${\displaystyle a_{n}=\left(b_{1}\lambda_{1}^{n}+b_{2}n\lambda_{1}^{n}+b_{3}n^{2 }\lambda_{1}^{n}+\cdots +b_{r}n^{r-1}\lambda_{1}^{n}\right)+\cdots +\left(b_{d- q+1}\lambda_{*}^{n}+\cdots +b_{d}n^{q-1}\lambda_{*}^{n}\right)}$

   Dies ist die allgemeine Lösung der ursprünglichen Rekursionsbeziehung. ( q ist die Vielfachheit von λ _* )

4. Gleichen Sie jeweils aus Teil 3 ( Einsetzen von n = 0, ..., d in die allgemeine Lösung der Rekursionsrelation) mit den bekannten Werten aus der ursprünglichen Rekursionsrelation aus. Die Werte a _n aus der verwendeten ursprünglichen Rekursionsrelation müssen jedoch in der Regel nicht zusammenhängend sein: Ausgenommen von Ausnahmefällen werden nur d davon benötigt (dh für eine ursprüngliche homogene lineare Rekursionsrelation der Ordnung 3 könnte man die Werte a ₀ , a ₁ , a ₄ ). Dieser Prozess erzeugt ein lineares System von d Gleichungen mit d Unbekannten. Das Auflösen dieser Gleichungen nach den unbekannten Koeffizienten der allgemeinen Lösung und das Wiedereinsetzen dieser Werte in die allgemeine Lösung ergibt die spezielle Lösung der ursprünglichen Rekursionsbeziehung, die zu den Anfangsbedingungen der ursprünglichen Rekursionsbeziehung passt (sowie alle nachfolgenden Werte der ursprünglichen Rekursionsbeziehung fits ).${\displaystyle a_{0},a_{1},\dots ,a_{d}}$${\displaystyle a_{0},a_{1},\dots ,a_{d}}$${\displaystyle b_{1},b_{2},\dots,b_{d}}$${\displaystyle a_{0},a_{1},a_{2},\dots}$

Die Methode zum Lösen linearer Differentialgleichungen ist der obigen Methode ähnlich – die "intelligente Schätzung" ( Ansatz ) für lineare Differentialgleichungen mit konstanten Koeffizienten ist e ^{λ x} wobei λ eine komplexe Zahl ist, die durch Einsetzen der Schätzung in die Differentialgleichung bestimmt wird .

Dies ist kein Zufall. Betrachten Sie die Taylor-Reihe der Lösung einer linearen Differentialgleichung:

${\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(xa)^{n}}$

es ist ersichtlich, dass die Koeffizienten der Reihe durch die n- ^te Ableitung von f ( x ) gegeben sind, die am Punkt a ausgewertet wird . Die Differenzialgleichung stellt eine lineare Differenzengleichung bereit, die diese Koeffizienten in Beziehung setzt.

Diese Äquivalenz kann verwendet werden, um die Rekursionsbeziehung für die Koeffizienten in der Potenzreihenlösung einer linearen Differentialgleichung schnell aufzulösen.

Die Faustregel (für Gleichungen, in denen das Polynom, das den ersten Term multipliziert, bei Null ungleich Null ist) lautet:

${\displaystyle y^{[k]}\to f[n+k]}$

und allgemeiner

${\displaystyle x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+km]}$

Beispiel: Die Rekursionsbeziehung für die Taylor-Reihenkoeffizienten der Gleichung:

${\displaystyle (x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0}$

wird gegeben von

${\displaystyle n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0 }$

oder

${\displaystyle -4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.}$

Dieses Beispiel zeigt, wie Probleme, die im Allgemeinen mit der in normalen Differentialgleichungsklassen gelehrten Potenzreihenlösungsmethode gelöst werden, viel einfacher gelöst werden können.

Beispiel: Die Differentialgleichung

${\displaystyle ay''+by'+cy=0}$

hat Lösung

${\displaystyle y=e^{ax}.}$

Die Umrechnung der Differenzialgleichung in eine Differenzengleichung der Taylor-Koeffizienten ist

${\displaystyle af[n+2]+bf[n+1]+cf[n]=0.}$

Es ist leicht zu erkennen, dass die n- te Ableitung von e ^ax, die bei 0 ausgewertet wird, a ^{n ist} .

Lösen über lineare Algebra

Eine linear rekursive Folge y der Ordnung n

${\displaystyle y_{n+k}-c_{n-1}y_{n-1+k}-c_{n-2}y_{n-2+k}+\cdots -c_{0}y_{k }=0}$

ist identisch mit

${\displaystyle y_{n}=c_{n-1}y_{n-1}+c_{n-2}y_{n-2}+\cdots +c_{0}y_{0}.}$

Erweitert mit n −1 Identitäten der Art wird diese Gleichung n- ter Ordnung in ein Matrixdifferenz-Gleichungssystem von n linearen Gleichungen erster Ordnung übersetzt, ${\displaystyle y_{nk}=y_{nk}}$

${\displaystyle \mathbf {y} _{n}={\begin{bmatrix}y_{n}\\y_{n-1}\\\vdots \\\vdots \\y_{1}\end{bmatrix} }={\begin{bmatrix}c_{n-1}&c_{n-2}&\cdots &\cdots &c_{0}\\1&0&\cdots &\cdots &0\\0&\ddots &\ddots &&\vdots \\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&1&0\end{bmatrix}}{\begin{bmatrix}y_{n-1}\\y_{n-2}\\ \vdots \\\vdots \\y_{0}\end{bmatrix}}=C\mathbf {y} _{n-1}=C^{n}\mathbf {y} _{0}.}$

Beachten Sie, dass der Vektor durch n Anwendungen der Begleitmatrix , C , auf den Anfangszustandsvektor , berechnet werden kann . Dabei ist der n- te Eintrag der gesuchten Folge y die oberste Komponente von . ${\displaystyle \mathbf{y}_{n}}$${\displaystyle y_{0}}$${\displaystyle \mathbf{y}_{n},y_{n}=\mathbf{y}_{n}[n]}$

Die Eigenzerlegung , in Eigenwerte, und Eigenvektoren , wird verwendet, um zu berechnen . Dank der entscheidenden Tatsache, dass das System C jeden Eigenvektor e zeitversetzt , indem es einfach seine Komponenten λ mal skaliert , ${\displaystyle \mathbf {y} _{n}=C^{n}\,\mathbf {y} _{0}=a_{1}\,\lambda_{1}^{n}\,\mathbf {e} _{1}+a_{2}\,\lambda_{2}^{n}\,\mathbf {e}_{2}+\cdots +a_{n}\,\lambda_{n }^{n}\,\mathbf{e}_{n}}$${\displaystyle \lambda_{1},\lambda_{2},\ldots,\lambda_{n}}$${\displaystyle \mathbf {e} _{1},\mathbf {e} _{2},\ldots ,\mathbf {e} _{n}}$${\displaystyle \mathbf{y}_{n}}$

${\displaystyle C\,\mathbf{e}_{i}=\lambda_{i}\mathbf{e}_{i}=C{\begin{bmatrix}e_{i,n}\\e_{i ,n-1}\\\vdots \\e_{i,1}\end{bmatrix}}={\begin{bmatrix}\lambda _{i}\,e_{i,n}\\\lambda _{ i}\,e_{i,n-1}\\\vdots \\\lambda_{i}\,e_{i,1}\end{bmatrix}}}$

das heißt, zeitverschobene Version des Eigenvektors, e , hat Komponenten λ - mal größer ist , werden die Eigenvektor - Komponenten sind Potenzen von λ , und somit wiederkehrende homogene lineare Gleichungslösung eine Kombination von Exponentialfunktionen ist . Aus den Anfangsbedingungen können die Komponenten bestimmt werden: ${\displaystyle \mathbf {e}_{i}={\begin{bmatrix}\lambda_{i}^{n-1}&\cdots &\lambda_{i}^{2}&\lambda_{ i}&1\end{bmatrix}}^{\mathrm{T}},}$${\displaystyle \mathbf{y}_{n}=\sum_{1}^{n}{c_{i}\,\lambda_{i}^{n}\,\mathbf{e}_{i }}}$${\displaystyle c_{i}}$

${\displaystyle \mathbf {y} _{0}={\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}= \sum_{i=1}^{n}{c_{i}\,\lambda_{i}^{0}\,\mathbf{e}_{i}}={\begin{bmatrix}\mathbf {e} _{1}&\mathbf {e} _{2}&\cdots &\mathbf {e} _{n}\end{bmatrix}}\,{\begin{bmatrix}c_{1}\\ c_{2}\\\vdots \\c_{n}\end{bmatrix}}=E\,{\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n} \end{bmatrix}}}$

Auflösen nach Koeffizienten,

${\displaystyle {\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}=E^{-1}\mathbf {y} _{0 }={\begin{bmatrix}\lambda_{1}^{n-1}&\lambda_{2}^{n-1}&\cdots &\lambda_{n}^{n-1}\ \\vdots &\vdots &\ddots &\vdots \\\lambda _{1}&\lambda _{2}&\cdots &\lambda _{n}\\1&1&\cdots &1\end{bmatrix}}^ {-1}\,{\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}.}$

Dies funktioniert auch mit beliebigen Randbedingungen , nicht notwendigerweise den Anfangs-, ${\displaystyle \underbrace {y_{a},y_{b},\ldots} _{n}}$

${\displaystyle {\begin{bmatrix}y_{a}\\y_{b}\\\vdots \end{bmatrix}}={\begin{bmatrix}\mathbf {y} _{a}[n]\\ \mathbf {y} _{b}[n]\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{a}\,\mathbf {e} _{i}[n]}\\\Summe _{i=1}^{n}{c_{i}\,\lambda_{i} ^{b}\,\mathbf {e} _{i}[n]}\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_ {i}\,\lambda_{i}^{a}\,\lambda_{i}^{n-1}}\\\Summe _{i=1}^{n}{c_{i}\ ,\lambda_{i}^{b}\,\lambda_{i}^{n-1}}\\\vdots \end{bmatrix}}}$

${\displaystyle ={\begin{bmatrix}\sum {c_{i}\,\lambda_{i}^{a+n-1}}\\\sum {c_{i}\,\lambda_{i }^{b+n-1}}\\\vdots \end{bmatrix}}={\begin{bmatrix}\lambda _{1}^{a+n-1}&\lambda _{2}^{ a+n-1}&\cdots &\lambda_{n}^{a+n-1}\\\lambda_{1}^{b+n-1}&\lambda_{2}^{b +n-1}&\cdots &\lambda_{n}^{b+n-1}\\\vdots &\vdots &\ddots &\vdots \end{bmatrix}}\,{\begin{bmatrix} c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}.}$

Diese Beschreibung unterscheidet sich wirklich nicht von der obigen allgemeinen Methode, ist jedoch prägnanter. Es funktioniert auch gut für Situationen wie

${\displaystyle {\begin{cases}a_{n}=a_{n-1}-b_{n-1}\\b_{n}=2a_{n-1}+b_{n-1}.\end {Fälle}}}$

wo es mehrere verbundene Wiederholungen gibt.

Auflösen mit Z-Transformationen

Bestimmte Differenzengleichungen – insbesondere Differenzgleichungen mit linearen konstanten Koeffizienten – können unter Verwendung von z-Transformationen gelöst werden . Die z- Transformationen sind eine Klasse ganzzahliger Transformationen , die zu bequemeren algebraischen Manipulationen und einfacheren Lösungen führen. Es gibt Fälle, in denen eine direkte Lösung praktisch unmöglich wäre, das Problem jedoch über eine sorgfältig gewählte Integraltransformation einfach zu lösen ist.

Lösen von inhomogenen linearen Rekursionsbeziehungen mit konstanten Koeffizienten

Wenn die Rekursion inhomogen ist, kann eine bestimmte Lösung durch die Methode der unbestimmten Koeffizienten gefunden werden und die Lösung ist die Summe der Lösung der homogenen und der bestimmten Lösungen. Eine andere Methode zur Lösung einer inhomogenen Rekurrenz ist die Methode der symbolischen Differenzierung . Betrachten Sie beispielsweise die folgende Wiederholung:

${\displaystyle a_{n+1}=a_{n}+1}$

Dies ist ein inhomogenes Rezidiv. Wenn wir n ↦ n +1 einsetzen, erhalten wir die Rekursion

${\displaystyle a_{n+2}=a_{n+1}+1}$

Subtrahiert man die ursprüngliche Rekursion von dieser Gleichung, erhält man

${\displaystyle a_{n+2}-a_{n+1}=a_{n+1}-a_{n}}$

oder äquivalent

${\displaystyle a_{n+2}=2a_{n+1}-a_{n}}$

Dies ist ein homogenes Rezidiv, das mit den oben erläuterten Methoden gelöst werden kann. Im Allgemeinen hat eine lineare Rekursion die Form

${\displaystyle a_{n+k}=\lambda_{k-1}a_{n+k-1}+\lambda_{k-2}a_{n+k-2}+\cdots +\lambda_ {1}a_{n+1}+\lambda_{0}a_{n}+p(n)}$

wobei konstante Koeffizienten sind und p ( n ) die Inhomogenität ist, dann, wenn p ( n ) ein Polynom vom Grad r ist , dann kann diese inhomogene Rekursion durch Anwendung der Methode der symbolischen Differenzierung r- mal auf eine homogene Rekursion reduziert werden . ${\displaystyle \lambda_{0},\lambda_{1},\dots,\lambda_{k-1}}$

Ob

${\displaystyle P(x)=\sum_{n=0}^{\infty}p_{n}x^{n}}$

ist die erzeugende Funktion der Inhomogenität, die erzeugende Funktion

${\displaystyle A(x)=\sum_{n=0}^{\infty}a(n)x^{n}}$

des inhomogenen Rezidivs

${\displaystyle a_{n}=\sum_{i=1}^{s}c_{i}a_{ni}+p_{n},\quad n\geq n_{r},}$

mit konstanten Koeffizienten c _i ergibt sich aus

${\displaystyle \left(1-\sum_{i=1}^{s}c_{i}x^{i}\right)A(x)=P(x)+\sum _{n=0} ^{n_{r}-1}[a_{n}-p_{n}]x^{n}-\sum _{i=1}^{s}c_{i}x^{i}\sum _ {n=0}^{n_{r}-i-1}a_{n}x^{n}.}$

Wenn P ( x ) eine rationale erzeugende Funktion ist, ist auch A ( x ) eine. Der oben diskutierte Fall, in dem p _n = K eine Konstante ist, ist ein Beispiel für diese Formel mit P ( x ) = K /(1− x ). Ein weiteres Beispiel, die Rekursion mit linearer Inhomogenität, ergibt sich aus der Definition der schizophrenen Zahlen . Die Lösung homogener Rezidive wird als p = P = 0 aufgenommen. ${\displaystyle a_{n}=10a_{n-1}+n}$

Lösen von inhomogenen Rekursionsbeziehungen erster Ordnung mit variablen Koeffizienten

Außerdem gilt für die allgemeine inhomogene lineare Rekursion erster Ordnung mit variablen Koeffizienten:

${\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,}$

Es gibt auch eine schöne Methode, um es zu lösen:

${\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}$

${\displaystyle {\frac {a_{n+1}}{\prod_{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod_{k=0}^{n}f_{k}}}}$

${\displaystyle {\frac {a_{n+1}}{\prod_{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod_{k= 0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod_{k=0}^{n}f_{k}}}}$

Lassen

${\displaystyle A_{n}={\frac {a_{n}}{\prod_{k=0}^{n-1}f_{k}}},}$

Dann

${\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod_{k=0}^{n}f_{k}}}}$

${\displaystyle \sum_{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^ {n-1}{\frac {g_{m}}{\prod_{k=0}^{m}f_{k}}}}$

${\displaystyle {\frac {a_{n}}{\prod_{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n -1}{\frac {g_{m}}{\prod_{k=0}^{m}f_{k}}}}$

${\displaystyle a_{n}=\left(\prod_{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{ n-1}{\frac {g_{m}}{\prod_{k=0}^{m}f_{k}}}\right)}$

Wenden wir die Formel an und nehmen den Grenzwert h→0, erhalten wir die Formel für lineare Differentialgleichungen erster Ordnung mit variablen Koeffizienten; die Summe wird ein Integral und das Produkt wird die Exponentialfunktion eines Integrals. ${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}$

Lösen allgemeiner homogener linearer Rekursionsbeziehungen

Viele homogene lineare Rekursionsbeziehungen können mit Hilfe der verallgemeinerten hypergeometrischen Reihe gelöst werden . Spezialfälle dieser führen zu Rekursionsbeziehungen für die orthogonalen Polynome und vielen speziellen Funktionen . Zum Beispiel die Lösung für

${\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}$

wird gegeben von

${\displaystyle J_{n}=J_{n}(z),}$

die Bessel-Funktion , während

${\displaystyle (bn)M_{n-1}+(2n-bz)M_{n}-nM_{n+1}=0}$

wird gelöst durch

${\displaystyle M_{n}=M(n,b;z)}$

die konfluente hypergeometrische Reihe . Folgen, die die Lösungen von linearen Differenzengleichungen mit Polynomkoeffizienten sind, werden als P-rekursiv bezeichnet . Für diese spezifischen Rekursionsgleichungen sind Algorithmen bekannt, die polynomielle , rationale oder hypergeometrische Lösungen finden.

Rationale Differenzengleichungen erster Ordnung lösen

Eine rationale Differenzengleichung erster Ordnung hat die Form . Eine solche Gleichung kann gelöst werden, indem man sie als nichtlineare Transformation einer anderen Variablen schreibt , die sich selbst linear entwickelt. Dann können Standardmethoden verwendet werden, um die lineare Differenzengleichung in zu lösen . ${\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}$${\displaystyle w_{t}}$${\displaystyle x_{t}}$${\displaystyle x_{t}}$

Stabilität

Stabilität linearer Rezidive höherer Ordnung

Die lineare Wiederkehr der Ordnung d ,

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{nd},}$

hat die charakteristische Gleichung

${\displaystyle \lambda^{d}-c_{1}\lambda^{d-1}-c_{2}\lambda^{d-2}-\cdots -c_{d}\lambda^{0}= 0.}$

Die Rekursion ist stabil , dh die Iterationen konvergieren genau dann asymptotisch gegen einen festen Wert, wenn die Eigenwerte (dh die Wurzeln der charakteristischen Gleichung), ob reell oder komplex, alle im Absolutwert kleiner als Eins sind.

Stabilität von linearen Matrixrekursionen erster Ordnung

In der Matrixdifferenzengleichung erster Ordnung

${\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}$

mit Zustandsvektor x und der Übergangsmatrix A , x konvergiert asymptotisch auf den stationären Zustandsvektor x * , wenn und nur wenn alle Eigenwerte der Übergangsmatrix A (ob real oder komplex) einen haben Absolutwert , der kleiner als 1 ist.

Stabilität nichtlinearer Rezidive erster Ordnung

Betrachten Sie die nichtlineare Rekursion erster Ordnung

${\displaystyle x_{n}=f(x_{n-1}).}$

Diese Rekursion ist lokal stabil , d. h. sie konvergiert gegen einen Fixpunkt x * von hinreichend nahe bei x * gelegenen Punkten , wenn die Steigung von f in der Umgebung von x * im Betrag kleiner als Eins ist:

${\displaystyle |f'(x^{*})|<1.}$

Eine nichtlineare Wiederholung könnte mehrere Fixpunkte aufweisen, wobei in diesem Fall einige Fixpunkte lokal stabil und andere lokal instabil sein können; für stetiges f können zwei benachbarte Fixpunkte nicht beide lokal stabil sein.

Eine nichtlineare Rekursionsbeziehung könnte auch einen Zyklus der Periode k für k > 1 haben. Ein solcher Zyklus ist stabil, d. h. er zieht eine Reihe von Anfangsbedingungen mit positivem Maß an, wenn die zusammengesetzte Funktion

${\displaystyle g(x):=f\circ f\circ \cdots\circ f(x)}$

mit k- mal auftretendem f ist nach dem gleichen Kriterium lokal stabil:

${\displaystyle |g'(x^{*})|<1,}$

wobei x * ein beliebiger Punkt auf dem Zyklus ist.

In einer chaotischen Rekursionsbeziehung bleibt die Variable x in einem begrenzten Bereich, konvergiert jedoch nie gegen einen Fixpunkt oder einen anziehenden Zyklus; alle Fixpunkte oder Zyklen der Gleichung sind instabil. Siehe auch Logistikkarte , dyadische Transformation und Zeltkarte .

Beziehung zu Differentialgleichungen

Beim numerischen Lösen einer gewöhnlichen Differentialgleichung stößt man typischerweise auf eine Rekursionsbeziehung. Zum Beispiel bei der Lösung des Anfangswertproblems

${\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}$

mit dem Euler-Verfahren und einer Schrittweite h berechnet man die Werte

${\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h), \ \ Punkte }$

durch die Wiederholung

${\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}$

Systeme linearer Differentialgleichungen erster Ordnung können mit den im Diskretisierungsartikel gezeigten Methoden analytisch exakt diskretisiert werden .

Anwendungen

Biologie

Einige der bekanntesten Differenzengleichungen haben ihren Ursprung in dem Versuch, Populationsdynamiken zu modellieren . Zum Beispiel wurden die Fibonacci-Zahlen einst als Modell für das Wachstum einer Kaninchenpopulation verwendet.

Die Logistikkarte wird entweder direkt zur Modellierung des Bevölkerungswachstums oder als Ausgangspunkt für detailliertere Modelle der Bevölkerungsdynamik verwendet . In diesem Zusammenhang werden häufig gekoppelte Differenzengleichungen verwendet, um die Interaktion zweier oder mehrerer Populationen zu modellieren. Zum Beispiel ist das Nicholson-Bailey-Modell für eine Wirt- Parasit- Interaktion gegeben durch

${\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}$

${\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}$

wobei N _t die Wirte repräsentiert und P _t die Parasiten zum Zeitpunkt  t .

Integrodifferenzengleichungen sind eine für die räumliche Ökologie wichtige Form der Rekursionsbeziehung . Diese und andere Differenzengleichungen sind besonders geeignet, um univoltine Populationen zu modellieren .

Informatik

Auch bei der Analyse von Algorithmen sind Rekursionsbeziehungen von grundlegender Bedeutung . Wenn ein Algorithmus so konzipiert ist, dass er ein Problem in kleinere Teilprobleme zerlegt ( Divide and Conquer ), wird seine Laufzeit durch eine Rekursionsbeziehung beschrieben.

Ein einfaches Beispiel ist die Zeit, die ein Algorithmus benötigt, um im schlimmsten Fall ein Element in einem geordneten Vektor mit Elementen zu finden . ${\displaystyle n}$

Ein naiver Algorithmus sucht von links nach rechts, ein Element nach dem anderen. Das schlimmstmögliche Szenario ist, wenn das erforderliche Element das letzte ist, sodass die Anzahl der Vergleiche . ${\displaystyle n}$

Ein besserer Algorithmus heißt binäre Suche . Es erfordert jedoch einen sortierten Vektor. Es wird zuerst überprüft, ob sich das Element in der Mitte des Vektors befindet. Wenn nicht, wird geprüft, ob das mittlere Element größer oder kleiner als das gesuchte Element ist. An diesem Punkt kann die Hälfte des Vektors verworfen werden und der Algorithmus kann auf der anderen Hälfte erneut ausgeführt werden. Die Anzahl der Vergleiche wird angegeben durch

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{n/2}}$

deren zeitliche Komplexität sein wird . ${\displaystyle O(\log_{2}(n))}$

Digitale Signalverarbeitung

In der digitalen Signalverarbeitung können Wiederholungsbeziehungen eine Rückkopplung in einem System modellieren, bei der Ausgaben auf einmal zu Eingaben für die Zukunft werden. Sie entstehen somit in digitalen Filtern mit unendlicher Impulsantwort (IIR) .

Die Gleichung für ein "Feedforward"-IIR- Kammfilter der Verzögerung T lautet beispielsweise:

${\displaystyle y_{t}=(1-\alpha)x_{t}+\alpha y_{tT},}$

wobei der Eingang zu der Zeit ist , t , ist das Ausgangssignal zum Zeitpunkt t und α steuert , wie viel von dem verzögerten Signal wird zurück in den Ausgang eingespeist. Daran sehen wir das ${\displaystyle x_{t}}$${\displaystyle y_{t}}$

${\displaystyle y_{t}=(1-\alpha)x_{t}+\alpha ((1-\alpha)x_{tT}+\alpha y_{t-2T})}$

${\displaystyle y_{t}=(1-\alpha)x_{t}+(\alpha -\alpha^{2})x_{tT}+\alpha^{2}y_{t-2T}}$

etc.

Wirtschaft

Rekursionsbeziehungen, insbesondere lineare Rekursionsbeziehungen, werden sowohl in der theoretischen als auch in der empirischen Ökonomie ausgiebig verwendet. Insbesondere in der Makroökonomie könnte man ein Modell verschiedener breiter Wirtschaftssektoren (Finanzsektor, Gütersektor, Arbeitsmarkt usw.) entwickeln, in dem die Handlungen einiger Akteure von verzögerten Variablen abhängen. Das Modell würde dann nach aktuellen Werten wichtiger Variablen ( Zinssatz , reales BIP usw.) in Bezug auf vergangene und aktuelle Werte anderer Variablen aufgelöst.

Siehe auch

Verweise

Fußnoten

Literaturverzeichnis

• Batchelder, Paul M. (1967). Eine Einführung in lineare Differenzengleichungen . Dover-Publikationen.
• Miller, Kenneth S. (1968). Lineare Differenzengleichungen . WA Benjamin.
• Fillmore, Jay P.; Marx, Morris L. (1968). "Lineare rekursive Sequenzen". SIAM-Rev . 10 (3). S. 324–353. JSTOR  2027658 .
• Brousseau, Alfred (1971). Lineare Rekursion und Fibonacci-Folgen . Fibonacci-Vereinigung.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , Zweite Auflage. MIT Press und McGraw-Hill, 1990. ISBN  0-262-03293-7 . Kapitel 4: Rezidive, S. 62–90.
• Graham, Ronald L.; Knuth, Donald E.; Pataschnik, Oren (1994). Konkrete Mathematik: Eine Grundlage für die Informatik (2 Aufl.). Addison-Wesley. ISBN 0-201-55802-5.
• Enders, Walter (2010). Angewandte ökonometrische Zeitreihen (3 Hrsg.). Archiviert vom Original am 10.11.2014.
• Cull, Paul; Flahive, Maria ; Robson, Robbie (2005). Differenzgleichungen: Vom Kaninchen zum Chaos . Springer. ISBN 0-387-23234-6. Kapitel 7.
• Jacques, Jan (2006). Wirtschaftsmathematik (Fünfte Aufl.). Lehrlingssaal. S.  551 – 568. ISBN 0-273-70195-9. Kapitel 9.1: Differenzengleichungen.
• Minh, Tang; Van To, Tan (2006). "Verwenden von Erzeugungsfunktionen zur Lösung linearer inhomogener Rekursionsgleichungen" (PDF) . Proz. Int. Konf. Simulation, Modellierung und Optimierung, SMO'06 . S. 399–404.
• Polyanin, Andrei D. "Differenz- und Funktionsgleichungen: Exakte Lösungen" . bei EqWorld - Die Welt der mathematischen Gleichungen.
• Polyanin, Andrei D. "Differenz- und Funktionsgleichungen: Methoden" . bei EqWorld - Die Welt der mathematischen Gleichungen.
• Wang, Xiang-Sheng; Wong, Roderick (2012). „Asymptotik orthogonaler Polynome über Rekursionsbeziehungen“. Anal. Anw . 10 (2): 215–235. arXiv : 1101.4371 . doi : 10.1142/S0219530512500108 . S2CID  28828175 .

Externe Links

• "Wiederkehrbeziehung" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Recurrence Equation" . MathWorld .
• "OEIS Index Rec" . OEIS- Index zu einigen tausend Beispielen linearer Rekursionen, sortiert nach Reihenfolge (Anzahl der Terme) und Signatur (Wertevektor der konstanten Koeffizienten)