Interval propagation

From HandWiki

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

x1+x2=x3,

which involves the three variables x1,x2 and x3.

The associated contractor is given by the following statements

[x3]:=[x3]([x1]+[x2])
[x1]:=[x1]([x3][x2])
[x2]:=[x2]([x3][x1])

For instance, if

x1[,5],
x2[,4],
x3[6,]

the contractor performs the following calculus

x3=x1+x2x3[6,]([,5]+[,4])=[6,][,9]=[6,9].
x1=x3x2x1[,5]([6,][,4])=[,5][2,]=[2,5].
x2=x3x1x2[,4]([6,][,5])=[,4][1,]=[1,4].
Figure 1: boxes before contraction
Error creating thumbnail: Unable to save thumbnail to destination
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

x2=sin(x1),

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)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[,],
b[1,1],
c[,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[23V,26V]
I[4A,8A]
U1[10V,11V]
U2[14V,17V]
P[124W,130W]
R1[0Ω,]
R2[0Ω,].

From the circuit, we have the following equations

P=EI
U1=R1I
U2=R2I
E=U1+U2.

After performing the interval propagation, we get

E[24V,26V]
I[4.769A,5.417A]
U1[10V,11V]
U2[14V,16V]
P[124W,130W]
R1[1.846Ω,2.307Ω]
R2[2.584Ω,3.355Ω].

References

  1. 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). http://www.ensta-bretagne.fr/jaulin/cdc02.pdf. 
  2. Cleary, J.L. (1987). Logical arithmetic. Future Computing Systems. 
  3. Jaulin, L. (2006). Localization of an underwater robot using interval constraints propagation. In Proceedings of CP 2006. http://www.ensta-bretagne.fr/jaulin/redermorcp06.pdf.