Equacions en diferències

En matemàtiques, una relació de recurrència és una equació que defineix recursivament una successió o una matriu multidimensional de valors, un cop es donen un o més termes inicials; cada terme següent de la seqüència o matriu es defineix com una funció dels termes anteriors.

De vegades, el terme equació en diferències (i als efectes d'aquest article) fa referència a un tipus específic de relació de recurrència, que relaciona diferents successions, sent una d'elles una successió desconeguda. No obstant això, sovint s'utilitza «equació en diferències» per referir-se a qualsevol relació de recurrència.

Són similars a les equacions diferencials, substituint les funcions per successions. Per a la seva resolució sol utilitzar el mètode de la transformada Z

Definició

Una relació de recurrència és una equació que expressa cada element d'una successió en funció dels elements anteriors. Més exactament, en el cas que només hi hagi l'element immediatament precedent, una relació de recurrència té la forma

${\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{per a}}\quad n>0,}$

on

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

és una funció, on X és un conjunt al qual han de pertànyer els elements d'una seqüència. Per ${\displaystyle u_{0}\in X}$, això defineix una seqüència única amb ${\displaystyle u_{0}}$ com a primer element, anomenat valor inicial.^[1]

És fàcil modificar la definició per obtenir seqüències a partir del terme de l'índex 1 o superior.

Això defineix la relació de recurrència de primer ordre. Té forma la relació de recurrència d'ordre k

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

on ${\displaystyle \varphi :\mathbb {N} \times X^{k}\to X}$ és una funció que inclou k elements consecutius de la seqüència. En aquest cas, es necessiten k valors inicials per definir una seqüència.

Exemples

Factorial

El factorial es defineix per la relació de recurrència

${\displaystyle n!=n(n-1)!\quad {\text{per a}}\quad n>0,}$

i la condició inicial

${\displaystyle 0!=1.}$

Mapa logístic

Un exemple de relació de recurrència és el mapa logístic:

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

amb una constant r donada; donat el terme inicial x₀ cada terme posterior es determina per aquesta relació

Resoldre una relació de recurrència significa obtenir una solució en forma tancada, una funció no-recursiva de n.

Nombres de Fibonacci

La recurrència d'ordre dos satisfeta pels nombres de Fibonacci és l'arquetip d'una relació de recurrència lineal homogènia amb coeficients constants (vegeu més avall). La seqüència de Fibonacci es defineix mitjançant la recurrència

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

amb condicions inicials

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

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

Explícitament, la recurrència produeix les equacions

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

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

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

etc.

Obtenim la seqüència de números de Fibonacci, que comença

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

La recurrència es pot resoldre mitjançant mètodes descrits a continuació, obtenint la fórmula de Binet, que inclou potències de les dues arrels del polinomi característic t² = t + 1; la funció generadora de la seqüència és la funció racional

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

Coeficients binomials

Un senzill exemple de relació de recurrència multidimensional ve donat pels coeficients binomials ${\displaystyle {\tbinom {n}{k}}}$, que compten el nombre de maneres de seleccionar k elements entre un conjunt de n elements. Es poden calcular mitjançant la relació de recurrència

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

