Relacja cykliczności - Recurrence relation

W matematyce , A związek nawrót jest równanie , które rekurencyjnie określa sekwencję lub wielowymiarowej tablicy wartości, gdy podane są jeden lub większą liczbę początkowych warunków tej samej funkcji; każdy kolejny termin sekwencji lub tablicy jest zdefiniowany jako funkcja poprzednich terminów tej samej funkcji.

Termin równanie różnicowe czasami (i na potrzeby tego artykułu) odnosi się do określonego typu relacji rekurencyjnej. Jednak „równanie różnicy” jest często używane w odniesieniu do dowolnej relacji powtarzalności.

Definicja

Nawrót związek to równanie wyraża każdego elementu sekwencji w zależności od tych poprzednich. Dokładniej, w przypadku, gdy zaangażowany jest tylko bezpośrednio poprzedzający element, relacja rekurencyjna ma postać

${\ Displaystyle u_ {n} = \ varphi (n, u_ {n-1}) \ quad {\ tekst {dla}} \ quad n> 0,}$

gdzie

${\ Displaystyle \ varphi: \ mathbb {N} \ razy X \ do X}$

jest funkcją, gdzie X jest zbiorem, do którego muszą należeć elementy sekwencji. Dla any definiuje to unikalną sekwencję, której pierwszym elementem jest wartość początkowa . ${\displaystyle u_{0}\w X}$${\displaystyle u_{0}}$

Łatwo jest zmodyfikować definicję, aby uzyskać ciągi zaczynające się od terminu o indeksie 1 lub wyższym.

To definiuje relację rekurencyjności pierwszego rzędu . Relacja rekurencyjna rzędu k ma postać

${\ Displaystyle u_ {n} = \ varphi (n, u_ {n-1}, u_ {n-2}, \ ldots, u_ {nk}) \ quad {\ tekst {dla}} \ quad n \ geq k ,}$

gdzie jest funkcją, która obejmuje k kolejnych elementów ciągu. W tym przypadku do zdefiniowania sekwencji potrzebne jest k wartości początkowych. ${\ Displaystyle \ varphi: \ mathbb {N} \ razy X ^ {k} \ do X}$

Przykłady

Factorial

Silnia jest określona zależnością nawrotu

${\ Displaystyle n! = n (n-1)! \ quad {\ tekst {dla}} \ quad n> 0,}$

i stan początkowy

${\displaystyle 0!=1.}$

Mapa logistyczna

Przykładem relacji rekurencyjnej jest mapa logistyczna :

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

z daną stałą r ; biorąc pod uwagę początkowy człon x _0, każdy kolejny człon jest określony tą relacją.

Rozwiązanie relacji rekurencyjnej oznacza uzyskanie rozwiązania w postaci zamkniętej : nierekurencyjnej funkcji n .

Liczby Fibonacciego

Powtarzalność rzędu drugiego spełnianego przez liczby Fibonacciego jest kanonicznym przykładem jednorodnej liniowej relacji powtarzalności o stałych współczynnikach (patrz poniżej). Ciąg Fibonacciego jest definiowany za pomocą rekurencji

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

z warunkami początkowymi

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

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

Wyraźnie rekurencja daje równania

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

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

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

itp.

Otrzymujemy ciąg liczb Fibonacciego, który zaczyna się

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

Rekurencję można rozwiązać metodami opisanymi poniżej, uzyskując wzór Bineta , który obejmuje potęgi dwóch pierwiastków wielomianu charakterystycznego t ²  =  t  + 1; funkcja generowania sekwencji jest funkcją wymierną

${\ Displaystyle {\ Frac {t} {1-tt ^ {2}}}.}$

Współczynniki dwumianowe

Prostym przykładem wielowymiarowej relacji rekurencyjności są współczynniki dwumianowe , które zliczają liczbę sposobów wyboru k elementów ze zbioru n elementów. Można je obliczyć za pomocą relacji rekurencyjnej ${\ Displaystyle {\ tbinom {n} {k}}}$

${\ Displaystyle {\ Binom {n} {k}} = {\ Binom {n-1} {k-1}} + {\ Binom {n-1} {k}}}$

z podstawowymi przypadkami . Użycie tego wzoru do obliczenia wartości wszystkich współczynników dwumianowych generuje nieskończoną tablicę zwaną trójkątem Pascala . Te same wartości można również obliczyć bezpośrednio za pomocą innej formuły, która nie jest cyklem, ale wymaga mnożenia, a nie tylko dodawania do obliczeń: ${\ Displaystyle {\ tbinom {n} {0}} = {\ tbinom {n} {n}} = 1}$${\ Displaystyle {\ Binom {n} {k}} = {\ Frac {n!} {k! (nk)!}}.}$

Związek z równaniami różnicowymi wąsko zdefiniowanymi

Biorąc pod uwagę, uporządkowana sekwencja z liczb rzeczywistych : the Pierwsza różnica jest zdefiniowany jako ${\ Displaystyle \ lewo \ {a_ {n} \ po prawej \} _ {n = 1} ^ {\ infty}}$ ${\ Displaystyle \ Delta (a_ {n})}$

