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

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

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

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

Пусть два числа известны с 15 верными цифрами, но совпадают в первых 13. Их разность имеет всего 2 верные цифры — остальные 13 «съелись». Само по себе вычитание точное, но оно проявляет ранее незаметную погрешность входных данных, раздувая её относительный вес. Классический пример — формула корней квадратного уравнения при b² ≫ 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_малый = c/(a·x_большой)) обходится без вычитания близких чисел и сохраняет полную точность. Лекарство от потери значимости общее: переписать выражение, заменив опасное вычитание умножением или делением.

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

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

# Сложим 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.6e-4 — для миллионов операций это уже видно невооружённым глазом. Алгоритм Кэхэна, отслеживая «потерянный хвост» каждого сложения, здесь и вовсе попал в ответ точно: ошибка 0.0. Стоит это лишь нескольких дополнительных арифметических действий на итерацию.

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

При вычитании a − b, где a ≈ b, абсолютная ошибка остаётся прежней (порядка eps·|a|), но результат мал — поэтому относительная ошибка взрывается: ошибка/результат становится огромной. При суммировании ошибка каждого шага ~ eps · |текущая сумма|; складываясь, в худшем случае они дают ~ n · eps · max. Кэхэн снижает накопление до ~ eps (не зависит от n в первом приближении), потому что аккуратно возвращает в сумму потерянные младшие биты.

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

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

Итоги

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