Diferencne jednačine

U matematici, diferencna jednačina je jednačina koja rekurzivno definiše niz ili multidimenzionalni red vrednosti, jednom kada je jedan ili više početnih uslova dato: svaki sledeći član niza ili reda je definisina kao funkcija prethodnih uslova.

Termin diferencna jednačina se ponekad (kao što je slučaj u ovom članku) odnosi na specifičan tip rekurzivne relacije. Međutim, "diferencna jednačina" se često odnosi na sve tipove rekurzivnih relacija.

Primeri

Logistička mapa

Primer rekurzivne relacije je logistička mapa:

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

sa datom konstantom r; datim početnim uslovom x₀ svaki član podniza je određen ovom relacijom.

Neke jednostavno definisane rekurzivne relacije mogu imati veoma kompleksne (teorija haosa) osobine, i oni pripadaju polju matematike koji je poznat pod nazivom nelinearna analiza.

Rešavanje rekurzivne relacije znači postizanje rešenja zatvorenog tipa: nerekurzivna funkcija po n.

Fibonačijev niz

Fibonačijev niz je prototip linearne, homogene rekurzivne relacije sa kostantnim koeficijentima (videti ispod). Oni su definisani pomoću linearne rekurzivne relacije.

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

sa početnim uslovima:

$F_{0}=0$

$F_{1}=1$

Eksplicitno, rekurzija daje jednačine:

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

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

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

itd.

Dobijamo niz Fibonačijevih brojeva, koji počinje:

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

On se može rešiti pomoću metoda koje su opisane u nastavku, dobijanjem izraza zatvorenog tipa, koji uključuje stepene dva rešenja karakterističnog polinoma t² = t + 1;  generativna funkcija niza je racionalna funkcija:

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

Binomni koeficijenti

Jednostavan primer multidimenzionalne rekurzivne relacije je dat pomoću binomnog koeficijenta ${\tbinom {n}{k}}$, koji računa broj načina selektovanja k iz seta od n elemenata. Oni se mogu izračunati pomoću rekurzivne relacije

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

gde su početni uslovi ${\tbinom {n}{0}}={\tbinom {n}{n}}=1$. Korišćenje ove formule za izračunavanje vrednosti svih binomnih koeficjenata, stvara beskonačan red koji je nazvan Paskalov trougao. Te vrednosti se takođe mogu izračunati i direktno pomoću formule koja nije rekurzivna, ali to zahteva množenje a ne samo sabiranje: ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$

Strukture

Linearne homogene rekurzivne relacije sa konstantnim koeficijentima

Niz d linearne homogene rekurzivne relacije sa konstantnim koeficijentima je jednačina forme

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

gde su d i koeficijenti c_i (za svako i) konstante.

Preciznije, ovo je beskonačna lista sličnih linearnih jednačina, jedna za svako n>d−1. Niz koji zadovoljava relaciju ovog oblika se zove linearni rekurzivni niz ili LRS. LRS ima d stepena slobode, kao početne vrednosti $a_{0},\dots ,a_{d-1}$ se mogu uzeti bilo koje vrednosti ali onda linearna rekurzija određuje niz jedinstveno.

Isti koeficijenti daju karakteristični polinom (takođe "pomoćni polinom")

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

čija d rešenja igraju bitnu ulogu u nalaženju i razumevanju niza koji zadovoljava rekurziju. Ako su sva rešenja r₁, r₂, ... posebna, onda je rešenje rekurzije oblika

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

gde je koeficijent k_i  određen tako da odgovara početnim uslovima rekurzije. Kada se isti koreni pojave veći broj puta, članovi formule koji odgovaraju drugom i narednim pojavama istog korena se množe tako da im stepenovi budu n. Na primer, ako karakteristični polinom može biti faktorisan kao (x−r)³, sa istim korenom r koji se pojavljuje tri puta, onda će rešenje biti oblika

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

Kao i Fibonačijev niz, i ostali nizovi nastali linearnom homogenom rekurzijom uključujući Lukasove brojeve i Lukasov niz, Jakobstalove brojeve, Pelove brojeve kao i rešenje Pelove jednačine.

