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

Было высказано предположение , что эта статья будет слита в катастрофические отмены . ( Обсудить ) Предлагается с марта 2021 года.

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален Найти источники:  «Потеря значимости»  -  новости  · газеты  · книги  · ученый  · JSTOR ( июль 2012 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) Эта статья может сбивать с толку или непонятна читателям . В частности, существуют различные варианты использования точности и точности (они не одинаковы) и значения с неясной взаимосвязью. Пожалуйста, разъясните значение явным, с конкретным примером, относящимся ко всем трем, и как получить их из цифр числа (считается ли цифра перед десятичной точкой и т. Д.). Помогите, пожалуйста, прояснить статью . На странице обсуждения может быть обсуждение этого вопроса . ( Июль 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Пример LOS в случае вычисления двух форм одной и той же функции

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

Демонстрация проблемы [ править ]

Вычитание [ править ]

Эффект можно продемонстрировать с помощью десятичных чисел. В следующем примере демонстрируется катастрофическая отмена для десятичного типа данных с плавающей запятой с 10 значащими цифрами:

Рассмотрим десятичное число

х = 0,1234567891234567890

Представление этого числа с плавающей запятой на машине, которая хранит 10 цифр с плавающей запятой, будет

у = 0,1234567891

что довольно близко при измерении ошибки в процентах от значения. Если измерять по порядку точности, он сильно отличается. Значение "x" с точностью до10 × 10 ⁻¹⁹ , а значение y имеет точность только до10 × 10 ⁻¹⁰ .

Теперь произведем расчет

х - у = 0,1234567891234567890 - 0,1234567890000000000

Ответ с точностью до 20 значащих цифр:

0,0000000001234567890

Однако на 10-значном компьютере с плавающей запятой вычисление дает

0,1234567891 - 0,1234567890 = 0,0000000001

В обоих случаях результат имеет тот же порядок величины, что и входные данные (-20 и -10 соответственно). Во втором случае ответ, кажется, состоит из одной значащей цифры, что приведет к потере значимости. Однако в компьютерной арифметике с плавающей запятой все операции можно рассматривать как выполняемые над антилогарифмами , для которых правила для значащих цифр указывают, что количество значащих цифр остается таким же, как наименьшее количество значащих цифр в мантиссах . Обозначить это и представить ответ на 10 значащих цифр можно следующим образом:

 1.000 000 000 × 10 −10

Потеря значащих битов [ править ]

Пусть x и y - положительные нормализованные числа с плавающей запятой.

В вычитания х - у , г значимые биты теряются , где

${\ displaystyle q \ leq r \ leq p,}$

${\ displaystyle 2 ^ {- p} \ leq 1 - {\ frac {y} {x}} \ leq 2 ^ {- q}}$

для некоторых натуральных чисел p и q .

Обходные пути [ править ]

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

Одна из наиболее важных частей численного анализа - избежать или минимизировать потерю значимости в расчетах. Если основная проблема поставлена ​​правильно, должен существовать стабильный алгоритм ее решения.

Иногда умные уловки алгебры могут преобразовать выражение в форму, позволяющую обойти проблему. Один из таких приемов - использовать известное уравнение

${\ Displaystyle \ влево (ху \ вправо) \ влево (х + у \ вправо) = х ^ {2} -y ^ {2}}$

Итак, с выражением умножьте числитель и знаменатель, дав${\ displaystyle xy}$${\ displaystyle x + y}$

${\ displaystyle {\ frac {x ^ {2} -y ^ {2}} {x + y}}}$

Теперь можно сократить выражение, чтобы исключить вычитание? Иногда может.${\ displaystyle x ^ {2} -y ^ {2}}$

Например, выражение может потерять значащие биты, если оно намного меньше 1. Поэтому перепишите выражение как${\ displaystyle 1 - {\ sqrt {1- \ delta}}}$${\ displaystyle | \ delta |}$

${\ displaystyle {\ frac {1- \ left (1- \ delta \ right)} {1 + {\ sqrt {1- \ delta}}}}}}$ или же ${\ displaystyle {\ frac {\ delta} {1 + {\ sqrt {1- \ delta}}}}}$

Неустойчивость квадратного уравнения [ править ]

Например, рассмотрим квадратное уравнение

${\ displaystyle ax ^ {2} + bx + c = 0,}$

с двумя точными решениями:

${\ displaystyle x = {\ frac {-b \ pm {\ sqrt {b ^ {2} -4ac}}} {2a}}.}$

Эта формула не всегда может дать точный результат. Например, когда очень мало, потеря значимости может произойти в любом из вычислений корня, в зависимости от знака .${\ displaystyle c}$${\ displaystyle b}$

Случай , , будет служить для иллюстрации проблемы:${\ displaystyle a = 1}$${\ displaystyle b = 200}$${\ displaystyle c = -0,000015}$

${\ displaystyle x ^ {2} + 200x-0,000015 = 0.}$

У нас есть

${\displaystyle {\sqrt {b^{2}-4ac}}={\sqrt {200^{2}+4\times 1\times 0.000015}}=200.00000015\dotso }$

В реальной арифметике корни

${\displaystyle (-200-200.00000015)/2=-200.000000075,}$

${\displaystyle (-200+200.00000015)/2=0.000000075.}$

В 10-значной арифметике с плавающей запятой:

${\displaystyle (-200-200.0000001)/2=-200.00000005,}$

${\displaystyle (-200+200.0000001)/2=0.00000005.}$

Обратите внимание, что решение большей величины имеет точность до десяти цифр, но первая ненулевая цифра решения меньшей величины неверна.

Из-за вычитания, которое происходит в квадратном уравнении, он не является стабильным алгоритмом для вычисления двух корней.

Лучший алгоритм [ править ]

Тщательная реализация на компьютере с плавающей запятой сочетает в себе несколько стратегий для получения надежного результата. Предполагая, что дискриминант b ² - 4 ac положителен, а b отличен от нуля, вычисление будет следующим: ^[1]

${\displaystyle {\begin{aligned}x_{1}&={\frac {-b-\operatorname {sgn}(b)\,{\sqrt {b^{2}-4ac}}}{2a}},\\x_{2}&={\frac {2c}{-b-\operatorname {sgn}(b)\,{\sqrt {b^{2}-4ac}}}}={\frac {c}{ax_{1}}}.\end{aligned}}}$

Здесь sgn обозначает знаковую функцию , где 1, если положительно, и -1, если отрицательно. Это позволяет избежать проблем с удалением между квадратным корнем из дискриминанта, гарантируя, что добавляются только числа с одинаковым знаком.${\displaystyle \operatorname {sgn}(b)}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$

Чтобы проиллюстрировать нестабильность стандартной квадратной формулы по сравнению с этой формулой, рассмотрим квадратное уравнение с корнями и . Для 16 значащих цифр, что примерно соответствует точности двойной точности на компьютере, моническое квадратное уравнение с этими корнями может быть записано как${\displaystyle 1.786737589984535}$${\displaystyle 1.149782767465722\times 10^{-8}}$

${\displaystyle x^{2}-1.786737601482363x+2.054360090947453\times 10^{-8}=0.}$

Используя стандартную квадратичную формулу и сохраняя 16 значащих цифр на каждом шаге, стандартная квадратная формула дает

${\displaystyle {\sqrt {\Delta }}=1.786737578486707,}$

${\displaystyle x_{1}=(1.786737601482363+1.786737578486707)/2=1.786737589984535,}$

${\displaystyle x_{2}=(1.786737601482363-1.786737578486707)/2=0.000000011497828.}$

Обратите внимание на то, как отмена приводит к вычислению с точностью до 8 значащих цифр.${\displaystyle x_{2}}$

Однако представленная здесь вариантная формула дает следующее:

${\displaystyle x_{1}=(1.786737601482363+1.786737578486707)/2=1.786737589984535,}$

${\displaystyle x_{2}=2.054360090947453\times 10^{-8}/1.786737589984535=1.149782767465722\times 10^{-8}.}$

Обратите внимание на сохранение всех значащих цифр для .${\displaystyle x_{2}}$

Обратите внимание, что хотя приведенная выше формулировка позволяет избежать катастрофической отмены между и , остается форма отмены между членами и дискриминанта, которая все еще может привести к потере до половины правильных значащих цифр. ^{[2] [3]} Дискриминант должен быть вычислен в арифметике с удвоенной точностью результата, чтобы избежать этого (например, четверная точность, если конечный результат должен быть точным до полной двойной точности). ^[4] Это может быть в форме объединенной операции умножения-сложения . ^[2]${\displaystyle b}$${\displaystyle {\sqrt {b^{2}-4ac}}}$${\displaystyle b^{2}}$${\displaystyle -4ac}$${\displaystyle b^{2}-4ac}$

Чтобы проиллюстрировать это, рассмотрим следующее квадратное уравнение, адаптированное из Kahan (2004): ^[2]

${\displaystyle 94906265.625x^{2}-189812534x+94906268.375.}$

Это уравнение имеет и корни ${\displaystyle \Delta =7.5625}$

${\displaystyle x_{1}=1.000000028975958,}$

${\displaystyle x_{2}=1.000000000000000.}$

Однако при вычислении с использованием арифметики двойной точности IEEE 754, соответствующей от 15 до 17 значащих цифр точности, округляется до 0,0, а вычисленные корни равны${\displaystyle \Delta }$

${\displaystyle x_{1}=1.000000014487979,}$

${\displaystyle x_{2}=1.000000014487979,}$

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

Другие примеры [ править ]

• Функция expm1 вычисляет экспоненту минус 1 . При малых х , ехр ( х ) - 1 приведет к потере значимости в вычитании; использование специально разработанной функции помогает решить проблему.

См. Также [ править ]

• Ошибка округления
• Алгоритм суммирования Кахана
• Карлсруэ Точная арифметика
• Exsecant
• Пример в викиучебнике: Отмена значащих цифр в числовых вычислениях

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