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

Computational error due to rounding numbers

В вычислениях ошибка округления , ^[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). Это может произойти, например, когда программное обеспечение выполняет арифметические действия в 80-битном формате с плавающей запятой x86, а затем округляет результат до IEEE 754binary64 с плавающей запятой .

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

По сравнению с системой счисления с фиксированной запятой , система счисления с плавающей запятой более эффективна для представления действительных чисел, поэтому она широко используется в современных компьютерах. В то время как действительные числа бесконечны и непрерывны, система счисления с плавающей запятой конечна и дискретна. Таким образом, в системе счисления с плавающей запятой возникает ошибка представления, приводящая к ошибке округления. ${\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{significand}})_{\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{significand}}<\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 _{\text{mach}}}$ ${\displaystyle x}$
  $${\displaystyle \epsilon _{\text{mach}}=\max _{x}{\frac {|x-fl(x)|}{|x|}}}$$
• Машинный эпсилон, обозначаемый , представляет собой наименьшее число такое, что . Таким образом, когда бы то ни было . ${\displaystyle \epsilon _{\text{mach}}}$ ${\displaystyle \epsilon }$ ${\displaystyle fl(1+\epsilon )>1}$ ${\displaystyle fl(1+\delta )=fl(1)=1}$ ${\displaystyle |\delta |<\epsilon _{\text{mach}}}$

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

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

• Round-by-chop : Расширение основания усекается после -й цифры. ${\displaystyle \beta }$ ${\displaystyle x}$ ${\displaystyle (p-1)}$
  • Это правило округления является предвзятым, поскольку оно всегда приближает результат к нулю.
• Округление до ближайшего : устанавливается на ближайшее число с плавающей запятой, равное . В случае равенства используется число с плавающей запятой, последняя сохраненная цифра которого четная (также последняя цифра в двоичной форме равна 0). ${\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}}$$

Поскольку 53-й бит справа от двоичной точки равен 1, а за ним следуют другие ненулевые биты, правило округления до ближайшего требует округления в большую сторону, то есть добавления 1 бита к 52-му биту. Таким образом, нормализованное представление с плавающей запятой в стандарте IEEE 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 _{\text{mach}}}$

Теорема

1. По кругу: ${\displaystyle \epsilon _{\text{mach}}=\beta ^{1-p}}$
2. Округление до ближайшего: ${\displaystyle \epsilon _{\text{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 следующее: Это сохраняется, поскольку в стандарте IEEE используется округление до ближайшего. Следовательно, в 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}}}$
  ${\displaystyle 1.\underbrace {00\ldots 0} _{\text{52 bits}}\times 2^{0}}$ ${\displaystyle 1+2^{-53}}$ ${\displaystyle 1}$ ${\displaystyle 2^{-53}}$

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

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

• Например, рассмотрим нормализованную систему счисления с плавающей запятой с основанием и точностью . Тогда и . Обратите внимание, но . Имеется ошибка округления . ${\displaystyle 10}$ ${\displaystyle 2}$ ${\displaystyle fl(62)=6.2\times 10^{1}}$ ${\displaystyle fl(41)=4.1\times 10^{1}}$ ${\displaystyle 62+41=103}$ ${\displaystyle fl(103)=1.0\times 10^{2}}$ ${\displaystyle 103-fl(103)=3}$

Ошибка такого рода может возникать наряду с ошибкой поглощения в одной операции.

Умножение

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

• Например, рассмотрим нормализованную систему счисления с плавающей запятой, в которой основание и значащие цифры не превышают . Тогда и . Обратите внимание, что , поскольку здесь не более значащих цифр. Ошибка округления будет равна . ${\displaystyle \beta =10}$ ${\displaystyle 2}$ ${\displaystyle fl(77)=7.7\times 10^{1}}$ ${\displaystyle fl(88)=8.8\times 10^{1}}$ ${\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}$

Разделение

В общем, частное 2p-значных чисел может содержать более 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 }$

Вычитание

Поглощение также применимо к вычитанию.

