4.1.2.4 : Somme

Un autre algorithme répandu dans la communauté est l'intégrateur de Monte-Carlo : essentiellement c'est une boucle qui échantillonne un espace de configuration, puis accumule une certaine contribution fonction du point échantillonné. On procède donc à l'addition de valeurs fluctuantes\footnoteS'il n'y avait pas de variance de cette contribution, un seul échantillonnage suffirait... dans un accumulateur qui va croissant. Plus on accumule et plus la précision de la contribution est gommée.

Idéalement, il faudrait trier les contributions de la plus petite à la plus grande\footnotepour des contributions de même signe pour être sûr de perdre le moins de précision possible. Une autre solution consiste à procéder à l'accumulation dans une arithmétique étendue, ou encore exploiter l'algorithme de sommation de W. Kahan [204]Pracniques: Further Remarks on Reducing Truncation Errors, 1965, Kahan, William ou d'autres sommes compensées [205]A comparison of methods for accurate summation, 2004, Mcnamee, John[250]On Floating-Point Summation, 1995, Espelid, T. O.[251]Numerical stability in mathematical analysis., 1968, Babuška, Ivo[253]The Accuracy of Floating Point Summation, 1993, Higham, Nicholas J.[248]Accurate Sum and Dot Product, 2005, Ogita, Takeshi. and Rump, Siegfried M. and Oishi, Shin'ichi.[249]Accurate Floating-Point Summation Part II: Sign, K-Fold Faithful and Rounding to Nearest, 2009, Rump, Siegfried M. and Ogita, Takeshi. and Oishi, Shin'ichi..

Précisons cet aspect incontournable des sommes qu'est l'accumulation d'erreur de troncation. Comme cette erreur va statistiquement se distribuer uniformément autant vers le haut que vers le bas, on peut l'assimiler à une marche de l'ivrogne, et dans l'hypothèse de termes de grandeur comparable, s'attendre pour la somme de N termes à une incertitude absolue résultante sur le total de l'ordre de O(N) . Ceci ne semble pas alarmant vu que l'incertitude relative associée sera en O(1/N) . Cette approche est toutefois naïve vu que l'erreur absolue de troncation d'une somme est comme l'erreur relative rapportée au plus grand des termes i.e. l'accumulateur. Ainsi l'erreur relative varie comme O(ϵN) . Par suite, l'addition de 4 millions de contributions dans un accumulateur en demie précision cause une incertitude relative de 100% sur le résultat et réduit la précision d'un accumulateur simple précision à quatre chiffres significatifs dans le meilleur des mondes (si chaque contribution est bien calculée à la précision de la machine et correctement arrondie). Le moindre Monte-Carlo est facilement à même de produire un tel échantillonnage.

On peut d'ailleurs combiner ces pertes de précision relativement douces (et d'autant plus traîtresses) avec des compensations calamiteuses. C'est par exemple le cas des séries relevant du théorème spécial des séries alternées : une somme de termes de signes alternés, de limite nulle à l'infini et de valeurs absolues décroissantes. La convergence de ces séries est mathématiquement garantie, et l'incertitude sur la somme partielle est majorée par la valeur absolue du premier terme négligé. Chaque paire de termes successifs est ainsi concernée par une compensation potentiellement calamiteuse. Si on peut en venir à bout dans le cas où une expression analytique des termes existe, il n'y a pas de solution générale pour les expressions purement numériques.