amb les condicions inicials ${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$.

Utilitzant aquesta fórmula per calcular els valors de tots els coeficients binomials es genera una matriu infinita anomenada triangle de Pascal. Els mateixos valors també es poden calcular directament mitjançant una fórmula diferent que no és una recurrència, però que requereix multiplicació i no només una addició per calcular:

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

Relacions amb equacions en diferències estretament definides

Donada una successió ordenada ${\displaystyle \left\{a_{n}\right\}_{n=1}^{\infty }}$ de nombres reals:

• La primera diferència ${\displaystyle \Delta (a_{n})}$ es defineix com

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

• La segona diferència ${\displaystyle \Delta ^{2}(a_{n})}$ es defineix com

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

que es pot simplificar a

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

• De manera general, la diferència k-èsima de la successió a_n, denotada ${\displaystyle \Delta ^{k}(a_{n})}$, es defineix recursivament com

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

(La seqüència i les seves diferències estan relacionades per una transformada binomial). La definició més restrictiva de l'equació en diferències és una equació composta per a_n i les seves k^èsimes diferències. (Una definició més àmpliament utilitzada tracta «equació en diferència» com a sinònim de «relació de repetició». Vegeu per exemple l'equació de racional en diferències i l'equació de matriu en diferències).

De fet, es veu fàcilment que,

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

Així, una equació en diferència es pot definir com una equació que implica a_n, a_n-1, a_{n-2 ,} etc. (o de manera equivalent, a_n, a_n+1, a_n+2, etc.)

Com que les equacions en diferències són una forma molt freqüent de recurrència, alguns autors utilitzen de manera intercanviable els dos termes. Per exemple, l'equació en diferències

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

equival a la relació de recurrència

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

Així, es pot resoldre moltes relacions de recurrència tornant a escriure-les com a equacions en diferències i, a continuació, resoldre l'equació en diferències, de manera analògica a com es resolen les equacions diferencials ordinàries. No obstant això, els nombres d'Ackermann són un exemple de relació de recurrència que no es correspon amb una equació en diferències, molt menys en la solució a una equació diferencial (Vegeu càlcul d'escala de temps per a una relacióde la teoria de les equacions en diferències amb la de les equacions diferencials).

Les equacions en sumes es relacionen amb equacions en diferències, ja que les equacions integrals es relacionen amb les equacions diferencials.

De successions a quadrícules

Les relacions de recurrència d'una sola variable o unidimensionals són sobre seqüències (és a dir, funcions definides a les quadrícules unidimensionals). Les relacions de recurrència multi-variables o n-dimensionals es refereixen a quadrícules n-dimensionals. Les funcions definides a les n-quadrícules també es poden estudiar amb equacions en diferències parcials.^[2]

Resolució

Resolució de relacions homogènies de recurrència lineal amb coeficients constants

Arrels de polinomis característics

Una recurrència lineal homogènia d'ordre d amb coeficients constants és una equació de la forma

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

on els d coeficients c_i (per a tot i) són constants, i ${\displaystyle c_{d}\neq 0}$.

Una seqüència constant-recursiva és una seqüència que satisfà una recuerrència d'aquesta forma. Hi ha d graus de llibertat per solucionar aquesta recurrència, és a dir, els valors inicials ${\displaystyle a_{0},\dots ,a_{d-1}}$ es pot considerar que són valors, però la recurrència determina la seqüència de forma única.

Els mateixos coeficients produeixen el polinomi característic (també «polinomi auxiliar»)

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

les d arrels les quals tenen un paper crucial per trobar i comprendre les seqüències que satisfan la recurrència. Si les arrels r₁, r₂, ... són diferents, llavors cada solució per a la recurrència pren la forma

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

on els k_i coeficients es determinen per adaptar-se a les condicions inicials de la recurrència. Quan les mateixes arrels es produeixen diverses vegades, els termes d'aquesta fórmula corresponents a la segona i posterior ocurrències de la mateixa arrel es multipliquen augmentant les potències de n. Per exemple, si el polinomi característic es pot factoritzar com (x−r)³, amb la mateixa arrel r que es produeix tres vegades, llavors la solució prendria la forma

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

A més dels nombres de Fibonacci, altres seqüències constant-recursiva inclouen els nombres de Lucas i la successió de Lucas, els nombres de Jacobsthal, els nombres de Pell i, més generalment, les solucions per a l'equació de Pell.

Per a l'ordre 1, la recurrència.

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

té la solució a_n = rⁿ amb a₀ = 1 i la solució més general és a_n = krⁿ amb a₀ = k. El polinomi característic equivocat a zero (l'equació característica) és simplement t − r = 0.

Les solucions a aquestes relacions de recurrència d'ordre superior es troben per mitjans sistemàtics, sovint utilitzant el fet que a_n = rⁿ és una solució per a la recurrència exactament quan t = r és una arrel del polinomi característic. Es pot abordar directament o utilitzant funcions generatrius (sèries formals de potències) o matrius.

Si es consiera, per exemple, una relació de recurrència de la forma

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

quan té una solució de la mateixa forma general que a_n = rⁿ? Substituint aquesta solució estimada (ansatz) en la relació de recurrència, trobem que

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

ha de ser cert per a tot n > 1.

Dividint a través de rⁿ⁻², assolim que totes aquestes equacions es redueixin a la mateixa cosa:

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

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

que és l'equació característica de la relació de recurrència. Resolent r per obtenir les dues arrels λ₁, λ₂: aquestes arrels es coneixen com les arrels característiques o valors propis de l'equació característica. S'obtenen diferents solucions segons la naturalesa de les arrels; Si aquestes arrels són diferents, tenim la solució general

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

mentre que si són idèntiques (quan A² + 4B = 0), tenim

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

Aquesta és la solució més general; les dues constants C i D es poden triar en funció de dues condicions inicials a₀ i a₁ per produir una solució específica.

En el cas de valors propis complexos (que també generen valors complexos per als paràmetres de solució C i D), es pot eliminar l'ús de nombres complexos reescrivint la solució en forma trigonomètrica. En aquest cas podem escriure els valors propis com ${\displaystyle \lambda _{1},\lambda _{2}=\alpha \pm \beta i.}$ Aleshores es pot demostrar que

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

es pot reescriure com^[4]

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

on

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

Aquí E i F (o equivalentment, G i δ) són constants reals que depenen de les condicions inicials. Utilitzant

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

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

es pot simplificar la solució anterior

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

on a₁ i a₂ són les condicions inicials, i

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

D'aquesta manera, no cal resoldre λ₁ ni λ₂.

En tots els casos (valors propis reals diferents, valors propis reals duplicats, i valors propis complexos conjugats) l'equació és estable (és a dir, la variable convergeix a un valor fix (específicament, zero)) si i només si ambdós valors propis tenen un valor absolut inferior a 1. En aquest cas de segon ordre, es pot demostrar que aquesta condició dels valors propis és equivalent a |A| < 1 − B < 2, que equival a |B| < 1 i |A| < 1 − B.^[5]

L'equació de l'exemple anterior era homogènia, ja que no hi havia un terme constant. Si es comença amb la recurrència no-homogènia

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

amb el terme K constant, es pot convertir en forma homogènia de la següent manera: L'estat estacionari es troba mitjançant per la configuració b_n = b_n−1 = b_n−2 = b*, obtenint

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

Lavors, la recurrència no-homogènia es pot reescriure de forma homogènia com

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

que es pot resoldre com abans.

La condició d'estabilitat esmentada anteriorment en termes de valors propis del cas de segon ordre continua essent vàlida per al cas general d'ordre n-èsim; l'equació és estable si i només si tots els valors propis de l'equació característica tenen un valor absolut inferior a 1.

Tenint en compte una relació de recurrència lineal homogènia amb coeficients constants de l'ordre d, fem que p(t) sigui el polinomi característic (també «polinomi auxiliar»)

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

de manera que cada c_i correspon a cada c_i en la relació de recurrència original (vegeu la forma general anterior). Suposem que λ és una arrel de p(t) amb multiplicitat r. Això vol dir que (t−λ)^r divideix p(t). Les dues propietats següents contenen:

1. Cadascuna de les r seqüències ${\displaystyle \lambda ^{n},n\lambda ^{n},n^{2}\lambda ^{n},\dots ,n^{r-1}\lambda ^{n}}$ satisfan la relació de recurrència.
2. Qualsevol seqüència que satisfaci la relació de recurrència es pot escriure de manera única com una combinació lineal de solucions construïdes en la primera part com a varies λ en funció de totes les arrels diferents de p(t).

Com a resultat d'aquest teorema, es pot resoldre una relació de recurrència lineal homogènia amb coeficients constants de la següent manera:

1. Cercar el polinomi característic p(t).

2. Cercar les arrels de p(t) comptant la multiplicitat.

3. Escriure a_n com a combinació lineal de totes les arrels (comptant la multiplicitat com es mostra al teorema anterior) amb coeficients b_i desconeguts.

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

Aquesta és la solució general a la relació de recurrència original (q és la multiplicitat de λ * ).

4. Igualar cada ${\displaystyle a_{0},a_{1},\dots ,a_{d}}$ a partir de la part 3 (connectant n = 0, ..., d a la solució general de la relació de recurrència) amb els valors coneguts ${\displaystyle a_{0},a_{1},\dots ,a_{d}}$ de la relació de recurrència original. Tanmateix, els valors a_n de la relació de recurrència original usada no solen ser contigus: excloent casos excepcionals, només calen alguns d'ells (és a dir, per a una relació de recurrència lineal homogènia original d'ordre 3 es podria utilitzar els valors a₀, a₁, a₄). Aquest procés produirà un sistema lineal de d equacions d amb incògnites. Resolent aquestes equacions per als coeficients desconeguts ${\displaystyle b_{1},b_{2},\dots ,b_{d}}$ de la solució general i connectar aquests valors a la solució general produirà la solució particular a la relació de recurrència original que s'ajusta a les condicions inicials de la relació de recurrència original (així com a tots els valors posteriors ${\displaystyle a_{0},a_{1},a_{2},\dots }$ de la relació de recurrència original).

El mètode per a resoldre equacions diferencials lineals és similar al mètode anterior, la «endevinació intel·ligent» (ansatz) per a equacions diferencials lineals amb coeficients constants és e^λx, on λ és un nombre complex que es determinat substituint l'endevinació a l'equació diferencial.

No és casualitat. Considerant la sèrie de Taylor de la solució a una equació diferencial lineal:

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

es pot veure que els coeficients de la sèrie són donats per la n-èsima derivada de f(x) avaluada al punt a. L'equació diferencial proporciona una equació en diferències lineal relacionada amb aquests coeficients.

Aquesta equivalència es pot utilitzar per resoldre ràpidament la relació de recurrència dels coeficients en la solució de sèries de potència d'una equació diferencial lineal.

La regla general (per a les equacions en què el polinomi que multiplica el primer terme és diferent de zero) és la següent:

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

i més generalment

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

Exemple: La relació de recurrència dels coeficients de la sèrie de Taylor de l'equació:

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

és donat per

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

o

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

Aquest exemple mostra com els problemes resolts generalment mitjançant el mètode de solució de sèries de potència impartit en classes d'equacions diferencials normals es poden resoldre de manera molt més senzilla.

Exemple: L'equació diferencial

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

té la solució

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

La conversió de l'equació diferencial a una equació en diferència dels coeficients de Taylor és

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

És fàcil veure que la n-èsima derivada de e^ax avaluada a 0 és aⁿ

Resolució mitjançant àlgebra lineal

Una seqüència linealment recursiva y d'ordre 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}$

és idèntica a

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

Expandit amb n-1 identitats de tipus ${\displaystyle y_{n-k}=y_{n-k},}$ aquesta equació de n-èsim ordre es tradueix en un sistema d'equacions de matrius en diferències de n equacions lineals de primer ordre,

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

Es pot observar que el vector ${\displaystyle {\vec {y}}_{n}}$ es pot calcular mitjançant n aplicacions de la matriu acompanyant, C, al vector d'estat inicial, ${\displaystyle y_{0}}$. Per tant, la n-èsima entrada de la seqüència buscada y, és el component superior de ${\displaystyle {\vec {y}}_{n},y_{n}={\vec {y}}_{n}[n]}$.

La descomposició de valor propis, ${\displaystyle {\vec {y}}_{n}=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}}$ en valors pròpis, ${\displaystyle \lambda _{1},\lambda _{2},\ldots ,\lambda _{n}}$, i vectors pròpis, ${\displaystyle {\vec {e}}_{1},{\vec {e}}_{2},\ldots ,{\vec {e}}_{n}}$, és usada en el càlcul de ${\displaystyle {\vec {y}}_{n}.}$ Gràcies al fet crucial que el sistema C canvia tots els vectors, tan sols per escalar els seus components λ vegades,

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

és a dir, la versió canviada del vector propi, e (té components λ vegades més grans), els components del vector propi són potències de λ, ${\displaystyle {\vec {e}}_{i}={\begin{bmatrix}\lambda _{i}^{n-1}&\cdots &\lambda _{i}^{2}&\lambda _{i}&1\end{bmatrix}}^{T},}$ i, per tant, la solució de l'equació lineal homogènia recurrent és una combinació de funcions exponencials, ${\displaystyle {\vec {y}}_{n}=\sum _{1}^{n}{c_{i}\,\lambda _{i}^{n}\,{\vec {e}}_{i}}}$. Els components ${\displaystyle c_{i}}$ es pot determinar fora de les condicions inicials:

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

Resolent per coeficients,

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

Això també funciona amb unes condicions de frontera arbitràries ${\displaystyle \underbrace {y_{a},y_{b},\ldots } _{\text{n}}}$, que no calen les condicions inicials,

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

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

Aquesta descripció no és realment diferent del mètode general anterior, però és més succinta. També funciona molt bé per a situacions com ara

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

on hi ha diverses recurrències enllaçades.^[6]

Resolució amb transformades Z

Algunes equacions en diferències (en particular, les equacions en diferències de coeficients constants lineals) es poden resoldre mitjançant transformades Z. Les transformades Z són una classe de transformades integrals que condueixen a manipulacions algebraiques més convenients i solucions més senzilles. Hi ha casos en què l'obtenció d'una solució directa seria tot impossible però, tot i així, és senzill resoldre el problema mitjançant una transformada integral escollida.

Resolució de relacions de recurrències lineals no-homogènies amb coeficients constants

Si la recurrència és no-homogènia, es pot trobar una solució particular pel mètode de coeficients no determinats i la solució és la suma de les solucions homogènies i particulars. Un altre mètode per resoldre una recurrència no homogènia és el mètode de diferenciació simbòlica. Per exemple, considerem la repetició següent:

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

Es tracta d'una recurrència no-homogènia. Si substituïm n ↦ n+1, obtenim la recurrència

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

Restant la recurrència original a aquesta equació es produeix

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

o de forma equivalent

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

Es tracta d'una recurrència homogènia, que es pot resoldre mitjançant els mètodes explicats anteriorment. En general, si té forma la recurrència lineal

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

on ${\displaystyle \lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}}$ són coeficients constants i p(n) és la inhomogeneïtat, aleshores si p(n) és un polinomi amb grau r, aquesta recurrència no-homogènia es pot reduir a una recurrència homogènia aplicant el mètode de diferenciació simbòlica r vegades.

