Stima asintotica

Da Wikipedia, l'enciclopedia libera.

Quando due successioni sono entrambe infinitesime o entrambe infinite è utile poter stabilire un confronto tra di esse per poter capire quale delle due tenda più rapidamente a 0 o all'infinito. In questo articolo si fa riferimento allo studio di stime asintotiche per le successioni. Operazioni analoghe si possono fare per le funzioni reali di una variabile reale, dove al posto di infinito può trovarsi qualunque punto di accumulazione comune alle due funzioni.

Ordini di infinito[modifica | modifica wikitesto]

Una funzione f si dice infinita in x_0 se il suo limite è infinito al tendere di x a x_0. In simboli, se  \lim_{x \to x_0}|f(x)| = +\infty . Per esempio \frac{1}{x} è infinita in 0 e -e^{-x} è infinita in -\infty.

Una successione (che può considerarsi una funzione definita nei numeri naturali) si dice infinita se il suo limite è infinito al tendere di n all'infinito. In simboli: se  \{a_n\} è una successione di numeri reali,  \lim_{n \to \infty}|a_n| = +\infty . Non tutti gli infiniti sono però identici tra loro: esiste infatti un ordine all'interno degli infiniti, che dipende dal tipo di andamento della funzione a infinito. Ecco alcuni tipi di infinito posti in ordine crescente:  a ,  b e  c sono numeri qualunque maggiori di 1, mentre  n è l'indice della successione.

 \log_a{n} \le n^b \le c^n \le n! \le n^n

Nota: il segno di  \,\le\, va inteso nel senso dell'o piccolo.

Altri esempi[modifica | modifica wikitesto]

Ecco alcuni esempi di ordini di infinito riferiti a funzioni, dove  \mathop{\mathrm{Ord}}_z indica l'ordine per la variabile tendente a  z :

 \mathrm{Ord}_{+\infty}  \, x^a \le \mathrm{Ord}_{+\infty}  \, e^x

 \mathrm{Ord}_0 \, \frac{1}{\sqrt x} \le \mathrm{Ord}_0 \, \frac{1} {x}

 \mathrm{Ord}_1 \, \frac{1} {\sqrt x -1} \le \mathrm{Ord}_1 \, \frac{1}{ x -1}

Ordini di infinitesimo[modifica | modifica wikitesto]

Una funzione f si dice infinitesima in x_0 se il suo limite è 0 al tendere di x a x_0. In simboli, se  \lim_{x \to x_0}f(x) = 0 . Per esempio \frac{1}{x} ed e^{-x} sono infinitesime in +\infty (la prima anche in -\infty).

Una successione  \{a_n\} si dice infinitesima quando il suo limite è uguale a zero al tendere di n all'infinito:

 \lim_{n \to \infty} a_n = 0 .

Come per gli infiniti esistono successioni che tendono a zero più velocemente di altre; prendendo i reciproci della sequenza di diseguaglianze sopra e cambiando i  \le in  \ge si ha la tabella corrispondente

 \tfrac{1}{n^n} \le \tfrac{1}{n!} \le \tfrac{1}{c^n}  \le \tfrac{1}{n^b} \le \tfrac{1}{\log_a n}

Nota: l'ordine di infinitesimo di  \tfrac{1}{n^n} è maggiore di quello di  \tfrac{1}{n!} , visto che quest'ultimo tende a zero più lentamente.

Altri tipi di limiti[modifica | modifica wikitesto]

Ecco alcuni esempi di ordini di infinitesimo riferiti a funzioni:

 \mathrm{ord}_0 \, \sqrt{x} \le \mathrm{ord}_0 \, x \le \mathrm{ord}_0 \, x^2 \le \mathrm{ord}_0 \, x^3

 \mathrm{ord}_{-\infty} \, \frac{1}{x^n} \le \mathrm{ord}_{-\infty} \, e^x

Successioni asintotiche[modifica | modifica wikitesto]

Date due successioni  a_n e  b_n , esse si dicono asintotiche o asintoticamente equivalenti e lo si indica con la notazione  a_n \sim b_n se
 \lim_{n \to \infty} \frac{a_n}  {b_n} = 1
(Ovviamente si deve supporre che esista un  N tale che  b_n \not=0, \ \ \forall n \ge N ).

In questo caso è possibile creare delle catene di relazioni asintotiche:

 \mathrm{se}\, \ a_n \sim b_n \sim ... \sim c_n \ \,\mathrm{ allora }\, \ a_n \sim c_n

