Interval propagation explained

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 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 [ -inf ty , 5 ], x _{2} \in [ -inf ty , 4 ], x _{3} \in [ 6 , inf ty]

the contractor performs the following calculus

x _{3=x} _{1+x} _{2} ⇒ x _{3} \in [ 6 , inf ty ] \cap ([ -inf ty, 5 ] + [ -inf ty , 4 ]) = [ 6 , inf ty ] \cap [ -inf ty , 9 ] = [ 6 , 9 ]. x _{1=x} _{3-x} _{2} ⇒ x _{1} \in [ -inf ty , 5 ]\cap ([ 6 , inf ty] - [ -inf ty , 4 ]) = [ -inf ty , 5 ] \cap [ 2 , inf ty ] = [ 2 , 5 ]. x _{2=x} _{3-x} _{1} ⇒ x _{2} \in [ -inf ty , 4 ]\cap ([ 6 , inf ty] - [ -inf ty , 5 ]) = [ -inf ty , 4 ] \cap [ 1 , inf ty ] = [ 1 , 4 ].

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 [ -inf ty , inf ty ] , b \in [ -1 , 1 ] , c \in [ -inf ty , 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. Assume that from different measurements, we know that

E \in [ 23 V, 26 V] I\in [ 4 A, 8 A] U _{1} \in [ 10 V, 11 V] U _{2} \in [ 14 V, 17 V] P \in [ 124 W, 130 W] R _{1} \in [ 0 \Omega, inf ty ] R _{2} \in [ 0 \Omega, inf ty ].

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 [ 24 V, 26 V] I \in [ 4 . 769 A, 5 . 417 A] U _{1} \in [ 10 V, 11 V] U _{2} \in [ 14 V, 16 V] P \in [ 124 W, 130 W] R _{1} \in [ 1 . 846 \Omega, 2 . 307 \Omega] R _{2} \in [ 2 . 584 \Omega, 3 . 355 \Omega].

Notes and References

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