689
правок
Изменения
м
Нет описания правки
'''Интервальная арифметика''' — способ работы с вещественной floating-point арифметикой, который для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Этот способ удобен для работы с величинами, значения которых известны только приближённо, то есть определён конечный интервал, в котором эти значения содержатся.
== Операции над интервалами ==
Мы будем рассматривать всевозможные конечные вещественные интервалы <tex> [a, b]\ (a \leqslant b) </tex>. Операции над ними определяются следующим образом:
* Сложение: <tex> [a, b] + [c, d] = [a \lfloor a + underline{\oplus} c , b \rfloor, overline{\lceil b + oplus} d \rceil] </tex>* Вычитание: <tex> [a, b] - [c, d] = [a \lfloor a - underline{\ominus} d , b \rfloor, overline{\lceil b - ominus} c \rceil] </tex>* Умножение: <tex> [a, b] \times [c, d] = [\min(a \lfloor ac underline{\rfloorotimes} c, a \lfloor ad underline{\rfloorotimes} d, b \lfloor bc underline{\rfloorotimes} c, b \lfloor bd underline{\rfloorotimes} d), \max(a \lceil ac overline{\rceilotimes} c, a \lceil ad overline{\rceilotimes} d, b \lceil bc overline{\rceilotimes} c, b \lceil bd overline{\rceilotimes} d)] </tex>* Деление: <tex> [a, b] / [c, d] = [\min(a \underline{\lfloor oslash} c, a/c \rfloorunderline{\oslash} d, b \lfloor a/d underline{\rflooroslash} c, \lfloor b/c \rfloor, underline{\lfloor b/oslash} d \rfloor), \max(a \lceil overline{\oslash} c, a/c \rceiloverline{\oslash} d, b \lceil a/d overline{\rceiloslash} c, \lceil b/c \rceil, overline{\lceil b/oslash} d \rceil)] </tex>
Здесь и далее <tex> \lfloor x underline{\rfloor odot} </tex> и <tex> \lceil x overline{\rceil odot} </tex> — округление числа выполнение операции <tex> x \odot </tex> по правилам вещественной арифметики с округлением в меньшую и большую сторону соответственно по правилам вещественной арифметики.
Из определения видно, что интервал-сумма содержит всевозможные суммы чисел из интервалов-слагаемых и определяет границы множества таких сумм. Аналогично трактуются прочие действия. Отметим, что операция деления определена только в том случае, когда интервал-делитель не содержит нуля.
Вырожденные интервалы, у которых начало и конец совпадают, можно отождествить с обычными вещественными числами. Для них данные выше определения совпадают с классическими арифметическими действиями.
== Применение в вычислительной геометрии ==
Допустим, нам нужно точно определить знак некоторого выражения (это может потребоваться, например, при вычислении предиката [[Предикат "левый поворот" |"левый поворот"]]). Будем использовать для его вычисления интервальную арифметику. Все исходные переменные, входящие в него, будут вырожденными интервалами. При выполнении одной из элементарных операций, описанных выше, будем вычислять нижнюю границу с округлением вниз, а верхнюю — с округлением вверх. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Если левая и правая границы интервала для всего выражения оказались одного знака, то и само выражение однозначно будет иметь тот же знак. В противном случае требуются дополнительные действия.
В Microsoft Visual СC++ и GCC режим округления и другие настройки вещественной арифметики можно изменить с помощью функции <tt>_controlfp</tt> (MSDN рекомендует использовать более безопасную версию <tt>_controlfp_s</tt>, но GCC ее не поддерживает).
== Проблемы и ограничения ==
Переключение режима округления в процессоре является довольно длительной операцией, поэтому, если использовать его в каждой элементарной операции, это может сильно замедлить вычисления. Впрочем, эту проблему можно легко решить. Пусть мы вычисляем операцию <tex>l = a \lfloor a underline{\circ odot} b \rfloor </tex>, тогда <tex> r = a \lceil a overline{\circ odot} b \rceil </tex> - можно вычислить, заменив знаки операндов на противоположные и восстановив корректный знак <tex> a \circ odot b </tex>. Например, для сложения, <tex> a \overline{\oplus} b = \ominus ((\ominus a) \underline{\oplus} (\ominus b)) </tex> Значит, можно включить округление вниз до работы с интервалами и вернуть стандартный режим после нее, тогда много переключений не потребуется.
Предполагается, что мы можем управлять округлением в операциях над вещественными числами. Стандарт IEEE 754 гарантирует такую возможность, но не все современные языки/архитектуры его выполняют. Например, согласно [http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf этому] материалу, вещественная арифметика в Java не соответствует стандарту IEEE 754 (в частности, не позволяет указывать правила округления). Поэтому на Java нельзя реализовать требуемую интервальную арифметику с использованием только примитивных типов double/float.
