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

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

Механизм потери значимости для десятичной и двоичной арифметик одинаков. Но, в отличие от этих арифметик, в  десятично-двоичной арифметике  потеря значимости приводит к результату, который и породил понятие – катастрофическая  отмена.

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

Рассмотрим потерю значимости, которая происходит при вычислении десятичных уравнений в десятичной арифметике. Такие уравнения, как правило, содержат  операции вычитания.   В Wikipedia  рассмотрен пример нахождения корней квадратного уравнения:

x2  — 1.786737601482363 x + 2.054360090947453*10-8 =0.

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

D =  (1,786737601482363) 2 — 4*2,054360090947453*10-8 = 3,192431174376543782196880063769

√D ≈ 1,7867375784867076506855657922848

x1 = (1,786737601482363 + 1,7867375784867076506855657922848)/2 = 1,7867375899845353253427828961424 ≈ 1,786737589984535

x2=(1,786737601482363 — 1,7867375784867076506855657922848)/2 = 0,0000000114978276746572171038576 ≈ 0,00000001149782767465722

Обратите внимание, что в этом решении число  x2  вычислено с точностью до 32 значащих цифр.

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

(1,786737601482363) 2 ≈ 3,192431256550947

4*2,054360090947453*10-8 = 0,00000008217440363789812

D = 3.192431256550947 — 0.0000008217440363789812  ≈ 3,192431174376543

√D  ≈ 1,786737578486707

x1 = (1,786737601482363 + 1,786737578486707)/2 = 1,786737589984535

x2 = (1,786737601482363 — 1,786737578486707)/2 = 0,000000011497828

Как мы видим,  корень x2 содержит всего 8 значащих цифр, вместо 16. Такой ответ получен в результате того, что  уменьшаемое и вычитаемое в нахождении корня x2,  округленные до 16 значащих цифр, имеют по 7 совпадающих старших цифр плюс еще одну цифру с погрешностью  < 0.5ulp. Т.е. они имеют по 8 верных цифр. В результате вычитания эти цифры обнулились, а поскольку промежуточные результаты округлялись до 16 значащих цифр, то для правильного ответа с заданной  точностью в 16 цифр не хватило еще 8 цифр.  Здесь налицо потеря значимости, которая связана с округлением промежуточных результатов. Заметим, что полученный нами результат в рамках 16-ти разрядной арифметики оказался  правильным (accuracy), но неточным.  Если теперь от x2 мы отнимем число 0,000000011497828, то получим 0. Это будет правильный результат, хотя и неточный.

Решим теперь эту задачу с помощью десятично-двоичной арифметики. Ниже представлен код на языке C++  определяющий корень x2  вышеописанного квадратного уравнения, от которого отнимается число 1.1497828e-8. Вычисления выполняются в формате double.

——————————————————————————————————

#include <iostream>

#include <math.h>

#include <iomanip>

using namespace std;

 

int main()

{

double b,c,p,x2,Sub,Mul,Dif,D;

 

b = 1.786737601482363,2;

c = 2.054360090947453e-8;

p=pow(b,2);

Mul=4*c;

Dif=p-Mul;

D=sqrt(Dif);

x2=(b-D)/2;

Rez = x2 — 1.1497828e-8  ;

return 0;

 

}

—————————————————————————————————

x2 = 1.1497827689943563e-008

Rez = -3.1005643681221624e-016

 

Как мы видим, в результате вычисления корня x2   мы получили ответ с точностью более 16 цифр, но этот ответ неправильный (not accuracy), т.к.  кроме 8 верных цифр он содержит 8 ложных цифр. В результате вычитания из x2 числа 1.1497828e-8  мы получили отрицательное число  -3.1005643681221624e-016, что является совершенно неправильным ответом. Очевидно, что потеря значимости здесь привела к катастрофическим последствиям, поэтому логично ее назвать катастрофической отменой.

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

Проблема катастрофической отмены является серьезной проблемой десятично-двоичных вычислений. Хотя сама проблема хорошо известна и рассматривается во многих работах по двоичным вычислениям, решается она, в основном, на качественном уровне в виде рекомендаций, таких как –   не отнимайте близкие по значению числа.

Серьезность этой проблемы можно продемонстрировать, например, на вычислениях в Excel, которые реализованы  согласно стандарту IEEE754 в формате double.

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

  1. Предположим, нам надо найти в десятично-двоичной арифметике разность двух десятичных 15-разрядных чисел:

9234567890123,45 — 9234567890123,43.

Поскольку эти числа 15-разрядные, их двоичные представления в формате double гарантированно будут иметь 15 верных цифр.

Найдем в Excel разность этих десятичных чисел:

A1|9234567890123,45

A2|9234567890123,43

A3|=A1-A2

Ответ: 0,019531250000000000E-02

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

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

  1. Рассмотрим еще один пример. Надо найти разность двух чисел: 9234,56789801233 и 9234,56789012345. При этом надо ответить на следующие вопросы. Являются ли эти числа близкие по значению? И сколько цифр надо вывести в десятичную строку, чтобы ответ был правильным.

Найдем в Excel разность этих десятичных чисел:

A1| 9234,56789801233

A2| 9234,56789012345

A3|=A1-A2

Ответ: 7,888880645623430E-06

Мы видим, что полученный в Excel ответ содержит  7 верных цифр. Это следует из  вычисления вручную, в котором разность наших чисел равна точно 0,000007888880. Обратите внимание, что в первом  нашем примере ответ содержал всего 2 верные цифры, а во-втором  7 цифр. Отсюда возникает проблема выбора количества цифр для правильного вывода результата вычислений  в строку. Даже если  в некоторых случаях, при решении алгебраических уравнений, алгоритмически можно избежать операции вычитания близких по значению чисел, мы должны иметь  какой-то критерий, по которому можно отличать близкие числа от остальных. Четкого критерия, к сожалению, мы не имеем.

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

 

Я изобретатель, имею 18 авторских свидетельств СССР на изобретения и два патента. Последние несколько лет занимаюсь исследованием проблем компьютерной математики.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *