Диференцне једначине

У математици, диференцна једначина је једначина која рекурзивно дефинише низ или мултидимензионални ред вредности, једном када је један или више почетних услова дато: сваки следећи члан низа или реда је дефинисина као функција претходних услова.

Термин диференцна једначина се понекад (као што је случај у овом чланку) односи на специфичан тип рекурзивне релације. Међутим, "диференцна једначина" се често односи на све типове рекурзивних релација.

Примери

Логистичка мапа

Пример рекурзивне релације је логистичка мапа:

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

са датом константом r; датим почетним условом x₀ сваки члан подниза је одређен овом релацијом.

Неке једноставно дефинисане рекурзивне релације могу имати веома комплексне (теорија хаоса) особине, и они припадају пољу математике који је познат под називом нелинеарна анализа.

Решавање рекурзивне релације значи постизање решења затвореног типа: нерекурзивна функција по n.

Фибоначијев низ

Фибоначијев низ је прототип линеарне, хомогене рекурзивне релације са костантним коефицијентима (видети испод). Они су дефинисани помоћу линеарне рекурзивне релације.

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

са почетним условима:

$F_{0}=0$

$F_{1}=1$

Експлицитно, рекурзија даје једначине:

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

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

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

итд.

Добијамо низ Фибоначијевих бројева, који почиње:

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

Он се може решити помоћу метода које су описане у наставку, добијањем израза затвореног типа, који укључује степене два решења карактеристичног полинома t² = t + 1;  генеративна функција низа је рационална функција:

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

Биномни коефицијенти

Једноставан пример мултидимензионалне рекурзивне релације је дат помоћу биномног коефицијента ${\tbinom {n}{k}}$, који рачуна број начина селектовања k из сета од n елемената. Они се могу израчунати помоћу рекурзивне релације

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

где су почетни услови ${\tbinom {n}{0}}={\tbinom {n}{n}}=1$. Коришћење ове формуле за израчунавање вредности свих биномних коефицјената, ствара бесконачан ред који је назван Паскалов троугао. Те вредности се такође могу израчунати и директно помоћу формуле која није рекурзивна, али то захтева множење а не само сабирање: ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$

Структуре

Линеарне хомогене рекурзивне релације са константним коефицијентима

Низ d линеарне хомогене рекурзивне релације са константним коефицијентима је једначина форме

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

где су d и коефицијенти c_i (за свако i) константе.

Прецизније, ово је бесконачна листа сличних линеарних једначина, једна за свако n>d−1. Низ који задовољава релацију овог облика се зове линеарни рекурзивни низ или ЛРС. ЛРС има d степена слободе, као почетне вредности $a_{0},\dots ,a_{d-1}$ се могу узети било које вредности али онда линеарна рекурзија одређује низ јединствено.

Исти коефицијенти дају карактеристични полином (такође "помоћни полином")

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

чија d решења играју битну улогу у налажењу и разумевању низа који задовољава рекурзију. Ако су сва решења r₁, r₂, ... посебна, онда је решење рекурзије облика

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

где је коефицијент k_i  одређен тако да одговара почетним условима рекурзије. Када се исти корени појаве већи број пута, чланови формуле који одговарају другом и наредним појавама истог корена се множе тако да им степенови буду n. На пример, ако карактеристични полином може бити факторисан као (x−r)³, са истим кореном r који се појављује три пута, онда ће решење бити облика

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

Као и Фибоначијев низ, и остали низови настали линеарном хомогеном рекурзијом укључујући Лукасове бројеве и Лукасов низ, Јакобсталове бројеве, Пелове бројеве као и решење Пелове једначине.

Рационална генеративна функција

Линеарни рекурзивни низови су прецизније низови чија је генеративна функција, рационална: именилац је полином добијен од помоћног полинома мењањем редоследа коефицијената, и бројилац је одређен почетним вредностима низа.

Најједноставнији случајеви су периодични низови, $a_{n}=a_{n-d},n\geq d$, чији је низ $a_{0},a_{1},\dots ,a_{d-1},a_{0},\dots$ и генеративна функција збир геометријских серија:

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

Уопштеније, дата рекурзивна релација:

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

са генеративном фукнцијом

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

