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

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

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

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

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

ИЭЭЭ 754 – 2008.	Общее имя	Тип данных С++	База $b$	Точность $p$	Округлительная машина эпсилон $b^{-(p-1)}/2$	Интервальная машина эпсилон $b^{-(p-1)}$
двоичный16	половинная точность	Н/Д	2	11 (один бит неявно)	2 −11 ≈ 4.88e-04	2 −10 ≈ 9.77e-04
двоичный32	одинарная точность	плавать	2	24 (один бит неявно)	2 −24 ≈ 5.96e-08	2 −23 ≈ 1.19e-07
двоичный64	двойная точность	двойной	2	53 (один бит неявно)	2 −53 ≈ 1.11e-16	2 −52 ≈ 2,22е-16
	расширенная точность , длинный двойной	_float80	2	64	2 −64 ≈ 5,42е-20	2 −63 ≈ 1.08e-19
двоичный128	четверная (тройная) точность	_float128	2	113 (один бит неявно)	2 −113 ≈ 9,63е-35	2 −112 ≈ 1,93е-34
десятичное32	десятичная дробь одинарной точности	_Decimal32	10	7	5 × 10 −7	10 −6
десятичная дробь64	десятичная дробь двойной точности	_Decimal64	10	16	5 × 10 −16	10 −15
десятичное128	десятичная точность четырехкратной (тройной) точности	_Decimal128	10	34	5 × 10 −34	10 −33

Формальное определение ( Машина округления эпсилон)

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

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

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

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

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

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

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

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

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

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

Основное определение ( эпсилон интервальной машины)

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

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

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

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

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

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

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

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

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

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

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

typedef union {
  long long i64;
  double d64;
} dbl_64;

double machine_eps (double value)
{
    dbl_64 s;
    s.d64 = value;
    s.i64++;
    return s.d64 - value;
}

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

    return (s.i64 < 0 ? value - s.d64 : s.d64 - value);

Пример на 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 ⁻⁵² как и ожидалось.

Приближение

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

epsilon = 1.0;

while (1.0 + 0.5 * epsilon) ≠ 1.0:
    epsilon = 0.5 * epsilon

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

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

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

Если ${\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}$ — количество битов, используемых для величины мантиссы , тогда:

$${\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}}$,

$${\begin{aligned}\left|x-y\right|&\leq \left|x_{b}-x_{u}\right|\\&=2^{-m+k}\end{aligned}}$$ $${\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)

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

• Андерсон, Э.; Руководство пользователя 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).