Катастрофическая отмена

Потеря точности в численном анализе

В численном анализе катастрофическое сокращение ^{[1] [2]} представляет собой явление, при котором вычитание хороших приближений двух соседних чисел может привести к очень плохому приближению к разнице исходных чисел.

Например, если есть два стержня, один длинный, а другой длинный, и они измерены линейкой, которая хороша только до сантиметра, то приближения могут получиться и . Это могут быть хорошие приближения, в относительной погрешности , к истинным длинам: приближения имеют погрешность менее 2% от истинных длин, . ${\displaystyle L_{1}=253.51\,{\text{cm}}}$ ${\displaystyle L_{2}=252.49\,{\text{cm}}}$ ${\displaystyle {\tilde {L}}_{1}=254\,{\text{cm}}}$ ${\displaystyle {\tilde {L}}_{2}=252\,{\text{cm}}}$ ${\displaystyle |L_{1}-{\tilde {L}}_{1}|/|L_{1}|<2\%}$

Однако, если вычесть приблизительные длины, то разница составит , хотя истинная разница между длинами составляет . Разница приближений, , имеет погрешность почти в 100% от величины разницы истинных значений, . ${\displaystyle {\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}}$ ${\displaystyle L_{1}-L_{2}=253.51\,{\text{cm}}-252.49\,{\text{cm}}=1.02\,{\text{cm}}}$ ${\displaystyle 2\,{\text{cm}}}$ ${\displaystyle 1.02\,{\text{cm}}}$

Катастрофическое погашение не зависит от того, насколько велики входные данные — оно применимо как к большим, так и к малым входным данным. Оно зависит только от того, насколько велика разница , и от погрешности входных данных. Точно такая же ошибка возникнет при вычитании из как приближений к и , или при вычитании из как приближений к и . ${\displaystyle 52\,{\text{cm}}}$ ${\displaystyle 54\,{\text{cm}}}$ ${\displaystyle 52.49\,{\text{cm}}}$ ${\displaystyle 53.51\,{\text{cm}}}$ ${\displaystyle 2.00052\,{\text{km}}}$ ${\displaystyle 2.00054\,{\text{km}}}$ ${\displaystyle 2.0005249\,{\text{km}}}$ ${\displaystyle 2.0005351\,{\text{km}}}$

Катастрофическое сокращение может произойти, даже если разница вычисляется точно, как в примере выше — это не свойство какого-либо конкретного вида арифметики, например, арифметики с плавающей точкой ; скорее, это присуще вычитанию, когда входные данные сами являются приближениями. Действительно, в арифметике с плавающей точкой, когда входные данные достаточно близки, разница с плавающей точкой вычисляется точно, согласно лемме Стербенца — нет ошибки округления, вносимой операцией вычитания с плавающей точкой.

Формальный анализ

Формально катастрофическое сокращение происходит из-за того, что вычитание плохо обусловлено на близких входах: даже если приближения и имеют малые относительные погрешности и от истинных значений и , соответственно, относительная погрешность разности приближений от разности истинных значений обратно пропорциональна разности истинных значений: ${\displaystyle {\tilde {x}}=x(1+\delta _{x})}$ ${\displaystyle {\tilde {y}}=y(1+\delta _{y})}$ ${\displaystyle |\delta _{x}|=|x-{\tilde {x}}|/|x|}$ ${\displaystyle |\delta _{y}|=|y-{\tilde {y}}|/|y|}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle {\tilde {x}}-{\tilde {y}}}$ ${\displaystyle x-y}$

$${\displaystyle {\begin{aligned}{\tilde {x}}-{\tilde {y}}&=x(1+\delta _{x})-y(1+\delta _{y})=x-y+x\delta _{x}-y\delta _{y}\\&=x-y+(x-y){\frac {x\delta _{x}-y\delta _{y}}{x-y}}\\&=(x-y){\biggr (}1+{\frac {x\delta _{x}-y\delta _{y}}{x-y}}{\biggr )}.\end{aligned}}}$$

Таким образом, относительная погрешность точного отличия приближений от отличия истинных значений равна ${\displaystyle {\tilde {x}}-{\tilde {y}}}$ ${\displaystyle x-y}$