серија је прекунита за a_d и изнад полиномом:

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

Тако, множењем генеративне функције полиномом се добија

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

што представља коефицијент уз $x^{n}$, и нестаје (рекурзивном релацијом) за n ≥ d. Тако

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

да дељење даје

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

представљајући генеративну функцију као рационалну.

Именилац је $x^{d}p\left(x^{-1}\right),$  трансформација помоћног полинома (еквивалентно, променом редоследа коефицјената); могао је да се узме и било који чинилац, али овај стандард је изабран због једноставне везе са  помоћним полиномом, тако да је $b_{0}=a_{0}$.

Однос са уско дефинисаним диференцним једначинама

Дати поредак низа $\left\{a_{n}\right\}_{n=1}^{\infty }$ реалних бројева: прва диференца $\Delta (a_{n})$ је дефинисана са

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

Друга диференца  $\Delta ^{2}(a_{n})$ је дефнисана са

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

која се може упростити на

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

Уопштено: k^та диференца низа a_n , написана као $\Delta ^{k}(a_{n})$ је дефинисана рекурзивно као

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

(Низ и његове диференце су повезани преко биномне трансформације.) Рестриктивнија дефиниција диференцне једначине је једначина састављена од a_n и њених k^ти диференци. (широко распрострањена дефиниција третира "диференцне једначине" као синоним за "рекурзивну релацију". Видети на пример рационалну диференцну једначину и матричну диференцну једначину.)

Заправо, лако се види да је$a_{n+k}={n \choose 0}a_{n}+{n \choose 1}\Delta (a_{n})+\cdots +{n \choose k}\Delta ^{k}(a_{n}).$ Тако, диференцна једначина може бити дефинисана као једначина које укључује a_n, a_n-1, a_n-2 итд. (или евентуално a_n, a_n+1, a_n+2 итд.)

Како су диференцне једначине врло препознатљив облик рекурзије, неки аутори користе ова два израза наизменично. На пример, диференцна једначина

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

је еквивалентна рекурзивној релацији

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

Тако да се многе рекурзивне релације могу решити превођењем у диференцне једначине, а онда аналогно решавању диференцних једначина, се могу решити обичне диференцијалне једначине. Међутим, Акерманова функција  је пример рекурзивне релације која се не пресликава у диференцијалну једначину.

Видети рачун на временској скали везан за уједињење теорије о диференцним једначинама са диференцијалним једначинама.

Дискретне интегралне једначине су везане за диференцне једначине као што су интегралне једначине везане за диференцијалне једначине.

Од низова до мрежа

Једно-променљиве или једно-димензионалне рекурзивне релације су везане та низове (тј. функције дефинисане на једно-димензионалним мрежама). Више-променљиве или н-димензионалне рекурзивне релације су везане за н-димензионалне мреже. Функције дефинисане на н-мрежама се такође могу изучавати у оквиру парцијалних диференцних једначина.

Решавање

Уопштене методе

За низ 1, рекурзија

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

има решење a_n = rⁿ са a₀ = 1 а најуопштеније решење је a_n = krⁿ са a₀ = k. Карактетистични полином изједначен са нулом је (карактеристична једначина)  t − r = 0.

Решења овакве рекурзивне релације вишег реда се налазе систематски, често се користи чињеница да је a_n = rⁿ  решење рекурзије тачно када је t = r  корен карактеристичног полинома. Овоме се може приступити директно или преко генеративних функција (формални степени ред) или матрица.

Размотримо, на пример, рекурзивну релацију облика

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

Када има решење облика a_n = rⁿ?  Заменом ове претпоставке (анзац) у рекурзивној релацији, налазимо да

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

мора бити тачно за свако n > 1.

Дељењем са rⁿ⁻², добијамо да се све једначине своде на исту ствар:

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

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

што је карактеристика једначине рекурзивне релације. Решавањем r добијамо два корена λ₁, λ₂: ови корени су познати као карактеристични корени (решења) или јединствена решења карактеристичне једначине. Другачија решења се добијају у зависности од природе корена: Ако су ови корени посебни, имамо уопштено решење

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

док, ако су они једнаки (када је A² + 4B = 0), имамо

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

