Интервальный подрядчик

В математике интервальный контрактор (или контрактор ) сокращенно связанный с набором $X$ является оператором $C$ который соответствует гиперпрямоугольнику $[x]$ в ${\mathbf {R}}^{n}$ еще одна коробка $C([x])$ из ${\mathbf {R}}^{n}$ такие, что всегда выполняются два следующих свойства:

• $C([x])\subset [x]$ (подрядная собственность)

• $C([x])\cap X=[x]\cap X$ (свойство полноты)

Подрядчик , связанный с ограничением (например, уравнением или неравенством ), представляет собой подрядчик, связанный с набором $X$ из всех $x$ которые удовлетворяют ограничению. Подрядчики позволяют повысить эффективность алгоритмов ветвей и границ, классически используемых в интервальном анализе .

Свойства подрядчиков

Подрядчик C является монотонным, если имеем $[x]\subset [y]\Rightarrow C([x])\subset C([y])$.

Оно минимально , если для всех ящиков [ x ] имеем $C([x])=[[x]\cap X]$,где [ A ] — интервальная оболочка множества A , т. е. наименьшеекоробка, в которой А. находится

Контрактор C является тонким если для всех точек x , $C(\{x\})=\{x\}\cap X$где { x } обозначает вырожденный прямоугольник, заключающий x как одну точку.

Контрактор C идемпотентен , если для всех ящиков [ x ] имеем $C\circ C([x])=C([x]).$

Контрактор C сходится , если для всех последовательностей [ x ]( k ) ящиков, содержащих x , мы имеем $[x](k)\rightarrow x\implies C([x](k))\rightarrow \{x\}\cap X.$

Иллюстрация

На рисунке 1 представлено множество X, окрашенное в серый цвет, а также несколько ящиков, некоторые из которых вырождены (т. е. соответствуют одиночным элементам). На рисунке 2 представлены эти коробки. после сокращения . Обратите внимание, что ни одна точка X не была удалена подрядчиком. Подрядчикминимально для голубого поля, но пессимистично для зеленого. Все вырожденные синие ящики сжимаются до коробка пустая . Пурпурный и красный прямоугольники нельзя сжать.

Рисунок 1: Коробки до сокращения

Рисунок 2: Коробки после сокращения

Алгебра подрядчика

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

$(C_{1}\cap C_{2})([x])=C_{1}([x])\cap C_{2}([x])$

$(C_{1}\cup C_{2})([x])=[C_{1}([x])\cup C_{2}([x])]$

$(C_{1}\circ C_{2})([x])=C_{1}(C_{2}([x]))$

$C^{\infty }([x])=C\circ C\circ C\circ \cdots \circ C([x])$

Строительные подрядчики

Существуют разные способы построения контракторов, связанных с уравнениями и неравенствами, скажем, f ( x ) в [ y ].Большинство из них основано на интервальной арифметике.Одним из наиболее эффективных и простых является прямой/обратный подрядчик (также называемый HC4-ревизией).

Принцип состоит в том, чтобы оценить f ( x ) с использованием интервальной арифметики (это шаг вперед).Полученный интервал пересекается с [ y ]. обратная оценка f ( x Затем выполняется ) чтобы сократить интервалы для x _i (это шаг назад). Теперь проиллюстрируем принцип на простом примере.

Рассмотрим ограничение $(x_{1}+x_{2})\cdot x_{3}\in [1,2].$Мы можем оценить функцию f ( x ), введя два промежуточных значения переменные a и b , как показано ниже

$a=x_{1}+x_{2}$

$b=a\cdot x_{3}$

Два предыдущих ограничения называются прямыми ограничениями . Мы получаем обратные ограничения беря каждое прямое ограничение в обратном порядке и изолируя каждую переменную в правой части. Мы получаем

$x_{3}={\frac {b}{a}}$

$a={\frac {b}{x_{3}}}$

$x_{1}=a-x_{2}$

$x_{2}=a-x_{1}$

Итоговый прямой/обратный подрядчик $C([x_{1}],[x_{2}],[x_{3}])$получается путем оценки прямых и обратных ограничений с использованием интервального анализа .

$[a]=[x_{1}]+[x_{2}]$

$[b]=[a]\cdot [x_{3}]$

$[b]=[b]\cap [1,2]$

$[x_{3}]=[x_{3}]\ \cap \ {\frac {[b]}{[a]}}$

$[a]=[a]\cap {\frac {[b]}{[x_{3}]}}$

$[x_{1}]=[x_{1}]\ \cap \ \ [a]-[x_{2}]$

$[x_{2}]=[x_{2}]\ \cap \ \ [a]-[x_{1}]$