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

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

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

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

The associated contractor is given by the following statements

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

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

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

For instance, if

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

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

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

the contractor performs the following calculus

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

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

${\displaystyle x_{2}=x_{3}-x_{1}\Rightarrow x_{2}\in [-\infty ,4]\cap ([6,\infty ]-[-\infty ,5])=[-\infty ,4]\cap [1,\infty ]=[1,4].}${\displaystyle 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

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

is provided by Figures 1 and 2.

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

${\displaystyle x+\sin(xy)\leq 0,}${\displaystyle x+\sin(xy)\leq 0,}

could be decomposed into

${\displaystyle a=xy}${\displaystyle a=xy}

${\displaystyle b=\sin(a)}${\displaystyle b=\sin(a)}

${\displaystyle c=x+b.}${\displaystyle c=x+b.}

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

${\displaystyle a\in [-\infty ,\infty ],}${\displaystyle a\in [-\infty ,\infty ],}

${\displaystyle b\in [-1,1],}${\displaystyle b\in [-1,1],}

${\displaystyle c\in [-\infty ,0].}${\displaystyle c\in [-\infty ,0].}

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]

Consider the electronic circuit of Figure 3.

Assume that from different measurements, we know that

${\displaystyle E\in [23V,26V]}${\displaystyle E\in [23V,26V]}

${\displaystyle I\in [4A,8A]}${\displaystyle I\in [4A,8A]}

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

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

${\displaystyle P\in [124W,130W]}${\displaystyle P\in [124W,130W]}

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

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

From the circuit, we have the following equations

${\displaystyle P=EI}${\displaystyle P=EI}

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

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

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

After performing the interval propagation, we get

${\displaystyle E\in [24V,26V]}${\displaystyle E\in [24V,26V]}

${\displaystyle I\in [4.769A,5.417A]}${\displaystyle I\in [4.769A,5.417A]}

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

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

${\displaystyle P\in [124W,130W]}${\displaystyle P\in [124W,130W]}

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

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Interval_propagation&oldid=1157439535"

Categories:

• Algebra of random variables
• Numerical analysis
• Statistical approximations

Hidden categories:

• Articles needing additional references from October 2013
• All articles needing additional references