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

В математика, подрядчик по интервалу (или же подрядчик для краткости)^[1] связанный с набором Икс оператор C который ассоциируется с ящиком [Икс] в р^п другая коробка C([Икс]) из р^п такая, что всегда выполняются два следующих свойства

${ Displaystyle С ([х]) подмножество [х]}$ (договорная собственность)

${ Displaystyle C ([x]) cap X = [x] cap X}$ (свойство полноты)

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

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

Подрядчик C является монотонный если у нас есть ${ Displaystyle [x] подмножество [y] Rightarrow C ([x]) подмножество C ([y])}$

это минимальный если для всех ящиков [Икс], у нас есть ${ Displaystyle С ([х]) = [[х] крышка X]}$ ,куда [А] это интервальный корпус из набора А, т. е. наименьший прямоугольник, охватывающий А.

Подрядчик C является тонкий если по всем пунктам Икс, ${ Displaystyle С ( {х }) = {х } крышка X}$ куда {Икс} обозначает вырожденный бокс, охватывающий Икс как единая точка.

Подрядчик C является идемпотент если для всех ящиков [Икс], у нас есть ${ Displaystyle C circ C ([x]) = C ([x]).}$

Подрядчик C является сходящийся если для всех последовательностей [Икс](k) ящиков, содержащих Икс, у нас есть ${ Displaystyle [x] (k) rightarrow x Rightarrow C ([x] (k)) rightarrow {x } cap X.}$

Иллюстрация

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

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

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

Контракторная алгебра

Некоторые операции могут выполняться с подрядчиками для создания более сложных подрядчиков.^[2]В пересечение, Союз, то сочинение и повторение определяется следующим образом.

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

{ Displaystyle (C_ {1} чашка C_ {2}) ([x]) = [C_ {1} ([x]) чашка C_ {2} ([x])]}

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

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

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

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

Принцип состоит в том, чтобы оценить ж(Икс) с помощью интервальная арифметика (это шаг вперед). интервал является пересекались с [y]. Обратная оценка ж(Икс) затем выполняется, чтобы сократить интервалы для Икс_я (это шаг назад). Теперь проиллюстрируем принцип на простом примере.

Рассмотрим ограничение ${ displaystyle (x_ {1} + x_ {2}) cdot x_ {3} in [1,2].}$ Мы можем оценить функцию ж(Икс) путем введения двух промежуточныхпеременные а и б, следующее

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

{ displaystyle b = a cdot x_ {3}}

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

{ displaystyle x_ {3} = { frac {b} {a}}}

{ displaystyle a = { frac {b} {x_ {3}}}}

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

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

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