Ошибка округления

Ошибки округления , ^[1] также называется ошибка округления , ^[2] представляют собой разность между результатом полученного по заданному алгоритму с использованием точного арифметическим и результат получает тем же самый алгоритм с использованием конечной точности, округленная арифметики. ^[3] Ошибки округления возникают из-за неточности в представлении действительных чисел и выполняемых с ними арифметических операций. Это форма ошибки квантования . ^[4] При использовании приближенных уравнений или алгоритмов, особенно при использовании конечного числа цифр для представления действительных чисел (которые теоретически имеют бесконечное количество цифр), одна из целейчисленный анализ предназначен для оценки ошибок вычислений. ^[5] Ошибки вычислений, также называемые числовыми ошибками , включают как ошибки усечения, так и ошибки округления.

Когда выполняется последовательность вычислений с вводом, включающим любую ошибку округления, ошибки могут накапливаться, иногда доминируя в вычислении. В плохо подготовленных задачах может накапливаться значительная ошибка. ^[6]

Короче говоря, есть два основных аспекта ошибок округления, связанных с численными расчетами: ^[7]

1. Цифровые компьютеры имеют ограничения по величине и точности их способности представлять числа.
2. Некоторые численные операции очень чувствительны к ошибкам округления. Это может быть связано как с математическими соображениями, так и с тем, как компьютеры выполняют арифметические операции.

Ошибка представления [ править ]

Ошибка, возникающая при попытке представить число с помощью конечной строки цифр, является формой ошибки округления, называемой ошибкой представления . ^[8] Вот несколько примеров ошибок представления в десятичных представлениях:

Увеличение числа цифр, разрешенных в представлении, снижает величину возможных ошибок округления, но любое представление, ограниченное конечным числом цифр, все равно вызовет некоторую степень ошибки округления для несчетного количества действительных чисел. Дополнительные цифры, используемые на промежуточных этапах вычислений, называются защитными цифрами . ^[9]

Многократное округление может привести к накоплению ошибок. ^[10] Например, если 9,945309 округляется до двух десятичных знаков (9,95), а затем снова округляется до одного десятичного знака (10,0), общая ошибка составляет 0,054691. Округление 9,945309 до одного десятичного знака (9,9) за один шаг приводит к меньшей ошибке (0,045309). Обычно это происходит при выполнении арифметических операций (см. « Потеря значимости» ).

Система счисления с плавающей запятой [ править ]

По сравнению с системой счисления с фиксированной запятой, система счисления с плавающей запятой более эффективна при представлении действительных чисел, поэтому она широко используется в современных компьютерах. В то время как действительные числа бесконечны и непрерывны, система счисления с плавающей запятой конечна и дискретна. Таким образом, ошибка представления, которая приводит к ошибке округления, возникает в системе счисления с плавающей запятой. ${\ Displaystyle \ mathbb {R}}$${\ displaystyle F}$

Обозначение системы счисления с плавающей запятой [ править ]

Система счисления с плавающей запятой характеризуется целыми числами:${\ displaystyle F}$${\ displaystyle 4}$

${\ displaystyle \ beta}$: основание или основание

${\ displaystyle p}$: точность

${\ displaystyle [L, U]}$: диапазон экспоненты, где - нижняя граница, а - верхняя граница${\ displaystyle L}$${\ displaystyle U}$

• Любой имеет следующий вид:${\ displaystyle x \ in F}$

${\displaystyle x=\pm (\underbrace {d_{0}.d_{1}d_{2}\ldots d_{p-1}} _{\text{mantissa}})_{\beta }\times \beta ^{\overbrace {E} ^{\text{exponent}}}=\pm d_{0}\times \beta ^{E}+d_{1}\times \beta ^{E-1}+\ldots +d_{p-1}\times \beta ^{E-(p-1)}}$

где - такое целое число, что для , и - такое целое число, что .${\displaystyle d_{i}}$${\displaystyle 0\leq d_{i}\leq \beta -1}$${\displaystyle i=0,1,\ldots ,p-1}$${\displaystyle E}$${\displaystyle L\leq E\leq U}$

