Машина эпсилон

Верхняя граница относительной ошибки из-за округления в арифметике с плавающей запятой

Машинный эпсилон или машинная точность — это верхняя граница относительной ошибки аппроксимации из-за округления в арифметике с плавающей запятой . Это значение характеризует компьютерную арифметику в области численного анализа и, в более широком смысле, в области вычислительной техники . Величина также называется мачепс и имеет символы греческого эпсилон . ${\displaystyle \varepsilon }$

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

Значения стандартной аппаратной арифметики

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

1. Согласно формальному определению, используемому профессором Деммелем, LAPACK и Scilab.
2. Согласно широко распространенному варианту определения, используемому профессором Хайэмом; стандарт ISO C; Константы языков Ada , C , C++ , Python и Rust ; Mathematica , MATLAB и Octave ; и различные учебники

Формальное определение

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

Чтобы определить значение из этого определения, необходима некоторая предыстория. Система счисления с плавающей запятой характеризуется системой счисления , которая также называется базой, и точностью , т.е. количеством цифр системы счисления мантиссы (включая любой ведущий неявный бит). Все числа с одинаковым показателем , имеют интервал . Расстояние меняется в числах, которые являются совершенными степенями ; расстояние на стороне большей величины в раз больше расстояния на стороне меньшей величины. ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle e}$ ${\displaystyle b^{e-(p-1)}}$ ${\displaystyle b}$ ${\displaystyle b}$

Поскольку машинный эпсилон является границей относительной ошибки, достаточно рассматривать числа с показателем степени . Также достаточно рассмотреть положительные числа. Для обычного округления до ближайшего абсолютная ошибка округления составляет не более половины интервала или . Это значение является максимально возможным числителем относительной ошибки. Знаменателем относительной ошибки является округляемое число, которое должно быть как можно меньшим, чтобы относительная ошибка была большой . Поэтому наихудшая относительная ошибка возникает, когда округление применяется к числам вида где находится между и . Все эти числа округляются до с относительной погрешностью . Максимум возникает, когда он находится в верхнем конце своего диапазона. В знаменателе пренебрежимо мало по сравнению с числителем, поэтому для удобства его оставляют и принимают просто за машинный эпсилон. Как было показано здесь, относительная ошибка наибольшая для чисел, которые округляются до , поэтому машинное эпсилон также называется единичным округлением , что примерно означает «максимальную ошибку, которая может возникнуть при округлении до единичного значения». ${\displaystyle e=0}$ ${\displaystyle b^{-(p-1)}/2}$ ${\displaystyle 1+a}$ ${\displaystyle a}$ ${\displaystyle 0}$ ${\displaystyle b^{-(p-1)}/2}$ ${\displaystyle 1}$ ${\displaystyle a/(1+a)}$ ${\displaystyle a}$ ${\displaystyle 1+a}$ ${\displaystyle b^{-(p-1)}/2}$ ${\displaystyle 1}$

Таким образом, максимальное расстояние между нормализованным числом с плавающей запятой и соседним нормализованным числом равно . ^[3] ${\displaystyle x}$ ${\displaystyle 2\varepsilon |x|}$

Арифметическая модель

Численный анализ использует машинный эпсилон для изучения последствий ошибки округления. Реальные ошибки машинной арифметики слишком сложны, чтобы их можно было изучать напрямую, поэтому вместо этого используется следующая простая модель. Стандарт арифметики IEEE гласит, что все операции с плавающей запятой выполняются так, как если бы можно было выполнить операцию с бесконечной точностью, а затем результат округляется до числа с плавающей запятой. Предположим, (1) — числа с плавающей запятой, (2) — арифметическая операция над числами с плавающей запятой, такая как сложение или умножение, и (3) — операция бесконечной точности. Согласно стандарту компьютер рассчитывает: ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \bullet }$ ${\displaystyle \circ }$

${\displaystyle x\bullet y={\mbox{round}}(x\circ y)}$

По смыслу машинного эпсилона относительная ошибка округления не превышает по величине машинного эпсилона, поэтому:

${\displaystyle x\bullet y=(x\circ y)(1+z)}$

где по абсолютной величине не более или u . Можно обратиться к книгам Деммеля и Хайэма, указанным в ссылках, чтобы увидеть, как эта модель используется для анализа ошибок, скажем, исключения Гаусса. ${\displaystyle z}$ ${\displaystyle \varepsilon }$

Варианты определений

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

Формальное определение машинного эпсилона использовано профессором Джеймсом Деммелем в сценариях лекций, ^[4] в пакете линейной алгебры LAPACK , ^{[5] в} исследовательских работах по числовым вычислениям ^[6] и в некоторых программах для научных вычислений. ^[7] Большинство специалистов по численному анализу используют слова « машинный эпсилон» и «единичное округление» как синонимы этого значения.

Это альтернативное определение гораздо более распространено за пределами академических кругов: машинный эпсилон — это разница между 1 и следующим по величине числом с плавающей запятой .

Согласно этому определению, равно значению единицы в последнем месте относительно 1, т. е. (где — основа системы с плавающей запятой и — точность), а округление единицы равно u , предполагая режим округления до ближайшего , и u , предполагая , что по кусочкам . ${\displaystyle \varepsilon }$ ${\displaystyle b^{-(p-1)}}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle \,=\varepsilon /2}$ ${\displaystyle \,=\varepsilon }$

Распространенность этого определения коренится в его использовании в стандарте ISO C для констант, относящихся к типам с плавающей запятой ^{[8] [9]} и соответствующих констант в других языках программирования. ^{[10] [11] [12]} Он также широко используется в программном обеспечении для научных вычислений, ^{[13] [14] [15]} , а также в числовой и вычислительной литературе. ^{[16] [17] [18] [19]}

Как определить машинный эпсилон

Там, где стандартные библиотеки не предоставляют заранее вычисленные значения (как < float.h > делает с FLT_EPSILON, DBL_EPSILONа LDBL_EPSILONдля C и < limits > делает с в C++), лучший способ определить машинный эпсилон — обратиться к таблице выше и использовать соответствующая формула мощности. Эпсилон вычислительной машины часто преподается в качестве упражнения из учебника. В следующих примерах машинный эпсилон вычисляется в смысле интервала между числами с плавающей запятой в 1, а не в смысле округления единицы.std::numeric_limits<T>::epsilon()

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

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

В строгом смысле термин « машинный эпсилон» означает точность, непосредственно поддерживаемую процессором (или сопроцессором), а не некоторую точность, поддерживаемую конкретным компилятором для конкретной операционной системы, если только не известно, что он использует лучший формат. ${\displaystyle 1+\varepsilon }$ ${\displaystyle 1+\varepsilon }$

Форматы с плавающей запятой IEEE 754 обладают свойством, которое при переинтерпретации как целое число с дополнением до двух одинаковой ширины, они монотонно увеличиваются по положительным значениям и монотонно уменьшаются по отрицательным значениям (см. двоичное представление 32-битных чисел с плавающей запятой ). У них также есть свойство , и (где находится вышеупомянутая целочисленная интерпретация ). В языках, которые допускают каламбур типов и всегда используют IEEE 754–1985, мы можем использовать это для вычисления машинного эпсилона за постоянное время. Например, в С: ${\displaystyle 0<|f(x)|<\infty }$ ${\displaystyle |f(x+1)-f(x)|\geq |f(x)-f(x-1)|}$ ${\displaystyle f(x)}$ ${\displaystyle x}$

typedef Union { long long i64 ; двойной д64 ; } dbl_64 ;        двойной Machine_eps ( двойное значение ) { dbl_64 s ; с . d64 = значение ; с . я64 ++ ; вернуть с . d64 – значение ; }             

