Как найти машинное эпсилон

From Wikipedia, the free encyclopedia

Machine epsilon or machine precision is an upper bound on the relative approximation error due to rounding in floating point arithmetic. This value characterizes computer arithmetic in the field of numerical analysis, and by extension in the subject of computational science. The quantity is also called macheps and it has the symbols Greek epsilon .

There are two prevailing definitions. In numerical analysis, machine epsilon is dependent on the type of rounding used and is also called unit roundoff, which has the symbol bold Roman u. However, by a less formal, but more widely-used definition, machine epsilon is independent of rounding method and may be equivalent to u or 2u.

Values for standard hardware arithmetics[edit]

The following table lists machine epsilon values for standard floating-point formats. Each format uses round-to-nearest.

IEEE 754 — 2008	Common name	C++ data type	Base	Precision	Machine epsilon[a]	Machine epsilon[b]
binary16	half precision	N/A	2	11 (one bit is implicit)	2−11 ≈ 4.88e-04	2−10 ≈ 9.77e-04
binary32	single precision	float	2	24 (one bit is implicit)	2−24 ≈ 5.96e-08	2−23 ≈ 1.19e-07
binary64	double precision	double	2	53 (one bit is implicit)	2−53 ≈ 1.11e-16	2−52 ≈ 2.22e-16
	extended precision, long double	_float80[1]	2	64	2−64 ≈ 5.42e-20	2−63 ≈ 1.08e-19
binary128	quad(ruple) precision	_float128[1]	2	113 (one bit is implicit)	2−113 ≈ 9.63e-35	2−112 ≈ 1.93e-34
decimal32	single precision decimal	_Decimal32[2]	10	7	5 × 10−7	10−6
decimal64	double precision decimal	_Decimal64[2]	10	16	5 × 10−16	10−15
decimal128	quad(ruple) precision decimal	_Decimal128[2]	10	34	5 × 10−34	10−33

Formal definition[edit]

Rounding is a procedure for choosing the representation of a real number in a floating point number system. For a number system and a rounding procedure, machine epsilon is the maximum relative error of the chosen rounding procedure.

Some background is needed to determine a value from this definition. A floating point number system is characterized by a radix which is also called the base, , and by the precision , i.e. the number of radix digits of the significand (including any leading implicit bit). All the numbers with the same exponent, , have the spacing, . The spacing changes at the numbers that are perfect powers of ; the spacing on the side of larger magnitude is times larger than the spacing on the side of smaller magnitude.

Since machine epsilon is a bound for relative error, it suffices to consider numbers with exponent . It also suffices to consider positive numbers. For the usual round-to-nearest kind of rounding, the absolute rounding error is at most half the spacing, or . This value is the biggest possible numerator for the relative error. The denominator in the relative error is the number being rounded, which should be as small as possible to make the relative error large. The worst relative error therefore happens when rounding is applied to numbers of the form where is between and . All these numbers round to with relative error . The maximum occurs when is at the upper end of its range. The in the denominator is negligible compared to the numerator, so it is left off for expediency, and just is taken as machine epsilon. As has been shown here, the relative error is worst for numbers that round to , so machine epsilon also is called unit roundoff meaning roughly «the maximum error that can occur when rounding to the unit value».

Thus, the maximum spacing between a normalised floating point number, , and an adjacent normalised number is .^[3]

Arithmetic model[edit]

Numerical analysis uses machine epsilon to study the effects of rounding error. The actual errors of machine arithmetic are far too complicated to be studied directly, so instead, the following simple model is used. The IEEE arithmetic standard says all floating-point operations are done as if it were possible to perform the infinite-precision operation, and then, the result is rounded to a floating-point number. Suppose (1) , are floating-point numbers, (2) is an arithmetic operation on floating-point numbers such as addition or multiplication, and (3) is the infinite precision operation. According to the standard, the computer calculates:

By the meaning of machine epsilon, the relative error of the rounding is at most machine epsilon in magnitude, so:

