Lors du calcul des moyennes arithmétiques, quelle est la méthode de sommation la plus précise?

Question

confiait la tâche de calculer la moyenne arithmétique des n IEEE 754 à double précision flottant points numéros x , x , ..., x_n-1 , est-il plus précis pour faire

(ksum _ix_i)/n

(à savoir la première fait un Kahan-somme de tous les x_i, puis en divisant par n) ou

ksum _i (x_i/n)

(c.-à-d. diviser en premier le x_i par n et ensuite Kahan-sommation)? Mes propres tests (avec des nombres aléatoires uniformément distribués dans [0, 1) et des nombres distribués normaux sur toute la plage de nombres à virgule flottante centrée sur 0 avec σ = 1) ont été non concluants, montrant que les deux sont très précis, mais mon choix de données de test aurait pu être particulièrement pauvre. Somme d'abord, puis diviser.

Answer 1

Si vous divisez d'abord puis somme dans le cas général, vous introduisez une erreur d'arrondi proportionnelle au plus grand summand de magnitude, qui bat le plus souvent le point de sommation de Kahan (en cas d'annulation catastrophique, ce que vous protégez, votre le résultat est l'erreur d'arrondi de la division).

La sommation d'abord présente un risque plus important de débordement excessif; pour gérer que correctement, vous devez redimensionner par une puissance exacte de deux que nécessaire pour éviter le débordement. Cependant, c'est assez rare, et jamais quelque chose dont vous avez besoin de vous inquiéter avec des données bien dimensionnées. Pour donner un exemple concret: considérez la moyenne des valeurs 4503599627370496, -4503599627370498 et 2 en double précision. Même en utilisant une sommation naïve, vous obtenez le résultat exact (0) si vous additionnez puis divisez. Si vous divisez et somme, la sommation est exacte (par le lemme de Sterbenz) et pourtant l'erreur est encore grande; le résultat calculé est -0.08333333333333337 (cela vient seulement de l'erreur d'arrondi dans 4503599627370496/3; -4503599627370498/3 est exact).