Установить инверсию - Set inversion
В математике инверсия множеств - это проблема характеристики прообраза X множества Y функцией f , т. Е. X = f −1 ( Y ) = { x ∈ R n | f ( x ) ∈ Y }. Его также можно рассматривать как проблему описания множества решений количественного ограничения «Y (f (x))», где Y (y) - ограничение, например неравенство, описывающее множество Y.
В большинстве приложений f является функцией от R n до R p, а множество Y является блоком R p (то есть декартовым произведением p интервалов R ).
Когда f является нелинейным, проблема обращения множества может быть решена с использованием интервального анализа в сочетании с алгоритмом ветвей и границ .
Основная идея заключается в строительстве мощения из R п из неперекрывающихся боксов. Для каждого блока [ x ] мы выполняем следующие тесты:
- если f ([ x ]) ⊂ Y, заключаем, что [ x ] ⊂ X ;
- если f ([ x ]) ∩ Y = ∅, заключаем, что [ x ] ∩ X = ∅;
- В противном случае прямоугольник [ x ] прямоугольник делится пополам, кроме случаев, когда его ширина меньше заданной точности.
Чтобы проверить два первых теста, нам понадобится расширение интервала (или функция включения) [ f ] для f . Классифицированные ящики хранятся в подположениях , т. Е. Объединении неперекрывающихся ящиков. Алгоритм можно сделать более эффективным, заменив подрядчиками тесты включения .
пример
Множество X = f −1 ([4,9]), где f ( x 1 , x 2 ) = x2
1+ х2
2 представлен на рисунке.
Например, поскольку [−2,1] 2 + [4,5] 2 = [0,4] + [16,25] = [16,29] не пересекает интервал [4,9], мы заключаем, что коробка [-2,1] × [4,5] находится за пределами Х . Поскольку [−1,1] 2 + [2, √ 5 ] 2 = [0,1] + [4,5] = [4,6] находится внутри [4,9], мы заключаем, что вся коробка [- 1,1] × [2, √ 5 ] находится внутри Х .
заявка
Инверсия множества в основном используется для планирования пути , для оценки набора нелинейных параметров , для локализации или для характеристики областей устойчивости линейных динамических систем. .