Потеря значимости и накопление ошибок

Урок про два главных способа испортить точность: катастрофическое вычитание близких чисел и накопление ошибки в длинных суммах.

Потеря значимости (catastrophic cancellation) — резкая потеря верных цифр при вычитании двух почти равных чисел: совпадающие старшие цифры взаимно уничтожаются, обнажая «шумящие» младшие.

Катастрофическое вычитание

Пусть два числа известны с 15 верными цифрами, но совпадают в первых 13. Их разность имеет всего 2 верные цифры — остальные 13 «съелись». Само по себе вычитание точное, но оно проявляет ранее незаметную погрешность входных данных, раздувая её относительный вес. Классический пример — формула корней квадратного уравнения при $b^2 \gg 4ac$: один из корней вычисляется как разность двух близких чисел.

import math

# x^2 - 200000 x + 1 = 0. Корни: огромный и крошечный.
a, b, c = 1.0, -200000.0, 1.0
D = math.sqrt(b * b - 4 * a * c)

# Наивная формула для МАЛОГО корня: (-b - D)/(2a) даёт большой,
# а (-b + D)/(2a) — малый, но через вычитание близких чисел!
x_малый_наивно = (-b - D) / (2 * a)   # тут вычитания нет, корень большой
x_большой = (-b + D) / (2 * a)         # тоже большой? проверим оба

# малый корень = 1/большой по теореме Виета (c/a = x1*x2)
print("большой корень:", x_большой)
малый_прямой = (-b - D) / (2 * a)
print("через (-b - D):", малый_прямой)
малый_устойчиво = c / (a * x_большой)   # формула Виета — без вычитания
print("через Виета:   ", малый_устойчиво)

Вывод:

большой корень: 199999.99999500002
через (-b - D): 4.999994416721165e-06
через Виета:    5.000000000125e-06

Прямая формула $(-b - D)/(2a)$ для малого корня даёт 4.99999...e-06 — верны лишь 6 цифр, дальше шум, потому что D и $|b|$ почти равны и при их вычитании теряются значащие разряды. Формула Виета ($x_{\text{малый}} = c/(a \cdot x_{\text{большой}})$) обходится без вычитания близких чисел и сохраняет полную точность. Лекарство от потери значимости общее: переписать выражение, заменив опасное вычитание умножением или делением.

Накопление ошибки в суммах

Второй враг — длинные суммы. Каждое сложение чуть округляет, и при миллионах слагаемых отклонение становится заметным. Особенно когда к большому накопленному значению добавляют крошечные — добавка частично теряется.

# Сложим 0.1 десять миллионов раз. Истина = 1000000.0
n = 10_000_000
наивно = 0.0
for _ in range(n):
    наивно += 0.1
print("наивная сумма:", repr(наивно))
print("ошибка:       ", наивно - n * 0.1)

# Суммирование Кэхэна: храним «потерянный хвост» и возвращаем его
s = 0.0
c = 0.0   # компенсация
for _ in range(n):
    y = 0.1 - c
    t = s + y
    c = (t - s) - y   # что потерялось при сложении
    s = t
print("сумма Кэхэна: ", repr(s))
print("ошибка:       ", s - n * 0.1)

Вывод:

наивная сумма: 999999.9998389754
ошибка:        -0.0001610246254131198
сумма Кэхэна:  1000000.0
ошибка:        0.0

Наивная сумма отклонилась на $1.6 \times 10^{-4}$ — для миллионов операций это уже видно невооружённым глазом. Алгоритм Кэхэна, отслеживая «потерянный хвост» каждого сложения, здесь и вовсе попал в ответ точно: ошибка 0.0. Стоит это лишь нескольких дополнительных арифметических действий на итерацию.

Как работает под капотом

При вычитании $a - b$, где $a \approx b$, абсолютная ошибка остаётся прежней (порядка $\varepsilon \cdot |a|$), но результат мал — поэтому относительная ошибка взрывается: $\text{ошибка}/\text{результат}$ становится огромной. При суммировании ошибка каждого шага $\sim \varepsilon \cdot |\text{текущая сумма}|$; складываясь, в худшем случае они дают $\sim n \cdot \varepsilon \cdot \max$. Кэхэн снижает накопление до $\sim \varepsilon$ (не зависит от $n$ в первом приближении), потому что аккуратно возвращает в сумму потерянные младшие биты.

Частые ошибки

• Не замечать вычитание близких чисел. Оно прячется в формулах: $1 - \cos(x)$ при малых $x$, $\sqrt{x+1} - \sqrt{x}$ при больших $x$ — переписывайте их алгебраически.
• Суммировать от больших к малым. Лучше сортировать по возрастанию модуля или применять Кэхэна — иначе мелкие слагаемые тонут.
• Считать дисперсию «школьной» формулой $E[x^2] - (E[x])^2$ — это разность близких чисел; численно устойчивее однопроходный алгоритм Уэлфорда.

Итоги

• Потеря значимости: вычитание близких чисел уничтожает старшие цифры и раздувает относительную ошибку.
• Лекарство — алгебраически переписать формулу, убрав опасное вычитание (Виета, домножение на сопряжённое).
• Длинные суммы накапливают ошибку; суммирование Кэхэна резко её уменьшает.
• Эти эффекты — не «грязь», а предсказуемое следствие конечной точности; их обходят выбором формулы.