Нормализованная система с плавающей запятой [ править ]

• Система счисления с плавающей запятой нормализуется, если первая цифра всегда отлична от нуля, если только число не равно нулю. ^[3] Поскольку мантисса равна , мантисса ненулевого числа в нормализованной системе удовлетворяет . Таким образом, нормализованная форма ненулевого числа с плавающей запятой IEEE - это где . В двоичном формате ведущая цифра всегда отображается, поэтому она не записывается и называется неявным битом. Это дает дополнительный бит точности, так что ошибка округления, вызванная ошибкой представления, уменьшается.${\displaystyle d_{0}}$${\displaystyle d_{0}.d_{1}d_{2}\ldots d_{p-1}}$${\displaystyle 1\leq {\text{ mantissa }}<\beta }$${\displaystyle \pm 1.bb\ldots b\times 2^{E}}$${\displaystyle b\in {0,1}}$${\displaystyle 1}$

• Поскольку система счисления с плавающей запятой конечна и дискретна, она не может представлять все действительные числа, что означает, что бесконечные действительные числа могут быть аппроксимированы только некоторыми конечными числами с помощью правил округления . С плавающей точкой приближения заданного вещественного числа В можно обозначить.${\displaystyle F}$${\displaystyle x}$${\displaystyle fl(x)}$
  • Общее количество нормализованных чисел с плавающей запятой равно

${\displaystyle 2(\beta -1)\beta ^{p-1}(U-L+1)+1}$, куда

${\displaystyle 2}$ считает выбор знака, положительный или отрицательный

${\displaystyle (\beta -1)}$ считает выбор первой цифры

${\displaystyle \beta ^{p-1}}$ считает оставшуюся мантиссу

${\displaystyle U-L+1}$ считает выбор показателей

${\displaystyle 1}$считает тот случай, когда число есть .${\displaystyle 0}$

Стандарт IEEE [ править ]

В стандарте IEEE база двоичная, т. Е. Используется нормализация. Стандарт IEEE хранит знак, показатель степени и мантиссу в отдельных полях слова с плавающей запятой, каждое из которых имеет фиксированную ширину (количество бит). Два наиболее часто используемых уровня точности для чисел с плавающей запятой - это одинарная точность и двойная точность. ${\displaystyle \beta =2}$

Машинный эпсилон [ править ]

Машинный эпсилон может использоваться для измерения уровня ошибки округления в системе счисления с плавающей запятой. Вот два разных определения. ^[3]

• Обозначенный машинный эпсилон представляет собой максимально возможную абсолютную относительную ошибку при представлении ненулевого действительного числа в системе счисления с плавающей запятой.${\displaystyle \epsilon _{mach}}$${\displaystyle x}$

${\displaystyle \epsilon _{mach}=\max _{x}{\frac {|x-fl(x)|}{|x|}}}$

• Обозначенный машинный эпсилон - это наименьшее число, такое что . Таким образом, всякий раз , когда .${\displaystyle \epsilon _{mach}}$${\displaystyle \epsilon }$${\displaystyle fl(1+\epsilon )>1}$${\displaystyle fl(1+\delta )=fl(1)=1}$${\displaystyle |\delta |<\epsilon _{mach}}$

Ошибка округления при разных правилах округления [ править ]

Существует два распространенных правила округления: округление за отрезком и округление до ближайшего. Стандарт IEEE использует округление до ближайшего.

• Поочередно : расширение по основанию усекается после цифры.${\displaystyle \beta }$${\displaystyle x}$${\displaystyle (p-1)^{th}}$
  • Это правило округления смещено, потому что оно всегда приближает результат к нулю.

