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 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
which involves the three variables x1,x2 and x3.
The associated contractor is given by the following statements
![{\displaystyle [x_{3}]:=[x_{3}]\cap ([x_{1}]+[x_{2}])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/732528ad8bf9b28b0851b638dbf10a59704283c7)
![{\displaystyle [x_{1}]:=[x_{1}]\cap ([x_{3}]-[x_{2}])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90c40d48a96a2a1d34be728721c0fc05e489cc11)
![{\displaystyle [x_{2}]:=[x_{2}]\cap ([x_{3}]-[x_{1}])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da4cbddbe15d801c3de706a117942a6b45c30a00)
For instance, if
![{\displaystyle x_{1}\in [-\infty ,5],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2b6c7d96609b720e0839ff5bf0ead4beb92052c)
![{\displaystyle x_{2}\in [-\infty ,4],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9db43b4901aa98257c1aeb8e476a9c28624a28e0)
![{\displaystyle x_{3}\in [6,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cce7f1c0b9268d4593fc1d12e2decc7590583b0)
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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f6f64a60a4628434b81fd529da46b17aceed9b1)
![{\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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8c564fe464fe6118e57fb401dab9eed8ea108b5)
![{\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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7974daac866a947d873a3bc8b5f75de76cf512e6)
For other constraints, a specific algorithm for implementing the atomic contractor should be written. An illustration is the atomic contractor associated to the equation
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
could be decomposed into
The interval domains that should be associated to the new intermediate variables are
![{\displaystyle a\in [-\infty ,\infty ],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8578c13eeee2dabddbbe333f85eadb6df4a92bc)
![{\displaystyle b\in [-1,1],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d106e33944553d0c7a17e223ed20134e366cc985)
![{\displaystyle c\in [-\infty ,0].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d50fb2d2dc32061898dab423a36c5825de4e241)
![{\displaystyle E\in [23V,26V]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/185b34b34288964ae81dda50bf6ab7c3ee78c353)
![{\displaystyle I\in [4A,8A]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5d1f323240d3a82e83cd95e8f22eaeb53cdb85d)
![{\displaystyle U_{1}\in [10V,11V]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab05c079717be65686ba5eab9377f233a24473b7)
![{\displaystyle U_{2}\in [14V,17V]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/410fd82a58749506ba8bcff3ba66ae1cd47bc4ed)
![{\displaystyle P\in [124W,130W]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/220fd970a4c0d720b155e032933d8a1d3fce49a1)
![{\displaystyle R_{1}\in [0\Omega ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7642fd80ec697592a4dfe9265c94ac4db791c82)
![{\displaystyle R_{2}\in [0\Omega ,\infty ].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd022b00e1abe16dc879ff97b5bd3cbaacb4092a)
![{\displaystyle E\in [24V,26V]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43b5243705cb4b19efc88d7ca30f5e1235595127)
![{\displaystyle I\in [4.769A,5.417A]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c53048434ae992e64734b24fcb414b43dcca599d)
![{\displaystyle U_{2}\in [14V,16V]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edea49c3f113c9d892db0b508d29f3bb4c847acf)
![{\displaystyle R_{1}\in [1.846\Omega ,2.307\Omega ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99d6b870dd044ad6d088e56b3619679522144583)
![{\displaystyle R_{2}\in [2.584\Omega ,3.355\Omega ].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b35f1f8750041d48e87e90456a7ec79fa49745f7)