間隔伝播

数値数学において、区間伝播または区間制約伝播は、一連の制約（方程式または不等式）と一致する値を削除せずに、 Rの変数に関連付けられた区間領域を縮小する問題です。これは、誤差が区間で表される状況で不確実性を伝播するために使用できます。^[1] 区間伝播は、推定問題を制約充足問題として扱います。

変数x ₁、...、x _nを含む方程式に関連付けられたコントラクターは、方程式と一致する変数の値を削除せずに、区間 [ x ₁ ]、...、[ x _n ] ( x _iを囲むはずの) を収縮する演算子です。

コントラクターは、他のコントラクターの合成として構築されていない場合、アトミックであると言われます。アトミック コントラクターの構築に使用される主な理論は、区間解析に基づいています。

例: 例えば次の式を考えてみましょう

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

これには 3 つの変数x ₁、x ₂、x ₃が含まれます。

関連請負業者は以下のとおりです。

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

例えば、

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

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

${\displaystyle x_{3}\in [6,\infty ]}$

請負業者は以下の計算を実行する

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

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

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

その他の制約については、アトミックコントラクターを実装するための特定のアルゴリズムを記述する必要があります。例として、方程式に関連付けられたアトミックコントラクターを示します。

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

図1と図2に示されています。

より複雑な制約については、アトミック制約（つまり、アトミックコントラクターが存在する制約）への分解を実行する必要があります。たとえば、制約を考えてみましょう。

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

分解すると

${\displaystyle a=xy}$

${\displaystyle b=\sin(a)}$

${\displaystyle c=x+b.}$

新しい中間変数に関連付ける必要がある間隔領域は

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

${\displaystyle b\in [-1,1],}$

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

区間伝播の原理は、利用可能なすべてのアトミックコントラクターを、それ以上の収縮が見られなくなるまで呼び出すことです。 ^[2]クナスター・タルスキー定理 の結果として、手順は常に変数のすべての実行可能な値を囲む区間に収束します。区間伝播の形式化は、コントラクター代数のおかげで行うことができます。区間伝播は結果に素早く収束し、数百の変数を含む問題を扱うことができます。 ^[3]

図3の電子回路を考えてみましょう。

さまざまな測定から、次のことが分かっていると仮定します。

${\displaystyle E\in [23V,26V]}$

${\displaystyle I\in [4A,8A]}$

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

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

${\displaystyle P\in [124W,130W]}$

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

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

回路から次の式が得られます。

${\displaystyle P=EI}$

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

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

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

区間伝播を実行すると、次のようになります。

${\displaystyle E\in [24V,26V]}$

${\displaystyle I\in [4.769A,5.417A]}$

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

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

${\displaystyle P\in [124W,130W]}$

${\displaystyle R_{1}\in [1.846\Omega ,2.307\Omega ]}$

${\displaystyle R_{2}\in [2.584\Omega ,3.355\Omega ].}$