Si

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

és la funció generatriu de la inhomogeneïtat, la funció generatriu

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

de la recurrència no-homogènia

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

amb coeficients constants c_i deriva de

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

Si P(x) és una funció generatriu racional, A(x) també és un. El cas comentat anteriorment, on p_n = K és una constant, es presenta com un exemple d'aquesta fórmula, amb P(x) = K/(1−x). Un altre exemple, la recurrència ${\displaystyle a_{n}=10a_{n-1}+n}$ amb la inhomogeneïtat lineal, sorgeix en la definició dels nombres esquizofrènics. S'incorpora la solució de recurrències homogènies com p = P = 0.

Resolució de relacions de recurrència no-homogènies de primer ordre amb coeficients variables

A més, per a la relació de recurrència lineal no-homogènia de primer ordre amb coeficients variables:

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

també hi ha un bon mètode per resoldre-ho:^[7]

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

Si fem

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

aleshores

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

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

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

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

Si apliquem la fórmula a ${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}$ i prenem el límit h→0, obtenim la fórmula d'equacions diferencials lineals de primer ordre amb coeficients variables; la suma es converteix en una integral, i el producte es converteix en la funció exponencial d'una integral.

Resolució general de relacions de recurrència lineals

Moltes relacions de recurrència lineal homogènia es poden resoldre mitjançant la sèrie hipergeomètrica generalitzada. Els casos especials d'aquests condueixen a relacions de recurrència dels polinomis ortogonals i moltes funcions especials. Per exemple, la solució a

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

és donada per

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

la funció de Bessel, mentre que

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

es resol per

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

la sèrie hipergeomètrica confluent. Les seqüències que són les solucions d'equacions en diferències lineals amb coeficients polinòmics s'anomenen P-recursives. Per a aquestes equacions de recurrència específica es coneixen algorismes que troben solucions polinòmiques, racionals o hipergeomètriques.

Resolució d'equacions de racionals en diferències de primer ordre

L'equació de racionals en diferències de primer ordre té la forma ${\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}$. Aquesta equació es pot resoldre escrivint ${\displaystyle w_{t}}$ com a transformació no-lineal d'una altra variable ${\displaystyle x_{t}}$ que evoluciona linealment. Aleshores es poden utilitzar mètodes estàndard per resoldre l'equació en diferències lineals en ${\displaystyle x_{t}}$.

Estabilitat

Estabilitat de les recurrències lineals d'ordre superior

La recurrència lineal d'ordre d,

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

té el polinomi característic

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

La recurrència és estable, el que significa que les iteracions convergeixen asimptòticament a un valor fix, si i només si tots els valors propis (és a dir, els arrels del polinomi característic), siguin reals o complexos, tenen un valor absolut inferior a 1.

Estabilitat de les recurrències de matrius lineals de primer ordre

A l'equació de matrius en diferències de primer ordre

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

amb el vector d'estat x i la matriu de transició A, x convergeix asimptòticament al vector d'estat estacionari x* si i només si tots els valors propis de la matriu de transició A (ja siguin reals o complexos) tenen un valor absolut inferior a 1.

Estabilitat de les recurrències no-lineals de primer ordre

Considerem la recurrència no-lineal de primer ordre

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

Aquesta recurrència és localment estable, el que significa que convergeix a un punt fix x* des de punts prou propers a x*, si la pendent de f a la zona propera de x* té un valor absolut inferior a 1; és a dir,

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

Una recurrència no-lineal podria tenir diversos punts fixos. En aquest cas alguns punts fixos poden ser estables localment i altres localment inestables; per a f contínua, dos punts fixos adjacents no poden ser estables localment.

Una relació de recurrència no-lineal també podria tenir un cicle de període k per a k > 1. Aquest cicle és estable, el que significa que atrau un conjunt de condicions inicials de mesura positiva; si la funció composta

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

amb f apareixent k vegades, és localment estable segons el mateix criteri:

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

on x* és qualsevol punt del cicle.

En una relació de recurrència caòtica, la variable x es queda en una regió delimitada, però mai no convergeix a un punt fix o a un cicle d'atracció; tots els punts o cicles fixos de l'equació són inestables (Vegeu també mapa logístic, transformació diàdica i mapa de tenda).

