Установить инверсию

Математическая задача нахождения множества, отображаемого заданной функцией в определенный диапазон

В математике инверсия множеств — это проблема характеристики прообраза X множества Y функцией f , то есть X = f ⁻¹ ( Y  ) = { x∈Rn ^| f ( x )∈Y }  . Её также можно рассматривать как проблему описания множества решений квантифицированного ограничения « Y ( f ( x  ) ) », где Y ( y  ) — ограничение, например, неравенство , описывающее множество Y.

В большинстве приложений f является функцией от R ⁿ до R ^p , а множество Y является ящиком R ^p (т.е. декартовым произведением p интервалов R ).

Когда f нелинейно, задача инверсии множества может быть решена ^[1] с использованием интервального анализа в сочетании с алгоритмом ветвей и границ . ^[2]

Основная идея состоит в построении мощения R ^p из неперекрывающихся коробок. Для каждой коробки [ x ] мы проводим следующие тесты:

1. если f  ([ x ]) ⊂ Y , то мы заключаем, что [ x ] ⊂ X ;
2. если f  ([ x ]) ∩ Y = ∅, то мы заключаем, что [ x ] ∩ X = ∅;
3. В противном случае ящик [ x ] делится пополам, за исключением случаев, когда его ширина меньше заданной точности.

Для проверки первых двух тестов нам нужно расширение интервала (или функция включения) [ f  ] для f . Классифицированные ящики хранятся в subpavings , т. е. объединении неперекрывающихся ящиков. Алгоритм можно сделать более эффективным, заменив тесты включения на contractors .

Пример

Множество X = f ⁻¹ ([4,9]), где f  ( x ₁ , x ₂ ) = x²
₁+ х²
₂представлено на рисунке.

Например, поскольку [−2,1] ² + [4,5] ² = [0,4] + [16,25] = [16,29] не пересекает интервал [4,9], мы заключаем, что ящик [−2,1] × [4,5] находится вне X. Поскольку [−1,1] ² + [2, √ 5 ] ² = [0,1] + [4,5] = [4,6] находится внутри [4,9], мы заключаем, что весь ящик [−1,1] × [2, √ 5 ] находится внутри X.

Кольцо определяется как проблема инверсии множества

Приложение

Инверсия множеств в основном используется для планирования пути , для нелинейной оценки набора параметров , ^{[3] [4]} для локализации ^{[5] [6]} или для характеристики областей устойчивости линейных динамических систем . ^[7]

Ссылки

1. Жолен, Л.; Уолтер, Э. (1993). «Инверсия множеств с помощью интервального анализа для нелинейной оценки ограниченной ошибки» (PDF) . Automatica . 29 (4): 1053–1064. doi :10.1016/0005-1098(93)90106-4.
2. Жолен, Л.; Киффер, М.; Дидрит, О.; Уолтер, Э. (2001). Прикладной интервальный анализ . Берлин: Шпрингер. ISBN 1-85233-219-0.
3. Jaulin, L.; Godet, JL; Walter, E.; Elliasmine, A.; Leduff, Y. (1997). "Анализ данных по рассеянию света с помощью инверсии множеств" (PDF) . Journal of Physics A: Mathematical and General . 30 (22): 7733–7738. Bibcode :1997JPhA...30.7733J. doi :10.1088/0305-4470/30/22/012.
4. Braems, I.; Berthier, F.; Jaulin, L.; Kieffer, M.; Walter, E. (2001). "Гарантированная оценка электрохимических параметров с помощью инверсии множеств с использованием интервального анализа" (PDF) . Журнал электроаналитической химии . 495 (1).
5. Колле, Э.; Галерн, С. (2013). «Локализация мобильного робота с помощью мультиангуляции с использованием инверсии множеств». Робототехника и автономные системы . 66 (1): 39–48. doi :10.1016/j.robot.2012.09.006.
6. Древель, В.; Боннифейт, Ф. (2011). «Подход на основе набора для высокоцелостного определения высоты спутникового позиционирования». GPS Solutions . 15 (4): 357–368. doi :10.1007/s10291-010-0195-3. S2CID  121728552.
7. Уолтер, Э.; Жолен, Л. (1994). «Гарантированная характеристика областей устойчивости с помощью инверсии множеств» (PDF) . IEEE Trans. Autom. Control . 39 (4): 886–889. doi :10.1109/9.286277.