Ово је најуопштеније решење; две константе C и D се могу изабрати на основу почетних услова  a₀ и a₁ како би се добило специфично решење.

У случају комплексних јединствених решења (што такође даје комплексне вредности за решења параметара C и D), коришћење комплексних бројева може бити елиминисано писањем решења у тригонометријском облику. У том случају можемо написати јединствена решења као $\lambda _{1},\lambda _{2}=\alpha \pm \beta i.$ Затим се може показати да

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

може бити написано као

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

где

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

Овде су E и F (еквивалентно, G и δ) реалне константе које зависе од почетних услова. Коришћењем

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

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

се може поједноставити решење дато итнад као

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

где су a₁ и a₂ почетни услови и

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

У овом случају нема потребе решавати λ₁ и λ₂.

У сваком случају за реална јединствена решења, реална дупла јединствена решења, и конјуговано комплексна јединствена решења—једначина је стабилна (тако је, променљива a претворена у фиксирану вредност (посебно, нула)); ако и само ако су обе јединствене вредности  мање од једне апсолутне вредности. У том случају, овај услов за јединствене вредности може бити приказан тако да буде еквивалентан са |A| < 1 − B < 2, што је еквивалентно |B| < 1 и |A| < 1 − B.

Једначина у претходном примеру је била хомогена, у којој није било константог члана. Ако полази са не-хомогеном рекурзијом

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

са константим чланом K, она може бити претворена у хомогени облик као: Стабилно стање је постигнуто постављањем b_n = b_n−1 = b_n−2 = b* како би се добило

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

Онда не-хомогена рекурзија може бити написана у хомогеном облику као 

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

која се може решити преко формуле изнад.

Стабилан услов који је претходно наведен за јединствене вредности у случај другог-реда остаје могућ за уопштен случај n^тог-реда: једначина је стабилна ако и само ако су све јединствене вредности карактеристичних једначина мање од једне апслутне вредности.

Решавање преко линеране алгебре

Линеаран рекурзиван низ у реда n

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

је идентичан са

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

Проширен са n-1 идентитетима типа $y_{n-k}=y_{n-k},$ овакав n-ти ред једначина је преведен у систем првих n  низова линеарних једначина,

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

Треба уочити да се вектор ${\vec {y}}_{n}$ може израчунати преко n уношења придружених матрица, C, на првобитан вектор, $y_{0}$.  Тиме је, n-ти унос траженог низа y,   компонента ${\vec {y}}_{n},y_{n}={\vec {y}}_{n}[n]$.

Јединствено разлагање ${\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}$ на једниствене вредности, $\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}$, и јединствене векторе, ${\vec {e}}_{1},{\vec {e}}_{2},\ldots ,{\vec {e}}_{n}$,  се користи да би се израчунао ${\vec {y}}_{n}.$ Захваљујући битној чињеници да систем C замењује сваки једниствен вектор, e, једноставним додавањем његових компонената λ пута,

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

то  јест, замењена верзија једниственог вектора,e, има компоненте λ пута веће, а компоненте једниственог вектора су степени од λ, ${\vec {e}}_{i}={\begin{bmatrix}\lambda _{i}^{n-1}&\cdots &\lambda _{i}^{2}&\lambda _{i}&1\end{bmatrix}}^{T},$ а, такође, решење рекурзивне линеарне хомогене једначине је комбинација експоненцијалих функција, ${\vec {y}}_{n}=\sum _{1}^{n}{c_{i}\,\lambda _{i}^{n}\,{\vec {e}}_{i}}$. Компоненте $c_{i}$ могу бити одређене преко почетних услова:

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

Решавање за коефицијенте,

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

Ово такође ради са произвољним граничним условима  $\underbrace {y_{a},y_{b},\ldots } _{\text{n}}$, и нису неопходни почетни услови,

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

Овакав опис се заиста не разликује од уопштених методе горе наведених, међутим много је сажетији. Он такође ради у ситуацијама типа

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

када има неколико повезаних рекурзија.

Решавање помоћу Z-трансформација