$${\displaystyle \left|{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right|.}$$

которые могут быть сколь угодно большими, если истинные значения и близки. ${\displaystyle x}$ ${\displaystyle y}$

В численных алгоритмах

Вычитание соседних чисел в арифметике с плавающей точкой не всегда приводит к катастрофическому сокращению или даже к любой ошибке — по лемме Стербенца , если числа достаточно близки, то разница с плавающей точкой точна. Но сокращение может усилить ошибки во входных данных, которые возникли из-за округления в другой арифметике с плавающей точкой.

Пример: Разность квадратов

При наличии чисел и наивная попытка вычислить математическую функцию с помощью арифметики с плавающей точкой подвержена катастрофическому сокращению, когда и близки по величине, поскольку вычитание может выявить ошибки округления при возведении в квадрат. Альтернативное разложение , оцененное с помощью арифметики с плавающей точкой , позволяет избежать катастрофического сокращения, поскольку оно позволяет избежать внесения ошибки округления, ведущей к вычитанию. ^[2] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle \operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x+y)(x-y)}$ ${\displaystyle \operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (x-y))}$

Например, если и , то истинное значение разности равно . В двоичной арифметике IEEE 75464 оценка альтернативного факторинга дает точный результат (без округления), но оценка наивного выражения дает число с плавающей точкой , в котором менее половины цифр являются правильными, а другие (подчеркнутые) цифры отражают пропущенные члены , потерянные из-за округления при вычислении промежуточных квадратов значений. ${\displaystyle x=1+2^{-29}\approx 1.0000000018626451}$ ${\displaystyle y=1+2^{-30}\approx 1.0000000009313226}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle 2^{-29}\cdot (1+2^{-30}+2^{-31})\approx 1.8626451518330422\times 10^{-9}}$ ${\displaystyle (x+y)(x-y)}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle 2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}}$ ${\displaystyle 2^{-59}+2^{-60}}$

Пример: комплексный арксинус

При вычислении комплексной функции арксинуса может возникнуть соблазн использовать логарифмическую формулу напрямую:

$${\displaystyle \arcsin(z)=i\log {\bigl (}{\sqrt {1-z^{2}}}-iz{\bigr )}.}$$

Однако предположим, что для . Тогда и ; назовем разницу между ними — очень маленькую разницу, почти нулевую. Если вычисляется в арифметике с плавающей точкой, давая ${\displaystyle z=iy}$ ${\displaystyle y\ll 0}$ ${\displaystyle {\sqrt {1-z^{2}}}\approx -y}$ ${\displaystyle iz=-y}$ ${\displaystyle \varepsilon }$ ${\displaystyle {\sqrt {1-z^{2}}}}$

$${\displaystyle \operatorname {fl} {\Bigl (}{\sqrt {\operatorname {fl} (1-\operatorname {fl} (z^{2}))}}{\Bigr )}={\sqrt {1-z^{2}}}(1+\delta )}$$

с любой ошибкой , где обозначает округление с плавающей точкой, затем вычисление разницы ${\displaystyle \delta \neq 0}$ ${\displaystyle \operatorname {fl} (\cdots )}$

$${\displaystyle {\sqrt {1-z^{2}}}(1+\delta )-iz}$$

из двух соседних чисел, оба очень близкие к , может усилить ошибку в одном входе в раз — очень большой раз, поскольку был близок к нулю. Например, если , истинное значение приблизительно равно , но использование наивной логарифмической формулы в двоичной арифметике IEEE 754 может дать , при этом только пять из шестнадцати цифр будут правильными, а все остальные (подчеркнутые) неверны. ${\displaystyle -y}$ ${\displaystyle \delta }$ ${\displaystyle 1/\varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle z=-1234567i}$ ${\displaystyle \arcsin(z)}$ ${\displaystyle -14.71937803983977i}$ ${\displaystyle -14.719{\underline {644263563968}}i}$