• Округление до ближайшего : устанавливается до ближайшего числа с плавающей запятой . При равенстве используется число с плавающей запятой, последняя сохраненная цифра которого четная.${\displaystyle fl(x)}$${\displaystyle x}$
  • Для стандарта IEEE , где основание является , это означает , когда есть связь оно округляется так , что последняя цифра равна .${\displaystyle \beta }$${\displaystyle 2}$${\displaystyle 0}$
  • Это правило округления более точное, но более затратное с точки зрения вычислений.
  • Округление таким образом, чтобы последняя сохраненная цифра была даже при равенстве, гарантирует, что она не округляется систематически в большую или меньшую сторону. Это сделано для того, чтобы избежать возможности нежелательного медленного отклонения в длинных вычислениях просто из-за смещения округления.

• В следующем примере показан уровень ошибки округления в соответствии с двумя правилами округления. ^[3] Правило округления, округление до ближайшего, в целом приводит к меньшей ошибке округления.

Расчет ошибки округления в стандарте IEEE [ править ]

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

• Пример: десятичное число можно преобразовать в${\displaystyle (9.4)_{10}=(1001.{\overline {0110}})_{2}}$

${\displaystyle +1.\underbrace {0010110011001100110011001100110011001100110011001100} _{\text{52 bits}}110\ldots \times 2^{3}}$

Поскольку бит справа от двоичной точки - это a, за которым следуют другие ненулевые биты, правило округления до ближайшего требует округления в большую сторону , то есть добавления бита к биту. Таким образом, нормализованное представление с плавающей запятой в стандарте IEEE является ${\displaystyle 53^{rd}}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle 52^{nd}}$${\displaystyle 9.4}$

${\displaystyle fl(9.4)=1.0010110011001100110011001100110011001100110011001101\times 2^{3}}$.

• Теперь ошибку округления можно вычислить при представлении с помощью .${\displaystyle 9.4}$${\displaystyle fl(9.4)}$

Это представление получается путем отбрасывания бесконечного хвоста

${\displaystyle 0.{\overline {1100}}\times 2^{-52}\times 2^{3}=0.{\overline {0110}}\times 2^{-51}\times 2^{3}=0.4\times 2^{-48}}$

от правого хвоста, а затем добавили на этапе округления. ${\displaystyle 1\times 2^{-52}\times 2^{3}=2^{-49}}$

Тогда .${\displaystyle fl(9.4)=9.4-0.4\times 2^{-48}+2^{-49}=9.4+(0.2)_{10}\times 2^{-49}}$

Таким образом, ошибка округления равна .${\displaystyle (0.2\times 2^{-49})_{10}}$

Измерение ошибки округления с помощью машинного эпсилона [ править ]

Машинный эпсилон может использоваться для измерения уровня ошибки округления при использовании двух вышеупомянутых правил округления. Ниже приведены формулы и соответствующие доказательства. ^[3] Здесь используется первое определение машинного эпсилон. ${\displaystyle \epsilon _{mach}}$

Теорема [ править ]

1. По очереди: ${\displaystyle \epsilon _{mach}=\beta ^{1-p}}$
2. Округление до ближайшего: ${\displaystyle \epsilon _{mach}={\frac {1}{2}}\beta ^{1-p}}$

Доказательство [ править ]