where in absolute magnitude is at most or u. The books by Demmel and Higham in the references can be consulted to see how this model is used to analyze the errors of, say, Gaussian elimination.

Variant definitions[edit]

The IEEE standard does not define the terms machine epsilon and unit roundoff, so differing definitions of these terms are in use, which can cause some confusion.

The formal definition for machine epsilon is the one used by Prof. James Demmel in lecture scripts,^[4] the LAPACK linear algebra package,^[5] numerics research papers^[6] and some scientific computing software.^[7] Most numerical analysts use the words machine epsilon and unit roundoff interchangeably with this meaning.

This alternative definition is much more widespread outside academia: machine epsilon is the difference between 1 and the next larger floating point number.

By this definition, equals the value of the unit in the last place relative to 1, i.e. (where is the base of the floating point system and is the precision) and the unit roundoff is u, assuming round-to-nearest mode, and u, assuming round-by-chop.

The prevalence of this definition is rooted in its use in the ISO C Standard for constants relating to floating-point types^[8][9] and corresponding constants in other programming languages.^[10][11][12] It is also widely used in scientific computing software,^[13][14][15] and in the numerics and computing literature.^{[16][17][18][19]}

How to determine machine epsilon[edit]

Where standard libraries do not provide precomputed values (as <float.h> does with FLT_EPSILON, DBL_EPSILON and LDBL_EPSILON for C and <limits> does with std::numeric_limits<T>::epsilon() in C++), the best way to determine machine epsilon is to refer to the table, above, and use the appropriate power formula. Computing machine epsilon is often given as a textbook exercise. The following examples compute machine epsilon in the sense of the spacing of the floating point numbers at 1 rather than in the sense of the unit roundoff.

Note that results depend on the particular floating-point format used, such as float, double, long double, or similar as supported by the programming language, the compiler, and the runtime library for the actual platform.

Some formats supported by the processor might not be supported by the chosen compiler and operating system. Other formats might be emulated by the runtime library, including arbitrary-precision arithmetic available in some languages and libraries.

In a strict sense the term machine epsilon means the accuracy directly supported by the processor (or coprocessor), not some accuracy supported by a specific compiler for a specific operating system, unless it’s known to use the best format.

IEEE 754 floating-point formats have the property that, when reinterpreted as a two’s complement integer of the same width, they monotonically increase over positive values and monotonically decrease over negative values (see the binary representation of 32 bit floats). They also have the property that , and (where is the aforementioned integer reinterpretation of ). In languages that allow type punning and always use IEEE 754-1985, we can exploit this to compute a machine epsilon in constant time. For example, in C:

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;
}

Example in 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

This will give a result of the same sign as value. If a positive result is always desired, the return statement of machine_eps can be replaced with:

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

64-bit doubles give 2.220446e-16, which is 2⁻⁵² as expected.

Approximation[edit]

The following simple algorithm can be used to approximate^{[clarification needed]} the machine epsilon, to within a factor of two (one order of magnitude) of its true value, using a linear search.

epsilon = 1.0;

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

The machine epsilon, can also simply be calculated as two to the negative power of the number of bits used for the mantissa.

Relationship to absolute relative error[edit]

If is the machine representation of a number then the absolute relative error in the representation is ^[20]

Proof[edit]

The following proof is limited to positive numbers and machine representations using round-by-chop.

If is a positive number we want to represent, it will be between a machine number below and a machine number above .

If , where is the number of bits used for the magnitude of the significand, then:

Since the representation of will be either or ,

Although this proof is limited to positive numbers and round-by-chop, the same method can be used to prove the inequality in relation to negative numbers and round-to-nearest machine representations.

See also[edit]

• Floating point, general discussion of accuracy issues in floating point arithmetic
• Unit in the last place (ULP)

Notes and references[edit]

External links[edit]

• MACHAR, a routine (in C and Fortran) to «dynamically compute machine constants» (ACM algorithm 722)
• Diagnosing floating point calculations precision, Implementation of MACHAR in Component Pascal and Oberon based on the Fortran 77 version of MACHAR published in Numerical Recipes (Press et al., 1992).

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

