Metraipolis › archive › dc_3a0216fed803
Sommatoria ricorsiva a coppie — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Sommatoria_ricorsiva_a_coppie
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-09T13:40:26.150Z
- SHA-256 of the archived text
470e7cc1bda03e7f4c122dc4164870c39affd74c6d998582ca1a3f3be3f9403d- Stable URL of this page
https://metraipolis.com/documento/dc_3a0216fed803
How to cite
Sommatoria ricorsiva a coppie — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Sommatoria_ricorsiva_a_coppie (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3a0216fed803 (Metraipolis archive dc_3a0216fed803, sha256 470e7cc1bda03e7f4c122dc4164870c39affd74c6d998582ca1a3f3be3f9403d)
BibTeX
@misc{dc3a0216fed803,
title = {Sommatoria ricorsiva a coppie — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Sommatoria_ricorsiva_a_coppie},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3a0216fed803; sha256 470e7cc1bda03e7f4c122dc4164870c39affd74c6d998582ca1a3f3be3f9403d},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Sommatoria_ricorsiva_a_coppie. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 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). 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 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(εlogn). 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). Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico). Fonte: Wikipedia in italiano, voce «Sommatoria ricorsiva a coppie» — https://it.wikipedia.org/wiki/Sommatoria_ricorsiva_a_coppie Wikidata Q17104961: «algorithmic technique» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17104961 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Sommatoria_ricorsiva_a_coppie?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 144058873, consultata il 2026-11-09T13:35:09.122Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 6baee19635e0d80690eb6ca8990228187d07b8ba28380a6d48913b2f632055c2