Интервальная арифметика

Интервальная арифметика — способ работы с вещественной арифметикой, который для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Этот способ удобен для работы с величинами, значения которых известны только приближённо, то есть определён конечный интервал, в котором эти значения содержатся.

Операции над интервалами

Мы будем рассматривать всевозможные конечные вещественные интервалы [math] [a, b]\ (a \leqslant b) [/math]. Операции над ними определяются следующим образом:

• Сложение: [math] [a, b] + [c, d] = [\lfloor a + c \rfloor, \lceil b + d \rceil] [/math]
• Вычитание: [math] [a, b] - [c, d] = [\lfloor a - d \rfloor, \lceil b - c \rceil] [/math]
• Умножение: [math] [a, b] \times [c, d] = [\min(\lfloor ac \rfloor, \lfloor ad \rfloor, \lfloor bc \rfloor, \lfloor bd \rfloor), \max(\lceil ac \rceil, \lceil ad \rceil, \lceil bc \rceil, \lceil bd \rceil)] [/math]
• Деление: [math] [a, b] / [c, d] = [\min(\lfloor a/c \rfloor, \lfloor a/d \rfloor, \lfloor b/c \rfloor, \lfloor b/d \rfloor), \max(\lceil a/c \rceil, \lceil a/d \rceil, \lceil b/c \rceil, \lceil b/d \rceil)] [/math]

Здесь и далее [math] \lfloor x \rfloor [/math] и [math] \lceil x \rceil [/math] — округление числа [math] x [/math] в меньшую и большую сторону соответственно по правилам вещественной арифметики.

Из определения видно, что интервал-сумма содержит всевозможные суммы чисел из интервалов-слагаемых и определяет границы множества таких сумм. Аналогично трактуются прочие действия. Отметим, что операция деления определена только в том случае, когда интервал-делитель не содержит нуля.

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

Применение в вычислительной геометрии

Допустим, нам нужно точно определить знак некоторого выражения (это может потребоваться, например, при вычислении предиката "левый поворот"). Будем использовать для его вычисления интервальную арифметику. Все исходные переменные, входящие в него, будут вырожденными интервалами. При выполнении одной из элементарных операций, описанных выше, будем вычислять нижнюю границу с округлением вниз, а верхнюю — с округлением вверх. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Если левая и правая границы интервала для всего выражения оказались одного знака, то и само выражение однозначно будет иметь тот же знак. В противном случае требуются дополнительные действия.

В Visual С++ режим округления и другие настройки вещественной арифметики можно изменить с помощью функции _controlfp (MSDN рекомендует использовать более безопасную версию _controlfp_s).

Проблемы и ограничения

Переключение режима округления в процессоре является довольно длительной операцией, поэтому, если использовать его в каждой элементарной операции, это может сильно замедлить вычисления. Впрочем, эту проблему можно легко решить. Пусть мы вычисляем операцию [math]l = \lfloor a \circ b \rfloor [/math], тогда [math] r = \lceil a \circ b \rceil [/math] - можно вычислить, заменив знаки операндов на противоположные и восстановив корректный знак [math] a \circ b [/math]. Значит, можно включить округление вниз до работы с интервалами и вернуть стандартный режим после нее, тогда много переключений не потребуется.

Предполагается, что мы можем управлять округлением в операциях над вещественными числами. Стандарт IEEE 754 гарантирует такую возможность, но не все современные языки/архитектуры его выполняют. Например, согласно этому материалу, вещественная арифметика в Java не соответствует стандарту IEEE 754 (в частности, не позволяет указывать правила округления). Поэтому на Java нельзя реализовать требуемую интервальную арифметику с использованием только примитивных типов double/float.

Ссылки

• Интервальная арифметика (Википедия)