Relació amb les equacions diferencials

Quan es resol numèricament una equació diferencial ordinària, se sol trobar una relació de recurrència. Per exemple, en resoldre el problema de valor inicial

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

amb el mètode d'Euler i un pas de mida h, es calculen els valors

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

per recurrència

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

Els sistemes d'equacions diferencials lineals de primer ordre es poden discretitzar exactament analíticament mitjançant els mètodes mostrats a l'article de discretització.

Aplicacions

Biologia

Algunes de les equacions en diferències més conegudes tenen l'origen en l'intent de modelar la dinàmica de poblacions. Per exemple, els nombres de Fibonacci van ser usats una vegada com a model per al creixement d'una població de conills.

El mapa logístic s'utilitza directament per modelar el creixement de la població o com a punt de partida per a models més detallats de dinàmica de poblacions. En aquest context, sovint s'utilitzen equacions en diferències per modelar la interacció de dues o més poblacions. Per exemple, el model de Nicholson-Bailey per a una interacció hoste-paràsit és donat per

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

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

on N_t representa l'hoste, i P_t el paràsit, al temps t.

Les equacions en integrodiferència són una forma de relació de recurrència important per a l'ecologia espacial. Aquestes i altres equacions en diferències s'adapten especialment a modelar poblacions univoltines.

Ciència de la computació

Les relacions de recurrència també són d'importància fonamental en l'anàlisi d'algorismes.^[8][9]

Si un algorisme està dissenyat de manera que convertirà un problema en subproblemes menors (dividèix i venceràs), el seu temps de funcionament es descriu amb una relació de recurrència.

Un exemple senzill és el temps que triga un algorisme a trobar un element amb un vector ordenat amb ${\displaystyle n}$ elements, en el pitjor dels casos.

Un algorisme ingenu cercarà d'esquerra a dreta, un element alhora. El pitjor escenari possible és quan l'element requerit és l'últim, de manera que el nombre de comparacions és ${\displaystyle n}$.

Un algorisme millor és l'anomenat cerca binària. Tot i això, requereix un vector ordenat. Primer comprovarà si l'element es troba al centre del vector. Si no és així, comprovarà si l'element mig és més gran o menor que l'element buscat. Arribats a aquest punt, es pot descartar la meitat del vector i l'algorisme es pot tornar a executar a l'altra meitat. El nombre de comparacions ve donat per

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

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

la complexitat temporal del qual serà ${\displaystyle O(\log _{2}(n))}$.

Processament de senyals digitals

En el processament de senyals digitals, les relacions de recurrència poden modelar feedback (retroalimentació) en un sistema, on les sortides es converteixen alhora en entrades per a temps futur. Així sorgeixen en filtres digitals de resposta infinita a l'impuls (filtre IIR).

Per exemple, l'equació per a un filtre pinta de resposta finita a l'impus (filtre FIR) de retard T és:

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

on ${\displaystyle x_{t}}$ és l'entrada (input) a l'hora t, ${\displaystyle y_{t}}$ és la sortida (output) a l'hora t, i α controla la quantitat del senyal retardat que es retorna a la sortida. A partir d'això podem observar:

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

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

etc.

Economia

