Интервальная арифметика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Интервальная арифметика''' — математическая структура, которая для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Данная математическая модель удобна для работы с величинами, значения которых известны только приближённо, то есть определён конечный интервал, в котором эти значения содержатся.
+
'''Интервальная арифметика''' — способ работы с floating-point арифметикой, который для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Этот способ удобен для работы с величинами, значения которых известны только приближённо, то есть определён конечный интервал, в котором эти значения содержатся.
  
 
== Операции над интервалами ==
 
== Операции над интервалами ==
  
 
Мы будем рассматривать всевозможные конечные вещественные интервалы <tex> [a, b]\ (a \leqslant b) </tex>. Операции над ними определяются следующим образом:
 
Мы будем рассматривать всевозможные конечные вещественные интервалы <tex> [a, b]\ (a \leqslant b) </tex>. Операции над ними определяются следующим образом:
* Сложение: <tex> [a, b] + [c, d] = [a + c, b + d] </tex>
+
* Сложение: <tex> [a, b] + [c, d] = [a \underline{\oplus} c, b \overline{\oplus} d] </tex>
* Вычитание: <tex> [a, b] - [c, d] = [a - d, b - c] </tex>
+
* Вычитание: <tex> [a, b] - [c, d] = [a \underline{\ominus} d, b \overline{\ominus} c] </tex>
* Умножение: <tex> [a, b] \times [c, d] = [\min(ac, ad, bc, bd), \max(ac, ad, bc, bd)] </tex>
+
* Умножение: <tex> [a, b] \times [c, d] = [\min(a \underline{\otimes} c, a \underline{\otimes} d, b \underline{\otimes} c, b \underline{\otimes} d), \max(a \overline{\otimes} c, a \overline{\otimes} d, b \overline{\otimes} c, b \overline{\otimes} d)] </tex>
* Деление: <tex> [a, b] / [c, d] = [\min(a/c, a/d, b/c, b/d), \max(a/c, a/d, b/c, b/d)] </tex>
+
* Деление: <tex> [a, b] / [c, d] = [\min(a \underline{\oslash} c, a \underline{\oslash} d, b \underline{\oslash} c, b \underline{\oslash} d), \max(a \overline{\oslash} c, a \overline{\oslash} d, b \overline{\oslash} c, b \overline{\oslash} d)] </tex>
 +
 
 +
Здесь и далее <tex> \underline{\odot} </tex> и <tex> \overline{\odot} </tex> — выполнение операции <tex> \odot </tex> по правилам вещественной арифметики с округлением в меньшую и большую сторону соответственно.
  
 
Из определения видно, что интервал-сумма содержит всевозможные суммы чисел из интервалов-слагаемых и определяет границы множества таких сумм. Аналогично трактуются прочие действия. Отметим, что операция деления определена только в том случае, когда интервал-делитель не содержит нуля.
 
Из определения видно, что интервал-сумма содержит всевозможные суммы чисел из интервалов-слагаемых и определяет границы множества таких сумм. Аналогично трактуются прочие действия. Отметим, что операция деления определена только в том случае, когда интервал-делитель не содержит нуля.
  
Вырожденные интервалы, у которых начало и конец совпадают, можно отождествить с обычными вещественными числами. Для них данные выше определения совпадают с классическими арифметическими действиями.
+
Вырожденные интервалы, у которых начало и конец совпадают, можно отождествить с обычными вещественными числами.
  
 
== Применение в вычислительной геометрии ==
 
== Применение в вычислительной геометрии ==
  
Допустим, нам нужно определить знак некоторого выражения (это может потребоваться, например, при вычислении предиката [[Предикат "левый поворот" |"левый поворот"]]). Ясно, что минимальное значение будет, если все округлять вниз, а максимальное - если вверх. {{TODO| t=поподробнее об этом}}
+
Допустим, нам нужно точно определить знак некоторого выражения (это может потребоваться, например, при вычислении предиката [[Предикат "левый поворот" |"левый поворот"]]). Будем использовать для его вычисления интервальную арифметику. Все исходные переменные, входящие в него, будут вырожденными интервалами. При выполнении одной из элементарных операций, описанных выше, будем вычислять нижнюю границу с округлением вниз, а верхнюю — с округлением вверх. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Если левая и правая границы интервала для всего выражения оказались одного знака, то и само выражение однозначно будет иметь тот же знак. В противном случае требуются дополнительные действия.
 +
 
 +
В Microsoft Visual C++ и GCC режим округления и другие настройки вещественной арифметики можно изменить с помощью функции <tt>_controlfp</tt> (MSDN рекомендует использовать более безопасную версию <tt>_controlfp_s</tt>, но GCC ее не поддерживает).
  
 
== Проблемы и ограничения ==
 
== Проблемы и ограничения ==
Переключение режима округления в процессоре является довольно длительной операцией, поэтому, если использовать его в каждой элементарной операции, это может сильно замедлить вычисления. Впрочем, эту проблему можно легко решить. {{TODO| t=написать о решении}}
 
  
Предполагается, что мы можем управлять округлением в операциях над вещественными числами. Стандарт IEEE 754 гарантирует такую возможность, но не все современные языки/архитектуры его выполняют. Например, согласно [http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf этому] материалу, вещественная арифметика в Java не соответствует стандарту IEEE 754 (в частности, не позволяет указывать правила округления). Поэтому на Java нельзя реализовать интервальную арифметику с использованием только примитивных типов double/float.
+
Переключение режима округления в процессоре является довольно длительной операцией, поэтому, если использовать его в каждой элементарной операции, это может сильно замедлить вычисления. Впрочем, эту проблему можно легко решить. Пусть мы вычисляем операцию <tex>l = a \underline{\odot} b </tex>, тогда <tex> r = a \overline{\odot} b </tex> можно вычислить, заменив знаки операндов на противоположные и восстановив корректный знак <tex> a \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.
 +
 
 +
== Ссылки ==
 +
* [http://ru.wikipedia.org/wiki/Интервальная_арифметика Интервальная арифметика (Википедия)]
 +
 
 +
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:31, 4 сентября 2022

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

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

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

  • Сложение: [math] [a, b] + [c, d] = [a \underline{\oplus} c, b \overline{\oplus} d] [/math]
  • Вычитание: [math] [a, b] - [c, d] = [a \underline{\ominus} d, b \overline{\ominus} c] [/math]
  • Умножение: [math] [a, b] \times [c, d] = [\min(a \underline{\otimes} c, a \underline{\otimes} d, b \underline{\otimes} c, b \underline{\otimes} d), \max(a \overline{\otimes} c, a \overline{\otimes} d, b \overline{\otimes} c, b \overline{\otimes} d)] [/math]
  • Деление: [math] [a, b] / [c, d] = [\min(a \underline{\oslash} c, a \underline{\oslash} d, b \underline{\oslash} c, b \underline{\oslash} d), \max(a \overline{\oslash} c, a \overline{\oslash} d, b \overline{\oslash} c, b \overline{\oslash} d)] [/math]

Здесь и далее [math] \underline{\odot} [/math] и [math] \overline{\odot} [/math] — выполнение операции [math] \odot [/math] по правилам вещественной арифметики с округлением в меньшую и большую сторону соответственно.

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

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

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

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

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

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

Переключение режима округления в процессоре является довольно длительной операцией, поэтому, если использовать его в каждой элементарной операции, это может сильно замедлить вычисления. Впрочем, эту проблему можно легко решить. Пусть мы вычисляем операцию [math]l = a \underline{\odot} b [/math], тогда [math] r = a \overline{\odot} b [/math] можно вычислить, заменив знаки операндов на противоположные и восстановив корректный знак [math] a \odot b [/math]. Например, для сложения, [math] a \overline{\oplus} b = \ominus ((\ominus a) \underline{\oplus} (\ominus b)) [/math] Значит, можно включить округление вниз до работы с интервалами и вернуть стандартный режим после нее, тогда много переключений не потребуется.

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

Ссылки