Un’altra famiglia di equazioni di ricorrenza che compaiono sovente nell’analisi degli algoritmi `e quella delle equazioni lineari a coefficienti costanti. Queste sono definite da uguaglianze della forma
a0tn+ a1tn−1+ · · · + aktn−k = gn (6.1) dove {tn} `e la sequenza incognita (che per semplicit`a sostituiamo alla funzione T (n)), k, a0, a1, . . . , ak sono costanti e {gn} `e una qualunque sequenza di numeri. Una sequenza di numeri {tn} si dice soluzione dell’equazione se la (6.1) `e soddisfatta per ogni n ≥ k. Chiaramente le varie soluzioni si differenziano per il valore dei primi k termini.
Un’equazione di questo tipo si dice omogenea se gn= 0 per ogni n ∈ IN. In questo caso esiste una nota regola generale che permette di ottenere esplicitamente tutte le soluzione dell’equazione. Inoltre, anche nel caso non omogeneo, per le sequenze {gn} pi`u comuni, `e possibile definire un metodo per calcolare la famiglia delle soluzioni.
6.5.1 Equazioni omogenee
Per illustrare la regola di soluzione nel caso omogeneo consideriamo un esempio specifico dato dalla seguente equazione:
tn− 7tn−1+ 10tn−2= 0 (6.2) Cerchiamo innanzitutto soluzioni della forma tn = rn per qualche costante r. Sostituendo tali valori l’equazione diventa
rn−2(r2− 7r + 10) = 0
che risulta verificata per le radici del polinomio r2− 7r + 10, ovvero per r = 5 e r = 2. L’equazione r2−7r+10 = 0 `e chiamata equazione caratteristica della ricorrenza 6.2. Ne segue allora che le sequenze {5n} e {2n} sono soluzioni di (6.2) e quindi, come `e facile verificare, lo `e anche la combinazione lineare {λ5n+ µ2n} per ogni coppia di costanti λ e µ.
Mostriamo ora che ogni soluzione non nulla {cn} della (6.2) `e combinazione lineare di {5n} e {2n}. Infatti, per ogni n ≥ 2, possiamo considerare il sistema di equazioni lineari
5n−1x + 2n−1y = cn−1
5n−2x + 2n−2y = cn−2
nelle incognite x, y. Questo ammette un’unica soluzione x = λ, y = µ poich´e il determinante dei coefficienti `e diverso da 0. Otteniamo cos`ı espressioni di cn−1 e cn−2 in funzione di 5n e 2n. Di conseguenza, sostituendo queste ultime in cn− 7cn−1+ 10cn−2 = 0 e ricordando che anche {5n} e {2n} sono soluzioni di (6.2), si ottiene
cn= λ5n+ µ2n. `
E facile verificare che i valori di λ e µ ottenuti non dipendono da n e possono essere ricavati considerando il sistema per n = 2. Cos`ı la relazione precedente `e valida per tutti gli n ∈ IN.
Come abbiamo visto, le soluzioni dell’equazione di ricorrenza considerata sono ottenute mediante le radici dell’equazione caratteristica associata. Se le radici sono tutte distinte questa propriet`a `e del tutto
generale e pu`o essere estesa a ogni equazione di ricorrenza lineare omogenea a coefficienti costanti, cio`e ad ogni equazione della forma
a0tn+ a1tn−1+ · · · + aktn−k = 0, (6.3) dove k, a0, a1, . . . , aksono costanti. Chiaramente, l’equazione caratteristica della relazione (6.3) `e
a0xn+ a1xn−1+ · · · + ak= 0.
Teorema 6.5 Sia
a0tn+ a1tn−1+ · · · + aktn−k = 0
un’equazione di ricorrenza lineare omogenea a coefficienti costanti e supponiamo che la sua equazione caratteristica abbia k radici distinte r1, r2, . . . , rk. Allora le soluzioni dell’equazione data sono tutte e sole le sequenze {tn} tali che, per ogni n ∈ IN,
tn= λ1rn1 + λ2rn2 + · · · + λkrnk
dove λ1, λ2, . . . , λksono costanti arbitrarie.
Dimostrazione. Il teorema pu`o essere dimostrato applicando lo stesso ragionamento presentato nel-l’esempio precedente. Si mostra innanzitutto che l’insieme delle soluzioni dell’equazione forma uno spazio vettoriale di dimensione k e poi si prova che le k soluzioni {r1n}, {rn
2}, . . . , {rn
k} sono linearmente indipendenti e formano quindi una base dello spazio stesso.
Esempio 6.3 Numeri di Fibonacci
Considera la sequenza {fn} dei numeri di Fibonacci, definita dall’equazione
fn=
( 0 se n = 0
1 se n = 1
fn−1+ fn−2 se n ≥ 2 La corrispondente equazione caratteristica `e x2− x − 1 = 0 che ha per radici i valori
φ =1 + √ 5 2 , φ = 1 −√ 5 2
Allora ogni soluzione {cn} dell’equazione considerata `e della forma cn = λφn+ µφn, con λ e µ costanti. Imponendo le condizioni iniziali c0= 0, c1= 1, otteniamo il sistema
λ + µ = 0
1+√5
2 λ +1−√5
2 µ = 1
che fornisce le soluzioni λ = √1
5, µ = −√1 5. Quindi, per ogni n ∈ IN, otteniamo
fn=√1 5 1 +√ 5 2 n −√1 5 1 −√ 5 2 n . Esempio 6.4
Vogliamo calcolare ora la sequenza {gn} definita dalla seguente equazione: gn=
n se 0 ≤ n ≤ 2
L’equazione caratteristica della ricorrenza `e x3− 3x2− 4x + 12 = 0 che ammette come radici i valori 3, −2, 2.
Ne segue che gn`e della forma gn= λ3n+ µ(−2)n+ ν2n. Imponendo le condizioni iniziali otteniamo il sistema
λ + µ + ν = 0 3λ − 2µ + 2ν = 1 9λ + 4µ + 4ν = 2
che fornisce la soluzione λ = 25, µ = −203, ν = −14. Quindi la sequenza cercata `e data dai valori
gn= 2 53 n − 3 20(−2) n −1 42 n
Finora abbiamo considerato solo ricorrenze la cui equazione caratteristica ammette radici semplici. La situazione `e solo leggermente pi`u complicata quando compaiono radici multiple. Infatti sappiamo che l’insieme delle soluzioni dell’equazione (6.3) forma uno spazio vettoriale di dimensione k e quindi l’unico problema `e quello di determinare k soluzioni linearmente indipendenti. Il seguente teorema, di cui omettiamo la dimostrazione, presenta la soluzione generale.
Teorema 6.6 Data l’equazione di ricorrenza
a0tn+ a1tn−1+ · · · + aktn−k = 0,
supponiamo che la corrispondente equazione caratteristica abbia h(≤ k) radici distinte r1, r2, . . . , rhe che ciascuna riabbia molteplicit`a mi. Allora le soluzioni dell’equazione di ricorrenza data sono tutte e sole le combinazioni lineari delle sequenze
{njrni}
dove j ∈ {0, 1, . . . , mi− 1} e i ∈ {1, 2, . . . , h}.
Esempio 6.5
Vogliamo calcolare la sequenza {hn} definita da
hn=
( 0 se n = 0, 1
1 se n = 2
7hn−1− 15hn−2+ 9hn−3 se n ≥ 3 In questo caso, l’equazione caratteristica `e x3− 7x2
+ 15x − 9 = 0; essa ammette la radice semplice x = 1 e la radice x = 3
di molteplicit`a 2.
Allora hn`e della forma hn= λn3n+ µ3n+ ν. Imponendo le condizioni iniziali otteniamo il sistema
µ + ν = 0
3λ + 3µ + ν = 0 18λ + 9µ + ν = 1
che fornisce la soluzione λ = 1
6, µ = −1 4, ν =1
4. Quindi la sequenza cercata `e data dai valori
hn= n3 n 6 −3 n 4 + 1 4
6.5.2 Equazioni non omogenee
Consideriamo ora un’equazione di ricorrenza lineare non omogenea a coefficienti costanti, cio`e una relazione della forma
a0tn+ a1tn−1+ · · · + aktn−k = gn (6.4) dove {tn} `e la sequenza incognita, k, a0, a1, . . . , ak sono costanti e {gn} `e una qualunque sequenza diversa da quella identicamente nulla. Siano {un} e {vn} due soluzioni della (6.4). Questo significa che, per ogni n ≥ k,
a0un+ a1un−1+ · · · + akun−k = gn a0vn+ a1vn−1+ · · · + akvn−k = gn Allora, sottraendo i termini delle due uguaglianze otteniamo
a0(un− vn) + a1(un−1− vn−1) + · · · + ak(un−k− vn−k) = 0 e quindi la sequenza {un− vn} `e soluzione dell’equazione omogenea associata alla (6.4).
Viceversa, se {un} `e soluzione di (6.4) e {wn} `e soluzione dell’equazione omogenea a0tn+ a1tn−1+ · · · + aktn−k = 0
allora anche la loro somma {un+ wn} `e soluzione della (6.4).
Abbiamo cos`ı dimostrato che tutte le soluzioni di (6.4) si ottengono sommando una soluzione parti-colare a tutte le soluzioni dell’equazione omogenea associata. Questo significa che per risolvere la (6.4) possiamo eseguire i seguenti passi:
1. trovare tutte le soluzioni dell’equazione omogenea associata applicando il metodo dell’equazione caratteristica descritto nella sezione precedente;
2. determinare una soluzione particolare dell’equazione data e sommarla alle precedenti.
Il problema `e che non esiste un metodo generale per determinare una soluzione particolare di un’e-quazione non omogenea. Esistono solo tecniche specifiche che dipendono dal valore del termine noto gn. In alcuni casi tuttavia la determinazione della soluzione particolare `e del tutto semplice.
Esempio 6.6
Vogliamo determinare le soluzioni dell’equazione
tn− 2tn−1+ 3 = 0
L’equazione caratteristica dell’omogenea associata `e x − 2 = 0 e quindi la sua soluzione generale `e {λ2n}, con λ costante
arbitraria. Inoltre `e facile verificare che la sequenza {un}, dove un = 3 per ogni n ∈ IN, `e una soluzione dell’equazione
iniziale. Quindi le soluzioni sono tutte e sole le sequenze della forma {3 + λ2n} con λ costante.
Metodo delle costanti indeterminate
Una delle tecniche pi`u comuni per determinare una soluzione particolare di una equazione non omoge-nea `e chiamata metodo delle costanti indeterminate. Questo consiste nel sostituire i termini tn dell’e-quazione (6.4) con quelli di una sequenza particolare nella quale alcune costanti sono incognite e quindi determinare il valore di queste ultime mediante identificazione. Si pu`o dimostrare che se il termine noto gndella (6.4) ha la forma gn= h X i=1 biPi(n)
dove, per ogni i = 1, 2, . . . , h, bi `e una costante e Piun polinomio in n, allora una soluzione particolare deve essere del tipo
un=
h
X
i=1
biQi(n) dove i Qi(n) sono polinomi che soddisfano le seguenti propriet`a :
1. se bi non `e radice dell’equazione caratteristica dell’omogenea associata a (6.4), allora il grado di Qi(n) `e uguale a quello di di Pi(n);
2. se bi `e radice di molteplicit`a mi dell’equazione caratteristica dell’omogenea associata a (6.4), allora il grado di Qi(n) `e la somma di mie del grado di Pi(n).
Esempio 6.7
Determiniamo tutte le soluzioni dell’equazione
tn− 3tn−1+ tn−2= n + 3n.
L’equazione caratteristica dell’omogenea associata `e x2− 3x + 2 = 0 che ammette le radici3+√5 2 e3−
√ 5
2 . Quindi la soluzione generale dell’equazione omogenea associata `e
λ 3 +√ 5 2 n + µ 3 −√ 5 2 n
dove λ e µ sono costanti. Cerchiamo ora una soluzione particolare applicando il metodo delle costanti indeterminate. Nel nostro caso b1= 1, b2= 3, Q1= n, Q2= 1; di conseguenza una soluzione candidata `e un= (an + b) + c3n, per opportune costanti a, b, c. Per determinare il loro valore sostituiamo unnell’equazione e otteniamo
un− 3un−1+ un−2= n + 3n
ovvero, svolgendo semplici calcoli,
(−a − 1)n + a − b + c
9− 13n= 0
che risulta soddisfatta per ogni n ∈ IN se e solo se
a = −1, b = −1, c = 9.
Quindi una soluzione particolare `e un= 3n+2− n − 1 e di conseguenza le soluzioni dell’equazione iniziale sono λ 3 +√ 5 2 n + µ 3 −√ 5 2 n + 3n+2− n − 1
al variare delle costanti λ e µ.
Esercizi
1) Descrivere un metodo per calcolare una soluzione particolare di un’equazione della forma (6.4) nella quale il termine noto gnsia costante.
2) Considera la seguente procedura:
ProcedureFun(n) ifn ≤ 1then returnn else begin x = Fun(n − 1) y = Fun(n − 2) return3x − y end
Sia D(n) il risultato del calcolo eseguito dalla procedura su input n. a) Calcolare il valore esatto di D(n) per ogni n ∈ IN.
b) Determinare il numero di operazioni aritmetiche eseguite dalla procedura su input n ∈ IN. c) Determinare l’ordine di grandezza del tempo di calcolo richiesto dalla procedura su input n ∈ IN assumendo il criterio di costo logaritmico.
3) Considera la seguente procedura che calcola il valore B(n) ∈ IN su input n ∈ IN, n > 0.
begin readn a = 2 fork = 1, . . . , ndo a = 2 + k · a outputa end
a) Esprimere il valore di B(n) in forma chiusa (mediante una sommatoria).
b) Determinare l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti dalla procedura assumendo il criterio di costo logaritmico.