Un'espressione composta da prodotto o quoziente di più fattori può essere stimata fattore per fattore:

 \mathrm{se }\, \ a_n \sim a'_n, \  b_n \sim b'_n, \ c_n \sim c'_n  \ \,\mathrm{allora}\, \ \frac{a_n b_n}  {c_n} \sim \frac{a'_n b'_n} {c'_n}

La relazione  \sim è una relazione di equivalenza, in quanto valgono le proprietà riflessiva, commutativa e transitiva rispetto all'operatore.

Regole operative[modifica | modifica wikitesto]

Confronti fra infiniti e infinitesimi[modifica | modifica wikitesto]

Siano  a_n e  b_n due successioni infinite. Per il limite del rapporto abbiamo che se  \lim_{n\to +\infty} \frac{a_n} {b_n} è uguale a:

  •  0 :
 a_n è un infinito di ordine inferiore a  b_n
  • l \not= 0 :
 a_n e  b_n sono infiniti dello stesso ordine
  •  \pm \infty :
 a_n è un infinito di ordine superiore a  b_n
  • non esiste:
 a_n e  b_n non sono confrontabili.

Valgono anche le implicazioni inverse: se  a_n domina  b_n allora il limite è infinito, e così via.


Lo stesso ragionamento può essere ripetuto per gli infinitesimi. Siano  a_n e  b_n due successioni infinitesime. Per il limite del rapporto abbiamo che se  \lim_{n\to +\infty} \frac{a_n} {b_n} è uguale a:

  •  0 :
 a_n è un infinitesimo di ordine superiore a  b_n
  •  l \not= 0 :
 a_n e  b_n sono infinitesimi dello stesso ordine
  • \pm \infty :
 a_n è un infinitesimo di ordine inferiore a  b_n
  • non esiste:
 a_n e  b_n non sono confrontabili.

Principio di sostituzione degli infiniti[modifica | modifica wikitesto]

Siano  a_n e  b_n due infiniti. Nel calcolo del limite del rapporto si possono aggiungere o togliere al numeratore e al denominatore degli infiniti che siano di ordine inferiore, in base a quanto visto nel paragrafo precedente.

Infatti, ad esempio:

 \lim_{n \to +\infty} \frac{n^2 + \sqrt n} {5 n ^ 2 - 3 n} = \lim_{n \to +\infty} \frac{n^2} {5 n ^ 2 - 3 n} + \lim_{n \to +\infty} \frac{\sqrt n} {5 n^ 2 -3 n } = \lim_{n \to +\infty} \frac{n^2} {5 n ^ 2 } + 0 = \frac{1} {5}

Principio di sostituzione degli infinitesimi[modifica | modifica wikitesto]

Siano  a_n ,  b_n due successioni infinitesime. Nel calcolo del limite del rapporto si possono aggiungere o togliere, in una somma di infinitesimi, al numeratore e al denominatore degli infinitesimi che siano di ordine superiore, in base a quanto visto nel paragrafo precedente.

Si ottiene così la seguente equazione utile per la risoluzione di problemi di limiti indeterminati:

 \lim_{n \to \infty} \frac{a_n} {b_n} = \lim_{n \to \infty} \frac{a_n + a'_n} {b_n + b'_n}

Ad esempio:

 \lim_{n \to \infty} \frac{n^{-2} + n ^ {-\frac{1}{2}} } {5n^{-3} - 4n^{-1} } = \lim_{ n \to \infty} \frac{ n ^ {-\frac{1}{2}} }  {  -4n ^   {    -1   } } = - \infty

Principio di sostituzione degli infinitesimi equivalenti[modifica | modifica wikitesto]

Siano  f(x) ,  g(x) due funzioni infinitesime. Per il limite del rapporto  \frac{f(x)} {g(x)} vale

 \lim_{x \to x_0} \frac{f(x)} {g(x)} = \lim_{x \to x_0} \frac{h(x)} {k(x)}

se risulta  f(x) \sim h(x) e g(x) \sim k(x) , cioè se numeratori e denominatori sono funzioni asintoticamente equivalenti.

Ad esempio, essendo  \tan x \sim x:

\lim_{x \to 0} \frac{\tan x} {\sqrt x} = \lim_{x \to 0}\frac{x} {\sqrt x} = 0

Espressioni asintotiche[modifica | modifica wikitesto]

