Relació de recurrencia

En matemàtica, una relació de recurrencia és una equació que definix una seqüència recursiva; cada terme de la seqüència és definit com una funció de térmens anteriors.^[1]

Definició

Una equació recurrent és un tipo específic de relació de recurrencia. Una relació de recurrencia per a la successió $a_{0}, a_{1}, a_{2}, \dots$ és una equació que relaciona $a_{n}$ en algun dels seus predecessors $a_{0}, a_{1}, \dots, a_{n - 1}$ . Les condicions inicials per a la successió $a_{0}, a_{1}, \dots$ són valors donats en forma explícita per a un número finito de térmens de la successió.^[2]

Resoldre una relació de recurrencia consistix en determinar una fòrmula explícita (tancada) per al terme general $a_{n}$ , és dir una funció no recursiva de n.

Hi ha tres métodos per a resoldre relacions recurrents: iteración, transformada Z i un método especial que s'aplica a les relacions de recurrencia llineals homogénees en coeficients constants.

Un eixemple d'una relació de recurrencia és el següent:

x_{n + 1} = r x_{n} (1 - x_{n})

Algunes definicions de recurrencia poden tindre relacions molt complexes (caòtiques), i els seus comportaments a voltes són estudiats pels físics i matemàtics en un camp conegut com anàlisis no llineal.

Resolució

Per hipòtesis comprovada

La forma més senzilla per a resoldre una relació de recurrencia és formular una possible solució (hipòtesis) i comprovar per inducció la validea de la mateixa.

En el cas de les "Torres d'Hanoi", sent $t$ el número de passos per a resoldre el problema en $n$ discs, $t_{n}$ està donat per la següent equació de recurrencia:

t_{1} : = 1; t_{n} : = 2 t_{n - 1} + 1

Resoldre la recurrencia seria trobar l'equació que nos dona el valor de $t_{n}$ en térmens de $n$ .

En analisar la correspondència per a cada valor de $t_{n}$ en n des de ${1, 2, 3, 4, 5} \to {1, 3, 7, 15, 31}$ especulem que potser la solució siga $t_{n} : = 2^{n} - 1$ , per lo que per a comprovar-la es procedix a substituir l'hipòtesis en l'equació de recurrencia:

t_{n} = 2 t_{n - 1} + 1 = 2 (2^{n - 1} - 1) + 1 = 2 (\frac{2^{n}}{2} - 1) + 1 = (2^{n} - 2) + 1 = 2^{n} - 1

comprovant-se l'hipòtesis com a verdadera.^[3]

Iteración

Per a resoldre una relació de recurrencia associada a la successió: $a_{0}, a_{1}, a_{2}$ per iteración, utilisem la relació de recurrencia per a escriure el n-ésimo terme $a_{n}$ en térmens d'alguns dels seus predecessors. Després utilisem de manera successiva la relació de recurrencia per a reemplaçar cada u dels térmens per alguns dels seus predecessors. Continuem fins a aplegar a algun dels casos base.

Recurrencias Llineals

Una relació de recurrencia és llineal d'orde k si té la següent estructura:

c_{0} (n) a_{n} + c_{1} (n) a_{n - 1} + ... + c_{k - 1} (n) a_{n - k + 1} + c_{k} (n) a_{n - k} = F (n)

per a $n \geq k$ , sent $c_{i} (n)$ funcions reals de $n$ , i $F (n)$ una funció de n.

L'adjectiu llineal indica que cada terme de la seqüència està definit com una funció llineal dels seus térmens anteriors. El orde d'una relació de recurrencia llineal és el número de térmens anteriors exigits per la definició.

En la relació $a_{n} = a_{n - 2}$ l'orde és dos, perque deu haver a lo manco dos térmens anteriors (ya siguen usats o no).

Eixemples :

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

Equació de Recurrencia llineal homogénea en coeficients constants

Es diu equació de recurrencia llineal homogénea d'orde k, en coeficients constants, a una expressió del tipo:

a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = 0, c_{i} \in 𝐑, c_{k} \neq 0

Per a poder trobar una solució, fan falta unes condicions de contorn o inicials $a_{0}, a_{1}, \dots, a_{k - 1}$ , sent k el grau de l'equació.

La recurrencia llineal, junt en les condicions inicials $a_{0}, \dots, a_{k - 1}$ , determinen la seqüència única.

Siga l'equació de recurrencia llineal homogénea d'orde k anterior, es denomina equació característica a l'equació de grau k:

x^{k} = c_{1} x^{k - 1} + \dots + c_{k}

La generació de la funció racional

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

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

\begin{matrix} \frac{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^{2 d} + \\ \dots \end{matrix}

Més general, donada la relació de recurrencia:

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

en funció de generació

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

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

1 - c_{1} x^{1} - c_{2} x^{2} - \dots - 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} - \dots - c_{d} a_{n - d}

com el coeficient en $x^{n}$ , que desapareix (per la relació de recurrencia) per a n ≥ d. Aixina:

(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 = \frac{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'orde dels coeficients); també es pot usar qualsevol múltiple d'esta, pero esta normalisació és elegida per abdós perque la relació simple del polinomi auxiliar, i d'eixe modo $b_{0} = a_{0}$ .

Relació en la diferència d'equacions

Donada una seqüència ${a_{n}}$ de número real: la primera diferència $d (a_{n})$ es definix com $a_{n} - a_{n - 1}$

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

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

Més general: la diferència $d^{k}$ es definix com $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 seues diferències. Cada relació de recurrencia pot ser formulada com una equació de diferència. Pel contrari, cada equació de diferència pot ser formulada com una relació de recurrencia. Alguns autors aixina utilisen els dos térmens intercanviables. Per eixemple, l'equació de la diferència:

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

és equivalent a la relació de recurrencia:

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

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

Vore escala de temps de càlcul per a l'unificació de la teoria de les equacions de diferència en la de les equacions diferencials.

Resolució

Sean

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

una equació de recurrencia llineal homogénea, $x^{k} + c_{n - 1} x^{k - 1} + \dots + c_{n - k}$ la seua equació característica i, $x_{1}, x_{2}, \dots, x_{s}$ les raïls de l'equació característica en multiplicitat $m_{1}, m_{2}, \dots, m_{s}$ respectivament. La solució d'esta equació seria:

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

Eixemple : Números de Fibonacci

Els números de Fibonacci estan definits usant la següent relació de recurrencia llineal:

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

en els valors inicials:

F_{1} = 1

F_{2} = 1

La seqüència dels números de Fibonacci comença: 1, 1, 2, 3 ,5, 8, 13, 21 ,34, 55, 89... L'objectiu de la resolució de l'equació de recurrencia és trobar una forma tancada per a calcular els números 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 lo tant, la solució general és:

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

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

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

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

Llavors:

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

i

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

La forma tancada per als números de Fibonacci és:

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

Equació de Recurrencia llineal no homogénea en coeficients constants

Rep el nom d'equació de recurrencia llineal no homogénea de grau k, en coeficients constants, una expressió del tipo: $c_{0} a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = F (n), c_{i} \in 𝐑, c_{k} \neq 0$ .

Resolució

La solució general seria: $a_{n} = a_{n}^{(h)} + a_{n}^{(p)}$ , a on $a_{n}^{(h)}$ és la solució de l'equació de recurrencia llineal homogénea associada és dir l'equació : $c_{0} a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = 0, c_{i} \in 𝐑, c_{k} \neq 0$ i a on $a_{n}^{(p)}$ és la solució particular que depén de la funció F(n). Per lo tant els passos a seguir serien, primer calcular la solució de l'equació homogénea, calcular una solució particular per a F(n) i sumar-la a l'homogénea, i a continuació aplicar les condicions inicials per a calcular les constants. En la següent taula, vàrem trobar cuales són les possibles solucions particulars:

$F (n)$		${a_{n}}^{(p)}$
$C, c o n s t a n t e$		$C_{0}, c o n s t a n t e$
$n$		$C_{0} + C_{1} n$
$n^{2}$		$C_{0} + C_{1} n + C_{2} n^{2}$
$n^{t}, t \in 𝐙^{+}$		$C_{0} + C_{1} n + \dots + C_{t} n^{t}$
$r^{n}, r \in 𝐑$		$C_{0} r^{n}$
$n^{t} r^{n}$		$r^{n} (C_{0} + C_{1} n + \dots + C_{t} n^{t})$
$\sin (A n), A \in 𝐑$		$C_{0} \sin (A n) + C_{1} \cos (A n)$
$\cos (A n), A \in 𝐑$		$C_{0} \sin (A n) + C_{1} \cos (A n)$
$r^{n} \sin (A n), A \in 𝐑$		$C_{0} r^{n} \sin (A n) + C_{1} r^{n} \cos (A n)$
$r^{n} \cos (A n), A \in 𝐑$		$C_{0} r^{n} \sin (A n) + C_{1} r^{n} \cos (A n)$

Consideracions:

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

2.- Si un dels sumants de F(n) és el producte d'una constant per una solució de l'equació característica homogénea associada, llavors és necessari multiplicar la solució particular corresponent a este sumant per la menor potència de n, tal que este nou producte no siga solució de l'equació característica homogénea associada.

Eixemple: Torres de Hanói

L'equació de recurrencia associada en el problema de les Torres de Hanói és la següent:

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

En les condicions inicials:

T_{1} = 1

Es resol la següent homogénea:

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

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

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

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

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

Recurrencias No llineals

Per a resoldre recurrencias no llineals tenim moltes opcions de les quals:

Buscar transformacions o canvis de variables que facen la recurrencia llineal.
Per al cas $t (n) = a \cdot t (\frac{n}{b}) + f (n)$ , hi ha una teorema molt útil que és el Teorema Mestra.

Vore també

Referències

↑ Lehman, Leighton i Meyer (2010). Mathematics for Computer Science, p. 283.
↑ Johnsonbaugh, Richard (2005). Matemàtiques Discretes, Pearson Education, pp. 280. ISBN 970-26-0637-3.
↑ Lehman, Leighton i Meyer (2010). Mathematics for Computer Science, p. 287.

Referències

Este artícul conté una traducció derivada de «Relación de recurrencia» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[mit283-1] Lehman, Leighton i Meyer (2010). Mathematics for Computer Science, p. 283.

[2] Johnsonbaugh, Richard (2005). Matemàtiques Discretes, Pearson Education, pp. 280. ISBN 970-26-0637-3.

[mit287-3] Lehman, Leighton i Meyer (2010). Mathematics for Computer Science, p. 287.

[1]

[2]

[3]