Кратко по сути и с примером.
1) Почему простой цикл даёт ошибки
- Модель округления: при сложении в плавающей точке
$$fl(a+b)=(a+b)(1+\delta ),|\delta |\le ϵ,$$ где $ϵ$ — машинный эпсилон (для IEEE‑754 double $ϵ\approx 2^{-53}\approx 1.11\cdot 10^{-16}$).
- Накопление ошибок: при наивном суммировании слева направо погрешность растёт примерно как $O(nϵ)$. Формально для вычисленной суммы ${\hat{s}}_n$ и истинной $s={\sum }_{i=1}^n{x}_i$ справедлива оценка
$$|{\hat{s}}_n-s|\le {\gamma }_{n-1}\sum _{i=1}^n|x_i|,{\gamma }_m=\frac{mϵ}{1-mϵ}.$$
Простой иллюстративный пример (double): числа $[1,10^{-16},-1]$. Истинная сумма $1+10^{-16}-1=10^{-16}$. Наивно слева направо:
- $1+10^{-16}$ округляется к $1$ (потеря малого слагаемого), затем $1-1=0$. Результат $0$ — потеря информации.
Kahan‑компенсация (см. ниже) восстановит значение близкое к $10^{-16}$.
2) Алгоритм Кахана (Kahan compensated summation)
Псевдокод (s — накопитель, c — компенсатор, инициализировать $s=0,c=0$):
for each $x$ do
$y=x-c$
$t=s+y$
$c=(t-s)-y$
$s=t$ end
Математически:
$$y=x_i-c,t=s+y,c=(t-s)-y,s=t.$$
Пояснение: $c$ аккумулирует потерянные при предыдущих сложениях мелкие биты; при следующем шаге они вычитаются из входа и корректируют сумму.
Эффект и стоимость:
- Значительно уменьшает накопление погрешности; в большинстве практических случаев даёт почти машинную точность результата.
- Стоимость: $O(n)$ сложений, но на каждый вход ~5 операций вместо 1 (доступ к памяти тот же). Практический замедляющий множитель ≈ $1.5-3\times$ по сравнению с наивным суммированием; дополнительная память $O(1)$.
3) Другие техники и их оценка
- Neumaier (улучшение для случаев, когда |s| < |x|): почти как Kahan, но чуть проще обработка знаков. Стоимость и эффект аналогичны Kahan, лучше в некоторых ситуациях с большими слагаемыми.
- Pairwise (divide‑and‑conquer) / Tree summation: разбить массив пополам, суммировать рекурсивно и складывать результаты.
- Ошибка ограничена через глубину дерева: вместо ${\gamma }_{n-1}$ появляется ${\gamma }_{\lceil {\log }_{2}n\rceil }$. То есть погрешность растёт как $O(\log n\cdot ϵ)$ вместо $O(nϵ)$.
- Стоимость: общее число операций $O(n)$ (приблизительно такое же), но накладные расходы на рекурсию/перестановку данных; хорошо распараллеливается (глубина $O(\log n)$). Память: при рекурсивной реализации потребуется стек/временные буферы $O(\log n)$ или $O(n)$ для итеративной перестановки.
- Сортировка по возрастанию абсолютных значений перед суммированием:
- Уменьшает явления отмены; хорошая практика при большом разбросе модулей.
- Стоимость: дополнительно $O(n\log n)$ сравнений и перестановок; итоговая погрешность близка к минимально возможной для фиксированной точности.
- Блочное суммирование + компенсация: разбить на блоки, в каждом блоке применять Kahan или pairwise, затем суммировать блоковые суммы pairwise. Хороший компромисс точности/параллелизма.
- Высокая точность (long double, quad, arbitrary precision):
- Простое и надёжное решение: вычислять в большей точности.
- Стоимость: аппаратный long double ~1.5–4×, программный quad или MPFR — десятки/сотни раз медленнее. Память и энергорасходы растут.
- Compensated expansions / double-double / Shewchuk: хранить сумму как расширение (несколько чисел), использовать точные преобразования TwoSum, FastTwoSum.
- Позволяет получить контролируемую (или практически точную) сумму, вплоть до произвольной точности, при возрастании числа компонент расширения.
- Стоимость линейно зависит от длины расширения; double‑double даёт ≈2× точности при ~3–6× затратах; более длинные расширения — пропорционально дороже.
4) Практические рекомендации
- Для большинства задач используйте Kahan (или Neumaier) — почти всегда существенное улучшение при малой цене.
- Если данные имеют сильно различающиеся порядки и точность критична — используйте pairwise summation (особенно в параллельной среде) или сортировку по модулю перед суммированием.
- Для гарантированной точности используйте более высокую точность или компенсированные расширения (double‑double / MPFR) — при этом будьте готовы к значительному замедлению.
- Для больших массивов в HPC: комбинация pairwise (для параллелизма) + локальный Kahan в блоках — хороший компромисс.
Краткая сравнительная сводка (точность / стоимость):
- Наивное: скорость $O(n)$, память $O(1)$, ошибка $O(nϵ)$.
- Kahan/Neumaier: скорость $O(n)$ (с фактором ≈1.5–3), память $O(1)$, ошибка ≈$O(ϵ)$ в большинстве случаев.
- Pairwise: скорость $O(n)$, лучше параллелизуется, ошибка $O(\log n\cdot ϵ)$.
- Сортировка по модулю: точность очень улучшает, стоимость $O(n\log n)$.
- Высокая точность / расширения: стоимость ×(2…100+), точность существенно выше (до произвольной).
Если нужно, могу привести короткую реализацию Kahan и показать тот же пример численно (пошагово).