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

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

Система чисел с плавающей точкой

По сравнению с системой счисления с фиксированной точкой , система счисления с плавающей точкой более эффективна в представлении действительных чисел, поэтому она широко используется в современных компьютерах. В то время как действительные числа бесконечны и непрерывны, система счисления с плавающей точкой конечна и дискретна. Таким образом, в системе счисления с плавающей точкой возникает ошибка представления, которая приводит к ошибке округления. ${\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 ^{p}}$ ${\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 использует округление к ближайшему.

• Округление с отсечением : расширение основания усекается после -й цифры. ${\displaystyle \beta }$ ${\displaystyle x}$ ${\displaystyle (p-1)}$
  • Это правило округления является предвзятым, поскольку оно всегда приближает результат к нулю.
• Round-to-nearest : устанавливается на ближайшее число с плавающей точкой к . При равенстве используется число с плавающей точкой, последняя сохраненная цифра которого четная (также последняя цифра в двоичной форме равна 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 double precision следующим образом, Это сохраняется как, поскольку округление до ближайшего используется в стандарте IEEE. Следовательно, равно в IEEE double precision, а ошибка округления равна . ${\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 double precision следующим образом, Это сохраняется как, поскольку округление до ближайшего используется в стандарте IEEE. Следовательно, равно в IEEE double precision, а ошибка округления составляет . ${\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}}}$$ ${\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. Chapra, Steven (2012). Прикладные численные методы с MATLAB для инженеров и ученых (3-е изд.). McGraw-Hill . ISBN 9780073401102.
8. Лаплант, Филип А. (2000). Словарь компьютерных наук, техники и технологий. CRC Press . стр. 420. ISBN 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. Collins, Charles (2005). "Condition and Stability" (PDF) . Кафедра математики в Университете Теннесси . Получено 28.10.2018 .

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

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

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

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