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

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

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

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

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

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

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

Многократное округление может привести к накоплению ошибки^[10]. Например, если число 9,945309 сначала округлить до двух знаков (9,95), а затес ещё раз до одного знака (получится 10,0), общая ошибка будет 0,054691. Округление 9,945309 до одного знака после запятой (получится 9,9) за один шаг даст меньшую ошибку (0,045309). Такое может случиться, например, если программа осуществляет арифметические вычисления в 80-битном формате x86 числа с плавающей запятой, а затем округляет результат до 64-битного формата IEEE 754.

В отличие от системы чисел с фиксированной запятой система чисел с плавающей запятой более эффективно представляет действительные числа, поэтому она широко используется в современных компьютерах. В то время как действительные числа ${\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{ мантисса}})_{\beta }\times \beta ^{\overbrace {E} ^{\text{показатель}}}=\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\leqslant d_{i}\leqslant \beta -1}$ для ${\displaystyle i=0,1,\ldots ,p-1}$, а ${\displaystyle E}$ является целым числом, таким что ${\displaystyle L\leqslant E\leqslant U}$.

• Система чисел с плавающей запятой нормализована, если старший знак ${\displaystyle d_{0}}$ всегда ненулевой, если число ненулевое^[3]. Поскольку мантисса равна ${\displaystyle d_{0}{,}d_{1}d_{2}\ldots d_{p-1}}$, мантисса ненулевого числа в нормализованном виде удовлетворяет неравенствам ${\displaystyle 1\leqslant {\text{мантисса}}<\beta ^{p}}$. Таким образом, нормализованная форма ненулевого IEEE числа с плавающей запятой имеет вид ${\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 основание равно двум (${\displaystyle \beta =2}$) и используется нормализация. По этому стандарту записываются знак числа, показатель и мантисса в отдельных полях слова с плавающей запятой, каждое из полей имеет фиксированный размер (в битах). Два наиболее распространённых уровня точности для чисел с плавающей запятой — одинарная точность и двойная точность.

Примечание: Остаток мантиссы — мантисса без старшего разряда (старший разряд всегда равен 1).

Машинный эпсилон может быть использован как мера уровня ошибки округления. Имеется два различных определения величины^[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}}}$.

Имеется два распространенных правила округления: округление отбрасыванием (англ. round-by-chop) и округление до ближайшего (англ. round-to-nearest). Стандарт IEEE использует округление до ближайшего.

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

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

• Пример: десятичтое число ${\displaystyle (9{,}4)_{10}=(1001{,}(0110))_{2}}$ может быть представлено в виде $${\displaystyle +1{,}\underbrace {0010110011001100110011001100110011001100110011001100} _{\text{52 бита}}110\ldots \times 2^{3}}$$

Поскольку 53-й бит справа от (двоичной) запятой равен 1 с последующим ненулевым битом, правило округления к ближайшему требует округление вверх, то есть, добавлению 1 к 52-му биту. Таким образом, представлением ${\displaystyle 9{,}4}$ в виде нормализованного числа с плавающей запятой в стандарте IEEE будет $${\displaystyle fl(9{,}4)=1{,}0010110011001100110011001100110011001100110011001101\times 2^{3}.}$$

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

Это представление получается отбрасыванием бесконечного хвоста $${\displaystyle 0{,}(1100)\times 2^{-52}\times 2^{3}=0{,}(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}}$.

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

1. Округление отбрасыванием: ${\displaystyle \epsilon _{\text{mach}}=\beta ^{1-p}}$
2. Округление к ближайшему: ${\displaystyle \epsilon _{\text{mach}}={\tfrac {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|}}\leqslant {\frac {\beta }{1}}\times \beta ^{-p}=\beta ^{1-p}}$. Поэтому, ${\displaystyle \epsilon =\beta ^{1-p}}$ для округления отбрасыванием. Доказательство для округления к ближайшему аналогично.

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

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

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

• Например, сложение ${\displaystyle 1}$ и ${\displaystyle 2^{-53}}$ чисел двойной точности в IEEE формате,
  ${\displaystyle {\begin{aligned}1{,}00\ldots 0\times 2^{0}+1{,}00\ldots 0\times 2^{-53}&=1{,}\underbrace {00\ldots 0} _{\text{52 бита}}\times 2^{0}+0{,}\underbrace {00\ldots 0} _{\text{52 бита}}1\times 2^{0}\\&=1{,}\underbrace {00\ldots 0} _{\text{52 бита}}1\times 2^{0}.\end{aligned}}}$
  Результат будет сохранён как ${\displaystyle 1{,}\underbrace {00\ldots 0} _{\text{52 бита}}\times 2^{0}}$, поскольку в стандарте IEEE будет использовано округление к ближайшему. Таким образом, ${\displaystyle 1+2^{-53}}$ равно ${\displaystyle 1}$ в стандарте IEEE чисел двойной точности и ошибка округления равна ${\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 }$ обрезается.

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

• Например, вычитание ${\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 бит}}\times 2^{0}-\underbrace {0{,}00\ldots 01} _{\text{60 бит}}\times 2^{0}\\&=\underbrace {0{,}11\ldots 1} {\text{60 бит}}\times 2^{0}.\end{aligned}}}$$ Результат сохраняется как ${\displaystyle \underbrace {1{,}00\ldots 0} _{\text{53 бит}}\times 2^{0}}$, поскольку используется округление стандарта IEEE к ближайшему. Таким образом, ${\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]. Например, вычисление ${\displaystyle f(x)={\sqrt {1+x}}-1}$ с помощью «очевидного» метода неустойчиво около ${\displaystyle x=0}$, поскольку получаем большую ошибку в результате вычитания двух близких величин, в то время как эквивалентное выражение ${\displaystyle \textstyle {f(x)={\frac {x}{{\sqrt {1+x}}+1}}}}$ устойчиво^[12].

К сожалению, не для всех задач можно найти устойчивые алгоритмы. Рассмотрим пример, придуманный Милнером. Пусть дана последовательность

${\displaystyle x_{0}=2,x_{1}=-4;x_{n+2}=111-{\tfrac {1130}{x_{n+1}}}+{\tfrac {3000}{x_{n+1}x_{n}}}}$

Можно доказать, что эта последовательность имеет предел при ${\displaystyle n\to +\infty }$, равный 6. Однако при вычислениях с плавающей точкой, какая бы точность ни была выбрана (можно выделять произвольно большое количество бит под мантиссу и экспоненту), вычисляемые значения ${\displaystyle x_{n}}$ стремятся к 100^[13].

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

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

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

• Усечение числа
• Округление
• Число с плавающей запятой
• Алгоритм Кэхэна
• Машинный эпсилон
• Полином Уилкинсона

• Matt Parker. Humble Pi: When Math Goes Wrong in the Real World. — Riverhead Books, 2021. — ISBN 978-0593084694.

• Roundoff Error at MathWorld.
• Goldberg, David (Март 1991). What Every Computer Scientist Should Know About Floating-Point Arithmetic (PDF). ACM Computing Surveys. 23 (1): 5—48. doi:10.1145/103162.103163. S2CID 222008826. Дата обращения: 20 января 2016. ([1], [2])
• 20 Famous Software Disasters
• Rounding Calculator