Английская Википедия:Interval propagation
In numerical mathematics, interval propagation or interval constraint propagation is the problem of contracting interval domains associated to variables of R without removing any value that is consistent with a set of constraints (i.e., equations or inequalities). It can be used to propagate uncertainties in the situation where errors are represented by intervals.[1] Interval propagation considers an estimation problem as a constraint satisfaction problem.
Atomic contractors
A contractor associated to an equation involving the variables x1,...,xn is an operator which contracts the intervals [x1],..., [xn] (that are supposed to enclose the xi's) without removing any value for the variables that is consistent with the equation.
A contractor is said to be atomic if it is not built as a composition of other contractors. The main theory that is used to build atomic contractors are based on interval analysis.
Example. Consider for instance the equation
- <math>
x_1+x_2 =x_3,
</math>
which involves the three variables x1,x2 and x3.
The associated contractor is given by the following statements
- <math>
[x_3]:=[x_3] \cap ([x_1]+[x_2]) </math>
- <math>
[x_1]:=[x_1] \cap ( [x_3]-[x_2]) </math>
- <math>
[x_2]:=[x_2] \cap ( [x_3]-[x_1]) </math>
For instance, if
- <math>
x_1 \in [-\infty ,5], </math>
- <math>
x_2 \in [-\infty ,4], </math>
- <math>
x_3 \in [ 6,\infty] </math>
the contractor performs the following calculus
- <math>
x_3=x_1+x_2 \Rightarrow x_3 \in [6,\infty ] \cap ([-\infty,5]+[-\infty ,4]) =[6,\infty ] \cap [-\infty ,9]=[6,9]. </math>
- <math>
x_1=x_3-x_2 \Rightarrow x_1 \in [-\infty ,5]\cap ([6,\infty]-[-\infty ,4]) =[-\infty ,5] \cap [2,\infty ]=[2,5]. </math>
- <math>
x_2=x_3-x_1 \Rightarrow x_2 \in [-\infty ,4]\cap ([6,\infty]-[-\infty ,5]) = [-\infty ,4] \cap [1,\infty ]=[1,4]. </math>
For other constraints, a specific algorithm for implementing the atomic contractor should be written. An illustration is the atomic contractor associated to the equation
- <math>
x_2=\sin(x_1), </math>
is provided by Figures 1 and 2.
Decomposition
For more complex constraints, a decomposition into atomic constraints (i.e., constraints for which an atomic contractor exists) should be performed. Consider for instance the constraint
- <math>
x+\sin (xy) \leq 0, </math>
could be decomposed into
- <math>
a=xy </math>
- <math>
b=\sin (a) </math>
- <math>
c=x+b. </math>
The interval domains that should be associated to the new intermediate variables are
- <math>
a \in [-\infty ,\infty ] , </math>
- <math>
b \in [-1 ,1 ] ,
</math>
- <math>
c \in [-\infty ,0].
</math>
Propagation
The principle of the interval propagation is to call all available atomic contractors until no more contraction could be observed. [2] As a result of the Knaster-Tarski theorem, the procedure always converges to intervals which enclose all feasible values for the variables. A formalization of the interval propagation can be made thanks to the contractor algebra. Interval propagation converges quickly to the result and can deal with problems involving several hundred of variables. [3]
Example
Consider the electronic circuit of Figure 3.
Assume that from different measurements, we know that
- <math>
E \in [23V,26V] </math>
- <math>
I\in [4A,8A] </math>
- <math>
U_1 \in [10V,11V] </math>
- <math>
U_2 \in [14V,17V] </math>
- <math>
P \in [124W,130W] </math>
- <math>
R_{1} \in [0 \Omega,\infty ] </math>
- <math>
R_{2} \in [0 \Omega,\infty ]. </math>
From the circuit, we have the following equations
- <math>
P=EI </math>
- <math>
U_{1}=R_{1}I </math>
- <math>
U_{2}=R_{2}I </math>
- <math>
E=U_{1}+U_{2}. </math>
After performing the interval propagation, we get
- <math>
E \in [24V,26V] </math>
- <math>
I \in [4.769A,5.417A] </math>
- <math>
U_1 \in [10V,11V] </math>
- <math>
U_2 \in [14V,16V] </math>
- <math>
P \in [124W,130W] </math>
- <math>
R_{1} \in [1.846 \Omega,2.307 \Omega] </math>
- <math>
R_{2}\in [2.584 \Omega,3.355 \Omega].
</math>
References
