# Interval propagation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Interval_propagation
> Markdown URL: https://mediated.wiki/source/Interval_propagation.md
> Source: https://en.wikipedia.org/wiki/Interval_propagation
> Source revision: 1157439535
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [numerical mathematics](/source/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](/source/Propagation_of_uncertainty) in the situation where [errors are represented by intervals](/source/Set_estimation).[1] Interval propagation considers an estimation problem as a [constraint satisfaction](/source/Constraint_satisfaction) problem.

## Atomic contractors

A contractor associated to an equation involving the variables *x*1,...,*x**n* is an operator which contracts the intervals [*x*1],..., [*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](/source/Interval_arithmetic).

**Example**. Consider for instance the equation

- x_1+x_2 =x_3,

which involves the three variables *x*1,*x*2 and *x*3.

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].

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 [-1 ,1 ] ,

- 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](/source/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](/source/Interval_contractor). 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 [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

1. Jaulin, L.; Braems, I.; Walter, E. (2002). [*Interval methods for nonlinear identification and robust control*](http://www.ensta-bretagne.fr/jaulin/cdc02.pdf). In Proceedings of the 41st IEEE Conference on Decision and Control (CDC)

1. Cleary, J.L. (1987). *Logical arithmetic*. Future Computing Systems.

1. Jaulin, L. (2006). [*Localization of an underwater robot using interval constraints propagation*](http://www.ensta-bretagne.fr/jaulin/redermorcp06.pdf). In Proceedings of CP 2006.

---
Adapted from the Wikipedia article [Interval propagation](https://en.wikipedia.org/wiki/Interval_propagation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Interval_propagation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.