Как
известно, существует 2 вида погрешностей
вычисления — абсолютная и относительная
(Ошибки
вычислений).
Под относительной погрешностью понимается
отношение

где
–
значение, полученное при округлении, а
—
точное значение вычислений.

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

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

.

Величину
принято
называть машинным
эпсилоном
(machine
epsilon).
Таким образом можно утверждать, что при
округлении дробного числа ближайшим к
нему числом с плавающей точкой
относительная погрешность округления
не превосходит машинного эпсилона.

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

Стандарт
IEEE

Существует
два разных стандарта IEEE для чисел с
плавающей точкой. IEEE 754 — двоичный стандарт
и требует, чтобы
,
а
для
одинарной точности (single)
и
для
двойной точности (double).
Также в стандарте IEEE 754 точно обговорено
использование битов при представлении
чисел в одинарной и двойной точностях.
В стандарте IEEE 854
может
принимать значение 10 или 2. Также ничего
не говорится о распределении битов
между мантиссой и степенью.

Понятие
стандарт
IEEE
используется для обозначения свойств,
присущих обоим из перечисленных
стандартов.

Основание
степени

Выбор
в качестве основания степени 10 не требует
особых разъяснений. Десятичная система
— система, привычная для человека. В
случае двоичной системы стоит обсудить
некоторые достоинства, присущие ей. Мы
договорились использовать нормализованные
формы чисел. Если
,
то в старшей позиции может стоять только
1. Это даёт нам возможность не хранить
эту единицу в памяти и тем самым получить
дополнительный бит для мантиссы. В этом
случае принято говорить, что стандарт
использует скрытый
бит
(hidden
bit).

Вернёмся
к вопросу о представлении нуля в
нормализованной форме. Ноль соответствует
нулевой мантиссе и степени
.
Таким образом ноль представляется в
виде
.

Точность представления

Стандарт
IEEE предлагает 4 разных точности: одинарная
(single),
двойная (double),
одинарная расширенная (single-extended)
и двойная расширенная (double-extended).
IEEE 754 жёстко обговаривают число бит
одинарной и двойной точности. Это
означает, что на всех ЭВМ, поддерживающих
IEEE 754, количество бит в представлении
чисел с одинарной точностью и с двойной
точностью фиксированы. Количество бит
расширенных точностей жёстко не
фиксируется. Расширенные форматы
призваны хоть немного увеличить
количество бит на мантиссу и на показатель
степени. Ниже представлена таблица
параметров различных точностей в
стандарте IEEE.

Приведём
ещё одну таблицу для наглядности.

Соседние файлы в папке вычМатКурсач

• #
• #
• #
• #
• #
• #

Машинный эпсилон — это наименьшее число eps, такое что eps+1=1.

Это заведомо неправильное определение. Нужно хотя бы заменить «наименьшее» на «наибольшее».
[Слово «наименьшее» будет фигурировать в таком определении машинного :
Машинное — это такое минимальное положительное число, которое при прибавлении к 1 даёт следующее за 1 число, т.е. наименьшее большее 1.]

[Дальше для случая нормализованных чисел.]

Если машинное определяется как максимальная предельная относительная погрешность представления числа, то оно равно , где — число отводимых для дробной части числа бит (т.е. без целой единицы). Для binary32 (Single) равно 23 ( приближенно равно ), для binary64 (Double) равно 52 ( приближенно равно ). В этом определении предполагается, что при округлении погрешность не более половины младшего бита.

Если машинное определяется как разность между 1 и ближайшему к нему числу большему 1, то оно равно . Такое определение eps используется в Scilab [см «epsilon (floating-point relative accuracy)»], Octave, Matlab (можно проверить, вызвав соответствующую функцию eps).

Вроде так.

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

Содержание

• 1 Значения для стандартной аппаратной арифметики с плавающей запятой
• 2 Формальное определение
• 3 Арифметическая модель
• 4 Определения вариантов
• 5 Как определить машинный эпсилон
  • 5.1 Аппроксимация