Racionalna generativna funkcija

Linearni rekurzivni nizovi su preciznije nizovi čija je generativna funkcija, racionalna: imenilac je polinom dobijen od pomoćnog polinoma menjanjem redosleda koeficijenata, i brojilac je određen početnim vrednostima niza.

Najjednostavniji slučajevi su periodični nizovi, $a_{n}=a_{n-d},n\geq d$, čiji je niz $a_{0},a_{1},\dots ,a_{d-1},a_{0},\dots$ i generativna funkcija zbir geometrijskih serija:

${\begin{aligned}{\frac {a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}}{1-x^{d}}}=&\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)+\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{d}+\\&\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{2d}+\cdots .\end{aligned}}$

Uopštenije, data rekurzivna relacija:

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

sa generativnom fukncijom

$a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots ,$

serija je prekunita za a_d i iznad polinomom:

$1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}.$

Tako, množenjem generativne funkcije polinomom se dobija

$b_{n}=a_{n}-c_{1}a_{n-1}-c_{2}a_{n-2}-\cdots -c_{d}a_{n-d}$

što predstavlja koeficijent uz $x^{n}$, i nestaje (rekurzivnom relacijom) za n ≥ d. Tako

$\left(a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots \right)\left(1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}\right)=\left(b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots +b_{d-1}x^{d-1}\right)$

da deljenje daje

$a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots ={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}}},$

predstavljajući generativnu funkciju kao racionalnu.

Imenilac je $x^{d}p\left(x^{-1}\right),$  transformacija pomoćnog polinoma (ekvivalentno, promenom redosleda koeficjenata); mogao je da se uzme i bilo koji činilac, ali ovaj standard je izabran zbog jednostavne veze sa  pomoćnim polinomom, tako da je $b_{0}=a_{0}$.

Odnos sa usko definisanim diferencnim jednačinama

Dati poredak niza $\left\{a_{n}\right\}_{n=1}^{\infty }$ realnih brojeva: prva diferenca $\Delta (a_{n})$ je definisana sa

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

Druga diferenca  $\Delta ^{2}(a_{n})$ je defnisana sa

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

koja se može uprostiti na

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

Uopšteno: k^ta diferenca niza a_n , napisana kao $\Delta ^{k}(a_{n})$ je definisana rekurzivno kao

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

(Niz i njegove diference su povezani preko binomne transformacije.) Restriktivnija definicija diferencne jednačine je jednačina sastavljena od a_n i njenih k^ti diferenci. (široko rasprostranjena definicija tretira "diferencne jednačine" kao sinonim za "rekurzivnu relaciju". Videti na primer racionalnu diferencnu jednačinu i matričnu diferencnu jednačinu.)

Zapravo, lako se vidi da je$a_{n+k}={n \choose 0}a_{n}+{n \choose 1}\Delta (a_{n})+\cdots +{n \choose k}\Delta ^{k}(a_{n}).$ Tako, diferencna jednačina može biti definisana kao jednačina koje uključuje a_n, a_n-1, a_n-2 itd. (ili eventualno a_n, a_n+1, a_n+2 itd.)

Kako su diferencne jednačine vrlo prepoznatljiv oblik rekurzije, neki autori koriste ova dva izraza naizmenično. Na primer, diferencna jednačina

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

je ekvivalentna rekurzivnoj relaciji

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

Tako da se mnoge rekurzivne relacije mogu rešiti prevođenjem u diferencne jednačine, a onda analogno rešavanju diferencnih jednačina, se mogu rešiti obične diferencijalne jednačine. Međutim, Akermanova funkcija  je primer rekurzivne relacije koja se ne preslikava u diferencijalnu jednačinu.

Videti račun na vremenskoj skali vezan za ujedinjenje teorije o diferencnim jednačinama sa diferencijalnim jednačinama.

Diskretne integralne jednačine su vezane za diferencne jednačine kao što su integralne jednačine vezane za diferencijalne jednačine.

Od nizova do mreža

