Ställ in inversion
Inom matematik är mängdinversion problemet med att karakterisera förbilden X av en mängd Y med en funktion f , dvs. X = f −1 ( Y ) = { x ∈ R n | f ( x ) ∈ Y }. Det kan också ses som problemet med att beskriva lösningsmängden för den kvantifierade begränsningen " Y ( f ( x ))", där Y ( y ) är en begränsning, t.ex. en olikhet , som beskriver mängden Y.
I de flesta applikationer är f en funktion från R n till Rp och mängden Y är en ruta av R p (dvs en kartesisk produkt av p- intervall av R ).
När f är olinjär kan uppsättningsinversionsproblemet lösas med hjälp av intervallanalys kombinerat med en gren-och-bunden algoritm.
Huvudidén består i att bygga en stenläggning av R p gjord med icke-överlappande lådor. För varje ruta [ x ] utför vi följande tester:
- om f ([ x ]) ⊂ Y drar vi slutsatsen att [ x ] ⊂ X ;
- om f ([ x ]) ∩ Y = ∅ drar vi slutsatsen att [ x ] ∩ X = ∅;
- delas rutan [ x ] boxen utom om dess bredd är mindre än en given precision.
För att kontrollera de två första testerna behöver vi en intervallförlängning (eller en inkluderingsfunktion) [ f ] för f . Klassificerade lådor lagras i underbeläggningar , dvs sammanfogning av icke-överlappande lådor. Algoritmen kan göras mer effektiv genom att ersätta inklusionstesterna av entreprenörer .
Exempel
Mängden X = f −1 ([4,9]) där f ( x 1 , x 2 ) = x
2 1 + x
2 2 representeras på figuren.
Till exempel, eftersom [−2,1] 2 + [4,5] 2 = [0,4] + [16,25] = [16,29] inte skär intervallet [4,9], drar vi slutsatsen att rutan [−2,1] × [4,5] är utanför X . Eftersom [−1,1] 2 + [2, √ 5 ] 2 = [0,1] + [4,5] = [4,6] är inuti [4,9], drar vi slutsatsen att hela rutan [− 1,1] × [2, √ 5 ] är inuti X .
Ansökan
Setinversion används huvudsakligen för vägplanering , för icke-linjär parameteruppsättningsuppskattning , för lokalisering eller för karakterisering av stabilitetsdomäner i linjära dynamiska system .