Nella valutazione del comportamento asintotico di un algoritmo vengono introdotte delle relazioni tra successioni numeriche che sono divenute di uso corrente. Tali notazioni si possono anche utilizzare per funzioni reali, con la specifica del valore del dominio a cui tende la variabile, che può non essere  \infty .

Schema generale[modifica | modifica wikitesto]

Le definizioni che introdurremo qui di seguito sono molteplici e a prima vista possono sembrare disorientanti, oppure può risultare faticoso ricordarle tutte assieme e confrontarle fra di loro. Per questa ragione, cioè per fornire un quadro d'insieme che sia anche di aiuto mnemonico, prima di procedere alle definizioni rigorose e specifiche illustreremo in modo discorsivo lo schema generale su cui si basano tutti questi concetti.

Quasi tutte le definizioni che stiamo per introdurre hanno le seguente struttura:

Diciamo che la successione  f(n) è una  \mathrm{X} della successione  g(n) , e scriviamo

 f(n) = \mathrm{X}(g(n))

se e solo se:

 [\mathrm{quantificatore}]C \ \exists N \colon \ \ \ \  \forall n > N, \ \ |f(n)| \prec \succ C |g(n)|

Nelle parentesi quadre abbiamo specificato le parti della definizione che di volta in volta variano. Al posto di [quantificatore] ci possono andare i due quantificatori  \forall ed  \exists , mentre la \prec \succ è una relazione d'ordine, e può essere  \le o \ge . Abbiamo pertanto due parametri ognuno dei quali può assumere due valori diversi, sicché le definizioni possibili saranno quattro:

 \forall \exists
\le \forall  C \ \exists N \colon \ \ \ \  \forall n > N, \ \ |f(n)| \le C |g(n)| \exists C \ \exists N \colon \ \ \ \  \forall n > N, \ \ |f(n)| \le C |g(n)|
\ge \forall  C \ \exists N \colon \ \ \ \  \forall n > N, \ \ |f(n)| \ge C |g(n)| \exists C \ \exists N \colon \ \ \ \  \forall n > N, \ \ |f(n)| \ge C |g(n)|

Per distinguere questi quattro casi bisogna che anche il simbolo  \mathrm{X}(\cdot) che definisce la relazione fra  f(n) e  g(n) possa assumere quattro valori diversi, definiti in qualche modo da due parametri: uno che definisce il quantificatore e l'altro che definisce la relazione d'ordine.

Tali simboli sono i seguenti:

  •  \mathrm{O} ("O grande") /  \mathrm{o} ("o piccolo"),
  •  \Omega ("omega grande") / \omega ("omega piccolo").

Come si vede si tratta effettivamente di quattro simboli definiti da due parametri:

  • italiano/greco
  • piccolo/grande

Di questi due parametri il primo, cioè "italiano/greco", viene utilizzato per specificare la relazione d'ordine, secondo la seguente associazione:

  • italiano:  \le
  • greco:  \ge

mentre il secondo, cioè "piccolo/grande", viene utilizzato per specificare il quantificatore, secondo la seguente associazione:

  • piccolo:  \forall
  • grande:  \exists

Queste associazioni possono sembrare decisamente controintuive. Ad esempio sembrerebbe più utile associare "piccolo/grande" alle relazioni d'ordine, in modo tale che "piccolo" stia per "più piccolo" (cioè  \le ) e "grande" stia per "più grande (cioè  \ge ). Invece per rendere la relazione d'ordine si usa lo strano parametro che abbiamo definito "italiano/greco".

Tutte queste apparenti stranezze si risolvono immediatamente non appena si faccia un po' di opera "filologica". In particolare è importante tenere presente che originariamente quella che ora chiamiamo "o" era in realtà una "omicron", cioè un'altra lettera greca (O-grande). Infatti nell'alfabeto greco esistono due lettere corrispondenti alla nostra "o":

  • la "o-micron", che significa "o piccola"
  • la "o-mega", che significa "o grande".

Pertanto originariamente la notazione indicava proprio quello che abbiamo intenzione di indicare noi: la "o piccola" ("omicron") stava per  \le e la "o grande" ("omega") stava per  \ge .

Quanto al parametro che fino a qui abbiamo indicato con "grande/piccolo", sappiamo bene che questo è solo un modo colloquiale di riferirsi alle lettere "maiuscole/minuscole".