Jedno-promenljive ili jedno-dimenzionalne rekurzivne relacije su vezane ta nizove (tj. funkcije definisane na jedno-dimenzionalnim mrežama). Više-promenljive ili n-dimenzionalne rekurzivne relacije su vezane za n-dimenzionalne mreže. Funkcije definisane na n-mrežama se takođe mogu izučavati u okviru parcijalnih diferencnih jednačina.

Rešavanje

Uopštene metode

Za niz 1, rekurzija

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

ima rešenje a_n = rⁿ sa a₀ = 1 a najuopštenije rešenje je a_n = krⁿ sa a₀ = k. Karaktetistični polinom izjednačen sa nulom je (karakteristična jednačina)  t − r = 0.

Rešenja ovakve rekurzivne relacije višeg reda se nalaze sistematski, često se koristi činjenica da je a_n = rⁿ  rešenje rekurzije tačno kada je t = r  koren karakterističnog polinoma. Ovome se može pristupiti direktno ili preko generativnih funkcija (formalni stepeni red) ili matrica.

Razmotrimo, na primer, rekurzivnu relaciju oblika

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

Kada ima rešenje oblika a_n = rⁿ?  Zamenom ove pretpostavke (anzac) u rekurzivnoj relaciji, nalazimo da

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

mora biti tačno za svako n > 1.

Deljenjem sa rⁿ⁻², dobijamo da se sve jednačine svode na istu stvar:

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

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

što je karakteristika jednačine rekurzivne relacije. Rešavanjem r dobijamo dva korena λ₁, λ₂: ovi koreni su poznati kao karakteristični koreni (rešenja) ili jedinstvena rešenja karakteristične jednačine. Drugačija rešenja se dobijaju u zavisnosti od prirode korena: Ako su ovi koreni posebni, imamo uopšteno rešenje

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

dok, ako su oni jednaki (kada je A² + 4B = 0), imamo

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

Ovo je najuopštenije rešenje; dve konstante C i D se mogu izabrati na osnovu početnih uslova  a₀ i a₁ kako bi se dobilo specifično rešenje.

U slučaju kompleksnih jedinstvenih rešenja (što takođe daje kompleksne vrednosti za rešenja parametara C i D), korišćenje kompleksnih brojeva može biti eliminisano pisanjem rešenja u trigonometrijskom obliku. U tom slučaju možemo napisati jedinstvena rešenja kao $\lambda _{1},\lambda _{2}=\alpha \pm \beta i.$ Zatim se može pokazati da

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

može biti napisano kao

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

gde

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

Ovde su E i F (ekvivalentno, G i δ) realne konstante koje zavise od početnih uslova. Korišćenjem

$\lambda _{1}+\lambda _{2}=2\alpha =A,$

$\lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,$

se može pojednostaviti rešenje dato itnad kao

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

gde su a₁ i a₂ početni uslovi i

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

U ovom slučaju nema potrebe rešavati λ₁ i λ₂.

U svakom slučaju za realna jedinstvena rešenja, realna dupla jedinstvena rešenja, i konjugovano kompleksna jedinstvena rešenja—jednačina je stabilna (tako je, promenljiva a pretvorena u fiksiranu vrednost (posebno, nula)); ako i samo ako su obe jedinstvene vrednosti  manje od jedne apsolutne vrednosti. U tom slučaju, ovaj uslov za jedinstvene vrednosti može biti prikazan tako da bude ekvivalentan sa |A| < 1 − B < 2, što je ekvivalentno |B| < 1 i |A| < 1 − B.

Jednačina u prethodnom primeru je bila homogena, u kojoj nije bilo konstantog člana. Ako polazi sa ne-homogenom rekurzijom

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

sa konstantim članom K, ona može biti pretvorena u homogeni oblik kao: Stabilno stanje je postignuto postavljanjem b_n = b_n−1 = b_n−2 = b* kako bi se dobilo

$b^{*}={\frac {K}{1-A-B}}.$

Onda ne-homogena rekurzija može biti napisana u homogenom obliku kao 

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

koja se može rešiti preko formule iznad.

