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

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

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

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

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

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

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

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

Допустим, нам нужно определить знак некоторого выражения (это может потребоваться, например, при вычислении предиката "левый поворот"). Ясно, что минимальное значение будет, если все округлять вниз, а максимальное - если вверх. TODO: поподробнее об этом

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

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

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