Это даст результат того же знака, что и значение. Если всегда желателен положительный результат, оператор возврата Machine_eps можно заменить на:

 return ( s . i64 < 0 ? значение - s . d64 : s . d64 - значение );           

Пример на Python:

def  MachineEpsilon ( func = float ):  Machine_epsilon  =  Func ( 1 )  while  Func ( 1 ) + Machine_epsilon  !=  Func ( 1 ):  Machine_epsilon_last  =  Machine_epsilon  Machine_epsilon  =  Func ( Machine_epsilon )  /  Func ( 2 )  return  Machine_epsilon_last

64-битные двойные значения дают 2.220446e-16, что, как и ожидалось, равно ^2–52 .

Приближение

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

эпсилон = 1,0;при этом (1,0 + 0,5 * эпсилон) ≠ 1,0: эпсилон = 0,5 * эпсилон

Машинный эпсилон также можно просто вычислить как двойку в отрицательной степени количества битов, используемых для мантиссы. ${\textstyle \varepsilon _{\text{mach}}}$

$${\displaystyle \varepsilon _{\text{mach}}\ =\ 2^{-{\text{bits used for magnitude of mantissa}}}}$$

Связь с абсолютной относительной ошибкой

Если это машинное представление числа , то абсолютная относительная ошибка представления равна ^[20] ${\textstyle y}$ ${\textstyle x}$ ${\textstyle \left|{\dfrac {x-y}{x}}\right|\leq \varepsilon _{\text{mach}}.}$

Доказательство

Следующее доказательство ограничено положительными числами и машинными представлениями с использованием метода round-by-chop .

Если это положительное число, которое мы хотим представить, оно будет находиться между номером машины ниже и номером машины выше . ${\textstyle x}$ ${\textstyle x_{b}}$ ${\textstyle x}$ ${\textstyle x_{u}}$ ${\textstyle x}$

Если , где – количество битов, используемых для величины мантиссы , то: ${\textstyle x_{b}=\left(1.b_{1}b_{2}\ldots b_{m}\right)_{2}\times 2^{k}}$ ${\textstyle m}$

$${\displaystyle {\begin{aligned}x_{u}&=\left[(1.b_{1}b_{2}\ldots b_{m})_{2}+(0.00\ldots 1)_{2}\right]\times 2^{k}\\&=\left[(1.b_{1}b_{2}\ldots b_{m})_{2}+2^{-m}\right]\times 2^{k}\\&=(1.b_{1}b_{2}\ldots b_{m})_{2}\times 2^{k}+2^{-m}\times 2^{k}\\&=(1.b_{1}b_{2}\ldots b_{m})_{2}\times 2^{k}+2^{-m+k}.\end{aligned}}}$$

Поскольку представление будет либо или , ${\textstyle x}$ ${\textstyle x_{b}}$ ${\textstyle x_{u}}$

$${\displaystyle {\begin{aligned}\left|x-y\right|&\leq \left|x_{b}-x_{u}\right|\\&=2^{-m+k}\end{aligned}}}$$

$${\displaystyle {\begin{aligned}\left|{\frac {x-y}{x}}\right|&\leq {\frac {2^{-m+k}}{x}}\\&\leq {\frac {2^{-m+k}}{x_{b}}}\\&={\frac {2^{-m+k}}{(1\cdot b_{1}b_{2}\ldots b_{m})_{2}2^{k}}}\\&={\frac {2^{-m}}{(1\cdot b_{1}b_{2}\ldots b_{m})_{2}}}\\&\leq 2^{-m}=\varepsilon _{\text{mach}}.\end{aligned}}}$$

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

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

• Плавающая запятая , общее обсуждение проблем точности в арифметике с плавающей запятой.
• Юнит на последнем месте (ULP)

Примечания и ссылки