В случае для использование тождества позволяет избежать сокращения, поскольку но , поэтому вычитание фактически является сложением с тем же знаком, которое не сокращается. ${\displaystyle z=iy}$ ${\displaystyle y<0}$ ${\displaystyle \arcsin(z)=-\arcsin(-z)}$ ${\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$ ${\displaystyle i(-z)=-iz=y}$

Пример: преобразование системы счисления

Числовые константы в программах часто записываются в десятичной системе счисления, например, во фрагменте C для объявления и инициализации переменной IEEE 754 binary64 с именем . Однако не является числом с плавающей точкой binary64; ближайшее число, которое будет инициализировано в этом фрагменте, — . Хотя преобразование основания из десятичного числа с плавающей точкой в ​​двоичное число с плавающей точкой приводит лишь к небольшой относительной ошибке, катастрофическое сокращение может усилить ее до гораздо большей:double x = 1.000000000000001;x ${\displaystyle 1.000000000000001}$x ${\displaystyle 1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}}$

double x = 1.000000000000001 ; // округлено до 1 + 5*2^{-52} double y = 1.000000000000002 ; // округлено до 1 + 9*2^{-52} double z = y - x ; // разница составляет ровно 4*2^{-52}              

Разница составляет . Относительные погрешности от и от ниже , а вычитание с плавающей точкой вычисляется точно по лемме Стербенца. ${\displaystyle 1.000000000000002-1.000000000000001}$ ${\displaystyle 0.000000000000001=1.0\times 10^{-15}}$x ${\displaystyle 1.000000000000001}$y ${\displaystyle 1.000000000000002}$ ${\displaystyle 10^{-15}=0.0000000000001\%}$y - x

Но даже несмотря на то, что входные данные являются хорошими приближениями, и хотя вычитание вычисляется точно, разница между приближениями имеет относительную погрешность более чем в разнице исходных значений, записанных в десятичной системе счисления: катастрофическое сокращение усилило крошечную ошибку в преобразовании основания системы счисления до большой ошибки в выходных данных. ${\displaystyle {\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}}$ ${\displaystyle 11\%}$ ${\displaystyle 1.0\times 10^{-15}}$

Доброкачественная отмена

Отмена иногда полезна и желательна в числовых алгоритмах. Например, алгоритмы 2Sum и Fast2Sum оба полагаются на такую ​​отмену после ошибки округления, чтобы точно вычислить, какой была ошибка в операции сложения с плавающей точкой как само число с плавающей точкой.

Функция , если ее оценить наивно в точках , потеряет большинство цифр при округлении . Однако сама функция хорошо обусловлена ​​на входах вблизи . Переписывая ее как использует отмену в , чтобы избежать ошибки от прямой оценки. ^[2] Это работает, потому что отмена в числителе и отмена в знаменателе противодействуют друг другу; функция достаточно хорошо обусловлена ​​вблизи нуля, что дает хорошее приближение к , и, таким образом, дает хорошее приближение к . ${\displaystyle \log(1+x)}$ ${\displaystyle 0<x\lll 1}$ ${\displaystyle x}$ ${\displaystyle \operatorname {fl} (1+x)}$ ${\displaystyle \log(1+x)}$ ${\displaystyle 0}$ $${\displaystyle \log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}}$$ ${\displaystyle {\hat {x}}:=\operatorname {fl} (1+x)-1}$ ${\displaystyle \log(1+x)}$ ${\displaystyle \log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})}$ ${\displaystyle {\hat {x}}=\operatorname {fl} (1+x)-1}$ ${\displaystyle \mu (\xi )=\log(1+\xi )/\xi }$ ${\displaystyle \mu ({\hat {x}})}$ ${\displaystyle \mu (x)}$ ${\displaystyle x\cdot \mu ({\hat {x}})}$ ${\displaystyle x\cdot \mu (x)=\log(1+x)}$

Ссылки

1. Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018). Справочник по арифметике с плавающей запятой (2-е изд.). Gewerbestrasse 11, 6330 Шам, Швейцария: Биркхойзер. п. 102. дои : 10.1007/978-3-319-76526-6. ISBN 978-3-319-76525-9.{{cite book}}: CS1 maint: location (link)
2. Goldberg, David (март 1991 г.). «Что каждый специалист по информатике должен знать об арифметике с плавающей точкой». ACM Computing Surveys . 23 (1). Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники: 5–48. doi : 10.1145/103162.103163. ISSN  0360-0300. S2CID  222008826. Получено 17 сентября 2020 г.