Пусть где , и пусть будет представление с плавающей запятой . Поскольку используется пошаговое определение, это означает: * Чтобы определить максимум этого количества, необходимо найти максимум числителя и минимум знаменателя. Поскольку (нормализованная система), минимальное значение знаменателя равно . Сверху числитель ограничен . Таким образом, . Поэтому для пошаговой инструкции. Доказательство для округления до ближайшего аналогично.${\displaystyle x=d_{0}.d_{1}d_{2}\ldots d_{p-1}d_{p}\ldots \times \beta ^{n}\in \mathbb {R} }$${\displaystyle n\in [L,U]}$${\displaystyle fl(x)}$${\displaystyle x}$${\displaystyle {\begin{aligned}{\frac {|x-fl(x)|}{|x|}}&={\frac {|d_{0}.d_{1}d_{2}\ldots d_{p-1}d_{p}d_{p+1}\ldots \times \beta ^{n}-d_{0}.d_{1}d_{2}\ldots d_{p-1}\times \beta ^{n}|}{|d_{0}.d_{1}d_{2}\ldots \times \beta ^{n}|}}\\&={\frac {|d_{p}.d_{p+1}\ldots \times \beta ^{n-p}|}{|d_{0}.d_{1}d_{2}\ldots \times \beta ^{n}|}}\\&={\frac {|d_{p}.d_{p+1}d_{p+2}\ldots |}{|d_{0}.d_{1}d_{2}\ldots |}}\times \beta ^{-p}\end{aligned}}}$${\displaystyle d_{0}\neq 0}$${\displaystyle 1}$${\displaystyle (\beta -1).(\beta -1){\overline {(\beta -1)}}=\beta }$${\displaystyle {\frac {|x-fl(x)|}{|x|}}\leq {\frac {\beta }{1}}\times \beta ^{-p}=\beta ^{1-p}}$${\displaystyle \epsilon =\beta ^{1-p}}$

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

Ошибка округления, вызванная арифметикой с плавающей запятой [ править ]

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

Дополнение [ править ]

Машинное сложение состоит из выстраивания десятичных знаков двух добавляемых чисел, их сложения и последующего сохранения результата как числа с плавающей запятой. Само сложение может быть выполнено с более высокой точностью, но результат должен быть округлен до указанной точности, что может привести к ошибке округления. ^[3]

Например, при добавлении к двойной точности IEEE следующим образом , ${\displaystyle 1}$${\displaystyle 2^{-53}}$

${\displaystyle {\begin{aligned}1.00\ldots 0\times 2^{0}+1.00\ldots 0\times 2^{-53}&=1.\underbrace {00\ldots 0} _{\text{52 bits}}\times 2^{0}+0.\underbrace {00\ldots 0} _{\text{52 bits}}1\times 2^{0}\\&=1.\underbrace {00\ldots 0} _{\text{52 bits}}1\times 2^{0}\end{aligned}}}$

• Это сохраняется, поскольку в стандарте IEEE используется округление до ближайшего. Поэтому, равно двойной точности IEEE и округление ошибка .${\displaystyle 1.\underbrace {00\ldots 0} _{\text{52 bits}}\times 2^{0}}$${\displaystyle 1+2^{-53}}$${\displaystyle 1}$${\displaystyle 2^{-53}}$

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

Умножение [ править ]

Как правило, произведение мантисс с -цифровыми числами содержит до цифр, поэтому результат может не соответствовать мантиссе. ^[3] Таким образом, в результат будет включена ошибка округления.${\displaystyle 2}$ ${\displaystyle p}$${\displaystyle 2p}$

• Например, рассмотрим нормализованную систему счисления с плавающей запятой, в которой основание и цифры мантиссы не больше . Потом и . Обратите внимание, но поскольку там не более цифр мантиссы. Ошибка округления будет .${\displaystyle \beta =10}$${\displaystyle 2}$${\displaystyle fl(77)=7.7\times 10}$${\displaystyle fl(88)=8.8\times 10}$${\displaystyle 77\times 88=6776}$${\displaystyle fl(6776)=6.7\times 10^{3}}$${\displaystyle 2}$${\displaystyle 6776-fl(6776)=6776-6.7\times 10^{3}=76}$

Подразделение [ править ]

Как правило, частное мантисс-цифр может содержать больше, чем -цифров. ^[3] Таким образом, в результат будет включена ошибка округления.${\displaystyle 2}$ ${\displaystyle p}$${\displaystyle p}$

• Например, если приведенная выше нормализованная система счисления с плавающей запятой все еще используется, то но . Итак, хвост отрезан.${\displaystyle 1/3=0.333\ldots }$${\displaystyle fl(1/3)=fl(0.333\ldots )=3.3\times 10^{-1}}$${\displaystyle 0.333\ldots -3.3\times 10^{-1}=0.00333\ldots }$

