Visualizza wikitesto di Sommatoria ricorsiva a coppie

In [[analisi numerica]], la '''sommatoria ricorsiva a coppie''' (''pairwise summation'' in [[Lingua inglese|inglese]]), chiamata anche '''sommatoria a cascata''' (''cascade summation''), è una tecnica per sommare una sequenza di [[Numero in virgola mobile|numeri in virgola mobile]] di [[Cifra significativa|precisione]] finita che, sostanzialmente, riduce l'[[Errore inerente|errore di arrotondamento]] accumulato in confronto a quello accumulato dalla semplice sommatoria in sequenza.<ref name=Higham93>{{Cita pubblicazione|titolo=The accuracy of floating point summation |nome1=Nicholas J. |cognome1=Higham |rivista=[[SIAM Journal on Scientific Computing]] |volume=14 |numero=4 |pp=783-799 |doi=10.1137/0914050 |anno=1993}}</ref>  Sebbene ci siano anche altre tecniche, come l'[[algoritmo di sommatoria di Kahan]], le quali, tipicamente, presentano anche errori di arrotondamento più piccoli, la sommatoria ricorsiva a coppie è quasi altrettanto buona (differendo soltanto di un fattore logaritmico), pur avendo un costo computazionale molto più basso; essa può essere implementata in modo da avere quasi lo stesso costo (e esattamente lo stesso numero di operazioni aritmetiche) della sommatoria semplice.

In particolare, la sommatoria ricorsiva a coppie di una sequenza di ''n'' numeri ''x<sub>n</sub>'' funziona dividendo [[Algoritmo ricorsivo|ricorsivamente]] la sequenza in due metà, sommando ogni metà e addizionando le due somme: un [[Divide et impera (informatica)|algoritmo di tipo ''divide et impera'']]. I suoi errori di arrotondamento nel peggiore dei casi crescono [[O-grande|asintoticamente]] al massimo come ''O''(ε&nbsp;log&nbsp;''n''), dove ε è la [[Epsilon di macchina|precisione di macchina]] (assumendo un [[Condizionamento (matematica)|numero di condizionamento]] fissato, come discusso sotto).<ref name=Higham93/>  In compenso, la semplice tecnica di accumulare la somma in sequenza (addizionando ogni ''x<sub>i</sub>'' uno alla volta per ''i''&nbsp;=&nbsp;1,&nbsp;...,&nbsp;''n'') ha errori di arrotondamento che crescono nel peggiore dei casi come ''O''(ε''n'').<ref name=Higham93/> La [[Algoritmo di sommatoria di Kahan|sommatoria di Kahan]] ha un errore nel peggiore dei casi approssimativamente di ''O''(ε), indipendente da ''n'', ma richiede un numero di operazioni aritmetiche molte volte maggiore.<ref name=Higham93/> Se gli errori di arrotondamento sono casuali e, in particolare, hanno segni casuali, allora essi danno luogo ad una [[passeggiata aleatoria]] e, per la sommatoria ricorsiva a coppie, la crescita dell'errore è ridotta a una media di <math>O(\varepsilon \sqrt{\log n})</math>.<ref name=Tasche>Manfred Tasche and Hansmartin Zeuner ''Handbook of Analytic-Computational Methods in Applied Mathematics'' Boca Raton, FL: CRC Press, 2000).</ref>

Una struttura ricorsiva molto simile di sommatoria si trova in molti algoritmi di [[trasformata di Fourier veloce]] (FFT) ed è responsabile dello stesso accumulo lento di errori di arrotondamento in tali FFT.<ref name="Tasche"/><ref name=JohnsonFrigo08>S. G. Johnson and M. Frigo, "[http://cnx.org/content/m16336/latest/ Implementing FFTs in practice], in ''[http://cnx.org/content/col10550/ Fast Fourier Transforms]'', edited by [[C. Sidney Burrus]] (2008).</ref>

La sommatoria ricorsiva a coppie è l'algoritmo di sommatoria predefinito nel [[NumPy]]<ref>[https://github.com/numpy/numpy/pull/3685 ENH: implement pairwise summation], github.com/numpy/numpy pull request #3685 (September 2013).</ref> e nel [[Julia (linguaggio di programmazione)|linguaggio di calcolo tecnico Julia]],<ref>[https://github.com/JuliaLang/julia/pull/4039 RFC: use pairwise summation for sum, cumsum, and cumprod], github.com/JuliaLang/julia pull request #4039 (August 2013).</ref> dove in entrambi i casi si trova che esso ha velocità confrontabile con la sommatoria semplice (grazie all'utilizzo di un ampio modello di base).

