Recurrències lineals i funcions generadores: polinomi característic i ressonància

Una recurrència defineix cada terme a partir dels anteriors. Apareixen a tot arreu: en l'anàlisi del cost d'un algorisme recursiu, en models de població discrets, en problemes de recompte on el cas $n$ es redueix als casos més petits. Resoldre-la vol dir trobar-ne una fórmula tancada, que et deixi calcular el terme mil sense passar pels nou-cents noranta-nou anteriors.

Si has fet EDO lineals d'ordre superior, tot el que ve ara et sonarà: l'estructura és exactament la mateixa, amb potències en comptes d'exponencials.

Primer ordre: iterar i sumar

Una recurrència d'ordre $r$ necessita normalment $r$ dades inicials. També cal dir a partir de quin índex és vàlida, cosa que s'oblida sovint i que canvia el resultat.

El cas bàsic és $a_n = \alpha\,a_{n-1} + \beta$. Iterant cap enrere s'hi veu l'estructura:

$$a_n = \alpha^{n}a_0 + \beta\sum_{j=0}^{n-1}\alpha^{j}.$$

Si $\alpha\neq 1$, la suma geomètrica val $\beta(\alpha^{n}-1)/(\alpha-1)$. Si $\alpha = 1$, la suma és simplement $n\beta$, i aquest cas no s'obté substituint a la fórmula anterior, que tindria denominador nul. Els casos excepcionals s'han de tractar a part, no maquillar.

Equació característica

Per a una recurrència lineal homogènia amb coeficients constants,

$$a_n = c_1 a_{n-1} + \cdots + c_r a_{n-r},$$

prova $a_n = \lambda^{n}$. Substituint i dividint per la potència més petita surt el polinomi característic

$$p(\lambda) = \lambda^{r} - c_1\lambda^{r-1} - \cdots - c_r.$$

Si les arrels són diferents i no nul·les, la solució general és una combinació lineal de les potències $\lambda_j^{n}$. Una arrel no nul·la de multiplicitat $m$ aporta $\lambda^{n}$, $n\lambda^{n}$, ..., $n^{m-1}\lambda^{n}$: apareixen factors polinòmics en $n$, exactament com apareixien factors $t^{k}$ a les equacions diferencials.

Les constants sempre es determinen al final amb les dades inicials, resolent un sistema lineal.

Terme forçat i ressonància

Amb una recurrència no homogènia, la solució general és una particular més la solució homogènia. Si el forçament té la forma $P(n)\alpha^{n}$ amb $P$ polinomi, es prova

$$n^{s}\,Q(n)\,\alpha^{n},$$

on $Q$ té el mateix grau que $P$ i $s$ és la multiplicitat d'$\alpha$ com a arrel característica (zero si no ho és). El factor $n^{s}$ és la correcció de ressonància, i és el mateix mecanisme que el factor $t^{m}$ de les equacions diferencials.

Un avís sobre les dades inicials: les constants no es determinen mirant la recurrència, sinó imposant els valors de partida. Dues successions amb la mateixa recurrència i dades inicials diferents són successions diferents, i la fórmula tancada ho ha de reflectir. Per això el darrer pas de tot exercici és sempre el mateix sistema lineal, i per això val la pena comprovar el resultat amb un terme que no hagis fet servir per determinar-les.

Un altre motiu per verificar sempre: les recurrències són molt sensibles a l'índex a partir del qual són vàlides. Si l'enunciat diu que la relació val a partir de $n = 2$ i tu l'apliques també a $n = 1$, estàs inventant una condició que no hi era, i la fórmula resultant no descriurà la successió que et demanaven. Escriu explícitament el rang de validesa al costat de la recurrència abans de començar a resoldre.

Funcions generadores

El mètode alternatiu, i el que funciona quan la recurrència no és de coeficients constants, consisteix a codificar tota la successió en una sèrie formal i manipular-la com una funció.

Per a Fibonacci, amb $F_0 = 0$, $F_1 = 1$ i la recurrència habitual, multiplica per $z^{n}$ i suma des de $n = 2$. El resultat és una equació algebraica per a la sèrie:

$$F(z) - z = zF(z) + z^{2}F(z), \qquad F(z) = \frac{z}{1 - z - z^{2}}.$$

Els termes inicials que s'han restat a l'esquerra són imprescindibles: si els omets, estàs resolent una successió diferent. Descomponent en fraccions simples i desenvolupant cada tros com una sèrie geomètrica s'obté la fórmula de Binet:

$$F_n = \frac{\varphi^{n} - \psi^{n}}{\sqrt{5}}, \qquad \varphi = \frac{1+\sqrt5}{2}, \quad \psi = \frac{1-\sqrt5}{2}.$$

Com que el segon terme té mòdul menor que $1$, tendeix a zero i $F_n$ creix essencialment com $\varphi^{n}/\sqrt5$. De fet, $F_n$ és l'enter més proper a aquesta quantitat, cosa que és una manera molt pràctica de calcular Fibonaccis grans.

Exercici resolt: recurrència de primer ordre amb terme constant

Resol $a_n = 3a_{n-1} + 4$ amb $a_0 = 1$.

Homogènia: l'arrel és $3$, o sigui $A\cdot 3^{n}$.

Particular: com que el forçament és constant i $1$ no és arrel característica, prova una constant $C$. Substituint: $C = 3C + 4$, d'on $C = -2$.

General i dades inicials: $a_n = A\cdot 3^{n} - 2$, i amb $a_0 = 1$ surt $A = 3$:

$$a_n = 3^{n+1} - 2.$$

Comprovació. $a_1$ hauria de ser $3\cdot 1 + 4 = 7$, i la fórmula dona $9 - 2 = 7$. Correcte.

Nota sobre el cas excepcional. Si el coeficient hagués estat $1$ en comptes de $3$, la constant hauria ressonat i l'assaig correcte seria $Cn$. La recurrència $a_n = a_{n-1}+4$ dona $a_n = a_0 + 4n$, com era d'esperar.

Exercici resolt: cost d'un algorisme recursiu

Un algorisme parteix el problema en dos de mida meitat i fa un treball lineal per combinar-los: $T(n) = 2T(n/2) + n$, amb $T(1) = 0$. Quin és el cost per a $n = 2^{k}$?

Divideix per $n = 2^{k}$ i posa $S(k) = T(2^{k})/2^{k}$:

$$S(k) = S(k-1) + 1,$$

perquè el terme $2T(n/2)$ dividit per $n$ dona $T(n/2)/(n/2)$, és a dir $S(k-1)$, i el terme $n$ dividit per $n$ dona $1$.

Amb $S(0) = 0$ surt $S(k) = k$, i desfent el canvi

$$T(2^{k}) = k\,2^{k}, \qquad \text{és a dir}\qquad T(n) = n\log_2 n.$$

Aquesta és exactament la recurrència de l'ordenació per fusió, i el resultat explica d'on ve el seu cost: hi ha $\log_2 n$ nivells de recursió i a cada nivell es fa un treball total lineal. Fixa't que el canvi de variable ha convertit una recurrència amb ressonància en la recurrència més senzilla que hi ha.