• Например, вычитание из двойной точности IEEE следующим образом: ${\displaystyle 2^{-60}}$ ${\displaystyle 1}$
  $${\displaystyle {\begin{aligned}1.00\ldots 0\times 2^{0}-1.00\ldots 0\times 2^{-60}&=\underbrace {1.00\ldots 0} _{\text{60 bits}}\times 2^{0}-\underbrace {0.00\ldots 01} _{\text{60 bits}}\times 2^{0}\\&=\underbrace {0.11\ldots 1} _{\text{60 bits}}\times 2^{0}.\end{aligned}}}$$
  Это сохраняется, поскольку в стандарте IEEE используется округление до ближайшего. Следовательно, в IEEE соответствует двойной точности, а ошибка округления равна . ${\displaystyle \underbrace {1.00\ldots 0} _{\text{53 bits}}\times 2^{0}}$ ${\displaystyle 1-2^{-60}}$ ${\displaystyle 1}$ ${\displaystyle -2^{-60}}$

Вычитание двух почти равных чисел называется вычитающим сокращением . ^[3] Если первые цифры удалены, результат может оказаться слишком маленьким для точного представления, и он будет представлен просто как . ${\displaystyle 0}$

• Например, пусть здесь используется второе определение машинного эпсилона. В чем заключается решение ? Известно, что и - почти равные числа, и . Однако в системе счисления с плавающей запятой . Хотя он достаточно велик, чтобы его можно было представить, оба экземпляра были округлены до . ${\displaystyle |\epsilon |<\epsilon _{\text{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}}$

Это тесно связано с явлением катастрофического сокращения , в котором эти два числа, как известно , являются приближениями.

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

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

Нестабильные алгоритмы

Алгоритм или численный процесс называется стабильным , если небольшие изменения входных данных приводят лишь к небольшим изменениям выходных данных, и нестабильным , если происходят большие изменения выходных данных. ^[12] Например, вычисление с использованием «очевидного» метода вблизи неустойчиво из-за большой ошибки, вносимой при вычитании двух одинаковых величин, тогда как эквивалентное выражение устойчиво. ^[12] ${\displaystyle f(x)={\sqrt {1+x}}-1}$ ${\displaystyle x=0}$ ${\displaystyle \textstyle {f(x)={\frac {x}{{\sqrt {1+x}}+1}}}}$

Плохо обусловленные проблемы

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

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

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

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

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

Рекомендации

1. Батт, Ризван (2009), Введение в численный анализ с использованием MATLAB, Jones & Bartlett Learning, стр. 11–18, ISBN 978-0-76377376-2
2. Юберхубер, Кристоф В. (1997), Численные вычисления 1: методы, программное обеспечение и анализ, Springer, стр. 139–146, ISBN 978-3-54062058-7
3. Форрестер, Дик (2018). Math/Comp241 Численные методы (конспекты лекций) . Дикинсон Колледж .
4. Аксой, Пелин; ДеНардис, Лаура (2007), Информационные технологии в теории, Cengage Learning, стр. 134, ISBN 978-1-42390140-2
5. Ралстон, Энтони; Рабиновиц, Филип (2012), Первый курс численного анализа, Dover Books on Mathematics (2-е изд.), Courier Dover Publications, стр. 2–4, ISBN 978-0-48614029-2
6. Чепмен, Стивен (2012), Программирование MATLAB с приложениями для инженеров, Cengage Learning, стр. 454, ISBN 978-1-28540279-6
7. Чапра, Стивен (2012). Прикладные численные методы с MATLAB для инженеров и ученых (3-е изд.). МакГроу-Хилл . ISBN 9780073401102.
8. Лаплант, Филип А. (2000). Словарь информатики, техники и технологий. ЦРК Пресс . п. 420. ИСБН 978-0-84932691-2.
9. Хайэм, Николас Джон (2002). Точность и устойчивость численных алгоритмов (2-е изд.). Общество промышленной и прикладной математики (SIAM). стр. 43–44. ISBN 978-0-89871521-7.
10. Волков, Е.А. (1990). Численные методы. Тейлор и Фрэнсис . п. 24. ISBN 978-1-56032011-1.
11. Биран, Адриан Б.; Брейнер, Моше (2010). «5». Что должен знать каждый инженер о MATLAB и Simulink . Бока-Ратон , Флорида : CRC Press . стр. 193–194. ISBN 978-1-4398-1023-1.
12. Коллинз, Чарльз (2005). «Состояние и стабильность» (PDF) . Кафедра математики в Университете Теннесси . Проверено 28 октября 2018 г.

дальнейшее чтение

• Мэтт Паркер (2021). Скромный Пи: когда математика в реальном мире идет не так . Книги Риверхеда. ISBN 978-0593084694.

Внешние ссылки

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