== L'algoritmo ==

In [[pseudocodice]], l'algoritmo di sommatoria ricorsiva a coppie for an [[array]] ''x'' di lunghezza ''n'' > 0 può essere scritto:

 ''s'' = '''pairwise'''(''x''[1&hellip;''n''])
       if ''n'' &le; ''N''                    ''modello base: sommatoria semplice per un array sufficientemente piccolo''
           ''s'' = ''x''[1]
           for ''i'' = 2 to ''n''
               ''s'' = ''s'' + ''x''[''i'']
       else                        ''[[Divide et impera (informatica)|divide et impera]]: somma ricorsivamente due metà dell'array''
           ''m'' = [[Parte intera|floor]](''n'' / 2)
           ''s'' = '''pairwise'''(''x''[1&hellip;''m'']) + '''pairwise'''(''x''[''m''+1&hellip;''n''])
       endif

Per alcuni ''N'' sufficientemente piccoli, questo algoritmo passa a una semplice sommatoria a loop come modello di base, il cui limite di errore è O(Nε).<ref>{{Cita libro|nome=Nicholas |cognome=Higham |titolo=Accuracy and Stability of Numerical Algorithms (2 ed)|editore=SIAM|anno=2002 |pp=81-82}}</ref> L'intera somma ha un errore nel caso peggiore che cresce asintoticamente come ''O''(ε&nbsp;log&nbsp;''n'') per grandi ''n'', per un dato numero di condizionamento (vedere sotto).

In un algoritmo di questo tipo (come in generale per un [[Divide et impera (informatica)|algoritmo di tipo ''divide et impera'']]<ref>Radu Rugina and Martin Rinard, "[https://people.csail.mit.edu/rinard/paper/lcpc00.pdf Recursion unrolling for divide and conquer programs]," in ''Languages and Compilers for Parallel Computing'', chapter 3, pp. 34–48.  ''Lecture Notes in Computer Science'' vol. 2017 (Berlin: Springer, 2001).</ref>), è preferibile usare un modello di base più ampio allo scopo di ammortizzare 29/5000
il sovraccarico della ricorsione. Se ''N''&nbsp;=&nbsp;1, allora c'è approssimativamente una chiamata ricorsiva ad una subroutine per ogni input, ma più in generale c'è una chiamata ricorsiva (approssimativamente) per ogni ''N''/2 input se la ricorsione si interrompe esattamente a&nbsp;''n''&nbsp;=&nbsp;''N''. Rendendo ''N'' sufficientemente grande, il sovraccarico della ricorsione può essere reso trascurabile (precisamente, questa tecnica di un ampio modello base per una sommatoria ricorsiva viene impiegata da implementazioni FFT ad alte prestazioni<ref name=JohnsonFrigo08/>).

Indipendentemente da ''N'', esattamente, in totale vengono eseguite ''n''&minus;1 addizioni, tante quante per la sommatoria semplice, quindi, se il sovraccarico della ricorsione è reso trascurabile, allora la sommatoria ricorsiva a coppie ha essenzialmente lo stesso costo computazionale della sommatoria semplice.

Una variante di questa idea è di dividere la somma in ''b'' blocchi ad ogni fase ricorsiva, summando ogni blocco ricorsivamente e poi sommando i risultati; tale variante è stata detta un algoritmo a "superblocco" dai suoi proponenti.<ref name=Castaldo08>Anthony M. Castaldo, R. Clint Whaley, and Anthony T. Chronopoulos, "Reducing floating-point error in dot product using the superblock family of algorithms," ''SIAM J. Sci. Comput.'', vol. 32, pp. 1156–1174 (2008).</ref> L'algoritmo della sommatoria ricorsiva a coppie visto sopra corrisponde al caso ''b''&nbsp;=&nbsp;2 per ogni fase tranne che per l'ultima in cui si ha&nbsp;''b''&nbsp;=&nbsp;''N''.

== Accuratezza ==

Supponiamo di sommare ''n'' valori ''x''<sub>''i''</sub>, per ''i''&nbsp;=&nbsp;1,&nbsp;...,&nbsp;''n''.  La somma esatta è:
:<math>S_n = \sum_{i=1}^n x_i</math>

(calcolata con precisione infinita).