${\ Displaystyle \ Delta (a_ {n}) = a_ {n + 1} -a_ {n}.}$

Inną różnicą jest zdefiniowany jako ${\ Displaystyle \ Delta ^ {2} (a_ {n})}$

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

które można uprościć do

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

Bardziej ogólnie: the k -tego różnica sekwencji _n zapisać jako jest zdefiniowana jako rekurencyjnie ${\ Displaystyle \ Delta ^ {k} (a_ {n})}$

${\ Displaystyle \ Delta ^ {k} (a_ {n}) = \ Delta ^ {k-1} (a_ {n + 1}) - \ Delta ^ {k-1} (a_ {n}) = \ suma _{t=0}^{k}{\binom {k}{t}}(-1)^{t}a_{n+kt}.}$

(Sekwencja i jej różnice są związane przez dwumianowego przekształcenie ). Im bardziej restrykcyjne określenia równania różnicowego jest równaniem składa się z a _n i jego k ^-tego różnic. (Szeroko stosowana szersza definicja traktuje „równanie różnicy” jako synonim „relacji powtarzalności”. Zobacz na przykład równanie różnicy wymiernej i równanie różnicy macierzowej .)

Właściwie łatwo zauważyć, że

${\ Displaystyle a_ {n + k} = {k \ wybierz 0} a_ {n} + {k \ wybierz 1} \ Delta (a_ {n}) + \ cdots + {k \ wybierz k} \ Delta ^ {k }(NS}).}$

Zatem równanie różnicowe można zdefiniować jako równanie, które obejmuje a _n , a _{n -1} , a _{n -2} itd. (lub równoważnie a _n , a _{n +1} , a _{n +2} itd.)

Ponieważ równania różnicowe są bardzo powszechną formą nawrotów, niektórzy autorzy używają tych dwóch terminów zamiennie. Na przykład równanie różnicowe

${\ Displaystyle 3 \ Delta ^ {2} (a_ {n}) +2 \ Delta (a_ {n}) + 7a_ {n} = 0}$

jest równoważne relacji rekurencyjnej

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

W ten sposób można rozwiązać wiele relacji rekurencyjnych, przeformułowując je jako równania różnicowe, a następnie rozwiązując równanie różnicowe, analogicznie do rozwiązywania równań różniczkowych zwyczajnych . Jednak liczby Ackermanna są przykładem relacji rekurencyjnej, która nie odwzorowuje równania różnicowego, a tym bardziej punktów na rozwiązanie równania różniczkowego.

Zobacz rachunek skali czasu dla ujednolicenia teorii równań różnicowych z równaniami różniczkowymi .

Równania sumujące odnoszą się do równań różnicowych, tak jak równania całkowe odnoszą się do równań różniczkowych.

Od sekwencji do siatek

Relacje rekurencyjne jednej zmiennej lub jednowymiarowej dotyczą sekwencji (tj. funkcji zdefiniowanych na siatkach jednowymiarowych). Wielowymiarowe lub n-wymiarowe relacje powtarzalności dotyczą siatek n-wymiarowych. Funkcje zdefiniowane na n-siatkach można również badać za pomocą równań różnic cząstkowych .

Rozwiązywanie

Rozwiązywanie jednorodnych liniowych relacji rekurencyjnych o stałych współczynnikach

Korzenie wielomianu charakterystycznego

Zamówienia- d jednorodny liniowy nawrót o stałych współczynnikach jest równanie postaci

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

gdzie d współczynniki c _I (dla wszystkich I ) są stałymi, a . ${\displaystyle c_{d}\neq 0}$

Ciąg stały-rekurencyjny to ciąg spełniający powtarzalność tej formy. Istnieje d stopni swobody dla rozwiązań tego powtarzania, tj. wartości początkowe mogą być traktowane jako dowolne wartości, ale wtedy powtarzalność jednoznacznie określa sekwencję. ${\displaystyle a_{0},\kropki,a_{d-1}}$

Te same współczynniki dają wielomian charakterystyczny (również „wielomian pomocniczy” lub „wielomian towarzyszący”)

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

którego d korzenie odgrywają kluczową rolę w znajdowaniu i zrozumieniu sekwencji spełniających nawrotom. Jeśli pierwiastki r ₁ , r ₂ , ... są różne, to każde rozwiązanie powtarzalności przyjmuje postać

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

gdzie współczynniki k _i są wyznaczane w celu dopasowania do warunków początkowych rekurencji. Gdy te same pierwiastki występują wielokrotnie, wyrazy w tym wzorze odpowiadające drugiemu i późniejszemu wystąpieniu tego samego pierwiastka są mnożone przez rosnące potęgi n . Na przykład, jeśli wielomian charakterystyczny można rozłożyć na czynniki jako ( x − r ) ³ , z tym samym pierwiastkiem r występującym trzy razy, to rozwiązanie przybrałoby postać

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

Jak również Fibonacciego inne sekwencje stałego rekurencyjne zawierać numery Lucas i sekwencje Lucas , o liczbie Jacobsthal , z Liczby Pella i bardziej ogólnie Roztwory równania Pella .

W przypadku zamówienia 1 nawrót

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

