Premessa

Ciao! Se è la prima volta che capiti su questo sito, ti consiglio di consultare la pagina principale di questo cosiddetto Giardino Digitale per scoprire meglio cos’è e come navigarlo.

Lo stato di questa nota è al momento: 🔴 Bozza.

Definizione: successione

Una successione è una funzione $a : N \to R$ , denotata con " $(a_{n})_{n \in N}$ " o " ${a_{n}}_{n \in N}$ " (o, quando non c’è ambiguità di notazione, anche $(a_{n})$ o ${a_{n}}$ ), che associa a ogni numero naturale $n \in N$ , detto indice della successione, un valore $a (n) \in R$ denotato con " $a_{n}$ " e detto termine della successione.

Osservazioni: successioni sono funzioni continue

Poiché una successione è una funzione definita su $N$ o su un suo sottoinsieme illimitato superiormente, il dominio della successione è un insieme discreto, cioè costituito solo da punti isolati, pertanto la successione è una funzione continua.

Osservazione: possibili applicazioni delle successioni

A cosa ci può servire quindi studiare queste successioni?

Una possibile applicazione del concetto di successione si può trovare in biologia per quanto riguarda la riproduzione cellulare: si può per esempio studiare una successione ${a_{n}}$ dove l’ $n$ -esimo termine indica il numero di cellule che costituiscono l’organismo all’ $n$ -esima generazione, similmente all’applicazione del concetto di derivata allo studio demografico di una popolazione.

Un’altra possibile applicazione è nello studio della complessità degli algoritmi in cui si può studiare una successione ${o_{n}}$ dove l’ $n$ -esimo termine indica il numero di operazioni per eseguire l’algoritmo su un array di dimensione $n$ .

Notazione: successione definita con una formula esplicita

Una successione si può definire attraverso una formula esplicita, cioè esattamente come facciamo con le funzioni definite con una formula esplicita, definendo qual è la trasformazione che viene applicata all’ $n$ -esimo termine: per esempio, possiamo definire una successione come
${a_{n}} = n!$
dove al termine $n$ -esimo viene assegnato il valore del suo fattoriale (es. $a_{5} = 5! = 120$ ), oppure la successione
${b_{n}} = n^{2} + 1$
dove al termine $n$ -esimo viene assegnato il valore di $n^{2} + 1$ (es. $b_{3} = 3^{2} + 1 = 10$ ).

Notazione: successione definita con una relazione ricorsiva

Una successione si può definire attraverso una relazione ricorsiva in cui si esprime ricorsivamente il valore del termine $n$ -esimo, in particolare:

si esprime il valore del termine $n$ -esimo rispetto a $k \geq 1$ termini che lo precedono, i quali sono parametri di una funzione $g (x_{n - 1}, x_{n - 2}, \dots, x_{n - k})$ detta relazione ricorsiva e

si esprime il valore iniziale dei primi $k$ termini della successione $a_{0}, \dots, a_{k - 1}$ :

${x_{n}} = ⎩ ⎨ ⎧ x_{0} = v_{0} x_{1} = v_{1} \dots x_{k - 1} = v_{k - 1} x_{n} = g (x_{n - 1}, x_{n - 2}, \dots, x_{n - k})$
Per esempio, nella successione
${r_{n}} = {r_{0} = 3 r_{n} = r_{n - 1}^{2} - r_{n - 1}$
abbiamo che:

$r_{1} = r_{0}^{2} - r_{0} = 3^{2} - 3 = 6$ ,

$r_{2} = r_{1}^{2} - r_{1} = 6^{2} - 6 = 30$ ,

$r_{3} = r_{2}^{2} - r_{2} = 3 0^{2} - 30 = 870$

e così via.

Un esempio invece di una successione definita con una relazione ricorsiva con $k = 2$ è la successione di Fibonacci.

Definizione: successione di Fibonacci

La successione (o sequenza) di Fibonacci è una successione definita come
${F_{n}} = ⎩ ⎨ ⎧ F_{0} = 0 F_{1} = 1 F_{n} = F_{n - 1} + F_{n - 2}$

Osservazione: differenza nelle due notazioni

La principale differenza tra la notazione con la formula esplicita e quella con la relazione ricorsiva è che la prima ci permette di calcolare direttamente l’ $n$ -esimo termine, mentre con la seconda siamo costretti a calcolare anche tutti gli altri termini precedenti.

Possiamo quindi fare un parallelismo con i tipi di accesso alla memoria in informatica, in cui la notazione con la formula esplicita ci permette di fare un accesso casuale all’ $n$ -esimo termine, mentre la notazione con la relazione ricorsiva ci permette di fare un accesso sequenziale.

Dal momento che le successioni sono in realtà funzioni, anche a loro si applicano concetti come quello di monotonia e limitatezza.

Definizione: successione monotona

Una successione ${a_{n}}$ si dice

monotona crescente se $\forall n \in N . (a_{n + 1} \geq a_{n})$

monotona strettamente crescente se $\forall n \in N . (a_{n + 1} > a_{n})$

monotona decrescente se $\forall n \in N . (a_{n + 1} \leq a_{n})$

monotona strettamente decrescente se $\forall n \in N . (a_{n + 1} < a_{n})$

monotona se è monotona crescente o monotona decrescente e

strettamente monotona se è strettamente monotona crescente o strettamente monotona decrescente.

Definizione: successione limitata

Una successione ${a_{n}}$ si dice

superiormente limitata se $\exists m \in R, \forall n \in N . (m \leq a_{n})$

inferiormente limitata se $\exists m \in R, \forall n \in N . (a_{n} \leq M)$

limitata se $\exists m, M \in R, \forall n \in N . (m \leq a_{n} \leq M)$

1 - Limiti di successioni

Una successione, essendo illimitata superiormente, si ha che $+ \infty$ è un punto di accumulazione per il suo dominio. È quindi l’unico punto di accumulazione. Ne segue che per le successioni l’unico limite che ha senso calcolare è quello per la variabile $n$ che tende a $+ \infty$ .

Richiamiamo la definizione di limite, adattandola alle successioni, per $n \to + \infty$ .

Definizione: limite di successione

Data una successione $(a_{n})$ e un valore $l \in R \cup {\pm \infty}$ , diciamo che $(a_{n})$ ha limite $l$ per $n$ che tende a $+ \infty$ se, per ogni intorno $I (l)$ di $l$ , esiste un $n_{0} \in N$ tale che per ogni $n \geq n_{0}$ si ha che $a_{n} \in I (l)$ . In tal caso scriviamo
$n \to + \infty lim a_{n} = l$
o, più semplicemente,
$n lim a_{n} = l$
Cioè
$n lim a_{n} = l ⇕ \forall I (l), \exists n_{0} \in N, \forall n \in N . (n \geq n_{0} ⟹ a_{n} \in I (l))$

In base al valore che può assumere il limite, la successione può essere convergente, divergente (positivamente o negativamente) o indeterminata.

Definizione: convergenza e divergenza di successioni

Una successione $(a_{n})$ si dice che:

converge a $l$ (oppure $a_{n}$ è una successione convergente) se $n lim a_{n} = l \in R$ .

diverge positivamente (oppure $a_{n}$ è una successione divergente positivamente) se $n lim a_{n} = + \infty$ .

diverge negativamente (oppure $a_{n}$ è una successione divergente negativamente) se $n lim a_{n} = - \infty$ .

è indeterminata se non esiste il limite $n lim a_{n}$ .

Teorema del legame tra la convergenza e la limitatezza di una successione

Se una successione ${a_{n}}$ è convergente allora è anche limitata.

Teorema del legame tra la monotonia e il limite di una successione

Se una successione ${a_{n}}$ è monotona allora il limite $n lim a_{n}$ esiste e, in particolare,

se ${a_{n}}$ è crescente e superiormente limitata allora ${a_{n}}$ è convergente,

se ${a_{n}}$ è decrescente e inferiormente limitata allora ${a_{n}}$ è convergente,

se ${a_{n}}$ è crescente e superiormente illimitata allora ${a_{n}}$ è divergente a $+ \infty$ ,

se ${a_{n}}$ è decrescente e inferiormente illimitata allora ${a_{n}}$ è divergente a $- \infty$ .

Osservazione: casi specifici del limite di successioni

Se una successione ha limite $l \in R$ (cioè è una successione convergente), si ha che
$n lim a_{n} = l \in R ⇕ \forall ε > 0, \exists n_{0} \in N, \forall n \in N . (n \geq n_{0} ⟹ ∣ a_{n} - l ∣ < ε)$
Invece, se ha limite $l = \pm \infty$ (cioè è una successione divergente positivamente o negativamente), si ha che
$n lim a_{n} = + \infty ⇕ \forall b \in R, \exists n_{0} \in N, \forall n \in N . (n \geq n_{0} ⟹ a_{n} > b) n lim a_{n} = - \infty ⇕ \forall b \in R, \exists n_{0} \in N, \forall n \in N . (n \geq n_{0} ⟹ a_{n} < b)$

1.1 - Legame tra limiti di funzioni e limiti di successioni

Osservazione: validità dei teoremi dei limiti nei limiti di successioni

Poiché i limiti di successioni non sono altro che limiti di funzioni per $n \to + \infty$ , per essi valgono tutti i teoremi e le considerazioni fatte per questi ultimi, in particolare:

il teorema di unicità del limite,

il teorema di limitatezza locale,

il teorema della permanenza del segno e le sue conseguenze,

l’algebra dei limiti (somma, prodotto, quoziente e composizione),

i teoremi del confronto e le loro conseguenze,

il teorema sui limiti delle successioni monotone.

Inoltre, anche per i limiti di successioni si introducono le stesse forme indeterminate e si hanno i seguenti limiti notevoli:

$n lim (1 + \frac{1}{n})^{n} = e$ ,

$\forall k \in R^{> 0}, \forall a \in R^{> 1} . (n lim \frac{n ^{k}}{a _{n}} = 0)$ ,

$\forall k \in R^{> 0}, \forall a \in R^{> 0} ∖ {1} . (n lim \frac{lo g _{a} n}{n ^{k}} = 0)$ ,

$\forall k \in R^{> 0}, \forall a \in (0, 1) . (n lim n^{k} a^{n} = 0)$ .

Inoltre, anche ai limiti di successioni si associano le nozioni di infinito, infinitesimo, $o$ -piccolo, equivalenza asintotica, ordini di infinito e di infinitesimo, infiniti e infinitesimi campione e parte principale.

1.2 - Teorema di caratterizzazione del limite

Il prossimo teorema lega tra loro le nozioni di limite di funzione e di limite di successione.

Teorema di caratterizzazione del limite

Data una funzione $f : A \subseteq R \to R$ (con $A \neq = \emptyset$ ), un punto di accumulazione $x_{0} \in R \cup {\pm \infty}$ per $A$ e un valore $l \in R \cup {\pm \infty}$ , allora $x \to x_{0} lim f (x) = l$ se e solo se, per ogni successione $(x_{n})$ in $A ∖ {x_{0}}$ che tende a $x_{0}$ si ha che $n lim f (x_{n}) = l$ :
$x \to x_{0} lim f (x) = l ⇕ \forall (x_{n}) \subseteq A ∖ {x_{0}} . (x_{n} \to x_{0} ⟹ n lim f (x_{n}) = l)$

2 - Sottosuccessioni

Se da una successione selezioniamo solo alcuni termini stiamo creando una sottosuccessione.

Definizione: sottosuccessione

Date due successioni $(a_{n})$ e $(b_{n})$ , diciamo che $(b_{n})$ è una sottosuccessione (o successione estratta) di $(a_{n})$ se $b_{n} = a_{φ (n)}$ , dove $φ : N \to N$ è una successione strettamente crescente.

$(b_{n})$ si può anche denotare come " $(a_{n_{k}})$ ".

Esempio di sottosuccessione

Consideriamo una successione qualsiasi $(a_{n})$ e consideriamo una sottosuccessione $(b_{n})$ definita da $b_{n} = a_{φ (n)}$ , dove $φ : N \to N$ è una successione strettamente crescente. Supponiamo che
$φ (0) = 2, φ (1) = 4, φ (2) = 5, φ (3) = 13, \dots$
Seguendo la regola $b_{n} = a_{φ (n)}$ , abbiamo che
$φ (0) = 2 ⟹ b_{0} = a_{φ (0)} = a_{2}, φ (1) = 4 ⟹ b_{1} = a_{φ (1)} = a_{4}, φ (2) = 5 ⟹ b_{2} = a_{φ (2)} = a_{5}, φ (3) = 13 ⟹ b_{3} = a_{φ (3)} = a_{13}, \dots$
Cioè, quello che stiamo facendo è selezionare tramite la funzione $φ$ gli indici dei termini di $(a_{n})$ che vogliamo associare a $(b_{n})$ .

Una sottosuccessione di una successione è quindi una successione i cui termini sono selezionati tra quelli della successione di partenza, in modo che se un elemento è selezionato (per esempio $a_{2}$ ), allora i successivi sono selezionati tra quelli che hanno un indice maggiore di quest’ultimo (cioè $a_{4}$ , $a_{5}$ , $a_{13}$ , ecc.).

Teorema di permanenza del limite per sottosuccessioni

Data una successione $(a_{n})$ , se ha limite uguale a $l \in R \cup {\pm \infty}$ , allora per ogni sottosuccessione $(a_{n_{k}})$ di $(a_{n})$ si ha che $k lim a_{n_{k}} = l$ :
$\forall (a_{n}), \forall (a_{n_{k}}) sottosuccessione di (a_{n}) . (n lim a_{n} = l \in R \cup {\pm \infty} ⟹ k lim a_{n_{k}} = l)$

Teorema di Bolzano-Weierstrass

Una successione $(a_{n})$ limitata ammette almeno una sottosuccessione convergente.

Criterio del rapporto per le successioni

Data una successione $(a_{n})$ a termini positivi, se esiste il limite $n lim \frac{a _{n + 1}}{a _{n}} = l \in [0, + \infty) \cup {+ \infty}$ , allora:

Se $l < 1$ , allora $n lim a_{n} = 0$ .

Se $l > 1$ , allora $n lim a_{n} = + \infty$ .

Osservazione: $l = 1$ nel criterio del rapporto per le successioni

Nel criterio del rapporto per le successioni non viene considerato il caso $l = 1$ perché, in questo caso, non si può concludere nulla ed è necessario ricorrere a un altro metodo per calcolare il limite $n lim a_{n}$ .

Criterio della radice per le successioni

Data una successione $(a_{n})$ a termini positivi, se esiste il limite $n lim n a_{n} = l \in [0, + \infty) \cup {+ \infty}$ , allora:

Se $l < 1$ , allora $n lim a_{n} = 0$ .

Se $l > 1$ , allora $n lim a_{n} = + \infty$ .

Osservazione: $l = 1$ nel criterio della radice per le successioni

Anche nel criterio della radice per le successioni non viene considerato il caso $l = 1$ perché, sempre per lo stesso motivo, in questo caso non si può concludere nulla ed è necessario ricorrere a un altro metodo per calcolare il limite $n lim a_{n}$ .

Teorema della generalità del criterio della radice

Data una successione $(a_{n})$ a termini positivi, se esiste il limite $n lim \frac{a _{n + 1}}{a _{n}} = l \in [0, + \infty) \cup {+ \infty}$ , allora $n lim n a_{n} = l$ .

3 - Successioni geometriche

Definizione: successione geometrica

Una successione ${a_{n}}$ si dice geometrica se
$\exists q \in R, \forall n \in N . (a_{n + 1} = q \cdot a_{n})$
In particolare, $q$ si dice ragione della successione.

Osservazioni: successioni geometriche definite solo con relazione ricorsiva

Data la loro natura in cui ogni termine è legato al precedente, le successioni geometriche si possono definire solo tramite la notazione con la relazione ricorsiva.

Per esempio, possiamo definire la successione geometrica
${a_{n}} = {a_{0} = 1 a_{n + 1} = 3 \cdot a_{n}$
in cui abbiamo che la sua ragione è $3$ e i primi $4$ termini sono:

$a_{0} = 1$ ,

$a_{1} = 3 \cdot a_{0} = 3 \cdot 1 = 3$ ,

$a_{2} = 3 \cdot a_{1} = 3 \cdot 3 = 9$ ,

$a_{3} = 3 \cdot a_{2} = 3 \cdot 9 = 27$ ,

e così via.

Osservazione: formula esplicita di una successione geometrica

Data una successione geometrica ${a_{n}}$ , se $a_{0} = 0$ , allora $a_{n} = 0$ per ogni $n \geq 0$ .

Se invece $a_{0} \neq = 0$ , allora avremo che:

$a_{1} = q \cdot a_{0}$ ,

$a_{2} = q \cdot a_{1} = q \cdot q \cdot a_{0} = q^{2} \cdot a_{0}$ ,

$a_{3} = q \cdot a_{2} = q \cdot q^{2} \cdot a_{0} = q^{3} \cdot a_{0}$ ,

e così via.

Possiamo generalizzare ciò come
$a_{n} = q^{n} \cdot a_{0}$
e questa formula viene detta formula esplicita della successione geometrica perché è un modo alternativo di definirla.

4 - Successioni definite con relazione ricorsiva

4.1 - Punti fissi

Approfondiamo le successioni definite con una relazione ricorsiva.

Definizione: punto fisso o punto di equilibrio di una relazione ricorsiva

In una successione ${x_{n}}$ definita con una relazione ricorsiva, un valore $x^{⋆} \in dom (g)$ viene detto punto fisso (o punto di equilibrio) di $g$ se
$g (x^{⋆}) = x^{⋆}$

Proposizione: legame tra la convergenza di una successione e il punto fisso

Data una funzione $g : R \to R$ continua e una successione ${x_{n}}$ definita con la relazione ricorsiva $g$ , se esiste il limite
$n lim x_{n} = x^{⋆} \in R$
(cioè ${x_{n}}$ converge), allora $x^{⋆}$ è un punto fisso di $g$ (cioè $g (x^{⋆}) = x^{⋆}$ ).

Dimostrazione del legame tra convergenza di una successione e punto fisso

Dimostriamo il legame tra la convergenza di una successione e il punto fisso.

Poiché la successione ${x_{n}}$ converge, cioè
$n lim x_{n} = x^{⋆}$
allora abbiamo anche che
$n lim x_{n + 1} = x^{⋆}$
e cioè, per definizione di relazione ricorsiva,
$n lim g (x_{n}) = x^{⋆}$
D’altra parte, poiché $g$ è continua in $x^{⋆}$ , per il teorema del limite della funzione composta (o, equivalentemente, per la caratterizzazione della continuità per successioni) possiamo portare il limite “dentro” $g$ :
$n lim g (x_{n}) = g (n lim x_{n}) = g (x^{⋆})$
Confrontando le due espressioni ottenute per $n lim g (x_{n})$ , cioè
$n lim g (x_{n}) = x^{⋆} \land n lim g (x_{n}) = g (x^{⋆})$
per il teorema di unicità del limite, otteniamo
$g (x^{⋆}) = x^{⋆}$
che è proprio la definizione di punto fisso di $g$ .

$■$

4.2 - Successioni ricorsive lineari

Consideriamo ora un caso specifico delle successioni ricorsive, ossia quelle lineari.

Definizione: successione ricorsiva lineare

Una successione ricorsiva ${x_{n}}$ si dice lineare quando la sua formula ricorsiva è della forma $g (x) = a x + b$ con $a, b \in R$ , ossia
${x_{0} = v_{0} x_{n} = a x_{n - 1} + b$

Osservazione: casi specifici di successioni ricorsive lineari

Se $b = 0$ , allora si trova che $x_{n} = a x_{n - 1}$ , ovvero la successione geometrica $x_{n} = a^{n} x_{0}$ , quindi

Se $x_{0} = 0$ , allora $x_{n} = 0$ per ogni $n \in N$

Se $x_{0} \neq = 0$ , allora $n lim x_{n} = ⎩ ⎨ ⎧ + \infty - \infty 0 \neq \exists se a > 1 \land x_{0} > 0 se a > 1 \land x_{0} < 0 se - 1 < a < 1 se a < - 1$

Se $b \neq = 0$ allora

$a = 1$ , allora $g (x) = x + b$ non ha punti fissi e la progressione è aritmetica: $x_{n} = x_{n - 1} + b$ e quindi $n lim x_{n} = {+ \infty - \infty se b > 0 se b < 0$ (ovviamente se $b = 0$ diventa un punto fisso)

$a \neq = 1$ , allora $g (x) = a x + b$ e ha come unico punto fisso $x^{⋆} = a x^{⋆} + b$ cioè $x^{⋆} = \frac{b}{1 - a}$ Definiamo ora $y_{n} = x_{n} - x^{⋆}$ e si ha che $y_{n} = x_{n} - x^{⋆} = g (x_{n - 1}) - x^{⋆} = a x_{n} + b - x^{⋆} = a y_{n} + a x^{⋆} + b - x^{⋆} = a y_{n}$ da cui $y_{n} = a^{n} y_{0}$ è una successione geometrica con $y_{0} = x_{0} - x^{⋆}$ e quindi $x_{n} = a^{n} (x_{0} - x^{⋆}) + x^{⋆}$ In particolare:

se $x_{0} = x^{⋆}$ allora $x_{n} = x^{⋆}$ per ogni $n \in N$

se $x_{0} \neq = x^{⋆}$ allora $n lim x_{n} = ⎩ ⎨ ⎧ + \infty x^{⋆} \neq \exists se a > 1 se - 1 < a < 1 se a \leq - 1$ Il caso $a = 1$ l’abbiamo già visto prima
Anche in questi casi si può visualizzare con il grafico a ragnatela.

4.3 - Successioni ricorsive non lineari

Ora vediamo il caso generale, ossia le successioni ricorsive non lineari.

In generale, non è possibile stabilire qual è il comportamento di una arbitraria successione ${x_{n}}$ , ma in molti casi è possibile farlo se $x_{0} ≃ x^{⋆}$ , cioè se prendiamo $x_{0}$ abbastanza vicino a $x^{⋆}$ , facendo così uno studio locale.

Definizione: punto di equilibrio stabile

Data una successione ricorsiva ${x_{n}}$ con formula ricorsiva $g$ e un punto fisso $x^{⋆} \in R$ di $g$ , diciamo che $x^{⋆}$ è un punto di equilibrio stabile se
$\forall ε > 0, \exists δ > 0, \forall n \in N . (∣ x_{0} - x^{⋆} ∣ < δ ⟹ ∣ x_{n} - x^{⋆} ∣ < ε)$
Altrimenti, si dice che $x^{⋆}$ è un punto di equilibrio instabile.

Definizione: punto di equilibrio asintoticamente stabile

Data una successione ricorsiva ${x_{n}}$ con formula ricorsiva $g$ e un punto fisso $x^{⋆} \in R$ di $g$ , diciamo che $x^{⋆}$ è un punto di equilibrio asintoticamente stabile se è stabile e se
$\exists \hat{δ} > 0. (∣ x_{0} - x^{⋆} ∣ < \hat{δ} ⟹ n lim x_{n} = x^{⋆})$

Teorema di stabilità per linearizzazione

Data una successione ricorsiva ${x_{n}}$ con formula ricorsiva $g$ e un punto fisso $x^{⋆} \in R$ di $g$ , allora:

Se $∣ g^{'} (x^{⋆}) ∣ < 1$ , allora $x^{⋆}$ è asintoticamente stabile.

Se $∣ g^{'} (x^{⋆}) ∣ > 1$ , allora $x^{⋆}$ è instabile.

Esempio del teorema di stabilità per linearizzazione

Dato un $g (x) = r x (1 - x)$ con $r > 0$ . Per ragioni applicative ci limitiamo al caso $x \geq 0$ .

Cerchiamo i punti fissi: $x^{⋆} = r x^{⋆} (1 - x^{⋆})$ e quindi $x^{⋆} (1 - r + r x^{⋆}) = 0$ e quindi

$x_{1}^{⋆} = 0$

$x_{2}^{⋆} = \frac{r - 1}{r} = 1 - \frac{1}{r}$ (notare che $x_{2}^{⋆} \geq 0 ⟺ r \geq 1$ )

Quindi se $0 < r < 1$ abbiamo che $x_{1}^{⋆} = 0$ è l’unico punto fisso.

Si ha $g^{'} (x) = - 2 r x + r$ e quindi $g^{'} (0) = r < 1$ dunque $x_{1}^{⋆}$ è asintoticamente stabile.

Notiamo che $\forall x_{0} \in [0, 1]$ abbiamo che $lim_{n} x_{n} = x_{1}^{⋆} = 0$ e l’intervallo $[0, 1]$ viene detto bacino di attrazione.

Vediamo invece che succede se $r = 2$ : ora $g^{'} (0) = 2 = r > 1$ , quindi $x_{1}^{⋆} = 0$ è instabile. Anche partendo con $x_{0}$ vicino a $x_{1}^{⋆}$ , la successione si allontana e sembra convergere a $x_{2}^{⋆}$ . In effetti, se $1 < r < 3$ , allora $g^{'} (x_{2}^{⋆}) = g^{'} (1 - \frac{1}{r}) = - 2 r (1 - \frac{1}{r}) + r = - r + 2 \in (- 1, 1)$ quindi essendo $∣ g^{'} (x_{2}^{⋆}) ∣ < 1$ abbiamo che $x_{2}^{⋆}$ è asintoticamente stabile.

Per $r \geq 3$ si può invece verificare che sia $x_{1}^{⋆}$ che $x_{2}^{⋆}$ sono instabili: al crescere del parametro $r$ , la dinamica diventa sempre più complicata (teoria del caos deterministico).

[!osservazione]+ Osservazione: applicazione delle successioni ricorsive nel merge sort

Vediamo ora un’applicazione delle successioni ricorsive nel merge sort.

Determiniamo la complessità $T (n)$ del merge sort su un array di $n$ elementi, supponendo per semplicità

n = 2^{m}

così posso continuare a dividere l’array in due metà della stessa lunghezza.

Il merge sort ha costo $c \cdot n$ (con $c$ costante), dunque

T (n) = 2 T (\frac{n}{2}) + c \cdot n

Quindi

T (n) = 2 (2 T (\frac{n}{4}) + c \cdot \frac{n}{2}) + c \cdot n = 4 T (\frac{n}{4}) + 2 c n = 8 T (\frac{n}{8}) + 3 c n = 16 T (\frac{n}{16}) + 4 c n = \dots = 2^{m} T (\frac{n}{2 ^{m}}) + m c n

Dato che nell’ipotesi iniziale $n = 2^{m}$ , abbiamo che

T (n) = 2^{m} T (1) + m c n = T (1) n + c lo g_{2} n \cdot n = O (n lo g_{2} n)

Quindi il merge sort ha complessità $O (n lo g n)$ nel caso peggiore.

Fonti

🏫 Corso di Laurea in Informatica (L-31 R) presso l’Università di Torino:

Corso di Analisi Matematica - canale C, A.A. 2020-21 (pagina Moodle):

Prof. Boscaggin Alberto, videolezioni:

L13a, L13b.

L15a, L15b.

L16a, L16b.

📚 Sergio Lancelotti, Lezioni di Analisi Matematica I, Celid, 2020 (ISBN: 978-8867891979):

Capitolo 3 - Limiti e continuità:

5 - Limiti di successioni.

🪴 Giardino Digitale di Rexus752

Explorer

Limiti di successioni

1 - Limiti di successioni

1.1 - Legame tra limiti di funzioni e limiti di successioni

1.2 - Teorema di caratterizzazione del limite

2 - Sottosuccessioni

3 - Successioni geometriche

4 - Successioni definite con relazione ricorsiva

4.1 - Punti fissi

4.2 - Successioni ricorsive lineari

4.3 - Successioni ricorsive non lineari

Indice