Извесне диференцне једначине - посебно, линеарне са константним коефицијентима  - се могу решити помоћу Z-трансформација. Z-трансформације су део интегралних трансформација које пружају знатно корисније алгебарске манипулације и много једноставнија решења. Постоје случајеви у којима би директно тражење решења било немогуће, а са друге стране решавање таквих проблема помоћу посебних интегралних трансформација би било врло једнставно.

Теорема

Дата је линеарно хомогена рекурзивна релација са константним коефицијентима реда d, нека је p(t) карактеристични полином (такође и  "помоћни полином")

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

такав да сваки c_i одговара сваком c_i у оригиналном рекурзивном дносу (видети уопштен услов изнад). Претпоставимо да је λ корен од p(t) који има разноврсност r. Тада (t−λ)^r дели p(t). Наредна два својства садрже:

1. Сваки r низ $\lambda ^{n},n\lambda ^{n},n^{2}\lambda ^{n},\dots ,n^{r-1}\lambda ^{n}$ задовољава рекурзивну релацију.
2. Било који низ који задовољава рекурзивну релацију може бити написан као линеарна комбинација решења конструисаних у првом делу као λ зависи од свих јединствених решења p(t).

Као резултат ове теоремем, линеарна хомогена рекурзивна релација са константним коефицијентима се може решити преко:

1. Налажења карактеристичног полинома p(t).
2. Налажења корена p(t) преко множења.
3. Писања a_n као линеарне комбинације решења (преко множења као што је показано у теореми изнад) са непознатим коефицијентима 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)$

Ово је уопштено решење оригиналне рекурзивне релације. (q је разноврсност по λ_*)

4. Изједначавања сваког $a_{0},a_{1},\dots ,a_{d}$ из трећег дела (убацујући  n = 0, ..., d у општа решења рекурзивне релације) са познатим вредностима $a_{0},a_{1},\dots ,a_{d}$ из рекурзивне релације. Међутим, вредности a_n из оригиналне рекурзивне релације не морају увек да буду граничне: искључујући посебне случајеве, само је d потребно (тј.., за оригиналну линеарну хомогену рекурзивну релацију реда три је могуће користити вредности a₀, a₁, a₄). Овај процес ће произвести линеарни систем од d једначина са d непознатих. Решавање ових једначина са непознатим коефицијетима $b_{1},b_{2},\dots ,b_{d}$ општих решења и враћањем тих врефности у опште решење ће произвести поебно решење за оригиналну рекурзивну релацију које одговара оригиналној рекурзивној рлацији почетних услова (као и све следствене вредности $a_{0},a_{1},a_{2},\dots$ оригиналне рекурзивне релације).

Метод за решавање линеарних диференцијалних једначина је сличан методу изнад—"паметна претпоставка" (анзац) за линеарне диференцијалне једначине са константним коефицијентима је e^λx где је λ комплексан број који се добија заменом претпоставке у самој диференцијалној једначини.

Ово није случајност. Разматрајући Тејлоров полином за решење линеарне диферецијалне једначине:

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

може се видети да су коефицијенти полинома дати за  n^ти извод од f(x) доспели до тачке a. Диференцијална једначина даје линеарну диференцну једначину везану овим коефицјентима.

Ова једнакост се може користити за брзо решавање рекурзивног односа за коефицијенте у степеној серији решења линеарне диференцијалне једначине.

Правило палца (за једначине у којима је полиномско множење првог члана  не-нула) је дато као:

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

уопштеније

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

Пример: Рекурзиван однос за коефицијенте Тејлоровог полинома једначине:

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

је дат као

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

или

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

Овај пример показује како се проблеми који се најчешће решавају помоћу метода степене серије за нормалне диференцијалне једначине могу решити на много простији начин.

Пример: Диференцијална једначина

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

има решење

$y=e^{ax}.$

Замена диференцијалне једначине диференцном једначином Тејлорових коефицијената је

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

Лако се види да n-ти извод од e^ax за 0 достиже aⁿ

Решавање не-хомогених рекурзивних релација

Ако је рекурзија нехомогена, својствено решење се може наћи помоћу методе неодређених коефицијената одакле је решење збир хомогеног и својственог решења. Још један метод за решавање нехомогених рекурзија је метода симболичке диференцијације. На пример, размотримо следћу рекурзију:

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

 Ово је нехомогена рекурзија. Ако заменимо n ↦ n+1, добијамо рекурзију

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

