Relació de recurrència

En matemàtica, una relació de recurrència és una equació que defineix una seqüència recursiva; cada terme de la seqüència es defineix com una funció de termes anteriors.

El terme equació de diferència es refereix a un tipus específic de ralació de recurrència. No obstant, s'utilitza sovint «equació de diferència» per referir-se a qualsevol relació de recurrència.

Definició

Una equació recurrent és un tipus específic de relació de recurrència. Una relació de recurrència per a la successió $a_{0},a_{1},a_{2},\ldots$ és una equació que relaciona $a_{n}\,$ amb algun dels seus predecessors $a_{0},a_{1},\ldots ,a_{n-1}$ . Les condicions inicials per a la successió $a_{0},a_{1},\ldots$ són valors donats en forma explícita per a un nombre finit de termes de la successió. ^[1]

Resoldre una relació de recurrència consisteix a determinar una fórmula explícita (tancada) per al terme general $a_{n}\,$ , és a dir una funció no recursiva de 'n' .

Hi ha dos mètodes per resoldre relacions recurrents: iteració i un mètode especial que s'aplica a les relacions de recurrència lineals homogènies amb coeficients constants.

Un exemple d'una relació de recurrència és el següent:

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

Algunes definicions de recurrència poden tenir relacions molt complexes (caòtiques), i els seus comportaments de vegades són estudiats pels físics i matemàtics en un camp conegut com a anàlisi no lineal.

Resolució

Iteració

Per resoldre una relació de recurrència associada a la successió: $a_{0},a_{1},a_{2}\,$ per iteració, utilitzem la relació de recurrència per escriure el n-èsim terme $a_{n}\,$ en termes d'alguns dels seus predecessors. Després utilitzem de manera successiva la relació de recurrència per reemplaçar cadascun dels termes per alguns dels seus predecessors. Continuem fins a arribar a algun dels casos base.

Recurrències Lineals

Una relació de recurrència és lineal de grau k si té la següent estructura:

c_{0}(n)a_{n}+c_{1}(n)a_{n-1}+\dots +c_{k-1}(n)a_{n-k+1}+c_{k}(n)a_{n-k}\,=0

sent $c_{i}(n)\,$ funcions reals de $n\,$ , i $F(n)\,$ una funció de n.^[2]

L'adjectiu lineal indica que cada terme de la seqüència està definit com una funció lineal dels seus termes anteriors. El ordre d'una relació de recurrència lineal és el nombre de termes anteriors exigits per la definició.

En la relació $a_{n}=a_{n-2}\,$ l'ordre és dos, perquè ha d'haver almenys dos termes anteriors (ja siguin usats o no).

exemples:

3a_{n}-{n-1}a_{n-1}+2a_{n-2}=0\,

Equació de Recurrència lineal homogènia amb coeficients constants

Es diu equació de recurrència lineal homogènia de grau k, amb coeficients constants, a una expressió del tipus:

a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=0,c_{i}\in \mathbf {R} ,c_{k}\neq 0

Per poder trobar una solució, calen unes condicions de contorn o inicials $a_{0},a_{1},\cdots ,a_{k-1}$ , sent kel grau de l'equació.

La recurrència lineal, juntament amb les condicions inicials $a_{0},\cdots ,a_{k-1}$ , determinen la seqüència única.

Sigui l'equació de recurrència lineal homogènia d'ordre k anterior, es denomina equació característica a l'equació de grau k:

x^{k}+c_{1}x^{k-1}+\cdots +c_{k}

La generació de la funció racional

Les seqüències lineals recursiva són precisament les seqüències la funció de generació és una funció racional: el denominador és el polinomi auxiliar (a una transformació), i el numerador s'obté amb els valors inicials.

El cas més senzill són les seqüències periòdiques, $a_{n}=a_{nd}$ , n≥d que tenen seqüència $a_{0},a_{1},\cdots ,a_{d-1},a_{0},\cdots$ i funció de generació una suma d'una sèrie geomètrica:

{\begin{array}{ll}{\cfrac {a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1}}{1-x^{d}}}=&(a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1})+\\&(a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1})x^{d}+\\&(a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1})x^{2d}+\\&\dots \end{array}}

Més general, donada la relació de recurrència:

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

amb funció de generació

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

la sèrie és aniquilada per $a_{k}$ i anteriorment pel polinomi:

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

Això és, multiplicant la funció de generació pel polinomi

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

com el coeficient a $x^{n}$ , que desapareix (per la relació de recurrència) per n ≥ d. així:

(a_{0}+a_{1}x^{1}+a_{2}x^{2}+\dots )(1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d})=(b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1})

com dividint:

a_{0}+a_{1}x^{1}+a_{2}x^{2}+\dots ={\cfrac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}}

expressant la funció de generació com una funció racional. El denominador és $x^{d}p(1/x)$ , una transformació del polinomi auxiliar (equivalent, invertint l'ordre dels coeficients); també es pot usar qualsevol múltiple d'aquesta, però aquesta normalització és triada per ambdues perquè la relació simple del polinomi auxiliar, i d'aquesta manera $b_{0}=a_{0}$ .

Relació amb equacions de diferència

Donada una seqüència $\{a_{n}\}\,$ de nombres reals: la primera diferència $d(a_{n})\,$ es defineix com a $a_{n}-a_{n-1}\,$

La segona diferència $d^{2}(a_{n})\,$ es defineix com a $d(a_{n})-d(a_{n-1})\,$ ,

que es pot simplificar a $a_{n}-2a_{n-1}+a_{n-2}\,$ .

Més general: la diferència $d^{k}\,$ es defineix com a $d^{k-1}(a_{n})-d^{k-1}(a_{n-1})\,$

A diferència de l'equació és una equació composta per $a_{n}$ i les seves diferències. Cada relació de recurrència pot ser formulada com una equació de diferència. Per contra, cada equació de diferència pot ser formulada com una relació de recurrència. Alguns autors així utilitzen els dos termes intercanviables. Per exemple, l'equació de la diferència:

3d^{2}(a_{n})+2d(a_{n})+7a_{n}=0\,

és equivalent a la relació de recurrència:

12a_{n}=8a_{n-1}-3a_{n-2}\,

D'aquesta manera es pot resoldre relacions de recurrència per la reiteració com a equacions diferència, i després la solució de l'equació de diferència, anàlogament com una solució d'equacions diferencials ordinàries.

Veure escala de temps de càlcul per a la unificació de la teoria de les equacions de diferència amb la de les equacions diferencials.

Resolució

siguin

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

una equació de recurrència lineal homogènia, $x^{k}+c_{n-1}x^{k-1}+\cdots +c_{nk}$ la seva equació característica i, $x_{1},x_{2},\cdots ,x_{s}$ les arrels de l'equació característica amb multiplicitats $m_{1},m_{2},\cdots ,m_{s}$ respectivament. La solució d'aquesta equació seria:

$a_{n}=P_{1}(n)(x_{1})^{n}+P_{2}(n)(x_{2})^{n}+\cdots +P_{s}(n)(x_{s})^{n}$

Amb $P_{i}(n)\$ el polinomi de grau menor o igual que $m_{i}-1\,$ . Per poder calcular els coeficients dels polinomis < $P_{i}(n)\,$ , necessitem saber les condicions inicials de l'equació de recurrència.

Exemple: Nombres de Fibonacci

Els nombres de Fibonacci estan definits usant la següent relació de recurrència lineal:

F_{n}=F_{n-1}+F_{n-2}\,

amb els valors inicials:

F_{1}=0\,

F_{2}=1\,

La seqüència dels nombres de Fibonacci comença: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ... L'objectiu de la resolució de l'equació de recurrència és trobar una forma tancada per calcular els nombres de Fibonacci.

L'equació característica és la següent:

x^{2}-x-1=0\,

x_{1}={\frac {1+{\sqrt {5}}}{2}}\,

x_{2}={\frac {1-{\sqrt {5}}}{2}}\,

per tant, la solució general és:

F(n)=A_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+A_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}

Per trobar el valor de $A_{1}$ i $A_{2}$ resolem les equacions:

F_{1}=A_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)+A_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)

F_{2}=A_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{2}+A_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{2}

llavors:

A_{1}={\frac {1}{\sqrt {5}}}

i

A_{2}={\frac {-1}{\sqrt {5}}}

La forma tancada per als nombres de Fibonacci és:

F(n)={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)

Equació de Recurrència lineal no homogènia amb coeficients constants

Rep el nom d'equació de recurrència lineal no homogènia de grau k, amb coeficients constants, una expressió del tipus: $c_{0}a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{nk}=F(n),c_{i}\in \mathbf {R} ,c_{k}\neq 0$ .

Resolució