ma rozwiązanie a _n  =  r ⁿ z a ₀  = 1 i najbardziej ogólnym rozwiązaniem jest a _n  =  kr ⁿ z a ₀  =  k . Charakterystyczny wielomian równy zeru ( równanie charakterystyczne ) to po prostu t  −  r  = 0.

Rozwiązania takich relacji rekurencyjnych wyższego rzędu znajdują się w sposób systematyczny, często wykorzystując fakt, że a _n  =  r ⁿ jest rozwiązaniem dla rekurencyjności dokładnie wtedy, gdy t  =  r jest pierwiastkiem wielomianu charakterystycznego. Można do tego podejść bezpośrednio lub za pomocą funkcji generujących ( formalnych szeregów potęgowych ) lub macierzy.

Rozważmy na przykład relację rekurencyjną formy

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

Kiedy ma rozwiązanie o tej samej formie ogólnej co a _n = r ⁿ ? Zastępując to przypuszczenie ( ansatz ) w relacji rekurencyjnej, stwierdzamy, że

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

musi być prawdziwe dla wszystkich  n  > 1.

Dzieląc przez r ^{n −2} , otrzymujemy, że wszystkie te równania sprowadzają się do tego samego:

${\ Displaystyle r ^ {2} = Ar + B}$

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

które jest równaniem charakterystycznym relacji rekurencyjnej. Rozwiąż r, aby otrzymać dwa pierwiastki λ ₁ , λ ₂ : pierwiastki te są znane jako pierwiastki charakterystyczne lub wartości własne równania charakterystycznego. W zależności od charakteru korzeni uzyskuje się różne rozwiązania: Jeśli te korzenie są różne, mamy rozwiązanie ogólne general

${\ Displaystyle a_ {n} = C \ lambda _ {1} ^ {n} + D \ lambda _ {2} ^ {n}}$

natomiast jeśli są identyczne (gdy A ² + 4 B = 0 ), mamy

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

To jest najbardziej ogólne rozwiązanie; dwie stałe C i D można wybrać na podstawie dwóch danych warunków początkowych a ₀ i a _1, aby uzyskać konkretne rozwiązanie.

W przypadku zespolonych wartości własnych (co powoduje również powstanie zespolonych wartości parametrów rozwiązania C i D ) można wyeliminować stosowanie liczb zespolonych poprzez przepisanie rozwiązania w postaci trygonometrycznej. W tym przypadku możemy zapisać wartości własne jako Wtedy można wykazać, że ${\ Displaystyle \ lambda _ {1} \ lambda _ {2} = \ alfa \ pm \ beta i.}$

${\ Displaystyle a_ {n} = C \ lambda _ {1} ^ {n} + D \ lambda _ {2} ^ {n}}$

można przepisać jako

${\ Displaystyle a_ {n} = 2 M ^ {n} \ lewo (E \ cos (\ theta n) + F \ sin (\ theta n) \ prawej) = 2GM ^ {n} \ cos (\ theta n-\ delta ),}$

gdzie