• 6 См. Также
• 7 Примечания и ссылки
• 8 Внешние ссылки

Значения для стандартной аппаратной арифметики с плавающей запятой

Следующие значения машинного эпсилон применяются к стандартным форматам с плавающей запятой:

IEEE 754 — 2008	Общепринятое имя	Тип данных C ++	Base b { displaystyle b}	Precision p { displaystyle p}	Машинный эпсилон b — (p — 1) / 2 { displaystyle b ^ {- (p-1)} / 2}	Машинный эпсилон b — (p — 1) { displaystyle b ^ {- (p-1)}}
binary16	половинная точность	Н / Д	2	11 (один бит неявный)	2 ≈ 4.88e-04	2 ≈ 9.77e-04
binary32	одинарная точность	float	2	24 (один бит неявный)	2 ≈ 5.96e-08	2 ≈ 1.19e-07
binary64	двойной точности	double	2	53 (один бит неявный)	2 ≈ 1.11e-16	2 ≈ 2.22e-16
	расширенная точность, long double	_float80	2	64	2 ≈ 5.42e-20	2 ≈ 1.08e-19
binary128	четверная (ruple) точность	_float128	2	113 (один бит неявный)	2 ≈ 9,63e-35	2 ≈ 1,93e-34
decimal32	десятичное число одинарной точности	_Decimal32	10	7	5 × 10	10
decimal64	десятичное с двойной точностью	_Decimal64	10	16	5 × 10	10
decimal128	четверное (ruple) десятичное число с точностью до	_Decimal128	10	34	5 × 10	10

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

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

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

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

Таким образом, максимальный интервал между нормализованным числом с плавающей запятой x { displaystyle x}и соседним нормализованным числом составляет 2 ϵ { displaystyle 2 эпсилон}x | х | { displaystyle | x |}.

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

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

x ∙ y = round (x ∘ y) { displaystyle x bullet y = { t_dv {round}} (x circ y)}

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

x ∙ y = (x ∘ y) (1 + z) { displaystyle x bullet y = (x circ y) (1 + z)}

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

Определения вариантов

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

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

Следующее другое определение гораздо более широко распространено за пределами академических кругов: Машинный эпсилон определяется как разница между 1 и следующим большим числом с плавающей запятой. Согласно этому определению, ϵ { displaystyle epsilon}равняется значению единицы на последнем месте относительно 1, т.е. b — (p — 1) { displaystyle b ^ {- (p-1)}}, а единичное округление равно u= ϵ / 2 { displaystyle = epsilon / 2}, предполагая режим округления до ближайшего. Преобладание этого определения связано с его использованием в стандарте ISO C для констант, относящихся к типам с плавающей запятой, и соответствующих констант в других языках программирования. Он также широко используется в программном обеспечении для научных вычислений, а также в числовой и компьютерной литературе.

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

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

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

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

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

IEEE 754 форматы с плавающей запятой обладают тем свойством, что при повторной интерпретации как целое число с дополнением до двух одинаковой ширины, они монотонно увеличиваются по сравнению с положительными значениями и монотонно уменьшаются по сравнению с отрицательными значениями (см. 32-битные числа с плавающей запятой ). У них также есть свойство 0 < |f(x)| < ∞, and |f(x+1) − f(x)| ≥ |f(x) − f(x−1)| (where f(x) is the aforementioned integer reinterpretation of x). In languages that allow типа punning и всегда использовать IEEE 754-1985, мы можем использовать это для вычисления машинного эпсилон в постоянное время. Например, в C:

typedef union {long long i64; двойной d64; } dbl_64; double machine_eps (двойное значение) {dbl_64 s; s.d64 = значение; s.i64 ++; return s.d64 - значение; }

Результат будет иметь тот же знак, что и значение. Если всегда желателен положительный результат, оператор return для machine_eps можно заменить на:

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

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

Аппроксимация

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

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

См. также

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

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

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

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