Заменом оригиналне рекурзије из ове једначине добијамо

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

чему је еквивалентно

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

Ово је хомогена рекурзија, која се може решити помоћу претходно описаних метода. У општем смислу, ако линеарна екурзија има облик

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

где су $\lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}$ константни коефицијенти и p(n) је нехомогено, онда, ако је p(n) полином степена r, оваква нехомогена рекурзија може бити редукована на хомогену применом методе симболичког диференцирања r пута.

Ако је

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

генеративна функција нехомогености, генеративна функција

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

нехомогене рекурзије

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

са константним коефицијентима c_i је изведена из

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

Ако је P(x) рационална генеративна функција, A(x) је такође. Случај који је већ дискутован, где је p_n = K константа, представља пример овр формуле, где је P(x) = K/(1−x). Други пример, рекурзија $a_{n}=10a_{n-1}+n$ са линеарном нехомогеношћу, се појављује у дефиницији шизофрених бројева. Решење хомогених рекурзија је представљено као p = P = 0.

Решавање не-хомогених рекурзивних релација са променљивим коефицијентима

Штавише, за уопштене линеарне нехомогене рекурзивне релације првог-реда са променљивим коефицијентима важи:

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

ово се може решити помоћу метода:

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

Нека је

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

Онда

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

Уопштене линеарно хомогене рекурзивне релације

Многе линеарно хомогене рекурзивне релације могу бити покривене под уопштена хипергеометријска серија. Њени посебни случајеви воде ка рекурзивној релацији за ортогоналне полиноме, и за многе специјалне функције. На пример, решење за

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

је дато као

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

Беселова функција, док

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

је решено преко

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

Кумерове функције.

Решавање рационалне диференцне једначине првог-реда

Рационалне диференцне једначине првог реда имају облик $w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}$. Таква једначина се може решити писањем $w_{t}$ као нелинеарне трансформације друге променљиве $x_{t}$ која расте линеарно. Онда се стандардне методе могу користити за решавање линеарне диференцне једначине за $x_{t}$.

Стабилност

Стабилност линеарних рекурзија вишег реда

Линеарна рекурзија реда d,

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

има карактеристичну једначину

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

Рекурзија је стабилна, што значи да вредност итерације конвергира асимптотски ка фиксној вредности, ако и само ако су све јединствене вредности (тј.., корени карактеристичне једначине), реалне или комплексне, заједно мање од један по апсолутној вредности.

Стабилност линеарних матричних рекурзија првог реда

У матричној диференцној једначини првог реда

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

са сталним вектором x и трнзиционом матрицом A, x асимптотски тежи ка стабилном стању вектора x* ако и само ако су све јединствене вредности транзиционе матрице A (реалне или комплексне) имају апсолутну вредност која је мања од 1.

Стабилност нелинеарних рекурзија првог реда

Размотримо нелинеарну рекурзију првог реда

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

Ова рекурзија је локално стабилна, што значи да тежи ка фиксној тачки x* од тачака које су довољно близу x*, ако је пад по f у близини x* мањи од  један по апсолутној вредности: онда је,

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

Нелинеарна рекурзија може имати више фиксних тачака, и у том случају неке фиксне тачке могу бити локано стабилне а друге локално нестабилне; за стално f две суседне фиксне тачке не могу обе бити локално стабилне.

Нелинеарна рекурзивна релација може такође да има кружни период k за k > 1. Такав круг је стабилан, што значи да он привлачи низ почетних услова позитивних вредности, ако се сложена функција

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

са f појављује k пута онда је она локално стабилна према истом кртитеријуму:

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

где је  x* било која тачка круга.

 У хаотичној рекурзивној релацији, променљива x остаје остаје у свом окружењу али никада не тежи кад фиксној тачки или привлачном кругу; било која фиксна тачка или круг једначине су нестабилни. Види још логистичку мапу, дуплирајућу мапу , и шатор мапу.

Веза са диференцијалним једначинама

Када се решава обична диференцијална једначина нумерички, она се најчешће своди на рекурзивну релацију. На пример, када се решава проблем почетних вредности

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