${\ Displaystyle {\ zacząć {tablica} {lcl} M = {\ sqrt {\ alfa ^ {2} + \ beta ^ {2}}} i \ cos (\ theta ) = {\ tfrac {\ alfa} {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{tablica}}}$

Tutaj E i F (lub równoważnie G i δ) są rzeczywistymi stałymi, które zależą od warunków początkowych. Za pomocą

${\ Displaystyle \ lambda _ {1} + \ lambda _ {2} = 2 \ alfa = A}$

${\ Displaystyle \ lambda _ {1} \ cdot \ lambda _ {2} = \ alfa ^ {2} + \ beta ^ {2} = - B}$

można uprościć powyższe rozwiązanie jako

${\ Displaystyle a_ {n} = (-B) ^ {\ Frac {n} {2}} \ lewo (E \ cos (\ theta n) + F \ sin (\ theta n) \ prawej)}$

gdzie ₁ i ₂ są warunki początkowe i

${\ Displaystyle {\ zacząć {wyrównany} 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{wyrównany}}}$

W ten sposób nie ma potrzeby rozwiązywania λ ₁ i λ ₂ .

We wszystkich przypadkach — rzeczywiste odrębne wartości własne, rzeczywiste zduplikowane wartości własne i złożone sprzężone wartości własne — równanie jest stabilne (to znaczy, że zmienna a zbiega się do stałej wartości [konkretnie zero]) wtedy i tylko wtedy, gdy obie wartości własne są mniejsze niż jeden w wartość bezwzględna . W tym przypadku drugiego rzędu można wykazać, że ten warunek na wartościach własnych jest równoważny | | < 1 −  B  < 2, co jest równoważne | B | < 1 i | | < 1 -  B .

Równanie w powyższym przykładzie było jednorodne , tzn. nie było wyrazu stałego. Jeśli zaczyna się od niejednorodnej nawrotu

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

ze stałym wyrazem K , można to przekształcić do postaci jednorodnej w następujący sposób: Stan ustalony jest ustalany przez ustawienie b _n =  b _{n -1} =  b _{n -2} =  b * w celu uzyskania

${\ Displaystyle b ^ {*} = {\ Frac {K} {1-AB}}.}$

Następnie niejednorodną rekurencję można przepisać w postaci jednorodnej jako

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

które można rozwiązać jak powyżej.

Warunek stabilności podano powyżej w odniesieniu do wartości własnych dla przypadku drugiego rodzaju jest ważne dla ogółu n ^-tego -order postępowania: równanie jest stabilny, wtedy i tylko wtedy, gdy wszystkie wartości własne charakterystycznego równania są mniejsze niż jeden w wartości bezwzględnej.

Mając jednorodną liniową relację rekurencyjności ze stałymi współczynnikami rzędu d , niech p ( t ) będzie wielomianem charakterystycznym (również "wielomianem pomocniczym")

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

tak, że każde c _i odpowiada każdemu c _i w oryginalnej relacji rekurencyjnej (patrz ogólny formularz powyżej). Załóżmy, że λ jest pierwiastkiem p ( t ) o wielokrotności r . To znaczy, że ( t −λ) ^r dzieli p ( t ). Następujące dwie właściwości posiadają:

1. Każda z sekwencji r spełnia relację rekurencyjną.${\ Displaystyle \ lambda ^ {n}, n \ lambda ^ {n}, n ^ {2} \ lambda ^ {n}, \ kropki, n ^ {r-1} \ lambda ^ {n}}$
2. Dowolny ciąg spełniający relację powtarzalności można zapisać jednoznacznie jako liniową kombinację rozwiązań skonstruowanych w części 1, ponieważ λ zmienia się po wszystkich odrębnych pierwiastkach  p ( t ).

W wyniku tego twierdzenia jednorodną liniową zależność rekurencyjności o stałych współczynnikach można rozwiązać w następujący sposób:

1. Znajdź wielomian charakterystyczny p ( t ).
2. Znajdź pierwiastki z liczebności p ( t ) .
3. Napisz a _n jako liniową kombinację wszystkich pierwiastków (licząc krotność, jak pokazano w powyższym twierdzeniu) o nieznanych współczynnikach b _i .

   ${\ Displaystyle a_ {n} = \ lewo (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)}$

   Jest to ogólne rozwiązanie oryginalnej relacji rekurencyjnej. ( q jest wielokrotnością λ _* )

4. Zrównaj każdą z części 3 (wstawiając n = 0, ..., d do ogólnego rozwiązania relacji rekurencyjnej) ze znanymi wartościami z oryginalnej relacji rekurencyjnej. Jednak wartości a _n z pierwotnej relacji rekurencyjności zwykle nie muszą być ciągłe: wyłączając wyjątkowe przypadki, wystarczy d z nich (tj. dla oryginalnej jednorodnej liniowej relacji rekurencyjnej rzędu 3 można użyć wartości a ₀ , ₁ , ₄ ). Ten sposób zapewnia system liniowy d równań d niewiadomymi. Rozwiązanie tych równań dla nieznanych współczynników rozwiązania ogólnego i wstawienie tych wartości z powrotem do rozwiązania ogólnego da konkretne rozwiązanie oryginalnej relacji powtarzalności, które pasuje do początkowych warunków oryginalnej relacji powtarzalności (jak również wszystkich kolejnych wartości oryginalnej relacji powtarzalności ).${\displaystyle a_{0},a_{1},\kropki,a_{d}}$${\displaystyle a_{0},a_{1},\kropki,a_{d}}$${\displaystyle b_{1},b_{2},\kropki,b_{d}}$${\displaystyle a_{0},a_{1},a_{2},\kropki}$

Metoda rozwiązywania liniowych równań różniczkowych jest podobna do powyższej metody — „inteligentne zgadywanie” ( ansatz ) dla liniowych równań różniczkowych o stałych współczynnikach to e ^{λ x} gdzie λ jest liczbą zespoloną wyznaczoną przez podstawienie zgadywania do równania różniczkowego .

To nie jest przypadek. Rozważając szereg Taylora rozwiązania liniowego równania różniczkowego:

${\ Displaystyle \ suma _ {n = 0} ^ {\ infty} {\ Frac {f ^ {(n)} (a)} {n!}} (xa) ^ {n}}$

widać, że współczynniki szeregu są dane przez n- ^tą pochodną f ( x ) obliczoną w punkcie a . Równanie różniczkowe zapewnia liniowe równanie różnicowe odnoszące się do tych współczynników.

Ta równoważność może być wykorzystana do szybkiego rozwiązania zależności powtarzalności dla współczynników w rozwiązaniu szeregu potęgowego liniowego równania różniczkowego.

Praktyczna zasada (dla równań, w których wielomian mnożący pierwszy człon jest niezerowy przy zerze) jest następujący:

${\ Displaystyle y ^ {[k]} \ do f [n + k]}$

i bardziej ogólnie

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

Przykład: Relacja rekurencyjna dla współczynników szeregu Taylora równania:

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

jest dany przez

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

lub

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

Ten przykład pokazuje, w jaki sposób problemy ogólnie rozwiązywane przy użyciu metody rozwiązywania szeregów potęgowych nauczanej w klasach normalnych równań różniczkowych można rozwiązać w znacznie łatwiejszy sposób.

Przykład: równanie różniczkowe

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

ma rozwiązanie

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

Konwersja równania różniczkowego do równania różnicowego współczynników Taylora jest

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

Łatwo jest zauważyć, że n p pochodną e ^ax oceniano w 0 to ⁿ .

Rozwiązywanie za pomocą algebry liniowej

Liniowo rekurencyjny ciąg y rzędu 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}$

jest identyczny z

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

Rozszerzone o n −1 tożsamości rodzaju , to równanie n- tego rzędu jest tłumaczone na macierzowy układ równań różnicowych n równań liniowych pierwszego rzędu, ${\ Displaystyle y_ {nk} = y_ {nk}}$

${\ Displaystyle \ mathbf {y} _ {n} = {\ zacząć {bmatrix} y_ {n} \ \ y_ {n-1} \ \ \ vdots \ \ \ vdots \ \ y_ {1} \ koniec {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}.}$

Zauważ, że wektor można obliczyć przez n zastosowań macierzy towarzyszącej , C , do wektora stanu początkowego, . Tym samym n- ty wpis poszukiwanej sekwencji y jest górnym składnikiem . ${\ Displaystyle \ mathbf {y} _ {n}}$${\displaystyle y_{0}}$${\ Displaystyle \ mathbf {y} _ {n}, y_ {n} = \ mathbf {y} _ {n} [n]}$

Dekompozycja własna , na wartości własne , i wektory własne, , służy do obliczania . Dzięki kluczowemu faktowi, że system C przesuwa w czasie każdy wektor własny, e , po prostu skalując jego składowe λ razy, ${\ 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 {\ zacząć {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{bmatryca}}}$

czyli przesunięta w czasie wersja wektora własnego, e , ma składowe λ razy większe, składowe wektora własnego są potęgami λ , a zatem powtarzalne jednorodne rozwiązanie równania liniowego jest kombinacją funkcji wykładniczych, . Składniki można określić z warunków początkowych: ${\ Displaystyle \ mathbf {e} _ {i} = {\ zacząć {bmatrix} \ lambda _ {i} ^ {n-1} i \ cdots i \ lambda _ {i} ^ {2} i \ lambda _ { i}&1\end{bmatryca}}^{\mathrm {T} },}$${\ Displaystyle \ mathbf {y} _ {n} = \ suma _ {1} ^ {n} {c_ {i} \ \ lambda _ {i} ^ {n} \ \ mathbf {e} _ {i }}}$${\displaystyle c_{i}}$

${\ Displaystyle \ mathbf {y} _ {0} = {\ zacząć {bmatrix} Y_ {0} \ \ Y_ {-1} \ \ \ vdots \ \ y_ {-n + 1} \ koniec {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{bmatryca}}}$

Rozwiązywanie dla współczynników,

${\ Displaystyle {\ zacząć {bmatrix} c_ {1} \ \ c_ {2} \ \ \ vdots \ \ c_ {n} \ koniec {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}}.}$

Działa to również z dowolnymi warunkami brzegowymi , niekoniecznie początkowymi, ${\ Displaystyle \ Underbrace {y_ {a}, y_ {b}, \ ldots} _ {n}}$

${\ Displaystyle {\ rozpocząć {bmatrix} Y_ {a} \ \ y_ {b} \ \ \ vdots \ koniec {bmatrix}} = {\ zacząć {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]}\\\sum _{i=1}^{n}{c_{i}\,\lambda _{i} ^{b}\,\mathbf {e} _{i}[n]}\\\vdots \end{bmacierz}}={\begin{bmacierz}\sum _{i=1}^{n}{c_ {i}\,\lambda _{i}^{a}\,\lambda _{i}^{n-1}}\\\sum _{i=1}^{n}{c_{i}\ ,\lambda _{i}^{b}\,\lambda _{i}^{n-1}}\\\vdots \end{bmatryca}}}$

${\ Displaystyle = {\ zacząć {bmatrix} \ suma {c_ {i} \ \ lambda _ {i} ^ {a + n-1}} \ \ \ suma {c_ {i} \ \ lambda _ {i }^{b+n-1}}\\\vdots \end{bmacierz}}={\begin{bmacierz}\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}}.}$

Ten opis tak naprawdę nie różni się od ogólnej metody powyżej, jest jednak bardziej zwięzły. Świetnie sprawdza się również w sytuacjach takich jak

${\ Displaystyle {\ zacząć {przypadki} a_ {n} = a_ {n-1}-b_ {n-1} \ \ b_ {n} = 2a_ {n-1} + b_ {n-1}. \ koniec {sprawy}}}$

gdzie istnieje kilka połączonych nawrotów.

Rozwiązywanie za pomocą przekształceń z

Niektóre równania różnicowe — w szczególności równania różnicowe o stałych współczynnikach liniowych — można rozwiązać za pomocą przekształceń z . W Z -transforms są klasą integralnych przekształceń prowadzących do bardziej dogodnych algebraicznych manipulacji i prostszych rozwiązań. Są przypadki, w których uzyskanie bezpośredniego rozwiązania byłoby prawie niemożliwe, ale rozwiązanie problemu za pomocą przemyślanej transformacji całkowej jest proste.

Rozwiązywanie niejednorodnych liniowych relacji rekurencyjnych o stałych współczynnikach

Jeżeli rekurencja jest niejednorodna, dane rozwiązanie można znaleźć metodą nieoznaczonych współczynników, a rozwiązanie jest sumą rozwiązania jednorodnego i poszczególnych rozwiązań. Inną metodą rozwiązywania niejednorodnej rekurencji jest metoda różnicowania symbolicznego . Rozważmy na przykład następującą powtarzalność:

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

Jest to nawrót niejednorodny. Jeśli podstawimy n ↦ n +1, otrzymamy rekurencję

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

Odjęcie oryginalnej rekurencji od tego równania daje

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

lub równoważnie

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

Jest to jednorodny nawrót, który można rozwiązać za pomocą wyjaśnionych powyżej metod. Ogólnie, jeśli rekurencja liniowa ma postać

${\ 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)}$

gdzie są stałe współczynniki, a p ( n ) jest niejednorodnością, to jeśli p ( n ) jest wielomianem o stopniu r , to ta niejednorodna rekurencyjność może być sprowadzona do rekurencyjnej jednorodnej poprzez zastosowanie metody symbolicznego różnicowania r razy. ${\ Displaystyle \ lambda _ {0} \ lambda _ {1} \ kropki \ lambda _ {k-1}}$

Jeśli

${\ Displaystyle P (x) = \ suma _ {n = 0} ^ {\ infty} p_ {n} x ^ {n}}$

jest funkcją tworzącą niejednorodności, funkcją tworzącą

${\ Displaystyle A (x) = \ suma _ {n = 0} ^ {\ infty} a (n) x ^ {n}}$

niejednorodnej nawrotu

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

ze stałymi współczynnikami c _i pochodzi z

${\ Displaystyle \ lewo (1-\ suma _ {i = 1} ^ {s} c_ {i} x ^ {i} \ prawej) A (x) = P (x) + \ suma _ {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}.}$

Jeśli P ( x ) jest wymierną funkcją generującą, A ( x ) jest również jedną. Omówiony powyżej przypadek, w którym p _n = K jest stałą, wyłania się jako jeden z przykładów tego wzoru, gdzie P ( x ) = K /(1− x ). Inny przykład, nawrót z niejednorodnością liniową, pojawia się w definicji liczb schizofrenicznych . Rozwiązanie jednorodnych rekurencji jest włączone jako p = P = 0. ${\ Displaystyle a_ {n} = 10a_ {n-1} + n}$

Rozwiązywanie niejednorodnych relacji rekurencyjnych pierwszego rzędu ze zmiennymi współczynnikami

Ponadto dla ogólnej niejednorodnej liniowej relacji rekurencyjnej pierwszego rzędu ze zmiennymi współczynnikami:

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

jest też fajna metoda na rozwiązanie tego problemu:

${\ 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}}}}$

