Algoritmo di Knuth per il calcolo di media e varianza

Media:
Prendiamo in considerazione la media aritmetica:

Se questa formula la poniamo in forma di algoritmo per eseguirla con un software apposito, possiamo andare incontro a diverse anomalie. Infatti, se i dati osservati sono particolarmente numerosi (ad esempio dati di grandi imprese o di banche), il calcolo della media semplice porta a risultati inefficienti  con tempi di calcolo e memoria abbastanza elevati e, a lungo andare, i risultati possono rivelarsi totalmente sbagliati a causa del fenomeno della catastrophic cancellation.
Per rimediare a questo problema, utilizzeremo l'algoritmo di Knuth.
L'informatico Donald Knuth ha proposto delle formule alternative per media e varianza che permettono di calcolare queste grandezze con una complessità computazionale ridotta.

Per calcolare la media con l'algoritmo di Knuth si applica una media ponderata che permette di aggiornare l'informazione ricavata fino al passo n-1 con quella fornita dall'ennesimo dato immesso:

• Calcolo della media con l'algoritmo di Knuth:

Da tale risultato si è sviluppato un algoritmo che permetta di calcolare la media in maniera sequenziale ovviando alla problematica della catastrophic cancellation.

Varianza:
Prendiamo in considerazione la varianza:

Poichè la varianza indica la concentrazione, allora:

• Minore è la varianza e maggiore è la concentrazione dei dati attorno al valore medio
• Maggiore è la varianza e più i dati si disperdono attorno al valore medio.

Anche in questo caso, come nella media, se poniamo tale formula in forma algoritmica possiamo andare incontro a diverse anomalie.
Anche per la varianza, Knuth ha proposto un algoritmo che permette di evitare di trovarsi di fronte al fenomeno della catastrophic cancellation:

• Calcolo della varianza con l'algoritmo di Knuth:

Codice algoritmo di Knuth (running algorithm) :


Quest'algoritmo è meno incline alla perdita di precisione dovuta alla cancellazione, ma potrebbe essere meno efficiente a causa dell'operazione di divisione all'interno del ciclo.


Esistono tanti altri algoritmi per il calcolo della media e della varianza.
Prendiamo in considerazione due algoritmi:

1. Algoritmo Naive
2. Two Step Algorithm

1.

Se volessimo utilizzare quest'algoritmo per calcolare la varianza per l'intera popolazione, basta modificare la variabile variance in questo modo:

variance= (Sum_sqr - (Sum*Sum)/n)/N

Per N abbastanza grande, i due valori Sum_sqr e (Sum*Sum)/n sono approssimativamente uguali e questo porta ad avere una varianza approssimativamente uguale a 0 e quindi ad una poca precisione del risultato.

2.

Due step per il calcolo della varianza:

1. Calcolo della media del campione:     
2. Calcolo della somma dei quadrati della varianza: 

Nella pratica è poco conveniente utilizzare questi due algoritmi, poichè è facile incorrere ad errori computazionali come la catastrophic cancellation, la quale prevede la cancellazione di molte cifre decimali. 

Per tale motivo, preferiamo utilizzare l'algoritmo del calcolo della media e della varianza di Knuth.