La solució general seria: $a_{n}=a_{n}^{(h)}+a_{n}^{(p)}$ , on $a_{n}^{(h)}$ és la solució de l'equació de recurrència lineal homogènia associada és a dir l'equació: $c_{0}a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{nk}=0,c_{i}\in \mathbf {R} ,c_{k}\neq 0$ i on $a_{n}^{(p)}$ és la solució particular que depèn de la funció F ( n ). Per tant els passos a seguir serien, primer calcular la solució de l'equació homogènia, calcular una solució particular per a F ( n ) i sumar-la a l'homogènia, i a continuació aplicar les condicions inicials per calcular les constants. A la següent taula, trobem quines són les possibles solucions particulars:

$F(n)$		${a_{n}}^{(p)}$
$C,{\rm {constant}}$		$C_{0},{\rm {constant}}$
$n$		$C_{0}+C_{1}n$
$n^{2}$		$C_{0}+C_{1}n+C_{2}n^{2}$
$n^{t},t\in \mathbf {Z} ^{+}$		$C_{0}+C_{1}n+\cdots +C_{t}n^{t}$
$r^{n},r\in \mathbf {R}$		$C_{0}r^{n}$
$n^{t}r^{n}$		$r^{n}(C_{0}+C_{1}n+C_{2}n^{2})$
$\sin(An),A\in \mathbf {R}$		$C_{0}\sin(An)+C_{1}\cos(An)$
$\cos(An),A\in \mathbf {R}$		$C_{0}\sin(An)+C_{1}\cos(An)$
$r^{n}\sin(An),A\in \mathbf {R}$		$C_{0}r^{n}\sin(An)+C_{1}r^{n}\cos(An)$
$r^{n}\cos(An),A\in \mathbf {R}$		$C_{0}r^{n}\sin(An)+C_{1}r^{n}\cos(An)$

* Consideracions:

1.- Si F ( n ) és una combinació lineal d'algunes de les funcions de la taula anterior, la seva solució particular és la combinació lineal de les solucions particulars d'aquestes mateixes funcions.

2.- Si un dels sumands de F ( n ) és el producte d'una constant per una solució de l'equació característica homogènia associada, llavors cal multiplicar la solució particular corresponent a aquest sumant per la menys potència de n , n' tal que aquest nou producte no sigui solució de l'equació característica homogènia associada.

Exemple: Torres de Hanoi

L'equació de recurrència associada amb el problema de les Torres de Hanoi és la següent:

T_{n}=2T_{n-1}+1\,

Amb les condicions inicials:

T_{1}=1\,

Es resol la següent homogènia:

T_{n}^{(h)}=2T_{n-1}

L'equació característica és: $x-2=0$ , entonces $x=2$

Llavors: $T_{n}^{(h)}=A2^{n}$

A continuació, es resol l'equació particular: $T_{n}^{(p)}=B=2B+1$ , llavors $B=-1$ .

$T_{n}=A2^{n}-1\,$ , llavors igualant amb les condicions inicials la solució és: $T_{n}=2^{n}-1\,$

Recurrències No lineals

Per resoldre recurrències no lineals tenim moltes opcions de les quals:

Cercar transformacions o canvis de variables que facin la recurrència lineal.
Per al cas $t(n)=a\cdot t\left({\frac {n}{b}}\right)+f(n)$ , hi ha un teorema molt útil que és el teorema Mestre.

La recurrència en la computació

La connexió amb l'anàlisi d'algorismes estreba que la forma que s'ha adoptat per mesurar les complexitats, utilitza funcions el domini són els nombres naturals, o en altres paraules, successions. Si l'algorisme és recurrent, és d'esperar que les complexitats, com a funcions que estimen la demanda de recursos al llarg de l'execució, siguin successions que satisfan certes equacions de recurrència. En un algorisme recursiu, la funció t (n) que estableix la seva complexitat ve donada per una equació de recurrència. Una equació de recurrència ens permeten indicar el temps d'execució per als diferents casos de l'algorisme recursiu (casos base i recursiu).

Exemple: Càlcul del factorial

int Fact(int n){
if(n<=0)
return 0;
else if(n==1)
return 1;
return n*Fact(n-1);
}

Considerant el producte com a operació bàsica, podem construir l'equació recurrent per calcular la complexitat de l'algorisme de la manera següent:

Com es veu en el codi, el cas base és per a n <= 1, per a aquests valors de n el nombre de multiplicacions que es realitza és 0. I en un altre cas es 1 més les necessàries per calcular el factorial de n-1. Així construïm la funció recurrent:

t(n)={\begin{cases}0&{\mbox{si }}n\leq 1\\t(n-1)+1&{\mbox{si }}n>1\end{cases}}