1. Плавающие типы — использование коллекции компиляторов GNU (GCC)
2. Decimal Float - Использование коллекции компиляторов GNU (GCC)
3. «Основные проблемы арифметики с плавающей запятой и анализа ошибок» . Калифорнийский университет, Беркли. 21 октября 1999 года . Проверено 11 июня 2022 г. Расстояние между 1 и следующим большим числом с плавающей запятой составляет 2*мачепс.
4. «Основные проблемы арифметики с плавающей запятой и анализа ошибок» . 21 октября 1999 года . Проверено 11 апреля 2013 г.
5. «Руководство пользователя LAPACK, третье издание» . 22 августа 1999 года . Проверено 9 марта 2012 г.
6. «Дэвид Голдберг: Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой, Обзоры вычислений ACM, том 23, № 1, март 1991 г.» (PDF) . Проверено 11 апреля 2013 г.
7. «Документация Scilab — Number_properties — определение параметров с плавающей запятой» . Проверено 11 апреля 2013 г.
8. Джонс, Дерек М. (2009). Новый стандарт C — экономический и культурный комментарий (PDF) . п. 377.
9. "Ссылка на float.h на cplusplus.com" . Проверено 11 апреля 2013 г.
10. "Ссылка на std::numeric_limits на cplusplus.com" . Проверено 11 апреля 2013 г.
11. «Документация Python — специфичные для системы параметры и функции» . Проверено 11 апреля 2013 г.
12. Расширенный Pascal ISO 10206:1990 (Технический отчет). Значение epsreal должно быть результатом вычитания 1,0 из наименьшего значения реального типа, превышающего 1,0.
13. «Документация Mathematica: $MachineEpsilon» . Проверено 11 апреля 2013 г.
14. «Документация Matlab — eps — Относительная точность чисел с плавающей запятой» . Архивировано из оригинала 7 августа 2013 г. Проверено 11 апреля 2013 г.
15. «Документация Octave — функция eps» . Проверено 11 апреля 2013 г.
16. Хайэм, Николас (2002). Точность и устойчивость численных алгоритмов (2-е изд.) . СИАМ. стр. 27–28.
17. Квартерони, Альфио ; Сакко, Риккардо; Салери, Фаусто (2000). Численная математика (PDF) . Спрингер. п. 49. ИСБН 0-387-98959-5. Архивировано из оригинала (PDF) 14 ноября 2017 г. Проверено 11 апреля 2013 г.
18. Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. Численные рецепты . п. 890.
19. Энгельн-Мюлльгес, Гизела; Ройтер, Фриц (1996). Нумерик-алгоритмы . п. 6. ISBN 3-18-401539-4.
20. «Машинное значение Эпсилон для альтернативного доказательства стандарта двойной точности IEEE с использованием относительной ошибки» . 12 октября 2020 г. Проверено 5 мая 2022 г.

• Андерсон, Э.; Руководство пользователя LAPACK, Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, третье издание, 1999 г.
• Коди, Уильям Дж.; MACHAR: программа для динамического определения параметров машины, Транзакции ACM в математическом программном обеспечении, Vol. 14(4), 1988, 303–311.
• Бессет, Дидье Х.; Объектно-ориентированная реализация численных методов, Морган и Кауфманн, Сан-Франциско, Калифорния, 2000.
• Деммель, Джеймс В. , Прикладная численная линейная алгебра, Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, 1997.
• Хайэм, Николас Дж.; Точность и стабильность числовых алгоритмов, Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, второе издание, 2002 г.
• Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; и Фланнери, Брайан П.; Численные рецепты на Фортране 77 , 2-е изд., гл. 20.2, стр. 881–886.
• Форсайт, Джордж Э.; Малькольм, Майкл А.; Молер, Клив Б.; «Компьютерные методы математических вычислений», Прентис-Холл, ISBN 0-13-165332-6 , 1977 г. 

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

• MACHAR, процедура (на C и Fortran) для «динамического вычисления машинных констант» (алгоритм ACM 722).
• Диагностика точности вычислений с плавающей запятой. Реализация MACHAR в Component Pascal и Oberon на основе версии MACHAR для Fortran 77, опубликованной в Numerical Recipes (Press et al., 1992).