Šíření intervalu - Interval propagation

v numerická matematika, intervalové šíření nebo šíření intervalového omezení je problém kontrakce intervalových domén spojených s proměnnými R bez odstranění jakékoli hodnoty, která je v souladu se sadou omezení (tj. rovnic nebo nerovností). Dá se na to zvyknout šířit nejistoty v situaci, kdy chyby jsou reprezentovány intervaly.^[1] Intervalové šíření považuje problém odhadu za a omezení spokojenosti problém.

Atomové dodavatelé

Dodavatel spojený s rovnicí zahrnující proměnné X₁,...,X_n je operátor, který uzavírá intervaly [X₁],..., [X_n] (které mají uzavřít X_i's) bez odstranění jakékoli hodnoty proměnných, která je v souladu s rovnicí.

Dodavatel se říká, že je atomový pokud to není postaveno jako složení jiných dodavatelů. Hlavní teorie, která se používá k vytváření atomových dodavatelů, je založena na intervalová analýza.

Příklad. Zvažte například rovnici

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

který zahrnuje tři proměnné X₁,X₂ a X₃.

Přidružený dodavatel je uveden v následujících prohlášeních

${ 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}])}$

Například pokud

${ displaystyle x_ {1} v [- infty, 5],}$

${ displaystyle x_ {2} v [- infty, 4],}$

${ displaystyle x_ {3} v [6, infty]}$

dodavatel provede následující počet

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

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

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

Obrázek 1: krabice před kontrakcí

Obrázek 2: Krabice po kontrakci

U dalších omezení by měl být napsán konkrétní algoritmus pro implementaci atomového kontraktora. Ilustrace je atomový dodavatel spojený s rovnicí

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

je poskytnut na obrázcích 1 a 2.

Rozklad

U složitějších omezení by měl být proveden rozklad na atomová omezení (tj. Omezení, pro která existuje atomový dodavatel). Zvažte například omezení

${ displaystyle x + sin (xy) leq 0,}$

mohl být rozložen na

${ displaystyle a = xy}$

${ displaystyle b = sin (a)}$

${ displaystyle c = x + b.}$

Intervalové domény, které by měly být přidruženy k novým zprostředkujícím proměnným, jsou

${ displaystyle a in [- infty, infty],}$

${ displaystyle b v [-1,1],}$

${ displaystyle c v [- infty, 0].}$

Propagace

Principem intervalového šíření je volání všech dostupných atomových kontraktorů, dokud nebude možné pozorovat další kontrakci. ^[2]V důsledku Knaster-Tarského věta, postup vždy konverguje na intervaly, které uzavírají všechny proveditelné hodnoty proměnných. Formalizaci šíření intervalu lze provést díky dodavatelská algebra. Intervalové šíření rychle konverguje k výsledku a dokáže řešit problémy zahrnující několik stovek proměnných.^[3]

Příklad

Zvažte elektronický obvod na obrázku 3.

Obrázek 3: Soubor: Elektronický obvod pro ilustraci šíření intervalu

Předpokládejme, že z různých měření to víme

${ displaystyle E v [23V, 26V]}$

${ displaystyle I v [4A, 8A]}$

${ displaystyle U_ {1} in [10V, 11V]}$

${ displaystyle U_ {2} in [14V, 17V]}$

${ displaystyle P v [124 W, 130 W]}$

${ displaystyle R_ {1} in [0 Omega, infty]}$

${ displaystyle R_ {2} in [0 Omega, infty].}$

Z obvodu máme následující rovnice

${ displaystyle P = EI}$

${ displaystyle U_ {1} = R_ {1} I}$

${ displaystyle U_ {2} = R_ {2} I}$

${ displaystyle E = U_ {1} + U_ {2}.}$

Po provedení intervalového šíření dostaneme

${ displaystyle E v [24V, 26V]}$

${ displaystyle I in [4,779 A, ​​5,417A]}$

${ displaystyle U_ {1} in [10V, 11V]}$

${ displaystyle U_ {2} in [14V, 16V]}$

${ displaystyle P v [124 W, 130 W]}$

${ displaystyle R_ {1} in [1,846 Omega, 2,307 Omega]}$

${ displaystyle R_ {2} in [2,584 Omega, 3,355 Omega].}$

Reference