Equacions en diferències

De Viquipèdia
Salta a la navegació Salta a la cerca
No s'ha de confondre amb equacions diferencials.

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

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

on

és una funció, on X és un conjunt al qual han de pertànyer els elements d'una seqüència. Per , això defineix una seqüència única amb 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

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

Factorial[modifica]

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

i la condició inicial

Mapa logístic[modifica]

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

amb una constant r donada; donat el terme inicial x0 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[modifica]

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

amb condicions inicials

Explícitament, la recurrència produeix les equacions

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 t2 = t + 1; la funció generadora de la seqüència és la funció racional

Coeficients binomials[modifica]

Un senzill exemple de relació de recurrència multidimensional ve donat pels coeficients binomials , 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

amb les condicions inicials .

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:

Relacions amb equacions en diferències estretament definides[modifica]

Donada una successió ordenada de nombres reals:

  • La primera diferència es defineix com
  • La segona diferència es defineix com

que es pot simplificar a

  • De manera general, la diferència k-èsima de la successió an , denotada , es defineix recursivament com

(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 an 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,

Així, una equació en diferència es pot definir com una equació que implica an, an-1, an-2 , etc. (o de manera equivalent, an, an+1, an+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

equival a la relació de recurrència

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

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

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

Arrels de polinomis característics[modifica]

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

on els d coeficients ci (per a tot i) són constants, i .

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

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

on els ki 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 (xr)3, amb la mateixa arrel r que es produeix tres vegades, llavors la solució prendria la forma

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

té la solució an = rn amb a0 = 1 i la solució més general és an = krn amb a0 = 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 an = rn é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

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

ha de ser cert per a tot n > 1.

Dividint a través de rn−2, assolim que totes aquestes equacions es redueixin a la mateixa cosa:

que és l'equació característica de la relació de recurrència. Resolent r per obtenir les dues arrels λ1, λ2: 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

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

Aquesta és la solució més general; les dues constants C i D es poden triar en funció de dues condicions inicials a0 i a1 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 Aleshores es pot demostrar que

es pot reescriure com[4]

on

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

es pot simplificar la solució anterior

on a1 i a2 són les condicions inicials, i

D'aquesta manera, no cal resoldre λ1 ni λ2.

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

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ó bnbn−1bn−2b*, obtenint

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

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

de manera que cada ci correspon a cada ci 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 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 an com a combinació lineal de totes les arrels (comptant la multiplicitat com es mostra al teorema anterior) amb coeficients bi desconeguts.
Aquesta és la solució general a la relació de recurrència original (q és la multiplicitat de λ *).
4. Igualar cada a partir de la part 3 (connectant n = 0, ..., d a la solució general de la relació de recurrència) amb els valors coneguts de la relació de recurrència original. Tanmateix, els valors an 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 a0, a1, a4). Aquest procés produirà un sistema lineal de d equacions d amb incògnites. Resolent aquestes equacions per als coeficients desconeguts 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 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:

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:

i més generalment

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

és donat per

o

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

té la solució

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

És fàcil veure que la n-èsima derivada de eax avaluada a 0 és an

Resolució mitjançant àlgebra lineal[modifica]

Una seqüència linealment recursiva y d'ordre n

és idèntica a

Expandit amb n-1 identitats de tipus 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,

Es pot observar que el vector es pot calcular mitjançant n aplicacions de la matriu acompanyant, C, al vector d'estat inicial, . Per tant, la n-èsima entrada de la seqüència buscada y, és el component superior de .

La descomposició de valor propis, en valors pròpis, , i vectors pròpis, , és usada en el càlcul de Gràcies al fet crucial que el sistema C canvia tots els vectors, tan sols per escalar els seus components λ vegades,

é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 λ, i, per tant, la solució de l'equació lineal homogènia recurrent és una combinació de funcions exponencials, . Els components es pot determinar fora de les condicions inicials:

Resolent per coeficients,

Això també funciona amb unes condicions de frontera arbitràries , que no calen les condicions inicials,

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

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

Resolució amb transformades Z[modifica]

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

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:

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

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

o de forma equivalent

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

on 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

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

de la recurrència no-homogènia

amb coeficients constants ci deriva de

Si P(x) és una funció generatriu racional, A(x) també és un. El cas comentat anteriorment, on pn = 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 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[modifica]

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

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

Si fem

aleshores

Si apliquem la fórmula a 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[modifica]

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

és donada per

la funció de Bessel, mentre que

es resol per

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

L'equació de racionals en diferències de primer ordre té la forma . Aquesta equació es pot resoldre escrivint com a transformació no-lineal d'una altra variable que evoluciona linealment. Aleshores es poden utilitzar mètodes estàndard per resoldre l'equació en diferències lineals en .

Estabilitat[modifica]

Estabilitat de les recurrències lineals d'ordre superior[modifica]

La recurrència lineal d'ordre d,

té el polinomi característic

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

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

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

Considerem la recurrència no-lineal de primer ordre

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,

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

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

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

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

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

per recurrència

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

Biologia[modifica]

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

on Nt representa l'hoste, i Pt 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ó[modifica]

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

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

la complexitat temporal del qual serà .

Processament de senyals digitals[modifica]

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:

on és l'entrada (input) a l'hora 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:

etc.

Economia[modifica]

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

  1. Jacobson, 2009, p. § 0.4. 16.
  2. Cheng, 2003.
  3. Greene i Knuth, 1982, p. 17.
  4. Chiang, 2004, p. 576-585.
  5. Papanicolaou, Vassilis «On the asymptotic stability of a class of linear difference equations» (en anglès). Mathematics Magazine, 69(1), febrer 1996, pàg. 34-43.
  6. Maurer i Ralston, 1998, p. 609.
  7. «Special Functions» (Noia 64 mimetypes pdf.pngPDF) (en anglès).
  8. Cormen et al., 2009.
  9. Sedewick i Flajolet, 2009.
  10. Stokey, Lucas i Prescott, 1989.
  11. Ljungqvist i Sargant, 2004.

Bibliografia[modifica]

Vegeu també[modifica]

Enllaços externs[modifica]