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

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

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

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

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

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

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

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

${\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

double x = 1.000000000000001;  // rounded to 1 + 5*2^{-52}
double y = 1.000000000000002;  // rounded to 1 + 9*2^{-52}
double z = y - x;              // difference is exactly 4*2^{-52}

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

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

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

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

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

Ссылки

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

[handbook-1] Мюллер, Жан-Мишель; Бруни, Николас; из Динешена, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018). Справочник по арифметике с плавающей запятой (2-е изд.). Gewerbestrasse 11, 6330 Шам, Швейцария: Биркхойзер. п. 102. дои : 10.1007/978-3-319-76526-6 . ISBN 978-3-319-76525-9 . {{cite book}}: CS1 maint: местоположение ( ссылка )

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

[1]

[2]