Relació de recurrència

De Viquipèdia
Jump to navigation Jump to search

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ó[modifica]

Una equació recurrent és un tipus específic de relació de recurrència. Una relació de recurrència per a la successió és una equació que relaciona amb algun dels seus predecessors . Les condicions inicials per a la successió 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 , é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:

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 anàlisi no lineal.

Resolució[modifica]

Iteració[modifica]

Per resoldre una relació de recurrència associada a la successió: per iteració, utilitzem la relació de recurrència per escriure el n-èsim terme 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[modifica]

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

sent funcions reals de , i 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ó l'ordre és dos, perquè ha d'haver almenys dos termes anteriors (ja siguin usats o no).

exemples:

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

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

Per poder trobar una solució, calen unes condicions de contorn o inicials , sent kel grau de l'equació.

La recurrència lineal, juntament amb les condicions inicials , 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:

La generació de la funció racional[modifica]

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, , n≥d que tenen seqüència i funció de generació una suma d'una sèrie geomètrica:

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

amb funció de generació

la sèrie és aniquilada per i anteriorment pel polinomi:

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

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

com dividint:

expressant la funció de generació com una funció racional. El denominador és , 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 .

Relació amb equacions de diferència[modifica]

Donada una seqüència de nombres reals: la primera diferència es defineix com

La segona diferència es defineix com ,

que es pot simplificar a .

Més general: la diferència es defineix com

A diferència de l'equació és una equació composta per 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:

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

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ó[modifica]

siguin

una equació de recurrència lineal homogènia, la seva equació característica i, les arrels de l'equació característica amb multiplicitats respectivament. La solució d'aquesta equació seria:

Amb el polinomi de grau menor o igual que . Per poder calcular els coeficients dels polinomis <, necessitem saber les condicions inicials de l'equació de recurrència.

Exemple: Nombres de Fibonacci[modifica]

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

amb els valors inicials:

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:

per tant, la solució general és:

Per trobar el valor de i resolem les equacions:

llavors:

i

La forma tancada per als nombres de Fibonacci és:

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

Rep el nom d'equació de recurrència lineal no homogènia de grau k, amb coeficients constants, una expressió del tipus: .

Resolució[modifica]

La solució general seria: , on és la solució de l'equació de recurrència lineal homogènia associada és a dir l'equació: i on é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:

* 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[modifica]

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

Amb les condicions inicials:

Es resol la següent homogènia:

L'equació característica és: , entonces

Llavors:

A continuació, es resol l'equació particular: , llavors .

, llavors igualant amb les condicions inicials la solució és:

Recurrències No lineals[modifica]

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 , hi ha un teorema molt útil que és el teorema Mestre.

La recurrència en la computació[modifica]

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[modifica]

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:

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

resolem l'homogènia:

resolguem ara la particular:

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

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

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

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

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

Aplicacions[modifica]

Biologia[modifica]

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 dóna per

amb Nt que representa els hostes, i Pt 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[modifica]

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:

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

etc.

Economia[modifica]

Les relacions de recurrència, especialment la recurrència lineal, s'usa tant en economia teòrica com 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[modifica]

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 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 .

Vegeu també[modifica]

Referències[modifica]

  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)