Потеря значимости - Loss of significance

Пример 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.000000000×10⁻¹⁰

Обходные пути

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

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

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

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

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

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

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

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

{ displaystyle { frac {1- left (1- delta right)} {1 + { sqrt {1- delta}}}}}}

или

{ displaystyle { frac { delta} {1 + { sqrt {1- delta}}}}}

Потеря значащих битов

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

При вычитании Икс − y, р значимые биты теряются там, где

{ displaystyle q leq r leq p,}

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

для некоторых положительных целых чисел п и q.

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

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

{ 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.}

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

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

Лучший алгоритм

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

{ displaystyle { begin {align} 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 {align}}}

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

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

{ 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.}

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

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

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

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

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

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

Это уравнение имеет ${ displaystyle Delta = 7,5625}$ и корни

{ displaystyle x_ {1} = 1.000000028975958,}

{ displaystyle x_ {2} = 1,00000000000000000.}

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

{ displaystyle x_ {1} = 1.000000014487979,}

{ displaystyle x_ {2} = 1,000000014487979,}

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

Смотрите также

использованная литература

^ Пресса, Уильям Генри; Фланнери, Брайан П.; Теукольский, Саул А.; Веттерлинг, Уильям Т. (1992). «Раздел 5.6: Квадратные и кубические уравнения». Числовые рецепты на C (2-е изд.).
^ ^а ^б ^c Кахан, Уильям Мортон (2004-11-20). «О стоимости вычислений с плавающей точкой без сверхточной арифметики» (PDF). Получено 2012-12-25.
^ Хайэм, Николас Джон (2002). Точность и стабильность численных алгоритмов. (2-е изд.). СИАМ. п. 10. ISBN 978-0-89871-521-7.
^ Хью, Дэвид (март 1981). «Применение предложенного стандарта IEEE 754 для арифметики с плавающей запятой». Компьютер. IEEE. 14 (3): 70–74. Дои:10.1109 / C-M.1981.220381.

[Press_1992-1] Пресса, Уильям Генри; Фланнери, Брайан П.; Теукольский, Саул А.; Веттерлинг, Уильям Т. (1992). «Раздел 5.6: Квадратные и кубические уравнения». Числовые рецепты на C (2-е изд.).

[Kahan_2004-2] а ^б ^c Кахан, Уильям Мортон (2004-11-20). «О стоимости вычислений с плавающей точкой без сверхточной арифметики» (PDF). Получено 2012-12-25.

[Higham_2002-3] Хайэм, Николас Джон (2002). Точность и стабильность численных алгоритмов. (2-е изд.). СИАМ. п. 10. ISBN 978-0-89871-521-7.

[Hough_1981-4] Хью, Дэвид (март 1981). «Применение предложенного стандарта IEEE 754 для арифметики с плавающей запятой». Компьютер. IEEE. 14 (3): 70–74. Дои:10.1109 / C-M.1981.220381.

[1]

[2]

[3]

[4]