Relazione di ricorrenza

Da Wikipedia, l'enciclopedia libera.

In matematica, una relazione di ricorrenza, chiamata anche equazione di ricorrenza , è un'equazione che, nei casi più semplici, riguarda i componenti di una successione la quale stabilisce un legame tra alcuni componenti che occupano posizioni generiche ma successive, cioè presenta una forma del tipo

$f(x_n,x_{n+1},...,x_{n+k})\,=\,0$ .

$\,k\,$ k viene detto ordine della relazione.

Vi sono anche relazioni di ricorrenza interessanti e utili che riguardano più successioni, matrici infinite e successioni con tre o più indici; in questo articolo però non le trattiamo.

In genere le relazioni di ricorrenza sono accompagnate da condizioni iniziali tali da rendere possibile, almeno in linea di principio, la valutazione dei componenti della successione.

Indice

1 Primi esempi
2 Espressioni alternative alle relazioni di ricorrenza
3 Soluzione delle relazioni di ricorrenza lineari
- 3.1 Esempio della successione di Fibonacci
4 Analisi di procedure ricorsive
5 Voci correlate

[modifica] Primi esempi

Il fattoriale del numero naturale n, n!, viene definito da

$0! := 1 ~; \quad n! := n\cdot(n-1)! ~~~\mathrm{per}~~ n=1, 2, 3, ...$

e per i primi fattoriali si trovano i valori

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ...

La successione di Fibonacci viene definita mediante due condizioni iniziali e una relazione di ricorrenza lineare:

$F_{0} = 0 \,$

$F_{1} = 1 \,$

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

quindi per i suoi primi componenti si trova

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

La mappa logistica corrisponde alla relazione:

$x_{n+1} \,=\, r x_n (1 - x_n)$ .

Questa è una delle relazioni di ricorrenza fornite da espressioni semplici, ma che con certe condizioni iniziali possono portare a processi evolutivi molto complessi, tanto da essere chiamati caotici. Essi vengono studiati piuttosto sistematicamente da fisici e matematici nell'ambito del settore della matematica chiamato analisi non lineare.

[modifica] Espressioni alternative alle relazioni di ricorrenza

Le relazioni di ricorrenza munite di opportune condizioni iniziali danno un controllo computazionale sulla successione che spesso risulta praticamente poco agevole. Può essere molto utile ricavare da una relazione di ricorrenza una espressione esplicita (o più espressioni) per ciascun componente $\,x_n\,$ della successione. Per questi problemi si parla di soluzione della relazione di ricorrenza ovvero di soluzione di equazione alle differenze. Naturalmente sono utili espressioni che consentono valutazioni efficienti e che permettano di ricavare proprietà e collegamenti (e quindi interpretazioni) per la successione.

[modifica] Soluzione delle relazioni di ricorrenza lineari

Si parla di relazione di ricorrenza lineare quando esprime l'annullamento di un polinomio di primo grado nei termini $\,x_m\,$ , cioè quando assume la forma

$c_nx_n + c_{n+1}x_{n+1}+ ... c_{n+k}x_{n+k} + c_0 \,=\, 0$ ,

con i coefficienti $\,c_m\,$ costanti, non dipendenti dagli $\,x_n\,$ . Si parla di relazione di ricorrenza lineare omogenea nel caso sia $c_0 \,=\,0$ . Le relazioni di ricorrenza lineari come le precedenti devono essere accompagnate da k condizioni iniziali; infatti, se si assegnano i primi k termini, seguendo qualsivoglia criterio, la stessa ricorrenza riscritta come assegnazione di un valore a $\,x_{n+k}\,$ implica la determinazione univoca dei successivi termini della successione.

Le relazioni di ricorrenza lineari possono essere risolte con procedimenti sistematici, spesso utilizzando le funzioni generatrici (ovvero le serie formali di potenze), oppure osservando che $\,r^n\,$ è una soluzione per particolari valori di r.

Per relazioni di ricorrenza della forma:

$x_n \,=\, A x_{n-1} + B x_{n-2}$

si ha la soluzione $\,r^n\,$ per la quale:

$r^{n}=Ar^{n-1}+Br^{n-2} \,$ .

Dividendo tutti i termini per $\,r^{n-2}\,$ si ottiene:

$r^2\,=\,Ar+B \quad\mathrm{ovvero}\quad r^2-Ar-B\,=\,0$ .