Stabilan uslov koji je prethodno naveden za jedinstvene vrednosti u slučaj drugog-reda ostaje moguć za uopšten slučaj n^tog-reda: jednačina je stabilna ako i samo ako su sve jedinstvene vrednosti karakterističnih jednačina manje od jedne apslutne vrednosti.

Rešavanje preko linerane algebre

Linearan rekurzivan niz u reda n

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

je identičan sa

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

Proširen sa n-1 identitetima tipa $y_{n-k}=y_{n-k},$ ovakav n-ti red jednačina je preveden u sistem prvih n  nizova linearnih jednačina,

${\vec {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\ {\vec {y}}_{n-1}=C^{n}{\vec {y}}_{0}.$

Treba uočiti da se vektor ${\vec {y}}_{n}$ može izračunati preko n unošenja pridruženih matrica, C, na prvobitan vektor, $y_{0}$.  Time je, n-ti unos traženog niza y,   komponenta ${\vec {y}}_{n},y_{n}={\vec {y}}_{n}[n]$.

Jedinstveno razlaganje ${\vec {y}}_{n}={\vec {C}}^{n}\,{\vec {y}}_{0}=c_{1}\,\lambda _{1}^{n}\,{\vec {e}}_{1}+c_{2}\,\lambda _{2}^{n}\,{\vec {e}}_{2}+\cdots +c_{n}\,\lambda _{n}^{n}\,{\vec {e}}_{n}$ na jednistvene vrednosti, $\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}$, i jedinstvene vektore, ${\vec {e}}_{1},{\vec {e}}_{2},\ldots ,{\vec {e}}_{n}$,  se koristi da bi se izračunao ${\vec {y}}_{n}.$ Zahvaljujući bitnoj činjenici da sistem C zamenjuje svaki jednistven vektor, e, jednostavnim dodavanjem njegovih komponenata λ puta,

$C\,{\vec {e}}_{i}=\lambda _{i}{\vec {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}}$

to  jest, zamenjena verzija jednistvenog vektora,e, ima komponente λ puta veće, a komponente jednistvenog vektora su stepeni od λ, ${\vec {e}}_{i}={\begin{bmatrix}\lambda _{i}^{n-1}&\cdots &\lambda _{i}^{2}&\lambda _{i}&1\end{bmatrix}}^{T},$ a, takođe, rešenje rekurzivne linearne homogene jednačine je kombinacija eksponencijalih funkcija, ${\vec {y}}_{n}=\sum _{1}^{n}{c_{i}\,\lambda _{i}^{n}\,{\vec {e}}_{i}}$. Komponente $c_{i}$ mogu biti određene preko početnih uslova:

${\vec {y}}_{0}={\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}=\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{0}\,{\vec {e}}_{i}}={\begin{bmatrix}{\vec {e}}_{1}&{\vec {e}}_{2}&\cdots &{\vec {e}}_{n}\end{bmatrix}}\,{\begin{bmatrix}c_{1}\\c_{2}\\\cdots \\c_{n}\end{bmatrix}}=E\,{\begin{bmatrix}c_{1}\\c_{2}\\\cdots \\c_{n}\end{bmatrix}}$

Rešavanje za koeficijente,

${\begin{bmatrix}c_{1}\\c_{2}\\\cdots \\c_{n}\end{bmatrix}}=E^{-1}{\vec {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}}.$

Ovo takođe radi sa proizvoljnim graničnim uslovima  $\underbrace {y_{a},y_{b},\ldots } _{\text{n}}$, i nisu neophodni početni uslovi,

${\begin{bmatrix}y_{a}\\y_{b}\\\vdots \end{bmatrix}}={\begin{bmatrix}{\vec {y}}_{a}[n]\\{\vec {y}}_{b}[n]\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{a}\,{\vec {e}}_{i}[n]}\\\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{b}\,{\vec {e}}_{i}[n]}\\\vdots \end{bmatrix}}={\begin{bmatrix}\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{bmatrix}}=$

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

Ovakav opis se zaista ne razlikuje od uopštenih metode gore navedenih, međutim mnogo je sažetiji. On takođe radi u situacijama tipa

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

kada ima nekoliko povezanih rekurzija.

Rešavanje pomoću Z-transformacija