преко Ојлеровог метода где је корак величине h, вредности се могу израчунати 

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

преко рекурзије

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

Системи линеарних диференцијалних једначина првог реда могу да се дискретизују аналитички коришћењем метода приказаних у чланку- дискретизација.

Примена

Биологија

Неке од врло познатих диференцних једначина имају своју примену у моделовању динамике становништва. На пример, Фибоначијев низ се некада користио као модел за израчунавање развића популације код зечева.

Логистичка мапа се користи и као директан модел за популациони раст, или као почетна тачка за многе друге моделе. У овом контексту, парне диференцне једначине се често користе као модел за приказивање односа две или више популација. На пример, Nicholson-Bailey модел за однос домаћин-паразит изгледа као

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

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

где је N_t број домаћина, и P_t паразита у времену t.

Интегродиференцне једначине су облик рекурзивних релација које су важне за просторну екологију. Ове као и друге диференцне једначине су као створене за моделовање униволитне популација.

Рачунарска наука

Рекурзивне релације су такође од кључног значаја у анализи алгоритама. Ако је алгоритам дизајниран тако да проблем растави на више ситних проблема (подели па владај), његово време рада је описано помоћу рекурзивне релације.

Једноставан пример је време које је потребно алгоритму да пронађе елемент у поретку вектора од $n$ елемената, у најгорем случају.

Наиван алгорита ће тражити слева надесно, један елемент по времену. Најгори могући сценарио је када је потребни елемент последњи, тако да је број поређења $n$.

Знатно бољи алгоритам се назива бинарна претрага . Међутим, он захтева сортитан вектор. Прво ће проверити да ли је елемент у средини вектора. Ако није, он ће проверити да ли је елемент у средини већи или мањи од траженог елемента. У почетном тренутку, половина вектора ћр бити одбачена, а алгоритам ће претраживати другу половину. Број компарација ће бити

$c_{1}=1$

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

што ће приближно бити $\log _{2}(n)$.

Процесовање дигиталних сигнала

У процесирању дигиталних сигнала, рекурзивни односи могу направити спрегу у систему, где садашња излазна информација постаје будућа улазна. Они се такође користе и за бесконачни импулсни одзив (БИО) дигиталних филтера.

На пример, једначина за "спрегу унапред" БИО комб филтера  кашњења T је:

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

Где је $x_{t}$ улазна информација за неко време t, $y_{t}$ излазна, и α контролише колико касни неки сигнал. Одатле имамо

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

итд.

Економија

Рекурзивне релације, посебно линеарне, се користе и у теоретској и у емпиријској економији. Посебно, у макроекономији оне се могу користити као модели за велики број економских сектора (финансијски сектор, сектор за робу, тржиште рада, итд.) у којима посао неког агента зависи од застојних варијабли. Модел би се прво решио за тренутне вредности кључних променљивих (каматна стопа, реалан БДП, итд.) у смислу егзогених променљих и преосталих ендогених променљивих. Види још и анализу временских серија.

Види још

• Итеративна функција
• Матрична диференцна једначина
• Ортогонални полиноми
• Рекурзија
• Рекурзија (рачунарске науке)
• Успорен Фибоначијев генератор
• Мастер теорема
• Подела круга на области
• Верижни разломак
• Рачун на временској скали
• Интегродиференцна једначина
• Комбинаторички принципи
• Бесконачни импулсни одзив

Литература

• 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. стр. 62–90.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, ур. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd изд.). Addison-Welsey. ISBN 978-0-201-55802-9. 
• Hazewinkel, Michiel, ур. (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 изд.). Prentice Hall. стр. 551-568. ISBN 978-0-273-70195-8. 
• Minh, Tang; Van To, Tan (2006). "Using generating functions to solve linear inhomogeneous recurrence equations" Архивирано на сајту Wayback Machine (4. март 2016) (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. стр. 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.

Спољашње везе

• Weisstein, Eric W., "Recurrence Equation", MathWorld.
• Mathews, John H. "Homogeneous Difference Equations".
• Balakrishnan, V. K. (1991). Introductory Discrete Mathematics. Dover Publications. стр. 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)