Con la sommatoria ricorsiva a coppie per un modello base ''N''&nbsp;=&nbsp;1, invece, si ottiene <math>S_n + E_n</math>, dove l'errore <math>E_n</math> è limitato superiormente da:<ref name=Higham93/>

:<math>|E_n| \leq \frac{\varepsilon \log_2 n}{1 - \varepsilon \log_2 n} \sum_{i=1}^n |x_i| </math>

dove ε è la [[Epsilon di macchina|precisione di macchina]] dell'aritmetica impiegata (per esempio ε&nbsp;&asymp;&nbsp;10<sup>&minus;16</sup> per il [[formato a precisione doppia in virgola mobile|formato standard a precisione doppia in virgola mobile]]).  Generalmente, la quantità di interesse è l'[[errore relativo]] <math>|E_n|/|S_n|</math>, che perciò è limitato superiormente da:
:<math>\frac{|E_n|}{|S_n|} \leq \frac{\varepsilon \log_2 n}{1 - \varepsilon \log_2 n} \left(\frac{\sum_{i=1}^n |x_i|}{\left| \sum_{i=1}^n x_i \right|}\right). </math>

Nell'espressione per il limite dell'errore relativo, la frazione (&Sigma;|''x<sub>i</sub>''|/|&Sigma;''x<sub>i</sub>''|) è il [[Condizionamento (matematica)|numero di condizionamento]] del problema corrispondente alla sommatoria.  Essenzialmente, il numero di condizionamento rappresenta la sensibilità ''intrinsica'' del problema corrispondente alla sommatoria agli errori, indipendentemente da quanto calcolato.<ref>L. N. Trefethen and D. Bau, ''Numerical Linear Algebra'' (SIAM: Philadelphia, 1997).</ref> Il limite dell'errore relativo di ''ogni'' metodo di sommatoria ([[Stabilità numerica|stabile all'indietro]]) per un algoritmo fissato con una precisione fissatsa (quindi non quelli che usano l'[[aritmetica a precisione arbitraria]], né algoritmi i cui requisiti di memoria e tempo cambiano a seconda dei dati), è proporzionale a questo numero di condizionamento.<ref name=Higham93/> Un problema di sommatoria mal condizionato è uno in cui questo rapporto è grande e in questo caso anche la sommatoria ricorsiva a coppie può avere un grande errore relativo. Per esempio, se gli addendi ''x<sub>i</sub>'' sono numeri casuali non correlati con media zero, la somma è una [[passeggiata aleatoria]] e il numero di condizionamento crescerà proporzionale a <math>\sqrt{n}</math>. D'altra parte, per input casuali con media non nulla il numero di condizionamento tende a una costante finita per <math>n\to\infty</math>.  Se gli input sono tutti [[Segno (matematica)|non negativi]], allora il numero di condizionamento è 1.

Notiamo che il denominatore <math>1 - \varepsilon \log_2 n</math> in pratica è 1, poiché <math>\varepsilon \log_2 n</math> è molto minore di 1 fino a che ''n'' diviene dell'ordine di 2<sup>1/ε</sup>, che è approssimativamente 10<sup>10<sup>15</sup></sup> in precisione doppia.

In confronto, il limite dell'errore relativo per la sommatoria semplice (semplice addizione dei numeri in sequenza, arrotondando ad ogni passo) cresce come <math>O(\varepsilon n)</math> moltiplicato per il numero di condizionamento.<ref name=Higham93/> In practica, è molto più probabile che gli errori di arrotondamento abbiano un segno casuale, con media zero, in modo che essi diano luogo ad una passeggiata aleatoria; in questo caso, la sommatoria semplice ha un errore relativo, considerando lo [[scarto quadratico medio]], che cresce come <math>O(\varepsilon \sqrt{n})</math> e la sommatoria ricorsiva a coppie ha un errore che cresce come <math>O(\varepsilon \sqrt{\log n})</math> in media.<ref name="Tasche"/>

== Note ==
<references />

== Voci correlate ==
* [[Divide et impera (informatica)]]
* [[Algoritmo di sommatoria di Kahan]]
* [[Condizionamento (matematica)]]
* [[Epsilon di macchina]]
* [[Formato a precisione doppia in virgola mobile]] 
* [[Formato a precisione quadrupla in virgola mobile]]
* [[Aritmetica a precisione arbitraria]]

{{Portale|matematica}}

[[Categoria:Analisi numerica]]
[[Categoria:Matematica per l'informatica]]