Izvesne diferencne jednačine - posebno, linearne sa konstantnim koeficijentima  - se mogu rešiti pomoću Z-transformacija. Z-transformacije su deo integralnih transformacija koje pružaju znatno korisnije algebarske manipulacije i mnogo jednostavnija rešenja. Postoje slučajevi u kojima bi direktno traženje rešenja bilo nemoguće, a sa druge strane rešavanje takvih problema pomoću posebnih integralnih transformacija bi bilo vrlo jednstavno.

Teorema

Data je linearno homogena rekurzivna relacija sa konstantnim koeficijentima reda d, neka je p(t) karakteristični polinom (takođe i  "pomoćni polinom")

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

takav da svaki c_i odgovara svakom c_i u originalnom rekurzivnom dnosu (videti uopšten uslov iznad). Pretpostavimo da je λ koren od p(t) koji ima raznovrsnost r. Tada (t−λ)^r deli p(t). Naredna dva svojstva sadrže:

1. Svaki r niz $\lambda ^{n},n\lambda ^{n},n^{2}\lambda ^{n},\dots ,n^{r-1}\lambda ^{n}$ zadovoljava rekurzivnu relaciju.
2. Bilo koji niz koji zadovoljava rekurzivnu relaciju može biti napisan kao linearna kombinacija rešenja konstruisanih u prvom delu kao λ zavisi od svih jedinstvenih rešenja p(t).

Kao rezultat ove teoremem, linearna homogena rekurzivna relacija sa konstantnim koeficijentima se može rešiti preko:

1. Nalaženja karakterističnog polinoma p(t).
2. Nalaženja korena p(t) preko množenja.
3. Pisanja a_n kao linearne kombinacije rešenja (preko množenja kao što je pokazano u teoremi iznad) sa nepoznatim koeficijentima b_i.

$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)$

Ovo je uopšteno rešenje originalne rekurzivne relacije. (q je raznovrsnost po λ_*)

4. Izjednačavanja svakog $a_{0},a_{1},\dots ,a_{d}$ iz trećeg dela (ubacujući  n = 0, ..., d u opšta rešenja rekurzivne relacije) sa poznatim vrednostima $a_{0},a_{1},\dots ,a_{d}$ iz rekurzivne relacije. Međutim, vrednosti a_n iz originalne rekurzivne relacije ne moraju uvek da budu granične: isključujući posebne slučajeve, samo je d potrebno (tj.., za originalnu linearnu homogenu rekurzivnu relaciju reda tri je moguće koristiti vrednosti a₀, a₁, a₄). Ovaj proces će proizvesti linearni sistem od d jednačina sa d nepoznatih. Rešavanje ovih jednačina sa nepoznatim koeficijetima $b_{1},b_{2},\dots ,b_{d}$ opštih rešenja i vraćanjem tih vrefnosti u opšte rešenje će proizvesti poebno rešenje za originalnu rekurzivnu relaciju koje odgovara originalnoj rekurzivnoj rlaciji početnih uslova (kao i sve sledstvene vrednosti $a_{0},a_{1},a_{2},\dots$ originalne rekurzivne relacije).

Metod za rešavanje linearnih diferencijalnih jednačina je sličan metodu iznad—"pametna pretpostavka" (anzac) za linearne diferencijalne jednačine sa konstantnim koeficijentima je e^λx gde je λ kompleksan broj koji se dobija zamenom pretpostavke u samoj diferencijalnoj jednačini.

Ovo nije slučajnost. Razmatrajući Tejlorov polinom za rešenje linearne diferecijalne jednačine:

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

može se videti da su koeficijenti polinoma dati za  n^ti izvod od f(x) dospeli do tačke a. Diferencijalna jednačina daje linearnu diferencnu jednačinu vezanu ovim koeficjentima.

Ova jednakost se može koristiti za brzo rešavanje rekurzivnog odnosa za koeficijente u stepenoj seriji rešenja linearne diferencijalne jednačine.

Pravilo palca (za jednačine u kojima je polinomsko množenje prvog člana  ne-nula) je dato kao:

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

uopštenije

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

