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

Question

[Александр Рак]

При реализации алгоритмов вычислительной геометрии, пользуясь книгой Окулова "Программирование в алгоритмах", столкнулся с проблемой использования "магического" числа, а точнее реализация алгоритма в книге подразумевала погрешность в 10^(-3) и меня заинтересовало откуда было взято это число.

Алгоритм проверки равенства:
ЕСЛИ |a - b| <= eps ТО числа равны
ИНАЧЕ числа не равны,
где eps - и есть та самая погрешность.

Answer 1

[Rsa97]

Если речь идёт об абстрактной математике, то надо рассматривать представление плавающего типа (float, double, long double) в конкретной архитектуре. В большинстве случаев используется IEEE 754-1985. Скажем, для float32 в нормализованной форме точность - то есть единица младшего разряда мантиссы - в зависимости от экспоненты может быть от 1.175494351×10⁻³⁸ до 3.402823466×10³⁸.

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

Answer 2

[Андрей]

Один из подходов к определению точности - вести "двойные" вычисления:
ведется обычный счет + в каждой формуле вычисляется погрешность итогового результата (исходя из входных погрешностей операндов и вида операций).
К тому моменту, когда Вы подойдете к сравнению двух чисел a и b - Вам будет достаточно удостовериться, что их интервалы с учетом погрешностей не пересекаются.

Заранее вычислить число eps возможно только в очень простых случаях.
Более того, указывать его фиксированным в общем случае - совершенно неправильно.
А что если Вы вычисляете треугольник со сторонами в миллиметры ?
А что если у Вас угол при вершине всего полградуса ?

Comments

[mrgloom]

а можете пример таких двойных вычислений.

[Андрей]

xplusy.isnet.ru/Files/Files_vuch_mat/Pogr.pdf
или поиском по "Погрешности вычислений"

[Rsa97]

@mrgloom Основные правила - при сложении/вычитании складываются абсолютные погрешности, при умножении/делении складываются относительные погрешности.
10±0.1 м + 20±0.1 м = 30±(0.1+0.1) = 30±0.2 м
10±0.1 м/с * 20±0.5 с = 200±(200*(0.1/10 + 0.5/20)) = 200±7 м

[mrgloom]

а может какие то ссылки на исходники готовых проектов в которых это используется или книги где это описывается? и еще коли вы в этом вопросе разбираетесь может прокомментируете еще и этот вопрос Перемножение матриц на PyCuda рост погрешности?

Answer 3

[mrgloom]

en.wikipedia.org/wiki/Machine_epsilon
What every scientist should know about floating-po...
www.parashift.com/c++-faq/floating-point-arith.html

наверно тут надо использовать std::numeric_limits::epsilon

#include <cmath>  /* for std::abs(double) */

inline bool isEqual(double x, double y)
{
  const double epsilon = /* some small number such as 1e-5 */;
  return std::abs(x - y) <= epsilon * std::abs(x);
  // see Knuth section 4.2.2 pages 217-218
}

Comments

[rafuck]

Кнуту, конечно, виднее, но нам, смертным, иногда хочется, чтобы iEqual(0, 1e-16) возвращало true, а не false.

Answer 4

[DancingOnWater]

Погрешность связана с процедурой измерения.

Применительно к численным вычислениям это означает следущее:
1) Если две различные реализации одного и тогоже схожи (наличествуют большие куски одного и тогоже кода), то точность определяется стандартом чисел, в которых идет вычисления (про это и говорил Rsa97)
2)В противном случае точность оценивается в рамках той задачи, которая решается. Приведу пример на примере решения задач небесной механики.
a) Решается научная задача по моделирования движения небесных тел. Тогда получаемая погрешность = погрешности модели.
б) Решается прикладная задача по вычислению положения спутника. Тогда погрешность = предъявляемым требованиям.

Answer 5

[tsarevfs]

Существуют техники позволяющие точно вычислить eps. Однако, точно проверить число на равенство 0 несколько сложнее. Пусть res - результат выражения, err - погрешность вычислений. Тогда |res| + |err| должно быть < eps. Для того, чтобы обеспечить это приходится использовать длинную арифметику и считать десятки тысяч знаков в числе. Однако в практических задачах математическая точность fp-вычислений важна не часто.

Comments

[DancingOnWater]

Учет 4-5 порядок малости при интегрировании на 10 000 шагов и все прелести точности вычислений как на ладони

Answer 6

[KOLANICH]

во всех нормальных ЯП есть константа, обычно зовётся EPS или EPSILON
А в принципе вычислить можно
Числа с плавающей точкой - это мантисса и экспонента
тебе нужна самая маленькая экспонента и самая маленькая мантисса - это и будет эпсилоном
но для этого нужно знать, как хранятся в памяти
проще использовать константу, тем паче что она одинакова для всех ЯП, использующих "железную" реализацию чисел с плавающей точкой

Comments

[tsarevfs]

важно то, что машинный эпсилон применим только отдельным элементарным операциям. (0.1 + 0.2 - 0.3) * 1e17 > 1 == True. Для сложных выражений, для определения точного результата, придется считать с повышенной точностью.

[KOLANICH]

Почитал комменты выше и понял, что речь идёт не о машинном эпсилоне, а о погрешности результата вычисления A-B, с которой и надо сравнивать. Если A и B вычисляются как результат функции .... то их погрешности хрен определишь, ведь на каждой арифметической операции вносится новая погрешность.

Answer 7

[afiskon]

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

Answer 8

[rafuck]

Обычно правильней вычислять относительную погрешность:
|a-b|/max{|a|, |b|} < eps
но нужно отдельно обрабатывать случай деления на ноль, что-то вроде этого:
(a == b || fabs(a-b)/max(fabs(a), fabs(b)))

Comments

[rafuck]

fabs(a-b)/max(fabs(a), fabs(b)) < eps конечно же