Stima asintotica

descrizione del comportamento limite di una funzione
(Reindirizzamento da O piccolo)

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

Una funzione   si dice infinita in   se il suo limite è infinito al tendere di   a  . In simboli, se

 

Per esempio   è infinita in   e   è infinita in  .

Una successione (che può considerarsi una funzione definita nei numeri naturali) si dice infinita se il suo limite è infinito al tendere di   all'infinito. In simboli: se   è una successione di numeri reali,

 

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:  ,   e   sono numeri qualunque maggiori di 1, mentre   è l'indice della successione.

 

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

Altri esempi

modifica

Ecco alcuni esempi di ordini di infinito riferiti a funzioni, dove   indica l'ordine per la variabile tendente a  :

 
 
 

Ordini di infinitesimo

modifica

Una funzione   si dice infinitesima in   se il suo limite è   al tendere di   a  . In simboli, se

 

Per esempio   ed   sono infinitesime in   (la prima anche in  ).

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

 

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   in   si ha la tabella corrispondente

 

Nota: l'ordine di infinitesimo di   è maggiore di quello di  , visto che quest'ultimo tende a zero più lentamente.

Altri tipi di limiti

modifica

Ecco alcuni esempi di ordini di infinitesimo riferiti a funzioni:

 
 

Successioni asintotiche

modifica

Date due successioni   e  , esse si dicono asintotiche o asintoticamente equivalenti e lo si indica con la notazione   se

 

(Ovviamente si deve supporre che esista un   tale che  ).

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

 

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

 

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

Regole operative

modifica

Confronti fra infiniti e infinitesimi

modifica

Siano   e   due successioni infinite. Per il limite del rapporto abbiamo che se   è uguale a:

  •  :
  è un infinito di ordine inferiore a  
  •  :
  e   sono infiniti dello stesso ordine
  •  :
  è un infinito di ordine superiore a  
  • non esiste:
  e   non sono confrontabili.

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

Lo stesso ragionamento può essere ripetuto per gli infinitesimi. Siano   e   due successioni infinitesime. Per il limite del rapporto abbiamo che se   è uguale a:

  •  :
  è un infinitesimo di ordine superiore a  
  •  :
  e   sono infinitesimi dello stesso ordine
  •  :
  è un infinitesimo di ordine inferiore a  
  • non esiste:
  e   non sono confrontabili.

Principio di sostituzione degli infiniti

modifica

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:

 

Principio di sostituzione degli infinitesimi

modifica

Siano  ,   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:

 

Ad esempio:

 

Principio di sostituzione degli infinitesimi equivalenti

modifica

Siano  ,   due funzioni infinitesime. Per il limite del rapporto   vale

 

se risulta   e  , cioè se numeratori e denominatori sono funzioni asintoticamente equivalenti.

Ad esempio, essendo  :

 

Espressioni asintotiche

modifica

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  .

Schema generale

modifica

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   è una   della successione  , e scriviamo

 

se e solo se

 

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   ed  , mentre la   è una relazione d'ordine, e può essere   o  . Abbiamo pertanto due parametri ognuno dei quali può assumere due valori diversi, sicché le definizioni possibili saranno quattro:

   
     
     

Per distinguere questi quattro casi bisogna che anche il simbolo   che definisce la relazione fra   e   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:

  •   ("O grande") /   ("o piccolo");
  •   ("omega grande") /   ("omega piccolo").

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

  • latino/greco;
  • piccolo/grande.

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

  • latino:  ;
  • greco:  .

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

  • piccolo:  ;
  • grande:  .

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è  ) e "grande" stia per "più grande (cioè  ). Invece per rendere la relazione d'ordine si usa lo strano parametro che abbiamo definito "latino/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. 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   e la "o grande" ("omega") stava per  .

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"):  
  • "mega" ("grande"):  
  • "minuscolo":  
  • "maiuscolo":  
   
     
     

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

 

Dobbiamo dire che la   è una "o-micron maiuscola" della  . Ricordiamo che:

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

Ecco dunque la definizione cercata:

Diciamo che   se e solo se

 

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

1) Ricordando che, in generale:

 

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

 

2) Se una relazione è vera   allora in particolare   un certo   che la soddisfa. Dunque se una successione   è una "minuscola" della successione   allora è anche "maiuscola" di essa:

 

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
  Lo stesso argomento in dettaglio: O-grande.

Siano   e   due funzioni definite su   a valori in  .

Si dice che   è un o grande di  , in simboli:

 

se  

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

Se la successione   ha valori definitivamente diversi da zero, una condizione equivalente, sfruttando il limite superiore, è che sia  .

 
 
 
 

O piccolo

modifica

Si dice che   è un o-piccolo di  , in simboli

 

se  

Omega grande

modifica

Si dice che   è un omega grande di  , in simboli

 

se  

Si dice anche che   ha ordine di grandezza maggiore o uguale a quello di  , o che   è dominata da  .

Usando la notazione del limite inferiore, una condizione equivalente è che sia

 

Omega piccolo

modifica

Si dice che   è un omega piccolo di  , in simboli

 

se  

Le funzioni   e   sono dette avere lo stesso ordine di grandezza, in simboli

 

se  .

Usando i limiti superiore e inferiore, questa condizione si può enunciare come  

Proprietà delle espressioni asintotiche

modifica

Per le espressioni asintotiche valgono le seguenti proprietà:

Proprietà di base

modifica
  1.  .
  2.  .
  3.  .
  4.  .

Implicazioni

modifica
  1.  .
    cioè:  .
  2.  .

Somme di funzioni

modifica
  1.  .
  2.  .
  3.  .
    cioè  .
  4.  .
  5.  .

Prodotti

modifica
  1.  
    cioè  .
  2.  .
  3.  .

Oltre a queste, all'interno di ognuna delle notazioni vale la proprietà transitiva, cioè, ad esempio, se   e   allora  .

La riflessività e la transitività di   implicano che esso è un preordine, la cui relazione di equivalenza associata è proprio  . Infatti dalla definizione di  , è proprio  .

Inoltre, se   è una costante, è definitivamente   se e solo se   e analogamente è definitivamente   se e solo se  .

Problemi di notazione

modifica

L'affermazione   è un o grande di   è di solito scritta come  . Questo è un leggero abuso di notazione, in quanto non si sta asserendo l'uguaglianza delle due funzioni. Inoltre la proprietà non è simmetrica:

 

Per questa ragione, alcuni autori preferiscono una notazione insiemistica e scrivono  , pensando a   come alla classe di tutte le funzioni dominate da  , o usano una notazione introdotta da Hardy, che è la seguente:

  e  

Grafici

modifica
 
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

Collegamenti esterni

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