Questa viene chiamata equazione caratteristica della relazione di ricorrenza. Essa fornisce per r due radici $\, \lambda_1, \lambda_2 \,$ . Se tali radici sono distinte abbiamo la soluzione

$x_n = C\lambda_1^n+D\lambda_2^n \,$ ;

Se invece coincidono, cioè se $\,A^2+4B=0\,$ , abbiamo

$x_n = C\lambda^n+Dn\lambda^n \,$

dove C e D sono costanti arbitrarie.

Per una equazione della forma $\,x_n = Ax_{n-1}+B\,$ nel caso particolare relativo a $\,n=2\,$ si ottiene $\,r^2=Ar+B\,$ come sopra. Le costanti C e D possono essere ricavate da "condizioni al contorno" che tipicamente sono date nella forma : $x_0\,=\,a ~,~~ x_1\,=\,b$ .

Si ottengono differenti soluzioni in dipendenza dalla natura delle radici dell'equazione caratteristica.

Se la relazione di ricorrenza non è omogenea, si può trovare una soluzione particolare con il metodo dei coefficienti indeterminati e la soluzione è la somma della soluzione della equazione di ricorrenza omogenea e della soluzione particolare.

È interessante notare che il metodo per risolvere le equazioni differenziali lineari è simile a quello ora illustrato (il "tentativo intelligente" per le equazioni differenziali lineari è $\,e^x\,$ ). Naturalmente questa non è una mera coincidenza. Se si considera la serie di Taylor della soluzione di una equazione differenziale lineare

$\sum_{n=0}^{\infin} \frac{f^{(n)}(a)}{n!} (x-a)^{n}$ ,

si osserva che i coefficienti della serie sono dati dalla n-esima derivata della $\,f(x)\,$ valutata al punto a. Dalla equazione differenziale si ricava una equazione alle differenze lineare che collega questi coefficienti.

Questa equivalenza può essere utilizzata per risolvere rapidamente la relazione di ricorrenza per i coefficienti nella soluzione mediante serie di potenze di una equazione differenziale lineare.

[modifica] Esempio della successione di Fibonacci

Dalla definizione, posto $\Phi := {1+\sqrt{5} \over 2}$ per la sezione aurea, si deduce l'espressione:

$F_n = {\Phi^n \over \sqrt{5}} - {(1-\Phi)^n \over \sqrt{5}}$

[modifica] Analisi di procedure ricorsive

Molti classici algoritmi possono essere descritti tramite procedure ricorsive. Di conseguenza l'analisi dei relativi tempi di calcolo è ridotta alla soluzione di una o più equazioni di ricorrenza nelle quali si esprime il termine n-esimo di una sequenza in funzione dei precedenti.

Se si vuole analizzare la complessità di un algoritmo mediante un insieme di procedure P1,P2,P3,...Pm che si richiamano tra di loro si sfrutta la funzione T_i(n) che rappresenta il tempo di calcolo impiegato dall'i-ma procedura su dati di dimensione n. Se la procedura richiama sé stessa diminuendo l'ordine dei dati la si può descrivere come T_i(k) dove k è un valore minore di n.

Analizzando una sola procedura che richiama sé stessa si può impostare la seguente relazione di ricorrenza:

$T(n)\leq f_n(T(n-1)),...T(2),T(1),T(0)$ .

In questo modo si fissa che con numero 0 di input si ha una sola funzione T(n) che la soddisfa.

L'analisi di un algoritmo ricorsivo prevede quindi due fasi:

Deduzione di relazioni di ricorrenza contenenti come incognita la funzione T(n) da stimare
Soluzione delle relazioni di ricorsività stesse.

Prendiamo come esempio il semplice codice scritto in linguaggio C per semplicità

 int B(int m) {
     int s,i;
     s = 0;
     for (i=0; i<=n; i++)
         s = s + A(i);
     return s;
 }

 int A(int n) {
     if (n==0)
         return 0;
     else
         return n+A(n-1);
 }

Questo codice prende un numero m ed effettua un ciclo da 0 a n incrementando il valore di s a A(i), dove A(i) ritorna 0 nel caso in cui è 0, oppure torna il valore di i + A(i-1) (essenzialmente effettua una ricorrenza su i).

Indicando con $T B (n)$ , $T A (n)$ , il tempo di calcolo di B, A vale:

$T_B(n) = c_1 + \sum_{i=0}^n (c_2 + T_A(i))$