Les relacions de recurrència, especialment les relacions de recurrència lineal, s'utilitzen àmpliament tant en economia teòrica com empírica.^[10][11] En particular, en macroeconomia es pot desenvolupar un model de diversos sectors amplis de l'economia (el sector financer, el sector de béns, el mercat laboral, etc.) en què les accions d'alguns agents depenen de variables retardades. Aleshores, el model es resoldria per a valors actuals de variables clau (tipus d'interès, PIB real, etc.) en termes de variables exògenes i variables endògenes endarrerides (vegeu també anàlisi de sèries temporals).

Referències

Bibliografia

• Batchelder, Paul M. An introduction to linear difference equations (en anglès). Dover Publications, 1967. 
• Brousseau, Alfred. Linear Recursion and Fibonacci Sequences (en anglès). Fibonacci Association, 1971. 
• Cheng, Sui Sun. Partial difference equations (en anglès). CRC Press, 2003. ISBN 978-0-415-29884-1. 
• Chiang, Alpha C. Fundamental Methods of Mathematical Economics (en anglès). McGraw-Hill, 2004. ISBN 978-1259097348. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. «cap 4: Recurrences». A: Introduction to Algorithms (en anglès). MIT Press i McGraw-Hill, 1990, p. 62-90. ISBN 978-0262033848. 
• Cull, Paul; Flahive, Mary; Robson, Robbie. «7». A: Difference Equations: From Rabbits to Chaos (en anglès). Springer, 2005. ISBN 0-387-23234-6. 
• Enders, Walter. Applied Econometric Times Series (en anglès), 2010. 
• Fillmore, Jay P.; Marx, Morris L. «Linear recursive sequences» (en anglès). SIAM Rev., 10(3), 1968, pàg. 324–353. JSTOR: 2027658.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics: A Foundation for Computer Science (en anglès). Addison-Welsey, 1994. ISBN 0-201-55802-5. 
• Greene, Daniel H.; Knuth, Donald E. «2.1.1 Constant coefficients – A) Homogeneous equations». A: Mathematics for the Analysis of Algorithms (en anglès). Birkhäuser, 1982. 
• Jacobson, Nathan. Basic Algebra 2 (en anglès). Dover Publications, 2009 (Dover Books on Mathematics). ISBN 978-0486471877. 
• Jacques, Ian. Mathematics for Economics and Business (en anglès). Prentice Hall, 2006. ISBN 0-273-70195-9. 
• Ljungqvist, Lars; Sargent, Thomas J. Recursive Macroeconomic Theory (en anglès). Cambridge: MIT Press, 2004. ISBN 0-262-12274-X. 
• Maurer, Stephen B.; Ralston, Anthony. Discrete Algorithmic Mathematics (en anglès). A K Peters, 1998. ISBN 9781568810911. 
• Miller, Kenneth S. Linear difference equations (en anglès). W. A. Benjamin, 1968. 
• Polyanin, Andrei D. «Difference and Functional Equations: Exact Solutions» (en anglès). EqWorld - The World of Mathematical Equations.
• Polyanin, Andrei D. «Difference and Functional Equations: Methods» (en anglès). EqWorld - The World of Mathematical Equations.
• Sedgewick, R.; Flajolet, F. An Introduction to the Analysis of Algorithms. Addison-Wesley, 2013. ISBN 978-0321905758. 
• Stokey, Nancy L.; Lucas, Robert E, Jr.; Prescott, Edward C. Recursive Methods in Economic Dynamics (en anglès). Harvard University Press, 1989. ISBN 0-674-75096-9. 
• Tang, Minh; Tan, Van To. «Using generating functions to solve linear inhomogeneous recurrence equations» (PDF) (en anglès). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06 p. 399-404, 2006. Arxivat de l'original el 2016-03-04. [Consulta: 18 desembre 2019].
• Wang, Xiang-Sheng; Wong, Roderick «Asymptotics of orthogonal polynomials via recurrence relations» (en anglès). Anal. Appl., 10(2), 2012, pàg. 215-235. arXiv: 1101.4371. DOI: 10.1142/S0219530512500108.

Vegeu també

• Algorisme recursiu
• Demostració per inducció
• Fracció contínua
• Recursivitat

Enllaços externs

• Michiel Hazewinkel (ed.). Recurrence relation. Encyclopedia of Mathematics (en anglès). Springer, 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric W., «Recurrence Equation» a MathWorld (en anglès).
• «OEIS Index Rec». OEIS índex a uns quants milers d'exemples de recurrències lineals, ordenades per ordre (nombre de termes) i signatura (vector de valors dels coeficients constants).