Вычитающая отмена [ править ]

Вычитание двух почти равных чисел называется вычитанием . ^[3]

• Когда первые цифры отменяются, результат может быть слишком маленьким для точного представления, и он будет представлен просто как .${\displaystyle 0}$
  • Например, let и здесь используется второе определение машинного эпсилон. Какое решение ? Известно, что и почти равны числа, и . Однако в системе счисления с плавающей запятой . Несмотря на то, что он достаточно большой, чтобы его можно было представить, оба экземпляра были округлены в виде пожертвований .${\displaystyle |\epsilon |<\epsilon _{mach}}$${\displaystyle (1+\epsilon )-(1-\epsilon )}$
    ${\displaystyle 1+\epsilon }$${\displaystyle 1-\epsilon }$${\displaystyle (1+\epsilon )-(1-\epsilon )=1+\epsilon -1+\epsilon =2\epsilon }$${\displaystyle fl((1+\epsilon )-(1-\epsilon ))=fl(1+\epsilon )-fl(1-\epsilon )=1-1=0}$${\displaystyle 2\epsilon }$${\displaystyle \epsilon }$${\displaystyle 0}$
• Даже при несколько большем значении результат в типичных случаях все равно существенно ненадежен. Нет особой веры в точность значения, потому что наибольшая неопределенность в любом числе с плавающей запятой - это цифры в крайнем правом углу.${\displaystyle \epsilon }$
  • Например, . Результат наглядно представим, но веры в него нет.${\displaystyle 1.99999\times 10^{2}-1.99998\times 10^{2}=0.00001\times 10^{2}=1\times 10^{-5}\times 10^{2}=1\times 10^{-3}}$${\displaystyle 1\times 10^{-3}}$

Накопление ошибки округления [ править ]

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

Нестабильные алгоритмы [ править ]

Алгоритм или численный процесс называется стабильным, если небольшие изменения на входе вызывают только небольшие изменения на выходе, и называется нестабильным, если производятся большие изменения на выходе. ^[11]

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

Например, для с данным. Это легко показать . Предположим, что это наше начальное значение и есть небольшая ошибка представления , что означает, что начальный вход в этот алгоритм вместо . Затем алгоритм выполняет следующую последовательность вычислений. ${\displaystyle y_{n}=\int _{0}^{1}\,{\frac {x^{n}}{x+5}}dx}$${\displaystyle n=1,2,\ldots ,8}$${\displaystyle y_{0}}$${\displaystyle y_{n}={\frac {1}{n}}-5y_{n-1}}$${\displaystyle y_{0}}$${\displaystyle \epsilon }$${\displaystyle y_{0}+\epsilon }$${\displaystyle y_{0}}$

${\displaystyle {\begin{aligned}y_{1}&=1-5(y_{0}+\epsilon )=1-5y_{0}-5\epsilon \\y_{2}&={\frac {1}{2}}-5(1-5y_{0}-5\epsilon )={\frac {1}{2}}-5+25y_{0}+5^{2}\epsilon \\\vdots \\y_{n}&=\ldots +5^{n}\epsilon \end{aligned}}}$

Ошибка округления увеличивается в последующих вычислениях, поэтому этот алгоритм нестабилен.

Плохо обусловленные проблемы [ править ]

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

Число обусловленности проблемы - это отношение относительного изменения решения к относительному изменению входных данных. ^[3] Проблема хорошо обусловлена, если небольшие относительные изменения входных данных приводят к небольшим относительным изменениям в решении. В противном случае проблема плохо обусловлена . ^[3] Другими словами, проблема является плохо обусловленной, если ее число условий «намного больше», чем . ${\displaystyle 1}$

Число обусловленности вводится как мера ошибок округления, которые могут возникнуть при решении плохо обусловленных задач. ^[7]

Например, полиномы более высокого порядка имеют тенденцию быть очень плохо обусловленными , то есть они имеют тенденцию быть очень чувствительными к ошибке округления. ^[7]

