In analisi numerica, lalgoritmo di sommatoria di Kahan (conosciuto anche come sommatoria compensataRigorosamente, esistono anche altre varianti di sommatoria compensata: vedere ) riduce significativamente l'errore numerico nel totale ottenuto sommando una sequenza di numeri in virgola mobile con precisione finita, se confrontato con il consueto procedimento. Ciò è ottenuto mantenendo una compensazione progressiva separata (una variabile per accumulare piccoli errori).
In particolare, la semplice somma algebrica di numeri in sequenza presenta un errore che, nel caso peggiore, cresce proporzionalmente ad ed uno scarto quadratico medio, che cresce come per addendi casuali (gli errori di arrotondamento producono una passeggiata aleatoria). Utilizzando invece la sommatoria compensata, anche nel caso peggiore l'errore è indipendente da , permettendo di sommare un gran numero di valori con un errore che dipende solo dalla precisione della rappresentazione in virgola mobile.
L'algoritmo è attribuito a William Kahan, anche se Ivo Babuška sembra aver ideato un algoritmo simile in maniera indipendente (da cui sommatoria di Kahan-Babuška). Tecniche precedenti simili sono, per esempio, l'algoritmo della linea di Bresenham, che tiene traccia dell'errore accumulato nelle operazioni sugli interi (anche se già presente in un articolo pubblicato circa nello stesso periodo) e la modulazione Sigma-Delta H. Inose, Y. Yasuda, J. Murakami, "A Telemetering System by Code Manipulation – ΔΣ Modulation," IRE Trans on Space Electronics and Telemetry, Sep. 1962, pp. 204–209. (che integra e non soltanto somma l'errore).
L'algoritmo In pseudocodice, l'algoritmo è:
function KahanSum(input) // Prepara l'accumulatore var sum = 0.0 // Una compensazione in esecuzione per i bit meno significativi persi. var c = 0.0 // L'array input ha elementi indicizzati da 1 a input.length. for i = 1 to input.length do // c è zero per la prima esecuzione. var y = input[i] - c // Purtroppo, sum è grande, y è piccola, quindi le cifre meno significative di y sono perse var t = sum + y // (t - sum) annulla la parte più significativa di y; // sottraendo y si recupera la parte meno significativa cambiata di segno c = (t - sum) - y // Algebricamente, c dovrebbe sempre essere zero. Attenzione // ai compilatori che ottimizzano in maniera troppo aggressiva! sum = t // Alla prossima iterazione, la parte meno significativa persa verrà aggiunta a y per un nuovo tentativo. next i
return sum
Esempio pratico L'algoritmo non necessita una specifica base numerica, solo per l'aritmetica di "normalizzare somme a virgola mobile prima di arrotondare o troncare". I computer, tipicamente, usano l'aritmetica binaria, ma per rendere l'esempio più leggibile verrà utilizzata la base decimale. Supponiamo di utilizzare l'aritmetica in virgola mobile a sei cifre e che sum abbia un valore di 10000,0 e che i prossimi due valori di input[i] siano 3,14159 e 2,71828. Il risultato esatto è 10005,85987 che viene si arrotonda a 10005,9. Con una sommatoria semplice, ogni valore introdotto sarebbe allineato a sum, e molte cifre meno significative andrebbero perse (per arrotondamento o troncamento). Incorrettamente, il primo risultato, dopo l'arrotondamento, sarebbe 10003,1 e il secondo sarebbe 10005,81828 prima dell'arrotondamento e 10005,8 dopo.
Tuttavia, con la sommatoria compensata, si ottiene il risultato arrotondato correttamente di 10005,9.
Assumiamo che c sia inizialmente zero. y = 3.14159 - 0 y = input[i] - c t = 10000.0 + 3.14159 t = sum + y = 10003.14159 Ma solo sei cifre vengono mantenute. = 10003.1 Molte cifre sono andate perse! c = (10003.1 - 10000.0) - 3.14159 Questo deve essere valutato come scritto! = 3.10000 - 3.14159 La parte assimilata di y, recuperata, in contrapposizione al valore originale completo di y. = -.0415900 Gli zeri finali vengono visualizzati perché si tratta di aritmetica a sei cifre. sum = 10003.1 Dunque, poche cifre da input(i) sono rimaste in quelle di sum.
La somma è così grande che solo le cifre più significative dei numeri di input vengono accumulate. Ma, all'iterazione successiva, c, approssimazione dell'errore, controbilancia il problema. y = 2.71828 - -.0415900 Il deficit ottenuto al passo precedente viene incluso. = 2.75987 È di dimensioni simili a y : le cifre più significative sono rimaste. t = 10003.1 + 2.75987 Ma poche sono rimaste nelle cifre di sum = 10005.85987 e il risultato è arrotondato = 10005.9 a sei cifre. c = (10005.9 - 10003.1) - 2.75987 Ciò estrae qualunque cosa sia stata ottenuta. = 2.80000 - 2.75987 In tal caso, c'è un eccesso. = .040130 Ma non importa, l'eccesso verrebbe sottratto alla volta successiva. sum = 10005.9 Il risultato esatto è 10005.85987, esso è correttamente arrotondato a 6 cifre.
L'algoritmo esegue la somma grazie a due accumulatori: sum accumula la somma e c le parti non assimilate in sum, per spostare la parte meno significativa di sum la volta successiva. Quindi la sommatoria procede con delle "cifre di guardia" in c, che è preferibile rispetto a non averle, ma è peggio rispetto al raddoppio della precisione in input. Tuttavia, aumentare semplicemente la precisione dei calcoli, in generale, non è pratico; se input è già in precisione doppia, pochi sistemi forniscono una precisione quadrupla e se lo fanno, input potrebbe potrebbe già essere in precisione quadrupla.
Accuratezza È necessaria un'attenta analisi degli errori nella sommatoria compensata per apprezzarne l'accuratezza. Pur essendo più accurata di una sommatoria semplice, può comunque restituire errori relativi molto grandi in sommatorie mal condizionate.
Supponiamo di sommare valori , per . La somma esatta è:
(calcolata con precisione infinita)
Con la sommatoria compensata, invece, si ottiene , dove l'errore è limitato da:
dove ε è la precisione di macchina dell'aritmetica utilizzata (per esempio, per il formato a precisione doppia in virgola mobile secondo lo standard IEEE). Generalmente, la quantità di interesse è l'errore relativo , che è quindi limitato superiormente da:
Nell'espressione per il limite dell'errore relativo, la frazione è il condizionamento del problema della sommatoria, ovvero la sensibilità intrinseca agli errori del problema della sommatoria, indipendentemente da come è calcolato. L. N. Trefethen e D. Bau, Numerical Linear Algebra (SIAM: Philadelphia, 1997). Il limite dell'errore relativo di ogni metodo di sommatoria (stabile all'indietro) tramite algoritmi statici a precisione fissata (cioè che non usano aritmetica di precisione arbitraria e i cui requisiti di memoria e tempo non cambiano in base ai dati), è proporzionale a tale condizionamento. In un problema di sommatoria mal condizionato, questo rapporto è grande, e in tal caso anche la sommatoria compensata può avere un grande errore relativo. Per esempio, se gli addendi sono numeri casuali non correlati con media nulla, la somma è una passeggiata aleatoria e il condizionamento crescerà proporzionalmente a . D'altra parte, per input casuali con media non nulla, il condizionamento tende a una costante finita per . Se gli input sono tutti non negativi, allora il condizionamento è .
Dato un certo valore di condizionamento, l'errore relativo della sommatoria compensata è indipendente da . In linea di principio, c'è il termine che cresce linearmente con , ma nella pratica questo termine è effettivamente zero: poiché il risultato finale è arrotondato ad una precisione , il termine tende a zero, tranne nel caso in cui . In precisione doppia, ciò corrisponde a un di approssimativamente , molto più grande della maggior parte delle somme. Quindi, per un valore fissato del condizionamento, gli errori della sommatoria compensata sono effettivamente , indipendentemente da .
In confronto, il limite dell'errore relativo per la sommatoria semplice (addizionando i numeri in sequenza e arrotondamento ad ogni passaggio) cresce come moltiplicato per il condizionamento. Questo errore peggiore possibile, tuttavia, raramente è osservato nella pratica, poiché si verifica solo se gli errori di arrotondamento sono tutti nella stessa direzione. In pratica, è molto più probabile che gli errori di arrotondamento abbiano un segno casuale, con media nulla, in modo tale da produrre una passeggiata aleatoria; in questo caso, la sommatoria semplice ha uno scarto quadratico medio, riferito agli errori relativi, che cresce come moltiplicato per il condizionamento. Manfred Tasche e Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000). Comunque, questo è ancora molto peggio della sommatoria compensata. Se la somma può essere eseguita con una precisione doppia, allora viene sostituito da e la sommatoria semplice ha un errore peggiore possibile comparabile con il termine nella sommatoria compensata alla precisione originale.
Per lo stesso motivo, il termine che appare sopra, in , è il limite peggiore possibile che si verifica solo se tutti gli errori di arrotondamento hanno lo stesso segno (e sono della grandezza massima possibile). In pratica, è più probabile che gli errori abbiano un segno casuale, nel qual caso i termini in sono sostituiti da una passeggiata aleatoria; in questo caso, anche per input casuali a media zero, l'errore cresce solo come (ignorando il termine ), con la stessa velocità cresce la somma , cancellando i fattori quando viene calcolato l'errore relativo. Pertanto, anche per somme asintoticamente mal condizionate, l'errore relativo per la sommatoria compensata spesso può essere molto più piccolo di quanto un'analisi del caso peggiore possa suggerire.
Ulteriori miglioramenti Neumaier ha introdotto una leggera modifica dell'algoritmo di Kahan che copre anche il caso in cui il termine successivo da aggiungere è maggiore in valore assoluto rispetto alla somma corrente, scambiando efficacemente il ruolo di ciò che è grande e ciò che è piccolo. In pseudocodice, l'algoritmo è:
function NeumaierSum(input) var sum = input var c = 0.0 // Una compensazione in corso per i bit meno significativi persi. for i = 2 to input.length do var t = sum + input[i] if |sum| >= |input[i]| do c += (sum - t) + input[i] // Se sum è più grande, le cifre meno significative di input[i] vanno perse. else c += (input[i] - t) + sum // Altrimenti, le cifre meno significative di sum vanno perse. sum = t return sum + c // Correzione applicata solo una volta alla fine.
Per molte sequenze di numeri, entrambi gli algoritmi concordano ma un simplice esempio dovuto a Peters mostra che essi possono differire. Sommando in doppia precisione, l'algoritmo di Kahan produce mentre l'algoritmo di Neumaier fornisce il valore corretto .
Alternative Sebbene con l'algoritmo di Kahan, sommando numeri, si realizzi una crescita dell'errore dell'ordine di , solo una crescita leggermente peggiore dell'ordine può essere realizzata da una sommatoria ricorsiva a coppie: si divide in modo ricorsivo l'insieme di numeri in due metà, sommando ogni metà, e quindi si addizionano le due somme. Questo presenta il vantaggio di richiedere lo stesso numero di operazioni aritmetiche della sommatoria semplice (a differenza dell'algoritmo di Kahan, che, rispetto a una sommatoria semplice, richiede un numero di operazioni aritmetiche e ha una latenza quattro volte maggiore) e il calcolo può essere eseguito in parallelo. Il modello di base della ricorsione potrebbe essere, in linea di principio, la somma solo di un numero (o zero numeri), ma per contenere il sovraccarico della ricorsione, normalmente, si usa un modello di base più ampio. L'equivalente della sommatoria ricorsiva a coppie è usato in molti algoritmi di trasformata di Fourier veloce (FFT), ed è responsabile della crescita logaritmica degli errori di arrotondamento in tali FFT. In pratica, con errori di arrotondamento di segno casuale, gli scarti quadratici medi della sommatoria ricorsiva a coppie, effettivamente, crescono come .