Sommatoria ricorsiva a coppie

In analisi numerica, la sommatoria ricorsiva a coppie (pairwise summation in inglese), chiamata anche sommatoria a cascata (cascade summation), è una tecnica per sommare una sequenza di numeri in virgola mobile di precisione finita che, sostanzialmente, riduce l'errore di arrotondamento accumulato in confronto a quello accumulato dalla semplice sommatoria in sequenza. 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_n funziona dividendo ricorsivamente la sequenza in due metà, sommando ogni metà e addizionando le due somme: un algoritmo di tipo divide et impera. I suoi errori di arrotondamento nel peggiore dei casi crescono asintoticamente al massimo come O(ε log n), dove ε è la precisione di macchina (assumendo un numero di condizionamento fissato, come discusso sotto). In compenso, la semplice tecnica di accumulare la somma in sequenza (addizionando ogni x_i uno alla volta per i = 1, ..., n) ha errori di arrotondamento che crescono nel peggiore dei casi come O(εn). La 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. 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 $O(\varepsilon {\sqrt {\log n}})$.

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.

La sommatoria ricorsiva a coppie è l'algoritmo di sommatoria predefinito nel NumPy e nel linguaggio di calcolo tecnico Julia, 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…n])
      if n ≤ 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: somma ricorsivamente due metà dell'array
          m = floor(n / 2)
          s = pairwise(x[1…m]) + pairwise(x[m+1…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ε). L'intera somma ha un errore nel caso peggiore che cresce asintoticamente come O(ε log n) per grandi n, per un dato numero di condizionamento (vedere sotto).

In un algoritmo di questo tipo (come in generale per un algoritmo di tipo divide et impera), è preferibile usare un modello di base più ampio allo scopo di ammortizzare 29/5000 il sovraccarico della ricorsione. Se N = 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 n = 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).

Indipendentemente da N, esattamente, in totale vengono eseguite n−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. L'algoritmo della sommatoria ricorsiva a coppie visto sopra corrisponde al caso b = 2 per ogni fase tranne che per l'ultima in cui si ha b = N.

Accuratezza

Supponiamo di sommare n valori x_i, per i = 1, ..., n. La somma esatta è:

$S_{n}=\sum _{i=1}^{n}x_{i}$

(calcolata con precisione infinita).

Con la sommatoria ricorsiva a coppie per un modello base N = 1, invece, si ottiene $S_{n}+E_{n}$, dove l'errore $E_{n}$ è limitato superiormente da:

$|E_{n}|\leq {\frac {\varepsilon \log _{2}n}{1-\varepsilon \log _{2}n}}\sum _{i=1}^{n}|x_{i}|$

dove ε è la precisione di macchina dell'aritmetica impiegata (per esempio ε ≈ 10⁻¹⁶ per il formato standard a precisione doppia in virgola mobile). Generalmente, la quantità di interesse è l'errore relativo $|E_{n}|/|S_{n}|$, che perciò è limitato superiormente da:

${\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).$

Nell'espressione per il limite dell'errore relativo, la frazione (Σ|x_i|/|Σx_i|) è il 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. Il limite dell'errore relativo di ogni metodo di sommatoria (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. 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_i sono numeri casuali non correlati con media zero, la somma è una passeggiata aleatoria e il numero di condizionamento crescerà proporzionale a ${\sqrt {n}}$. D'altra parte, per input casuali con media non nulla il numero di condizionamento tende a una costante finita per $n\to \infty$. Se gli input sono tutti non negativi, allora il numero di condizionamento è 1.

Notiamo che il denominatore $1-\varepsilon \log _{2}n$ in pratica è 1, poiché $\varepsilon \log _{2}n$ è molto minore di 1 fino a che n diviene dell'ordine di 2^1/ε, che è approssimativamente 10¹⁰¹⁵ 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 $O(\varepsilon n)$ moltiplicato per il numero di condizionamento. 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 $O(\varepsilon {\sqrt {n}})$ e la sommatoria ricorsiva a coppie ha un errore che cresce come $O(\varepsilon {\sqrt {\log n}})$ in media.

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