title: Interval propagation
text: # 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. Interval propagation considers an estimation problem as a 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.
  
  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.
  
  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.
  
  ## 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 ].$
  