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

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

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

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

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

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

1. Согласно формальному определению — использованному проф. Деммелем, LAPACK и Scilab . Он представляет собой наибольшую относительную ошибку округления в режиме округления к ближайшему . Обоснование заключается в том, что ошибка округления составляет половину интервала вверх до следующего представимого числа с конечной точностью. Таким образом, относительная ошибка округления для числа равна . В этом контексте наибольшая относительная ошибка возникает, когда , и равна , поскольку действительные числа в нижней половине интервала 1,0 ~ 1,0+ULP(1) округляются вниз до 1,0, а числа в верхней половине интервала округляются вверх до 1,0+ULP(1). Здесь мы используем определение ULP(1) ( единица на последнем месте ) как положительную разность между 1,0 (которое может быть представлено точно с конечной точностью) и следующим большим числом, представимым с конечной точностью. ${\displaystyle x}$ ${\displaystyle [interval/2]/x}$ ${\displaystyle x=1.0}$ ${\displaystyle [ULP(1.0)/2]/1.0}$
2. Согласно общепринятому определению — используемому профессором Хайэмом; применяемому в языковых константах в Ada , C , C++ , Fortran , MATLAB , Mathematica , Octave , Pascal , Python и Rust и т. д., и определенному в учебниках, таких как « Numerical Recipes » Пресса и др . Он представляет собой наибольший относительный интервал между двумя ближайшими числами с конечной точностью или наибольшую ошибку округления в режиме round-by-chop . Обоснование заключается в том, что относительный интервал для числа равен , где — расстояние до следующего представимого числа с конечной точностью. В этом контексте наибольший относительный интервал возникает, когда , и — интервал между 1,0 (которое может быть представлено точно с конечной точностью) и следующим большим представимым числом с плавающей точкой. Этот интервал равен ULP(1) . ${\displaystyle x}$ ${\displaystyle [interval]/x}$ ${\displaystyle interval}$ ${\displaystyle x=1.0}$

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

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

Для определения значения из этого определения необходимы некоторые сведения. Система с плавающей точкой характеризуется основанием , которое также называется основанием, , и точностью , т. е. числом цифр основания мантиссы ( включая любой ведущий неявный бит). Все числа с одинаковой экспонентой , , имеют интервал, . Интервал изменяется в числах, которые являются совершенными степенями ; интервал со стороны большей величины в раз больше интервала со стороны меньшей величины. ${\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, т.е. (где b — основание системы с плавающей точкой, а p — точность), а округление единицы равно u = ε / 2, предполагая режим округления до ближайшего значения , и u = ε , предполагая режим округления по частям . ${\displaystyle b^{-(p-1)}}$

Распространенность этого определения коренится в его использовании в стандарте 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, мы можем использовать это для вычисления машинного эпсилона за постоянное время. Например, в C: ${\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 ; double d64 ; } dbl_64 ;        double machine_eps ( double value ) { dbl_64 s ; s . d64 = value ; s . i64 ++ ; return s . d64 - value ; }             

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

 возврат ( 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. Десятичное число с плавающей точкой — использование коллекции компиляторов GNU (GCC)
3. «Основные вопросы арифметики с плавающей точкой и анализ ошибок». Калифорнийский университет в Беркли. 21 октября 1999 г. Получено 11 июня 2022 г. Расстояние между 1 и следующим большим числом с плавающей точкой равно 2*macheps.
4. "Основные вопросы арифметики с плавающей точкой и анализ ошибок". 21 октября 1999 г. Получено 11 апреля 2013 г.
5. "LAPACK User's Guide Third Edition". 22 августа 1999 г. Получено 9 марта 2012 г.
6. «Дэвид Голдберг: Что каждый специалист по информатике должен знать об арифметике с плавающей точкой, ACM Computing Surveys, том 23, № 1, март 1991 г.» (PDF) . Получено 11 апреля 2013 г.
7. "Документация Scilab - number_properties - определение параметров с плавающей точкой" . Получено 11 апреля 2013 г. .
8. Джонс, Дерек М. (2009). Новый стандарт языка Си — экономический и культурный комментарий (PDF) . стр. 377.
9. "float.h reference at cplusplus.com" . Получено 11 апреля 2013 г. .
10. "std::numeric_limits reference at cplusplus.com" . Получено 11 апреля 2013 г. .
11. "Документация Python - Системно-специфические параметры и функции" . Получено 11 апреля 2013 г.
12. Расширенный Паскаль ISO 10206:1990 (Технический отчет). Значение epsreal должно быть результатом вычитания 1,0 из наименьшего значения типа real, которое больше 1,0.
13. "Документация Mathematica: $MachineEpsilon" . Получено 11 апреля 2013 г.
14. "Matlab documentation - eps - Floating-point relative precision". Архивировано из оригинала 2013-08-07 . Получено 11 апреля 2013 .
15. "Octave documentation - eps function" . Получено 11 апреля 2013 г. .
16. Хайэм, Николас (2002). Точность и устойчивость численных алгоритмов (2-е изд.) . SIAM. стр. 27–28.
17. Квартерони, Альфио ; Сакко, Риккардо; Салери, Фаусто (2000). Численная математика (PDF) . Спрингер. п. 49. ИСБН 0-387-98959-5. Архивировано из оригинала (PDF) 2017-11-14 . Получено 2013-04-11 .
18. Пресс, Уильям Х.; Тьюкольски, Сол А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. Численные рецепты . стр. 890.
19. Энгельн-Мюлльгес, Гизела; Ройтер, Фриц (1996). Нумерик-алгоритмы . п. 6. ISBN 3-18-401539-4.
20. "Значение машинного эпсилона для альтернативного доказательства стандарта двойной точности IEEE с использованием относительной погрешности". 12 октября 2020 г. Получено 5 мая 2022 г.

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

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

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