В 1901 году Карл Рунге опубликовал исследование об опасностях полиномиальной интерполяции высокого порядка. Он посмотрел на следующую простую на вид функцию:

${\displaystyle f(x)={\frac {1}{1+25x^{2}}}}$

которая теперь называется функцией Рунге . Он взял равноудаленные точки данных из этой функции на интервале . Затем он использовал интерполяционные полиномы возрастающего порядка и обнаружил, что по мере того, как он брал больше точек, полиномы и исходная кривая значительно отличались, как показано на Рисунке «Сравнение1» и Рисунке «Сравнение 2». Дальше ситуация сильно ухудшилась по мере увеличения приказа. Как показано на Рисунке «Сравнение 2», посадка стала еще хуже, особенно на концах интервала. ${\displaystyle [-1,1]}$

Нажмите на рисунки, чтобы увидеть полное описание.

Пример из реального мира: отказ ракеты «Патриот» из-за увеличения ошибки округления [ править ]

25 февраля 1991 года, во время войны в Персидском заливе, американская ракетная батарея «Пэтриот» в Дхаране, Саудовская Аравия, не смогла перехватить приближающуюся иракскую ракету «Скад». Скад врезался в казармы американской армии и убил 28 солдат. Отчет тогдашней Главной бухгалтерииозаглавленный «Противоракетная оборона Patriot: проблема программного обеспечения, приведшая к отказу системы в Дахране, Саудовская Аравия», сообщал о причине сбоя: неточный расчет времени с момента загрузки из-за компьютерных арифметических ошибок. В частности, время в десятых долях секунды, измеренное внутренними часами системы, было умножено на 10, чтобы получить время в секундах. Этот расчет был выполнен с использованием 24-битного регистра с фиксированной запятой. В частности, значение 1/10, которое имеет неограниченное двоичное расширение, было прервано на 24 бита после точки счисления. Небольшая ошибка прерывания, умноженная на большое число, дающее время в десятых долях секунды, привела к значительной ошибке. Действительно, батарея Patriot проработала около 100 часов,и простой расчет показывает, что результирующая временная ошибка из-за увеличенной ошибки прерывания составила около 0,34 секунды. (Число 1/10 равно${\displaystyle 1/2^{4}+1/2^{5}+1/2^{8}+1/2^{9}+1/2^{12}+1/2^{13}+\ldots }$. Другими словами, двоичное разложение 1/10 равно . Теперь 24-битный регистр в Патриоте хранится вместо того, чтобы вводить ошибку двоичного или десятичного порядка . Умножение на количество десятых секунды в часах дает ). Скад едет примерно${\displaystyle 0.0001100110011001100110011001100\ldots }$${\displaystyle 0.00011001100110011001100}$${\displaystyle 0.0000000000000000000000011001100\ldots }$${\displaystyle 0.000000095}$${\displaystyle 100}$${\displaystyle 0.000000095\times 100\times 60\times 60\times 10=0.34}$1676 метров в секунду, то есть за это время проходит более полукилометра. Этого было достаточно, чтобы приближающийся Скад находился за пределами «ворот дальности», которые отслеживал Патриот. По иронии судьбы, тот факт, что вычисление плохого времени было улучшено в некоторых частях кода, но не во всех, способствовал возникновению проблемы, поскольку это означало, что неточности не отменялись. ^[12]

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

• Точность (арифметика)
• Усечение
• Округление
• Потеря значимости
• Плавающая точка
• Алгоритм суммирования Кахана
• Машина эпсилон
• Полином Уилкинсона

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

Внешние ссылки [ править ]

• Ошибка округления в MathWorld.
• Гольдберг, Дэвид (март 1991). «Что должен знать каждый компьютерный ученый об арифметике с плавающей точкой» (PDF) . ACM Computing Surveys . 23 (1): 5–48. DOI : 10.1145 / 103162.103163 . Проверено 20 января 2016 .( [1] , [2] )
• 20 известных программных катастроф