Interval propagation

From Wikipedia, the free encyclopedia

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 is 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 x₁,...,x_n is an operator which contracts the intervals [x₁],..., [x_n] (that are supposed to enclose the x_i'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

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

which involves the three variables x₁,x₂ and x₃.

The associated contractor is given by the following statements

$[x_{3}]:=[x_{3}]\cap ([x_{1}]+[x_{2}])$

$[x_{1}]:=[x_{1}]\cap ([x_{3}]-[x_{2}])$

$[x_{2}]:=[x_{2}]\cap ([x_{3}]-[x_{1}])$

For instance, if

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

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

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

the contractor performs the following calculus

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

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

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

Figure 1: boxes before contraction

Figure 2: boxes after contraction

For other constraints, a specific algorithm for implementing the atomic contractor should be written. An illustration is the atomic contractor associated to the equation

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

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

$x+\sin(xy)\leq 0,$

could be decomposed into

$a=xy$

$b=\sin(a)$

$c=x+b.$

The interval domains that should be associated to the new intermediate variables are

$a\in [-\infty ,\infty ],$

$b\in [-\infty ,\infty ],$

$c\in [-\infty ,0].$

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.

Figure 3: File:Electronic circuit to illustrate the interval propagation

Assume that from different measurements, we know that

$E\in [23V,26V]$

$I\in [4A,8A]$

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

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

$P\in [124W,130W]$

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

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

From the circuit, we have the following equations

$P=EI$

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

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

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

After performing the interval propagation, we get

$E\in [24V,26V]$

$I\in [4.769A,5.417A]$

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

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

$P\in [124W,130W]$

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

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

References

↑ Jaulin, L.; Braems, I.; Walter, E. (2002). Interval methods for nonlinear identification and robust control. In Proceedings of the 41st IEEE Conference on Decision and Control (CDC).
↑ Cleary, J.L. (1987). Logical arithmetic. Future Computing Systems.
↑ Jaulin, L. (2006). Localization of an underwater robot using interval constraints propagation. In Proceedings of CP 2006.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.