Primer: Rekurzivan odnos za koeficijente Tejlorovog polinoma jednačine:

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

je dat kao

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

ili

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

Ovaj primer pokazuje kako se problemi koji se najčešće rešavaju pomoću metoda stepene serije za normalne diferencijalne jednačine mogu rešiti na mnogo prostiji način.

Primer: Diferencijalna jednačina

$ay''+by'+cy=0$

ima rešenje

$y=e^{ax}.$

Zamena diferencijalne jednačine diferencnom jednačinom Tejlorovih koeficijenata je

$af[n+2]+bf[n+1]+cf[n]=0.$

Lako se vidi da n-ti izvod od e^ax za 0 dostiže aⁿ

Rešavanje ne-homogenih rekurzivnih relacija

Ako je rekurzija nehomogena, svojstveno rešenje se može naći pomoću metode neodređenih koeficijenata odakle je rešenje zbir homogenog i svojstvenog rešenja. Još jedan metod za rešavanje nehomogenih rekurzija je metoda simboličke diferencijacije. Na primer, razmotrimo sledću rekurziju:

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

 Ovo je nehomogena rekurzija. Ako zamenimo n ↦ n+1, dobijamo rekurziju

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

Zamenom originalne rekurzije iz ove jednačine dobijamo

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

čemu je ekvivalentno

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

Ovo je homogena rekurzija, koja se može rešiti pomoću prethodno opisanih metoda. U opštem smislu, ako linearna ekurzija ima oblik

$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)$

gde su $\lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}$ konstantni koeficijenti i p(n) je nehomogeno, onda, ako je p(n) polinom stepena r, ovakva nehomogena rekurzija može biti redukovana na homogenu primenom metode simboličkog diferenciranja r puta.

Ako je

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

generativna funkcija nehomogenosti, generativna funkcija

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

nehomogene rekurzije

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

sa konstantnim koeficijentima c_i je izvedena iz

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

Ako je P(x) racionalna generativna funkcija, A(x) je takođe. Slučaj koji je već diskutovan, gde je p_n = K konstanta, predstavlja primer ovr formule, gde je P(x) = K/(1−x). Drugi primer, rekurzija $a_{n}=10a_{n-1}+n$ sa linearnom nehomogenošću, se pojavljuje u definiciji šizofrenih brojeva. Rešenje homogenih rekurzija je predstavljeno kao p = P = 0.

Rešavanje ne-homogenih rekurzivnih relacija sa promenljivim koeficijentima

Štaviše, za uopštene linearne nehomogene rekurzivne relacije prvog-reda sa promenljivim koeficijentima važi:

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

ovo se može rešiti pomoću metoda:

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

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

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

Neka je

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

Onda

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

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

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

$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)$

Uopštene linearno homogene rekurzivne relacije

Mnoge linearno homogene rekurzivne relacije mogu biti pokrivene pod uopštena hipergeometrijska serija. Njeni posebni slučajevi vode ka rekurzivnoj relaciji za ortogonalne polinome, i za mnoge specijalne funkcije. Na primer, rešenje za

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

je dato kao

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

Beselova funkcija, dok

$(b-n)M_{n-1}+(2n-b-z)M_{n}-nM_{n+1}=0\,$

je rešeno preko

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

Kumerove funkcije.

Rešavanje racionalne diferencne jednačine prvog-reda

Racionalne diferencne jednačine prvog reda imaju oblik $w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}$. Takva jednačina se može rešiti pisanjem $w_{t}$ kao nelinearne transformacije druge promenljive $x_{t}$ koja raste linearno. Onda se standardne metode mogu koristiti za rešavanje linearne diferencne jednačine za $x_{t}$.

Stabilnost

Stabilnost linearnih rekurzija višeg reda

Linearna rekurzija reda d,

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots +c_{d}a_{n-d},\,$

ima karakterističnu jednačinu

$\lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\dots -c_{d}\lambda ^{0}=0.\,$

Rekurzija je stabilna, što znači da vrednost iteracije konvergira asimptotski ka fiksnoj vrednosti, ako i samo ako su sve jedinstvene vrednosti (tj.., koreni karakteristične jednačine), realne ili kompleksne, zajedno manje od jedan po apsolutnoj vrednosti.

