Алгоритм Кэхэна
Материал из Википедии — свободной encyclopedia
В вычислительной математике алгоритм Кэхэна (также известный как компенсационное суммирование) — это алгоритм вычисления суммы последовательности чисел c плавающей запятой, который значительно уменьшает вычислительную погрешность[англ.] по сравнению с наивным подходом. Уменьшение погрешности достигается введением дополнительной переменной для хранения нарастающей суммы погрешностей.
В частности, простое суммирование чисел в худшем случае имеет погрешность, которая растёт пропорционально
и при суммировании случайных чисел имеет среднее квадратичное отклонение, пропорциональное
(ошибки округления вызывают случайное блуждание)[1]. При компенсационном суммировании погрешность даже в худшем случае не зависит от
, так что большое число слагаемых могут быть просуммированы с погрешностью, зависящей только от точности числа с плавающей запятой[1].
Авторство алгоритма приписывают Уильяму Кэхэну[2].