Simboli di Landau — ingegnerismo.it

I simboli di Landau servono a confrontare l’ordine di grandezza di funzioni o successioni.

Si scrive:

f=o(g)

se:

\frac{f}{g}\to0

cioè $f$ è trascurabile rispetto a $g$ .

Si scrive:

f=O(g)

se $|f|$ è dominata da una costante moltiplicativa di $|g|$ in un intorno del punto considerato.

Il punto considerato può essere $x\to0$ , $x\to+\infty$ , $n\to\infty$ o qualunque altro limite rilevante. Per evitare ambiguità, il limite va sempre dichiarato o reso evidente dal contesto.

Piccolo o

La scrittura:

f(x)=o(g(x))\quad \text{per }x\to a

significa:

\lim_{x\to a}\frac{f(x)}{g(x)}=0,

quando $g$ non si annulla in modo problematico nell’intorno considerato. In parole operative, $f$ è di ordine strettamente inferiore a $g$ . Per esempio:

x^2=o(x)\quad \text{per }x\to0,

perché $x^2/x=x\to0$ . Invece, per $x\to+\infty$ , è $x=o(x^2)$ .

Grande O

La scrittura:

f(x)=O(g(x))\quad \text{per }x\to a

significa che esistono costanti $C>0$ e un intorno del punto limite tali che:

|f(x)|\le C|g(x)|.

Il simbolo $O$ esprime una dominazione, non un’equivalenza. Dire che $f=O(g)$ significa che $f$ non cresce, o non diverge localmente, più velocemente di $g$ a meno di una costante. Per esempio:

3x^2-5x+1=O(x^2)\quad \text{per }x\to+\infty.

Equivalenza asintotica

Una notazione collegata è:

f\sim g

che significa:

\frac{f}{g}\to1.

L’equivalenza è più forte della stima $O$ e diversa dal piccolo $o$ . Se $f\sim g$ , allora $f-g=o(g)$ ; se $f=o(g)$ , allora $f$ è trascurabile rispetto a $g$ , non equivalente.

Regole operative

Le regole dei simboli di Landau permettono di manipolare sviluppi e stime:

o(g)+o(g)=o(g),

O(g)+O(g)=O(g),

o(g)\cdot O(h)=o(gh).

Queste regole sono utili negli sviluppi di Taylor, nella propagazione degli errori, nell’analisi numerica e nella complessità degli algoritmi. Tuttavia richiedono che tutte le quantità siano considerate nello stesso limite. Mescolare $x\to0$ e $n\to\infty$ senza dichiararlo porta a formule prive di significato.

Esempio con Taylor

La formula:

\sin x=x-\frac{x^3}{6}+O(x^5)\quad \text{per }x\to0

dice che l’errore commesso fermandosi al termine cubico è dominato da una costante per $|x|^5$ in un intorno di zero. Se invece si scrive:

\sin x=x+o(x),

si conserva solo l’informazione di primo ordine: il resto è trascurabile rispetto a $x$ .

Errori comuni

Un errore frequente è leggere $O(g)$ come “circa uguale a $g$ ”. Non è così: anche $1$ è $O(x^2)$ per $x\to+\infty$ , perché è dominato da $x^2$ , ma non è equivalente a $x^2$ . Un altro errore è cancellare simboli $O$ come se fossero numeri: $O(x^2)-O(x^2)$ resta in generale $O(x^2)$ , non zero.

La notazione è fondamentale per Taylor, limiti, sviluppi asintotici, analisi dell’errore e complessità asintotica.

Vedi anche: Equivalenza asintotica, Sviluppo asintotico, Formula di Taylor, Limite di funzione.