Dunque, se torniamo all'uso originale di tutti questi simboli, abbiamo le seguenti associazioni:

  • "micron" ("piccolo"):  \le
  • "mega" ("grande"):  \ge
  • "minuscolo":  \forall
  • "maiuscolo":  \exists
 \forall \exists
\le  \mathrm{O}  \mathrm{o}
\ge  \Omega  \omega

Forti di questo schema generale, che può esserci utile anche come regola mnemonica, proviamo a scrivere, ad esempio, la definizione della seguente espressione:

 f(n) = \mathrm{O}(g(n))

Dobbiamo dire che la  f(n) è una "o-micron maiuscola" della  g(n) . Ricordiamo che:

  • "micron" sta per "più piccolo", cioè  \le ;
  • "maiuscolo" sta per:  \exists (almeno un)  C tale che...

Ecco dunque la definizione cercata:

Diciamo che  f(n) = \mathrm{O}(g(n)) se e solo se:

 \exists C \ \exists N \colon \ \ \ \  \forall n > N, \ \ |f(n)| \le C |g(n)|

Infine ci interessa conoscere le implicazioni fra tutte queste relazioni. Tali implicazioni si possono ricavare immediatamente dalle seguenti considerazioni:

1) Ricordando che, in generale:

 a \le b \ \Leftrightarrow \ b \ge a

allora  f è una "omicron" (cioè "più piccola") di  g se e solo se g è una "omega" (cioè "più grande") di f:

f(x) = \mathrm{O} / \mathrm{o}(g(x)) \ \Leftrightarrow \ g(x) = \Omega / \omega (f(x))

2) Se una relazione è vera  \forall C allora in particolare  \exists un certo  C che la soddisfa. Dunque se una successione f(n) è una "minuscola" della successione  g(n) allora è anche "maiuscola" di essa:

f(x) = \mathrm{o}/\omega(g(x)) \ \Rightarrow \ f(x) = \mathrm{O} / \Omega (g(x))

Ciò può essere espresso anche dicendo che l'insieme delle "minuscole" di una certa funzione è contenuto nell'insieme delle "maiuscole" di quella funzione, e questa vale anche come regola mnemonica per il parametro "maiuscolo/minuscolo".

O grande[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi O-grande.

Siano  f e  g due funzioni definite su \N a valori in \R.

Si dice che  f(n) è un o grande di  g(n) , in simboli

 f(n) = \mathrm{O}(g(n))

se  \exists c > 0, n_0 \in N \colon \ \ \ \  \forall n \ge n_0, \ \ |f(n)| \le  c |g(n)| .

Si dice anche che  f(n) ha ordine di grandezza minore o uguale a quello di  g(n) , cioè la funzione  g(n) domina  f(n) .

Se la successione  g(n) ha valori definitivamente diversi da zero, una condizione equivalente, sfruttando il limite superiore, è che sia  \limsup_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| < \infty.

Esempi[modifica | modifica wikitesto]

 n = \mathrm{O}(2n)

 n = \mathrm{O}( \frac{n} {2} )

 4n^2 + n = \mathrm{O}(n^2)

 n \log n \neq \mathrm{O}(n)

O piccolo[modifica | modifica wikitesto]

Si dice che  f(n) è un o-piccolo di  g(n) , in simboli

 f(n) = \mathrm{o}(g(n))

se  \lim_{n \to \infty} \frac{f(n)} {g(n)} = 0

Omega grande[modifica | modifica wikitesto]

Si dice che  f(n) è un omega grande di  g(n) , in simboli

 f(n) = \Omega(g(n))

se  \exists c >0, n_0 \in \N\colon \ \ \ \ \forall n \ge n_0, \ \ |f(n)| \geq c |g(n)|.

Si dice anche che  f(n) ha ordine di grandezza maggiore o uguale a quello di  g(n) , o che  g(n) è dominata da  f(n) .

Usando la notazione del limite inferiore, una condizione equivalente è che sia  \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0

Omega piccolo[modifica | modifica wikitesto]

Si dice che  f(n) è un omega piccolo di  g(n) , in simboli

 f(n) = \omega(g(n))

se  \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty

Theta[modifica | modifica wikitesto]

 f(n) e  g(n) sono dette avere lo stesso ordine di grandezza, in simboli

 f(n) = \Theta(g(n))

se  \exists c_1,c_2 > 0, n_0 \in \N \colon \ \ \ \ \forall n \ge n_0, \ \ c_1  |g(n)| \leq |f(n)| \leq c_2 |g(n)| .

Usando i limiti superiore e inferiore, questa condizione si può enunciare come  0 < \liminf_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| \leq \limsup_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| < \infty -->

Proprietà delle espressioni asintotiche[modifica | modifica wikitesto]

Per le espressioni asintotiche valgono le seguenti proprietà:

Proprietà di base[modifica | modifica wikitesto]
  1.  f = \mathrm{O}(g) \iff g = \Omega(f) .
  2.  f = \mathrm{o}(g) \iff  g = \omega(f) .
  3.  f = \mathrm{O}(f) .
  4.  f = \mathrm{o}(f) \ \Rightarrow \  f \equiv 0 .
Implicazioni[modifica | modifica wikitesto]
  1.  g = \mathrm{o}(f) \ \Rightarrow \ g = \mathrm{O}(f) .
    cioè:  o(f) \subseteq \mathrm{O}(f) .
  2.  f = \mathrm{O}(g) \ \not \Rightarrow \ f = \mathrm{o}(g) .
Somme di funzioni[modifica | modifica wikitesto]
  1.  \mathrm{O}(f) + \mathrm{O}(g) = \mathrm{O}(\max \lbrace |f|,|g| \rbrace) .
  2.  \mathrm{O}(k g) = \mathrm{O}(g), \ \forall k \in \R_0 .
  3.  \mathrm{O}(f) + \mathrm{O}(f) = \mathrm{O}(f) .
    cioè  g=\mathrm{O}(f) \land  h=\mathrm{O}(f) \ \Rightarrow g+h = \mathrm{O}(f) .
  4.  \mathrm{O}(f) + \mathrm{o}(f) = \mathrm{O}(f) .
  5.  \mathrm{o}(f) + \mathrm{o}(f) = \mathrm{o}(f) .
Prodotti[modifica | modifica wikitesto]
  1.  \mathrm{O}(f) \mathrm{O}(g) = \mathrm{O}(f g)
    cioè  h=\mathrm{O}(f) \land k=\mathrm{O}(g) \ \Rightarrow h k = \mathrm{O}(f g)  .
  2.  \mathrm{O}(f) \mathrm{o}(g) = \mathrm{o}(f g) .
  3.  \mathrm{o}(f) \mathrm{o}(g) = \mathrm{o}(f g) .


Oltre a queste, all'interno di ognuna delle notazioni vale la proprietà transitiva, cioè, ad esempio, se  f = \mathrm{O}(g) e  g = \mathrm{O}(h)  allora  f = \mathrm{O}(h) .

La riflessività e la transitività di  \mathrm{O} implicano che esso è un preordine, la cui relazione di equivalenza associata è proprio \Theta . Infatti dalla definizione di \Theta , è proprio  f = \Theta(g)\iff f=\mathrm{O}(g)\land g=\mathrm{O}(f) .

Inoltre, se  p è una costante, è definitivamente  f(x) \leq p se e solo se  f(n) = \mathrm{O}(1) e analogamente è definitivamente  f \geq p se e solo se  f(n) = \Omega(1) .

Problemi di notazione[modifica | modifica wikitesto]

L'affermazione  f(x) è un o grande di  g(x) è di solito scritta come  f(x)=\mathrm{O}(g(x)) . Questo è un leggero abuso di notazione, in quanto non si sta asserendo l'uguaglianza delle due funzioni. Inoltre la proprietà non è simmetrica:

 \mathrm{O}(x) = \mathrm{O}(x^2) \ \ \mathrm{ ma } \ \ \mathrm{O}(x^2)\ne \mathrm{O}(x) .

Per questa ragione, alcuni autori preferiscono una notazione insiemistica e scrivono  f \in \mathrm{O}(g) , pensando a \mathrm{O}(g) come alla classe di tutte le funzioni dominate da  g , o usano una notazione introdotta da Hardy, che è la seguente:

 f\lesssim g \iff f \in \mathrm{O}(g)   e    f\ll g \iff f\in \mathrm{o}(g) .

Grafici[modifica | modifica wikitesto]

Esempio di notazione O-grande: f(x) = O(g(x)), esistono c>0 e un valore x0 tale che a destra di x0 si abbia f(x) < c g(x)
Esempio di notazione Ω-grande: f(x) = Ω(g(x)), esistono c>0 e un valore x0 tale che a destra di x0 si abbia f(x) > c g(x)

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica