L'equazione caratteristica della relazione ricorsiva

L'equazione caratteristica permette di trovare la formula chiusa di una successione ricorsiva del tipo rn dove r è una costante.

Come calcolare l'equazione caratteristica

La relazione ricorsiva lineare di una successione {an} è una combinazione lineare del tipo $$ a_n = b_1 a_{n-1} + b_2 a_{n-2} + ... + b_k a_{n-k} + b $$

Dove n è un numero appartenente all'insieme dei numeri naturali, mentre b1...bk sono numeri scalari.

La relazione è detta relazione lineare di grado k.

Se b=0 la relazione è detta omogenea

$$ a_n = b_1 a_{n-1} + b_2 a_{n-2} + ... + b_k a_{n-k} $$

Se per ipotesi la soluzione ( formula chiusa ) della successione ricorsiva fosse del tipo rn con r costante potrei riscrivere la relazione lineare in questo modo

$$ r^n = b_1 r^{n-1} + b_2 r^{n-2} + ... + b_k r^{n-k} $$

Dividendo ambo i membri per rn-k.

$$ \frac{r^n}{r^{n-k}} = \frac{b_1 r^{n-1}}{r^{n-k}} + \frac{b_2 r^{n-2}}{r^{n-k}} + ... + \frac{b_k r^{n-k}}{r^{n-k}} $$

$$ r^n \cdot r^{-(n-k)} = b_1 r^{n-1} \cdot r^{-(n-k)} + b_2 r^{n-2} \cdot r^{-(n-k)} + ... + b_k $$

$$ r^{n-n+k} = b_1 r^{n-1-n+k} + b_2 r^{n-2-n+k} + ... + b_k $$

$$ r^k = b_1 r^{k-1} + b_2 r^{k-2} + ... + b_k $$

Portando tutti i membri a sinistra ottengo l'equazione caratteristica della relazione ricorsiva.

$$ r^k - b_1 r^{k-1} - b_2 r^{k-2} - ... - b_k = 0 $$

A questo punto verifico se esistono valori di r che soddisfano l'equazione omogenea.

Posso procedere soltanto se

  • Se esiste una soluzione (banale)
  • Se esistono più soluzioni r1,r2,r3 tutte distinte tra loro.

Queste soluzioni sono dette radici caratteristiche.

Se le condizioni precedenti sono soddisfatte posso scrivere la soluzione in questa forma

$$ \{ a_n \} = c_1 r_1^n+c_2 r_2^n + ... + c_k r_k^n $$

Dove i coefficienti c1,...,ck sono costanti.

A cosa serve?

Grazie a questo procedimento posso trovare una formula esplicita ( formula chiusa ) per rappresentare la successione, senza dover andare per tentativi.

Qualche esempio dovrebbe rendere più chiare le idee

Un esempio pratico

Devo trovare la formula chiusa di questa successione ricorsiva per n≥2.

$$ \{ a_n \} = 5 a_{n-1} + 6 a_{n-2} $$

I primi termini della successione sono

$$ a_0 = 1 \\ a_1 = 3 $$

E' una successione ricorsiva lineare del secondo ordine.

    Nota

  • è ricorsiva perché il termine ennesimo è in funzione dei termini precedenti
  • è lineare perché tutti i termini sono di grado 1°
  • è del secondo ordine perché i termini precedenti sono due (k=2)

Calcolo l'equazione caratteristica per verificare se esiste una soluzione del tipo rn.

$$ r^n = 5 r^{n-1} + 6 r^{n-2} + ... + b_k r^{n-k} $$

$$ \frac{r^n}{r^{n-k}} = \frac{5 r^{n-1}}{r^{n-k}} + \frac{6 r^{n-2}}{r^{n-k}} $$

$$ r^k = 5 r^{k-1} + 6 r^{k-2} $$

So già che k=2 e lo sostituisco

$$ r^2 = 5 r^{2-1} + 6 r^{2-2} $$

$$ r^2 = 5 r + 6 $$

Poi sposto tutti i membri a sinistra

Ho così trovato l'equazione caratteristica della successione ricorsiva.

$$ r^2 - 5 r - 6 = 0 $$

Calcolo le radici caratteristiche dell'equazione.

$$ r = \frac{-b ± \sqrt{b^2-4ac} }{2a} $$

$$ r = \frac{5 ± \sqrt{25+24} }{2} = \frac{5 ± 7 }{2} = \begin{cases} r=6 \\ \\ r=-1 \end{cases} $$

Entrambe le radici sono diverse tra loro. Quindi, posso procedere.

Nota. Se le radici fossero state uguali il procedimento sarebbe finito qui, senza alcuna soluzione.

Scrivo le radici appena trovate nella formula della soluzione

$$ \{ a_n \} = c_1 r_1^n+c_2 r_2^n + ... + c_k r_k^n $$

poiché k=2, r1=6 e r2=-1

$$ \{ a_n \} = c_1 6^n+c_2 (-1)^n $$

I coefficienti c1 e c2 li ottengo sostituendo an con i primi due termini della successione a0 e a1 che già conosco.

$$ \{ a_0 \} = c_1 6^0+c_2 (-1)^0 $$

$$ \{ a_1 \} = c_1 6^1+c_2 (-1)^1 $$

ossia

$$ \{ a_0 \} = c_1 +c_2 $$

$$ \{ a_1 \} = c_1 6-c_2 $$

Sostituisco i valori di a0=1 e a1=3

$$ 1 = c_1 +c_2 $$

$$ 3 = c_1 6-c_2 $$

Poi metto tutto sotto sistema e cerco i valori dei coefficienti c1 e c2.

$$ \begin{cases} 1 = c_1 +c_2 \\ 3 = c_1 6-c_2 \end{cases} $$

Lo risolvo per sostituzione

$$ \begin{cases} c_1 = 1 -c_2 \\ 3 = (1 -c_2) 6-c_2 \end{cases} $$

$$ \begin{cases} c_1 = 1 -c_2 \\ c_2 =\frac{3}{7} \end{cases} $$

$$ \begin{cases} c_1 = 1 -\frac{3}{7} \\ c_2 =\frac{3}{7} \end{cases} $$

$$ \begin{cases} c_1 = \frac{4}{7} \\ c_2 =\frac{3}{7} \end{cases} $$

Sostituisco i coefficienti c1 e c2 nella soluzione

$$ \{ a_n \} = c_1 6^n+c_2 (-1)^n $$

$$ \{ a_n \} = \frac{4}{7} 6^n+\frac{3}{7} (-1)^n $$

Ho così trovato la formula esplicita detta formula chiusa per calcolare il termine ennesimo della successione per n≥2 senza conoscere i precedenti.

$$ \{ a_n \} = \frac{4}{7} 6^n+\frac{3}{7} (-1)^n $$

Per verificare provo a calcolare i primi 4 termini della successione in entrambi i modi

I primi due termini n=0 e n=1 sono uguali perché la formula ricorsiva vale solo per n≥2

n formula ricorsiva formula esplicita/chiusa
0 $$ a_0 = 1 $$ $$ a_0 = 1 $$
1 $$ a_1 = 3 $$ $$ a_1 = 3 $$
2 $$ a_2 = 5 a_1 + 6 a_0 =21 $$ $$ a_2 = \frac{4}{7} 6^2+\frac{3}{7} (-1)^2 =21 $$
3 $$ a_3 = 5 a_2 + 6 a_1 =123 $$ $$ a_3 = \frac{4}{7} 6^3+\frac{3}{7} (-1)^3 =123 $$
4 $$ a_4 = 5 a_3 + 6 a_2 =741 $$ $$ a_4 = \frac{4}{7} 6^4+\frac{3}{7} (-1)^4 =741 $$

Entrambe le formule ( ricorsiva e chiusa ) restituiscono gli stessi risultati.

Il caso delle radici multiple

Se l'equazione caratteristica di una successione ricorsiva ha radici distinte ma alcune radici (s) sono ripetute m volte, ossia multiple, si deve usare una formula diversa. $$ a_n = ( c_{1,0} + c_{1,1} n + c_{1,2} n^2 + ... + c_{1,m1-1} n^{m1-1} \cdot r_1^n ) + \\ \:\:\:\:\:\:\:\:\:
( c_{2,0} + c_{2,1} n + c_{2,2} n^2 + ... + c_{2,m1-1} n^{m1-1} ) \cdot r_2^n + \\
\:\:\:\:\:\:\:\:\:\:\:\:\: \vdots \\ \:\:\:\:\:\:\:\:\:\:
( c_{s,0} + c_{s,1} n + c_{s,2} n^2 + ... + c_{s,m1-1} n^{m1-1} ) \cdot r_s^n $$

Dove i coefficienti c sono costanti.

I coefficienti m_s indicano il numero di volte che la radice r_s è ripetuta nelle soluzioni.

Un esempio pratico

Una equazione caratteristica omogenea ha le seguenti radici:

$$ r = 1,2,3,1,1

Tre radici sono distinte (1,2,3) ma la radice 1 è ripetuta tre volte.

Quindi, calcolo i coefficienti di molteplicità m per ogni radice.

$$ r_1 = 1 \:\:\: m_1 = 3 \\ r_1 = 2 \:\:\: m_2 = 1 \\ r_3 = 3 \:\:\: m_3 = 1 $$

La radice multipla r1=1 ha una molteplicità m1=3.

Poi applico la formula delle radici multiple.

$$ a_n = ( c_{1,0} + c_{1,1} n + c_{1,2} n^2 ) \cdot (1)^n + c_{2,0} \cdot (2)^n + c_{3,0} \cdot (3)^n $$

E così via.

 


 

Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

FacebookTwitterLinkedinLinkedin
knowledge base

La ricorsività