Stabilnost linearnih matričnih rekurzija prvog reda

U matričnoj diferencnoj jednačini prvog reda

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

sa stalnim vektorom x i trnzicionom matricom A, x asimptotski teži ka stabilnom stanju vektora x* ako i samo ako su sve jedinstvene vrednosti tranzicione matrice A (realne ili kompleksne) imaju apsolutnu vrednost koja je manja od 1.

Stabilnost nelinearnih rekurzija prvog reda

Razmotrimo nelinearnu rekurziju prvog reda

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

Ova rekurzija je lokalno stabilna, što znači da teži ka fiksnoj tački x* od tačaka koje su dovoljno blizu x*, ako je pad po f u blizini x* manji od  jedan po apsolutnoj vrednosti: onda je,

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

Nelinearna rekurzija može imati više fiksnih tačaka, i u tom slučaju neke fiksne tačke mogu biti lokano stabilne a druge lokalno nestabilne; za stalno f dve susedne fiksne tačke ne mogu obe biti lokalno stabilne.

Nelinearna rekurzivna relacija može takođe da ima kružni period k za k > 1. Takav krug je stabilan, što znači da on privlači niz početnih uslova pozitivnih vrednosti, ako se složena funkcija

$g(x):=f\circ f\circ \cdot \cdot \cdot \circ f(x)$

sa f pojavljuje k puta onda je ona lokalno stabilna prema istom krtiterijumu:

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

gde je  x* bilo koja tačka kruga.

 U haotičnoj rekurzivnoj relaciji, promenljiva x ostaje ostaje u svom okruženju ali nikada ne teži kad fiksnoj tački ili privlačnom krugu; bilo koja fiksna tačka ili krug jednačine su nestabilni. Vidi još logističku mapu, duplirajuću mapu , i šator mapu.

Veza sa diferencijalnim jednačinama

Kada se rešava obična diferencijalna jednačina numerički, ona se najčešće svodi na rekurzivnu relaciju. Na primer, kada se rešava problem početnih vrednosti

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

preko Ojlerovog metoda gde je korak veličine h, vrednosti se mogu izračunati 

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

preko rekurzije

$\,y_{n+1}=y_{n}+hf(t_{n},y_{n}).$

Sistemi linearnih diferencijalnih jednačina prvog reda mogu da se diskretizuju analitički korišćenjem metoda prikazanih u članku- diskretizacija.

Primena

Biologija

Neke od vrlo poznatih diferencnih jednačina imaju svoju primenu u modelovanju dinamike stanovništva. Na primer, Fibonačijev niz se nekada koristio kao model za izračunavanje razvića populacije kod zečeva.

Logistička mapa se koristi i kao direktan model za populacioni rast, ili kao početna tačka za mnoge druge modele. U ovom kontekstu, parne diferencne jednačine se često koriste kao model za prikazivanje odnosa dve ili više populacija. Na primer, Nicholson-Bailey model za odnos domaćin-parazit izgleda kao

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

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

gde je N_t broj domaćina, i P_t parazita u vremenu t.

Integrodiferencne jednačine su oblik rekurzivnih relacija koje su važne za prostornu ekologiju. Ove kao i druge diferencne jednačine su kao stvorene za modelovanje univolitne populacija.

Računarska nauka

Rekurzivne relacije su takođe od ključnog značaja u analizi algoritama. Ako je algoritam dizajniran tako da problem rastavi na više sitnih problema (podeli pa vladaj), njegovo vreme rada je opisano pomoću rekurzivne relacije.

Jednostavan primer je vreme koje je potrebno algoritmu da pronađe element u poretku vektora od $n$ elemenata, u najgorem slučaju.

Naivan algorita će tražiti sleva nadesno, jedan element po vremenu. Najgori mogući scenario je kada je potrebni element poslednji, tako da je broj poređenja $n$.

