Sommatoria ricorsiva a coppie

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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.[1] 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 xn 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).[1] In compenso, la semplice tecnica di accumulare la somma in sequenza (addizionando ogni xi uno alla volta per i = 1, ..., n) ha errori di arrotondamento che crescono nel peggiore dei casi come On).[1] 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.[1] 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 .[2]

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.[2][3]

La sommatoria ricorsiva a coppie è l'algoritmo di sommatoria predefinito nel NumPy[4] e nel linguaggio di calcolo tecnico Julia,[5] 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[modifica | modifica wikitesto]

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 nN                    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ε).[6] 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[7]), è 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[3]).

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.[8] 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[modifica | modifica wikitesto]

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

(calcolata con precisione infinita).

Con la sommatoria ricorsiva a coppie per un modello base N = 1, invece, si ottiene , dove l'errore è limitato superiormente da:[1]

dove ε è la precisione di macchina dell'aritmetica impiegata (per esempio ε ≈ 10−16 per il formato standard a precisione doppia in virgola mobile). Generalmente, la quantità di interesse è l'errore relativo , che perciò è limitato superiormente da:

Nell'espressione per il limite dell'errore relativo, la frazione (Σ|xi|/|Σxi|) è 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.[9] 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.[1] 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 xi sono numeri casuali non correlati con media zero, la somma è una passeggiata aleatoria e il numero di condizionamento crescerà proporzionale a . D'altra parte, per input casuali con media non nulla il numero di condizionamento tende a una costante finita per . Se gli input sono tutti non negativi, allora il numero di condizionamento è 1.

Notiamo che il denominatore in pratica è 1, poiché è molto minore di 1 fino a che n diviene dell'ordine di 21/ε, che è approssimativamente 101015 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 moltiplicato per il numero di condizionamento.[1] 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 e la sommatoria ricorsiva a coppie ha un errore che cresce come in media.[2]

Note[modifica | modifica wikitesto]

  1. ^ a b c d e f g Nicholas J. Higham, The accuracy of floating point summation, in SIAM Journal on Scientific Computing, vol. 14, n. 4, 1993, pp. 783–799, DOI:10.1137/0914050.
  2. ^ a b c Manfred Tasche and Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000).
  3. ^ a b S. G. Johnson and M. Frigo, "Implementing FFTs in practice, in Fast Fourier Transforms, edited by C. Sidney Burrus (2008).
  4. ^ ENH: implement pairwise summation, github.com/numpy/numpy pull request #3685 (September 2013).
  5. ^ RFC: use pairwise summation for sum, cumsum, and cumprod, github.com/JuliaLang/julia pull request #4039 (August 2013).
  6. ^ Nicholas Higham, Accuracy and Stability of Numerical Algorithms (2 ed), SIAM, 2002, pp. 81–82.
  7. ^ Radu Rugina and Martin Rinard, "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).
  8. ^ 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).
  9. ^ L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM: Philadelphia, 1997).

Voci correlate[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica