Ustaw inwersję
W matematyce odwrócenie zbioru jest problemem scharakteryzowania preobrazu X zbioru Y przez funkcję f , tj. X = f −1 ( Y ) = { x ∈ R n | fa ( x ) ∈ Y }. Można to również postrzegać jako problem opisania zbioru rozwiązań ilościowego ograniczenia „ Y ( f ( x ))", gdzie Y ( y ) jest ograniczeniem, np. nierównością opisującą zbiór Y .
W większości zastosowań f jest funkcją od Rn do Rp , a zbiór Y jest pudełkiem Rp ( tj . iloczynem kartezjańskim p przedziałów R ).
Gdy f jest nieliniowe, problem inwersji zestawu można rozwiązać za pomocą analizy przedziałowej połączonej z algorytmem rozgałęzień i ograniczeń .
Główna idea polega na zbudowaniu nawierzchni R p wykonanej z nienachodzących na siebie skrzynek. Dla każdego pudełka [ x ] przeprowadzamy następujące testy:
- jeśli f ([ x ]) ⊂ Y wnioskujemy, że [ x ] ⊂ X ;
- jeśli f ([ x ]) ∩ Y = ∅ wnioskujemy, że [ x ] ∩ X = ∅;
- W przeciwnym razie pudełko [ x ] jest podzielone na pół, chyba że jego szerokość jest mniejsza niż podana dokładność.
Aby sprawdzić dwa pierwsze testy, potrzebujemy rozszerzenia przedziału (lub funkcji inkluzji) [ f ] dla f . Skrzynki sklasyfikowane są składowane w podrzędnych nawierzchniach , tj. połączeniu nienachodzących na siebie skrzynek. Algorytm można usprawnić, zastępując testy włączenia przez wykonawców .
Przykład
Zbiór X = f −1 ([4,9]), gdzie f ( x 1 , x 2 ) = x
2 1 + x
2 2 jest przedstawiony na rysunku.
Na przykład, ponieważ [−2,1] 2 + [4,5] 2 = [0,4] + [16,25] = [16,29] nie przecina przedziału [4,9], wnioskujemy, że pudełko [−2,1] × [4,5] znajduje się na zewnątrz X . Ponieważ [−1,1] 2 + [2, √ 5 ] 2 = [0,1] + [4,5] = [4,6] jest wewnątrz [4,9], wnioskujemy, że całe pudełko [− 1,1] × [2, √ 5 ] jest wewnątrz X .
Aplikacja
Odwrócenie zestawu jest używane głównie do planowania ścieżki , do estymacji zestawu parametrów nieliniowych , do lokalizacji lub do charakteryzowania domen stabilności liniowych układów dynamicznych .