Znatno bolji algoritam se naziva binarna pretraga . Međutim, on zahteva sortitan vektor. Prvo će proveriti da li je element u sredini vektora. Ako nije, on će proveriti da li je element u sredini veći ili manji od traženog elementa. U početnom trenutku, polovina vektora ćr biti odbačena, a algoritam će pretraživati drugu polovinu. Broj komparacija će biti

$c_{1}=1$

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

što će približno biti $\log _{2}(n)$.

Procesovanje digitalnih signala

U procesiranju digitalnih signala, rekurzivni odnosi mogu napraviti spregu u sistemu, gde sadašnja izlazna informacija postaje buduća ulazna. Oni se takođe koriste i za beskonačni impulsni odziv (BIO) digitalnih filtera.

Na primer, jednačina za "spregu unapred" BIO komb filtera  kašnjenja T je:

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

Gde je $x_{t}$ ulazna informacija za neko vreme t, $y_{t}$ izlazna, i α kontroliše koliko kasni neki signal. Odatle imamo

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

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

itd.

Ekonomija

Rekurzivne relacije, posebno linearne, se koriste i u teoretskoj i u empirijskoj ekonomiji. Posebno, u makroekonomiji one se mogu koristiti kao modeli za veliki broj ekonomskih sektora (finansijski sektor, sektor za robu, tržište rada, itd.) u kojima posao nekog agenta zavisi od zastojnih varijabli. Model bi se prvo rešio za trenutne vrednosti ključnih promenljivih (kamatna stopa, realan BDP, itd.) u smislu egzogenih promenljih i preostalih endogenih promenljivih. Vidi još i analizu vremenskih serija.

Vidi još

• Iterativna funkcija
• Matrična diferencna jednačina
• Ortogonalni polinomi
• Rekurzija
• Rekurzija (računarske nauke)
• Usporen Fibonačijev generator
• Master teorema
• Podela kruga na oblasti
• Verižni razlomak
• Račun na vremenskoj skali
• Integrodiferencna jednačina
• Kombinatorički principi
• Beskonačni impulsni odziv

Literatura

• Batchelder, Paul M. (1967). An introduction to linear difference equations. Dover Publications. 
• Cheng, Sui Sun (2003). Partial Difference Equations. CRC Press. ISBN 978-0-415-29884-1. 
• Miller, Kenneth S. (1968). Linear difference equations. W.  A. Benjamin.
• Fillmore, Jay P.; Marx, Morris L. (1968). „Linear Recursive Sequences”. SIAM Review. 10 (3): 342—353. Bibcode:1968SIAMR..10..342F. JSTOR 2027658. S2CID 14722188. doi:10.1137/1010059. 
• Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
• Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (1990). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.  Chapter 4: Recurrences. str. 62–90.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, ur. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd izd.). Addison-Welsey. ISBN 978-0-201-55802-9. 
• Hazewinkel, Michiel, ur. (2001). „Finite-difference calculus”. Encyclopedia of Mathematics. Springer. ISBN 978-1-55608-010-4. 
• Enders, Walter (2010). Applied Econometric Times Series (3 ed.).
• Cull, Paul; Flahive, Mary; Robson, Robbie (2005). „7”. Difference Equations: From Rabbits to Chaos. Springer. ISBN 978-0-387-23234-8. 
• Jacques, Ian (2006). „Difference Equations”. Mathematics for Economics and Business (5thd izd.). Prentice Hall. str. 551-568. ISBN 978-0-273-70195-8. 
• Minh, Tang; Van To, Tan (2006). "Using generating functions to solve linear inhomogeneous recurrence equations" Arhivirano na sajtu Wayback Machine (4. mart 2016) (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. str. 399–404.
• Polyanin, Andrei D. "Difference and Functional Equations: Exact Solutions". at EqWorld - The World of Mathematical Equations.
• Polyanin, Andrei D. "Difference and Functional Equations: Methods". at EqWorld - The World of Mathematical Equations.

Spoljašnje veze

• Weisstein, Eric W., "Recurrence Equation", MathWorld.
• Mathews, John H. "Homogeneous Difference Equations".
• Balakrishnan, V. K. (1991). Introductory Discrete Mathematics. Dover Publications. str. 95—. ISBN 978-0-486-69115-2. 
• "OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)