Ara si resolem l'equació recurrent sabrem la complexitat d'aquest algorisme en funció de n. Procedim a resoldre aquesta equació recurrent no lineal:

t(n)=t(n-1)-1\,

resolem l'homogènia:

t(n)=t(n-1)\longrightarrow \quad r-1=0\longrightarrow \quad r=1a_{n}^{h}=c1^{n}\longrightarrow \quad a_{n}^{h}=c

resolguem ara la particular:

com la particular 'coincideix amb la r, hem d'augmentar el grau multiplicant per n

\longrightarrow a_{n}^{p}=n1^{n}\longrightarrow \quad a_{n}^{p}=n

de manera que la solució de l'equació recurrent queda així:

t(n)=c+n\,

Ara calculem c utilitzant el cas base, t (1) = 0

t(1)=c+1=0\longrightarrow \quad c=-1

ja tenim la solució: t (n) = n - 1

L'equació que ens ha quedat és de grau 1 pel que la complexitat és de l'ordre exacte de n -> θ (n)

Per exemple per calcular el factorial de 3 necessitarem t (3) productes el que és igual a

3-1=2\longrightarrow \quad 3\cdot (2\cdot (1))

Com veiem són 2 productes com ens ha tornat l'equació.

Aplicacions

Biologia

Algunes de les equacions de diferència més ben conegudes tenen el seu origen en l'intent de fer un model de dinàmica de la població- Per exemple, el nombres de Fibonacci s'usaren ca a model pel creixement de la població de conills. El mapa logístic s'utilitza o directament com a model de creixement de població, o com a punt d'inici de models més detallats. En aquest context, les equacions de diferència acoblades s'usen sovint per fer un model de la interacció de dues o més poblacions. Per exemple, el model de Nicholson-Bailey per la interacció hoste-paràsit es dona per

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

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

amb N_t que representa els hostes, i P_t els paràsits, en un temps t.

Les equacions d'integrodiferència són una forma de relació de recurrència important en ecologia espacial. Aquestes i altres equacions de diferència són particularment adequades per modes de poblacions univoltines.

Processament de senyals digitals

En processament de senyals digitals, les relacions de recurrència poden retroalimentar el model en un sistema, on les sortides de cop es converteixen en entrades futures. D'aquesta manera sorgeixen filtres digitals IIR.

Per exemple, l'equació per un filtre pinta IIR d'endarreriment T és:

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

On $x_{t}$ és l'entrada a temps t, $y_{t}$ és la sortida a temps t, i α controla com el senyal endarrerit retroalimenta la sortida. D'aquí podem veure que

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

etc.

Economia

Les relacions de recurrència, especialment la recurrència lineal, s'usa tant en economia teòrica com en economia empírica.^[3] En particular, en macroeconomia es pot desenvolupar un model d'amplis sectors de l'economia (sector financer, sector de bens, mercat laboral, etc) en el que algunes accions dels agents depenen de variables endarrerides. El model llavors es resoldria per a valors corrents de variables clau (taxa d'interès, PIB real, etc.) en termes de variables exògenes i endògenes endarrerides.

Ciència computacional

Les relacions de recurrència també són fonamentals en l'anàlisi d'algorismes.^[4]^[5] Si un algoritme està dissenyat per tal que trenqui un problema en subproblemes més petits, el temps d'execució es descriu mitjançant una relació de recurrència.

Un exemple senzill és el temps que un algoritme necessita per trobar un element en un vector ordenat amb $n$ elements, en el pitjor cas.

Un algoritme senzill cercarà d'esquerra a dreta, un element en cada moment. El pitjor escenari possible és presenta quan l'element requerit és l'últim, per tant el nombre de comparacions és is $n$ .

Vegeu també

Recursivitat

Referències

↑ «Matemàtiques Discretes». Pearson Education, 2005, pàg. 280.
↑ Brouseau, Alfred «Linear Recursion and Fibonacci Sequences». Fibonacci Association, 1971.(anglès)
↑ Sargent, Thomas J., Dynamic Macroeconomic Theory, Harvard University Press, 1987.(anglès)
↑ Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009(anglès)
↑ R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013(anglès)

[1] «Matemàtiques Discretes». Pearson Education, 2005, pàg. 280.

[2] Brouseau, Alfred «Linear Recursion and Fibonacci Sequences». Fibonacci Association, 1971.(anglès)

[3] Sargent, Thomas J., Dynamic Macroeconomic Theory, Harvard University Press, 1987.(anglès)

[4] Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009(anglès)

[5] R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013(anglès)

[1]

[2]

[3]

[4]

[5]