Relazione di ricorrenza: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
+fonti da en |
mNessun oggetto della modifica |
||
Riga 1:
In [[matematica]], una '''relazione di ricorrenza''', chiamata anche '''equazione di ricorrenza''', è un'equazione che, nei casi più semplici, riguarda i componenti di una [[successione (matematica)|successione]] la quale stabilisce un legame tra alcuni componenti che occupano posizioni generiche ma successive, cioè presenta una forma del tipo:
:<math>f(x_n,x_{n+1},\dots,x_{n+k})
Il numero <math>
Vi sono anche relazioni di ricorrenza
== Primi esempi ==
Line 39 ⟶ 37:
:<math>c_nx_n + c_{n+1}x_{n+1}+ ... c_{n+k}x_{n+k} + c_0 \,=\, 0</math>
con i coefficienti <math>\,c_m</math> costanti, non dipendenti dagli <math>\,x_n</math>. Si parla di
Le relazioni di ricorrenza lineari possono essere risolte con procedimenti sistematici, spesso utilizzando le [[funzione generatrice|funzioni generatrici]] (ovvero le [[serie formale di potenze|serie formali di potenze]]), oppure osservando che <math>\,r^n</math> è una soluzione per particolari valori di
Per relazioni di ricorrenza della forma:
Line 55 ⟶ 53:
:<math> r^2\,=\,Ar+B \quad\mathrm{ovvero}\quad r^2-Ar-B\,=\,0</math>
:<math>x_n = C\lambda_1^n+D\lambda_2^n </math>
Se invece coincidono, cioè se <math>\,A^2+4B=0</math>,
:<math>x_n = C\lambda^n+Dn\lambda^n </math>
dove
Per un'equazione della forma <math>\,x_n = Ax_{n-1}+B</math> nel caso particolare relativo a <math>\,n=2</math> si ottiene <math>\,r^2=Ar+B</math> come sopra. Le costanti <math>C</math> e <math>D</math> possono essere ricavate da "condizioni al contorno" che tipicamente sono date nella forma:
:<math>x_0\,=\,a ~,~~ x_1\,=\,b</math>
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 è <math>\,e^x</math>). Naturalmente questa non è una mera coincidenza. Se si considera la [[serie di Taylor]] della soluzione di un'equazione differenziale lineare:
Line 71 ⟶ 73:
:<math>\sum_{n=0}^{\infin} \frac{f^{(n)}(a)}{n!} (x-a)^{n}</math>
si osserva che i coefficienti della serie sono dati dalla ''n''-esima derivata della <math>\,f(x)</math> valutata al punto
===
Dalla definizione, posto <math>\Phi := {1+\sqrt{5} \over 2}</math> per la [[sezione aurea]], si deduce l'espressione:
Line 82 ⟶ 84:
Molti classici [[algoritmo|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
Analizzando una sola procedura che richiama sé stessa si può impostare la seguente relazione di ricorrenza:
Line 88 ⟶ 90:
:<math>T(n)\leq f_n(T(n-1),\dotsT(2),T(1),T(0))</math>
In questo modo si fissa che con numero 0 di input si ha una sola funzione <math>T(n)</math> che la soddisfa. L'analisi di un algoritmo ricorsivo prevede quindi due fasi:
* Deduzione di relazioni di ricorrenza contenenti come incognita la funzione <math>T(n)</math> da stimare
* Soluzione delle relazioni di ricorsività stesse.
int B(int m) {
Line 112 ⟶ 114:
Questo codice prende un numero m ed effettua un ciclo da 0 a m 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).
:<math> T_B(n) = c_1 + \sum_{i=0}^n (c_2 + T_A(i)) </math>
Line 118 ⟶ 120:
:<math> T_A(n) = d_2 T_A(n-1) \, n \,>\, 0 \, T_A(0) =d_1 </math>
A queste successioni
:<math>S = {a_n} = a_0,a_1,a_2, \dots a_n </math>
| |||