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

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

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

Например, если есть две шпильки, одна длинная, а другая длинная, и они измерены линейкой, допускающей точность только до сантиметра, то приближения могут получиться равными и . Это могут быть хорошие аппроксимации с относительной ошибкой истинных длин: аппроксимации погрешны менее чем на 2% от истинных длин . ${\displaystyle L_{1}=253.5\,{\text{cm}}}$ ${\displaystyle L_{2}=252.5\,{\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.5\,{\text{cm}}-252.5\,{\text{cm}}=1\,{\text{cm}}}$ ${\displaystyle 2\,{\text{cm}}}$ ${\displaystyle 1\,{\text{cm}}}$

На катастрофическое аннулирование не влияет размер входных данных — оно одинаково применимо как к большим, так и к малым входным данным. Это зависит только от того, насколько велика разница и от погрешности входных данных. Точно такая же ошибка возникнет при вычитании из as приближений к и или при вычитании из as приближений к и . ${\displaystyle 52\,{\text{cm}}}$ ${\displaystyle 54\,{\text{cm}}}$ ${\displaystyle 52.5\,{\text{cm}}}$ ${\displaystyle 53.5\,{\text{cm}}}$ ${\displaystyle 2.00052\,{\text{km}}}$ ${\displaystyle 2.00054\,{\text{km}}}$ ${\displaystyle 2.000525\,{\text{km}}}$ ${\displaystyle 2.000535\,{\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))}$

Например, если и , то истинное значение разницы равно . В бинарной64-арифметике IEEE 754 оценка альтернативного факторинга дает точный результат (без округления), но оценка простого выражения дает число с плавающей запятой , из которого менее половины цифр являются правильными, а остальные (подчеркнутые) цифры отражают недостающие члены , потерянные из-за округления при вычислении промежуточных значений квадратов. ${\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 )}.}$$

Однако предположим, что для . Тогда и ; назовите разницу между ними — очень маленькая разница, почти нулевая. If оценивается в арифметических операциях с плавающей запятой, давая ${\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}$$

двух соседних чисел, оба очень близких к , может увеличить ошибку в одном входе в очень большой раз, поскольку она была почти равна нулю. Например, если , истинное значение приблизительно равно , но использование простой логарифмической формулы в двоичной64-арифметике 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}$

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

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

Разница в том . Относительные ошибки from и from ниже , а вычитание с плавающей запятой вычисляется точно по лемме Штербенца. ${\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 полагаются на такую ​​отмену после ошибки округления, чтобы точно вычислить ошибку в операции сложения с плавающей запятой как само число с плавающей запятой.

Функция , если она вычисляется наивно в точках , потеряет большую часть цифр при округлении . Однако сама функция хорошо обусловлена ​​на входах вблизи . Переписав это как ${\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}}}$$

^[2] ${\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. Голдберг, Дэвид (март 1991 г.). «Что каждый ученый-компьютерщик должен знать об арифметике с плавающей запятой». Обзоры вычислительной техники ACM . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. 23 (1): 5–48. дои : 10.1145/103162.103163. ISSN  0360-0300. S2CID  222008826 . Проверено 17 сентября 2020 г.