Интервальное распространение - Interval propagation

В вычислительной математике , интервал распространение или распространение интервала ограничения является проблемой заражения интервальных доменов , связанных с переменным R без удаления какого - либо значения, которое согласуется с набором ограничений (т.е. уравнений или неравенств). Его можно использовать для распространения неопределенностей в ситуации, когда ошибки представлены интервалами . Распространение по интервалам рассматривает проблему оценки как проблему удовлетворения ограничений .

Атомные подрядчики

Подрядчик, связанный с уравнением, включающим переменные x ₁ , ..., x _n, является оператором, который сокращает интервалы [ x ₁ ], ..., [ x _n ] (которые, как предполагается, должны включать x _i ) без удаления каких-либо значений переменных, которые согласуются с уравнением.

Подрядчик называется атомарным, если он не построен в составе других подрядчиков. Основная теория построения атомных подрядчиков основана на интервальном анализе .

Пример . Рассмотрим, например, уравнение

{\ displaystyle x_ {1} + x_ {2} = x_ {3},}

который включает в себя три переменные x ₁ , x ₂ и x ₃ .

Ассоциированный подрядчик определяется следующими утверждениями

{\ displaystyle [x_ {3}]: = [x_ {3}] \ cap ([x_ {1}] + [x_ {2}])}

{\ displaystyle [x_ {1}]: = [x_ {1}] \ cap ([x_ {3}] - [x_ {2}])}

{\ displaystyle [x_ {2}]: = [x_ {2}] \ cap ([x_ {3}] - [x_ {1}])}

Например, если

{\ Displaystyle х_ {1} \ в [- \ infty, 5],}

{\ Displaystyle х_ {2} \ в [- \ infty, 4],}

{\ displaystyle x_ {3} \ in [6, \ infty]}

подрядчик выполняет следующий расчет

{\ displaystyle x_ {3} = x_ {1} + x_ {2} \ Rightarrow x_ {3} \ in [6, \ infty] \ cap ([- \ infty, 5] + [- \ infty, 4]) = [6, \ infty] \ cap [- \ infty, 9] = [6,9].}

{\ displaystyle x_ {1} = x_ {3} -x_ {2} \ Rightarrow x_ {1} \ in [- \ infty, 5] \ cap ([6, \ infty] - [- \ infty, 4]) = [- \ infty, 5] \ cap [2, \ infty] = [2,5].}

{\ displaystyle x_ {2} = x_ {3} -x_ {1} \ Rightarrow x_ {2} \ in [- \ infty, 4] \ cap ([6, \ infty] - [- \ infty, 5]) = [- \ infty, 4] \ cap [1, \ infty] = [1,4].}

Рисунок 1: прямоугольники перед сокращением

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

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

{\ displaystyle x_ {2} = \ sin (x_ {1}),}

представлена на рисунках 1 и 2.

Разложение

Для более сложных ограничений следует выполнить декомпозицию на атомарные ограничения (т. Е. Ограничения, для которых существует атомарный подрядчик). Рассмотрим, например, ограничение

{\ Displaystyle х + \ грех (ху) \ leq 0,}

можно разложить на

{\ Displaystyle а = ху}

{\ Displaystyle Ь = \ грех (а)}

{\ displaystyle c = x + b.}

Домены интервалов, которые должны быть связаны с новыми промежуточными переменными:

{\ Displaystyle а \ в [- \ infty, \ infty],}

{\ displaystyle b \ in [-1,1],}

{\ displaystyle c \ in [- \ infty, 0].}

Распространение

Принцип интервального распространения заключается в вызове всех доступных атомных подрядчиков до тех пор, пока сокращение больше не будет наблюдаться. В результате теоремы Кнастера-Тарского процедура всегда сходится к интервалам, которые включают в себя все возможные значения переменных. Формализация интервального распространения может быть произведена с помощью контрактной алгебры . Распространение интервалов быстро сводится к результату и может решить проблемы, связанные с несколькими сотнями переменных.