Pozwolić

${\ Displaystyle A_ {n} = {\ Frac {a_ {n}} {\ prod _ {k = 0} ^ {n-1} f_ {k}}}}$

Następnie

${\ Displaystyle A_ {n + 1}-A_ {n} = {\ Frac {g_ {n}} {\ prod _ {k = 0} ^ {n} f_ {k}}}}$

${\ Displaystyle \ suma _ {m = 0} ^ {n-1} (A_ {m + 1} -A_ {m}) = A_ {n} - A_ {0} = \ suma _ {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}+ \ suma _ {m = 0} ^ {n -1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\ Displaystyle a_ {n} = \ lewo (\ prod _ {k = 0} ^ {n-1} f_ {k} \ prawo) \ lewo (A_ {0}+ \ suma _ {m = 0} ^ { n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)}$

Jeśli zastosujemy wzór do i przyjmiemy granicę h→0, otrzymamy wzór na równania różniczkowe liniowe pierwszego rzędu ze zmiennymi współczynnikami; suma staje się całką, a iloczyn staje się funkcją wykładniczą całki. ${\ Displaystyle a_ {n + 1} = (1 + hf_ {nh}) a_ {n} + hg_ {nh}}$

Rozwiązywanie ogólnych jednorodnych liniowych relacji rekurencyjnych

Wiele jednorodnych liniowych zależności rekurencyjnych można rozwiązać za pomocą uogólnionych szeregów hipergeometrycznych . Ich szczególne przypadki prowadzą do relacji rekurencyjnych dla wielomianów ortogonalnych i wielu funkcji specjalnych . Na przykład rozwiązanie:

${\ Displaystyle J_ {n + 1} = {\ Frac {2n} {z}} J_ {n}-J_ {n-1}}$

jest dany przez

${\ Displaystyle J_ {n} = J_ {n} (z)}$

funkcja Bessela , natomiast

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

jest rozwiązany przez

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

confluent hipergeometryczny serii . Ciągi będące rozwiązaniami równań różniczkowych liniowych o współczynnikach wielomianowych nazywamy P-rekursywnymi . Dla tych specyficznych równań rekurencyjnych znane są algorytmy, które znajdują rozwiązania wielomianowe , wymierne lub hipergeometryczne .

Rozwiązywanie racjonalnych równań różniczkowych pierwszego rzędu

Wymierne równanie różnicy pierwszego rzędu ma postać . Takie równanie można rozwiązać, pisząc jako nieliniowe przekształcenie innej zmiennej, która sama ewoluuje liniowo. Następnie można zastosować standardowe metody do rozwiązania równania różnicy liniowej w . ${\ Displaystyle w_ {t + 1} = {\ tfrac {aw_ {t} + b} {cw_ {t} + d}}}$${\displaystyle w_{t}}$${\displaystyle x_{t}}$${\displaystyle x_{t}}$

Stabilność

Stabilność liniowych rekurencji wyższego rzędu

Rekurencyjność liniowa rzędu d ,

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

ma charakterystyczne równanie

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

Powtarzalność jest stabilna , co oznacza, że ​​iteracje zbiegają się asymptotycznie do stałej wartości wtedy i tylko wtedy, gdy wartości własne (tj. pierwiastki równania charakterystycznego), zarówno rzeczywiste, jak i złożone, są mniejsze niż jedność w wartości bezwzględnej.

Stabilność liniowych rekurencji macierzy pierwszego rzędu

W macierzowym równaniu różnicowym pierwszego rzędu

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

z wektorem stanu x i macierzą przejścia A , x zbiega się asymptotycznie do wektora stanu ustalonego x * wtedy i tylko wtedy, gdy wszystkie wartości własne macierzy przejścia A (zarówno rzeczywiste, jak i złożone) mają wartość bezwzględną mniejszą niż 1.

Stabilność nieliniowych nawrotów pierwszego rzędu

Rozważmy nieliniową nawrót pierwszego rzędu

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

Ta rekurencja jest lokalnie stabilna , co oznacza, że zbiega się do ustalonego punktu x * z punktów wystarczająco bliskich x *, jeśli nachylenie f w sąsiedztwie x * jest mniejsze niż jedność w wartości bezwzględnej:

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

Rekurencja nieliniowa może mieć wiele punktów stałych, w którym to przypadku niektóre punkty stałe mogą być lokalnie stabilne, a inne lokalnie niestabilne; dla ciągłej f dwa sąsiednie punkty stałe nie mogą być oba lokalnie stabilne.

Nieliniowa relacja rekurencyjności może mieć również cykl o okresie k dla k > 1. Taki cykl jest stabilny, co oznacza, że ​​przyciąga zbiór warunków początkowych o dodatniej mierze, jeśli funkcja złożona

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

gdzie f występuje k razy jest lokalnie stabilna według tego samego kryterium:

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

gdzie x * jest dowolnym punktem w cyklu.

W chaotycznej relacji powtarzalności zmienna x pozostaje w ograniczonym regionie, ale nigdy nie zbiega się do ustalonego punktu lub cyklu przyciągania; wszelkie stałe punkty lub cykle równania są niestabilne. Zobacz także mapę logistyczną , transformację dwójkową i mapę namiotową .

Związek z równaniami różniczkowymi

Rozwiązując numerycznie równanie różniczkowe zwyczajne , zwykle napotyka się relację rekurencyjną. Na przykład podczas rozwiązywania problemu z wartością początkową

${\ Displaystyle y'(t) = f (t, r (t)), \ \ r (t_ {0}) = r_ {0},}$

z metodą Eulera i kroku h , wylicza się wartości

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

przez nawrót

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

Układy liniowych równań różniczkowych pierwszego rzędu można dokładnie zdyskretyzować analitycznie przy użyciu metod przedstawionych w artykule o dyskretyzacji .

Aplikacje

Biologia

Niektóre z najbardziej znanych równań różnicowych wywodzą się z próby modelowania dynamiki populacji . Na przykład liczby Fibonacciego były kiedyś używane jako model wzrostu populacji królików.

Odwzorowanie logistyczne służy bezpośrednio do modelu wzrostu populacji, lub jako punkt wyjścia dla bardziej szczegółowych modeli dynamiki populacji . W tym kontekście do modelowania interakcji dwóch lub więcej populacji często stosuje się sprzężone równania różnicowe. Na przykład model Nicholsona-Baileya dla interakcji żywiciel- pasożyt jest podany przez:

${\ Displaystyle N_ {t + 1} = \ lambda N_ {t} e ^ {-AP_ {t}}}$

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

gdzie N _t reprezentuje gospodarzy, a P _t pasożyty, w czasie  t .

Równania całkoróżnicowe są formą relacji rekurencyjnej ważnej dla ekologii przestrzennej . Te i inne równania różnicowe szczególnie nadają się do modelowania populacji uniwoltowych .

Informatyka

Relacje rekurencyjne mają również fundamentalne znaczenie w analizie algorytmów . Jeśli algorytm jest zaprojektowany tak, aby rozbijał problem na mniejsze podproblemy ( dziel i zwyciężaj ), jego czas działania jest opisany relacją powtarzalności.

Prostym przykładem jest czas, jaki zajmuje algorytmowi znalezienie elementu w uporządkowanym wektorze z elementami, w najgorszym przypadku. ${\ Displaystyle n}$

Algorytm naiwny przeszukuje od lewej do prawej, po jednym elemencie na raz. Najgorszym możliwym scenariuszem jest sytuacja, gdy wymagany element jest ostatnim, a więc liczba porównań wynosi . ${\ Displaystyle n}$

Lepszy algorytm nazywa się wyszukiwaniem binarnym . Wymaga jednak posortowanego wektora. Najpierw sprawdzi, czy element znajduje się w środku wektora. Jeśli nie, to sprawdzi, czy środkowy element jest większy czy mniejszy od poszukiwanego elementu. W tym momencie połowa wektora może zostać odrzucona, a algorytm może zostać uruchomiony ponownie na drugiej połowie. Liczba porównań zostanie podana przez

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

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

złożoność czas którego będzie . ${\displaystyle O(\log_{2}(n))}$

Przetwarzanie sygnału cyfrowego

W cyfrowym przetwarzaniu sygnałów relacje rekurencyjne mogą modelować sprzężenie zwrotne w systemie, w którym wyjścia w jednym czasie stają się wejściami w czasie przyszłym. Powstają zatem w filtrach cyfrowych o nieskończonej odpowiedzi impulsowej (IIR) .

Na przykład równanie dla „sprzężenia do przodu” filtru grzebieniowego IIR o opóźnieniu T jest następujące:

${\ Displaystyle y_ {t} = (1-\ alfa) x_ {t} + \ alfa y_ {tT}}$

gdzie jest wejściem w czasie t , jest wyjściem w czasie t , a α określa, jaka część opóźnionego sygnału jest zwracana na wyjście. Z tego widać, że ${\displaystyle x_{t}}$${\displaystyle y_{t}}$

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

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

itp.

Ekonomia

Relacje rekurencyjne, zwłaszcza liniowe relacje rekurencyjne, są szeroko stosowane zarówno w ekonomii teoretycznej, jak i empirycznej. W szczególności w makroekonomii można opracować model różnych szerokich sektorów gospodarki (sektor finansowy, sektor towarów, rynek pracy itp.), w których działania niektórych podmiotów zależą od zmiennych opóźnionych. Model zostałby następnie rozwiązany dla bieżących wartości kluczowych zmiennych ( stopa procentowa , realny PKB itp.) w kategoriach przeszłych i bieżących wartości innych zmiennych.

Zobacz też

Bibliografia

Przypisy

Bibliografia

• Batchelder, Paul M. (1967). Wprowadzenie do równań różnicowych liniowych . Publikacje Dovera.
• Miller, Kenneth S. (1968). Równania różnicowe liniowe . WA Benjamin.
• Fillmore, Jay P.; Marks, Morris L. (1968). „Liniowe sekwencje rekurencyjne”. SIAM Rev . 10 (3). s. 324-353. JSTOR  2027658 .
• Alfred Brousseau (1971). Rekurencja liniowa i ciągi Fibonacciego . Stowarzyszenie Fibonacciego.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 1990. ISBN  0-262-03293-7 . Rozdział 4: Nawroty, s. 62-90.
• Graham, Ronald L.; Knuth, Donald E.; Patasznik, Oren (1994). Matematyka konkretna: podstawa informatyki (2 wyd.). Addisona-Wesleya. Numer ISBN 0-201-55802-5.
• Enders, Walter (2010). Applied Econometric Times Series (3 wyd.). Zarchiwizowane od oryginału w dniu 2014-11-10.
• Pozbądź się, Paul; Flahive, Maryjo ; Robson, Robbie (2005). Równania różnicowe: od królików do chaosu . Skoczek. Numer ISBN 0-387-23234-6. Rozdział 7.
• Jacques, Ian (2006). Matematyka dla ekonomii i biznesu (wyd. piąte). Sala Prezydencka. s.  551 -568. Numer ISBN 0-273-70195-9. Rozdział 9.1: Równania różnicowe.
• Minh, Tang; Van To, Tan (2006). „Wykorzystywanie funkcji generujących do rozwiązywania liniowych niejednorodnych równań rekurencyjnych” (PDF) . Proc. wewn. Konf. Symulacja, modelowanie i optymalizacja, SMO'06 . s. 399-404.
• Polyanin, Andrei D. „Różnice i równania funkcjonalne: dokładne rozwiązania” . w EqWorld - Świat równań matematycznych.
• Polyanin, Andrei D. „Różnice i równania funkcjonalne: metody” . w EqWorld - Świat równań matematycznych.
• Wang, Xiang-Sheng; Wong, Roderick (2012). „Asymptotyki wielomianów ortogonalnych poprzez relacje nawrotów”. Analny. Zał . 10 (2): 215–235. arXiv : 1101.4371 . doi : 10.1142/S0219530512500108 . S2CID  28828175 .

Linki zewnętrzne

• „Relacja nawrotów” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Równanie nawrotu” . MatematykaŚwiat .
• „Indeks rekomendacji OEIS” . Indeks OEIS do kilku tysięcy przykładów rekurencji liniowych, posortowanych według kolejności (liczba terminów) i sygnatury (wektor wartości stałych współczynników)