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

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

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

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

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

Формальный анализ [ править ]

Формально катастрофическая отмена происходит потому, что вычитание плохо обусловлено на близлежащих входах: даже если приближения и имеют небольшие относительные ошибки и от истинных значений и , соответственно, относительная ошибка приблизительного отличия от истинного различия обратно пропорциональна истинному различию:${\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 {\biggl |}{\frac {x\delta _{x}-y\delta _{y}}{x-y}}{\biggr |}.}$$

который может быть сколь угодно большим, если истинные входы и близки.${\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 754 binary64 арифметике оценка альтернативного факторизации дает точный результат (без округления), но оценка наивного выражения дает ближайшее к нему число с плавающей запятой , из которых только половина цифр верна, а другая половина (подчеркнута) мусор.${\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 1.8626451{\underline {49230957}}\times 10^{-9}}$

Пример: сложный арксинус [ править ]

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

$${\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 binary64 арифметика может дать только пять из шестнадцати цифр правильными, а остаток (подчеркнутый) - мусор.${\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)}$${\displaystyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$${\displaystyle i(-z)=-iz=y}$

Пример: преобразование Radix [ править ]

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

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

Разница есть . Относительные погрешности from и of 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}}}$$

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

Ссылки [ править ]