Dubbio su un'equazione di ricorrenza

[Richard_Dedekind]

Salve a tutti. Ho trovato questa equazione di ricorrenza lineare ma inspiegabilmente qualcosa non mi quadra nella sua risoluzione. Si trata di:
[tex]\begin{cases}
t_0=2 \\
t_1=3 \\
t_2=10 \\
t_3=11 \\
t_n=2t_{n-2}-t_{n-4} + 8 \end{cases}[/tex]

Io ho tentato di risolverla con il comune metodo per le equazioni lineari a coefficienti costanti. Ho considerato l'equazione omogenea associata e la sua equazione caratteristica [tex]r^4-2r^2+1=0[/tex] che ha come uniche soluzioni [tex]r=\pm 1[/tex]. Necessariamente le soluzioni dell'equazione di ricorrenza associata sono date dalle combinazioni lineari del tipo [tex]t_n=\lambda +\mu(-1)^n[/tex]. A questo punto dovrei trovare una soluzione particolare dell'equazione non omogenea. Ma qui, non so perché, tutto smette di funzionare. Cercando soluzioni costanti o lineari non trovo niente di conclusivo.
Sapete aiutarmi?

[hamming_burst]

Ciao,
queste non sono "equazioni di ricorrenza" proprie di Informatica ed algoritmica.
Ma se proprio penso siano di algebra, o almeno io le ho viste chiamate "successioni". Ti consiglio di postare in "Algebra", almeno avrai una risposta ed uno svolgimento matematico, e non informatico

[hamming_burst]

Scusa, ma ho riletto la tua domanda.
Questa terminologia "equazioni lineari a coefficienti costanti" mi ha ricordato una tipologia di equazioni di ricorrenza che hanno un modo particolare per essere risolte, tipo il Master Theorem. Ho cercato su un libro, perchè devo dire che non me le ricordavo

Se la riscrivo in questo modo:

$T(n) = 2T(n-2) - T(n-4) + 8$

mi è più familiare, ma se parli di "equzioni omogenee" si sfora in campi differenti. Con la tipologia di risoluzione delle "Ricorrenze lineari di ordine costante" si trovano limitazioni superiori, non soluzioni di un'equazione, che penso tu voglia trovare.
se invece cerchi stime asintotiche (limitazioni superiori - $O()$) allora ti posso dare una mano, se no parliamo due linguaggi differenti

[Richard_Dedekind]

Ti riporto la definizione che conosco io.
Chiamiamo equazione di ricorrenza lineare a coefficienti costanti le uguaglianze del tipo

[tex]a_0t_n+a_1t_{n-1}+\ldots+a_kt_{n-k}=g_n[/tex]

dove per semplicità [tex]t_n=T(n)[/tex] e dove [tex]a_0,\ldots,a_k[/tex] sono costanti e [tex]g_n[/tex] è una successione.
Si dice che l'equazione è omogenea se [tex]g_n\equiv 0[/tex].

Il metodo di risoluzione proposto è il seguente:
1) si considera l'equazione omogenea associata [tex]a_0t_n+\ldots+a_kt_{n-k}=0\quad(1)[/tex];
2) si trovano le soluzioni [tex]\lambda_1,\ldots,\lambda_k[/tex] dell'equazione polinomiale caratteristica [tex]a_0r^k+a_1r^{k-1}+\ldots+a_{k-1}r+a_k=0[/tex];
3) le sequenze soluzioni dell'equazione [tex](1)[/tex] sono le combinazioni lineari del tipo [tex]t_n=c_1\lambda_1^n+\ldots+c_k\lambda_k^n\quad(2)[/tex] (supponendo che ogni [tex]\lambda_i[/tex] abbia molteplicità 1);
4) si trova una soluzione particolare dell'equazione completa;
5) la sequenza soluzione generale è data dalla somma delle sequenze [tex](2)[/tex] con la soluzione particolare. Le costanti si determinano dalle condizioni iniziali.

Il teorema Master mi risulta essere un espediente per calcolare l'ordine di grandezza di equazioni del tipo divide et impera.

[hamming_burst]

molto interessante.
Secondo me il tipo di stima asintotica di queste equazioni, è preso dalla tua risoluzione di algebra lineare (?).
Sì, come supponevo non posso aiutarti in questa metodologia, sorry. Ma l'elencazione è parecchio simile al:

Teorema delle Ricorrenze Lineari di ordine costante

Siano $a_1,a_2,...,a_h$ costanti intere non negative, con $h$ costante positiva, $c$ e $beta$ costanti reali tali che $c>0$ e $beta>=0$, e sia $T(n)$ definita dalla relazione di ricorrenza:


$T(n) = {(\text{costante} if n<=m<=h),( \sum_(1<=i<=h) a_iT(n-i) + cn^\beta if n>m):}$

Posto $a = \sum_(1<=i<=h) a_i$, allora

(1) $T(n)$ è $O(n^(beta+1)) if a=1$
(2) $T(n)$ è $O(a^n n^beta) if a>=2$

Come molti concetti matematici, sono scritti in maniera differente e sono utilizzati in campi differenti. Per curiosità che materia stai studiando?

comunque interessante

Per il Master Theorem: sì la tecnica devide et impera produce algoritmi che hanno equazioni di ricorrenza, risolvibili con questo teorema (anche se produce stime non sempre "ottime), ma non è una implicazione.

EDIT:
sistemato formule.

[Richard_Dedekind]

La forma dell'equazione è proprio la stessa, direi. Anzi, la tua è un caso particolare ([tex]g_n=cn^\beta[/tex])!
Il metodo che ti ho riportato è molto simile a quello che si usa per risolvere equazioni differenziali di ordine superiore a coefficienti costanti. Lo abbiamo fatto nel corso di Informatica per matematici, una sorta di Algoritmi e strutture dati. Le dispense che utilizziamo (solo per alcune parti) sono le seguenti http://homes.dsi.unimi.it/~goldwurm/Appunti/appu08.pdf, scritte dai proff. Bertoni e Goldwurm.

[hamming_burst]

aah guarda un po'. Adesso che me lo fai notare è una tipologia di un'equazione differenziali, il nome era fuorviante.
non sapevo che quel teorema nasceva da qui. Penso che Algoritmi studiati in questo modo sia molto bello, come lo ho affrontato io è diverso, più informatico che matematico formale.

Scusa un po' l'OT, ma mi incuriosiva la cosa

Molto interessanti anche le dispense, adesso mi spiego il perchè di alcuni teoremi di Analisi degli Algoritmi (anche se quelle dispense da nomi alle equazioni per "classe di algoritmi" o tecnica utilizzata).
Il teorema che ti ho scritto penso nasca da questa affermazione delle dispense:

Il problema e che non esiste un metodo generale per determinare una soluzione particolare di un’equazione non omogenea.
Esistono solo tecniche specifiche che dipendono dal valore del termine noto $g_n$. In alcuni casi tuttavia la determinazione della soluzione particolare e del tutto semplice.

[Richard_Dedekind]

Sì, hai ragione. Si tratta di un metodo piuttosto formale e con una teoria dietro di per sé abbastanza carina per un matematico. Ripeto che la somiglianza con le equazioni differenziali mi ha spiazzato: è proprio eclatante. La difficoltà è trovare quella soluzione particolare, che a mio avviso nell'equazione da me riportata dovrebbe essere una costante o al più un polinomio. Ma non riesco a trovare nulla!

Per il resto, noi abbiamo fatto Algoritmi sostanzialmente studiando il costo computazionale e le varie relazioni di ricorrenza; per un corso di matematica, d'altra parte, è forse più interessante, mentre per un informatico può apparire abbastanza fine a sé stesso.

[yoshiharu]

"Richard_Dedekind":Salve a tutti. Ho trovato questa equazione di ricorrenza lineare ma inspiegabilmente qualcosa non mi quadra nella sua risoluzione. Si trata di:
[tex]\begin{cases}
t_0=2 \\
t_1=3 \\
t_2=10 \\
t_3=11 \\
t_n=2t_{n-2}-t_{n-4} + 8 \end{cases}[/tex]

Ciao,
il metodo non lo conoscevo (anzi: grazie per averlo postato!), ma mi sembra che ci possa essere un intoppo importante.
La successione si separa in 2 sottosuccessioni (indice pari e indice dispari).
Per ognuna il polinomio associato all' equazione omogenea (associata) dovrebbe essere $x^2-2 x +1$, che ha una radice degenere.
Normalmente nelle ODE questo da' un piccolo intoppo, probabilmente lo da' anche con questo metodo (che ammetto devo ancora studiarmelo ).

Just my 2 pence

[Richard_Dedekind]

In realtà che [tex]x=1[/tex] sia una radice di molteplicità 2 non è problematico. Il metodo fornisce soluzione anche in questo caso. Se il polinomio caratteristico ha una radice [tex]\lambda[/tex] di molteplicità [tex]m>1[/tex] allora la successione di soluzioni dell'omogenea associata è data da
[tex]c_1\lambda^n+c_2n\lambda^n+c_3n^2\lambda^n+\ldots+c_{m-1}n^{m-1}\lambda^n[/tex]
Chiaramente se ci sono più radici con molteplicità diverse si tratta semplicemente di usare i due metodi contemporaneamente e sommare i risultati. Per i dettagli puoi vedere quelle dispense (c'è anche la dimostrazione).

Tuttavia anche a me questo caso è sembrato un po' particolare. Anche perché in altre ricorrenze, come ad esempio [tex]t_n=2t_{n-1}-3[/tex] non ci sono problemi.

[apatriarca]

Ciao, metodo interessante. Ho provato ad usare il metodo suggerito per trovare la soluzione e, in effetti, non sono riuscito a trovare costanti per cui valga l'equazione. Credo ti convenga chiedere al tuo professore.

EDIT: Forse riesci ad ottenere qualcosa spezzando la successione nelle due sottosuccessioni. Ho fatto qualche calcolo e sembra promettente.

[Deckard1]

Hai provato con le funzioni generatrici? Ne ho ricavato una formula chiusa, ma è molto, molto brutta e non so come semplificarla. Ci sono una serie di "trucchi" per manipolare le f.g. con cui si dovrebbe cavar fuori qualcosa, ma purtroppo sono molto arrugginito e quindi in parte non ricordo, in parte non ho mai avuto il tempo di studiare.

[OT] Per ricollegarmi al discorso di ham_burst, eq. di questo tipo non si vedono mai nel valutare la complessità di un algoritmo, tuttavia sono piuttosto comuni in combinatoria.
Comunque anch'io ho studiato su quelle dispense.[/OT]

[Richard_Dedekind]

Bah, alla fine una soluzione particolare era data dalla sequenza [tex]t_n=n^2[/tex]. Il professore dice di provare con polinomi di grado due e vedere che termini si devono annullare. Insomma, non è così chiaro.
Piuttosto, la cosa buffa è che in effetti quelle non sono equazioni di ricorrenza. Diciamo che sono assimilabili ad esercizi sulla successione di Fibonacci e simili. Una equazione di ricorrenza tipica potrebbe essere questa:
[tex]T(n)=T(\lfloor\log_2 (2^n -1)\rfloor)+2^n[/tex]
di cui si può trovare solo una stima della complessità usando la disuguaglianza (credo?) [tex]\lfloor \log_2(2^n-1)\rfloor \geq n-1\,\,\forall n\geq 1[/tex], dalla quale
[tex]T(n)=T(\lfloor\log_2 (2^n -1)\rfloor)+2^n\geq T(n-1)+2^n[/tex]

[hamming_burst]

Ah ecco, mi puzzava un attimo che ci fosse $T() - T()$, anche se si è in stime asintotiche si può benissimo convertire in $+$

La seconda invece è risolvibile con le classiche tecniche, quello che fai te, con la disuguaglianza, è trovare una limitazione inferiore $Omega()$ (metodo della sostituzione o metodo per tentativi).

Già che avevo un po' di voglia, ho fatto alcuni conti, se ti servono

$2^n -> 2^log(2^n-1) = 2^n-1 -> 2^n-2 -> ..... -> 2^n-k$

$T(1)$ quando $k=2^n$

perciò:

$sum_{k=0}^{2^(n-1)} 2^n-k = sum_{i=1}^{2^n} i = (2^n*(2^n+1))/2 = 2^(2n)/2 + 2^n/2$

In conclusione: $T(n) = 2^(2n)/2 + 2^n/2 + O(1) in O(2^(2n))$

ha limitazione superiore esponenziale: $O(4^n)$

è anche facile da dimostrare che ha limitazione inferiore di $Omega(2^n)$ (induzione).

[OT]
PS: le note che hai linkato le metterò nella sezione dispense. Le trovo davvero molto complete.
[/OT]