En matemáticas numéricas , la propagación de intervalo o la propagación de restricción de intervalo es el problema de contraer dominios de intervalo asociados a variables de R sin eliminar ningún valor que sea consistente con un conjunto de restricciones (es decir, ecuaciones o desigualdades). Se puede utilizar para propagar incertidumbres en situaciones en las que los errores están representados por intervalos . [1] La propagación de intervalos considera un problema de estimación como un problema de satisfacción de restricciones .
Contratistas atómicos
Un contratista asociado a una ecuación que involucra las variables x 1 , ..., x n es un operador que contrae los intervalos [ x 1 ], ..., [ x n ] (que se supone que encierran las x i ) sin quitar ningún valor de las variables que sea consistente con la ecuación.
Se dice que un contratista es atómico si no está construido como una composición de otros contratistas. La teoría principal que se utiliza para construir contratistas atómicos se basa en análisis de intervalos .
Ejemplo . Considere, por ejemplo, la ecuación
que involucra las tres variables x 1 , x 2 y x 3 .
El contratista asociado viene dado por las siguientes declaraciones
Por ejemplo, si
el contratista realiza el siguiente cálculo
Para otras restricciones, se debe escribir un algoritmo específico para implementar el contratista atómico. Una ilustración es el contratista atómico asociado a la ecuación.
se proporciona en las Figuras 1 y 2.
Descomposición
Para restricciones más complejas, se debe realizar una descomposición en restricciones atómicas (es decir, restricciones para las que existe un contratista atómico). Considere, por ejemplo, la restricción
podría descomponerse en
Los dominios de intervalo que deben asociarse a las nuevas variables intermedias son
Propagación
El principio de la propagación del intervalo es llamar a todos los contratistas atómicos disponibles hasta que no se pueda observar más contracción. [2] Como resultado del teorema de Knaster-Tarski , el procedimiento siempre converge a intervalos que encierran todos los valores factibles para las variables. Se puede realizar una formalización de la propagación del intervalo gracias al álgebra del contratista . La propagación por intervalos converge rápidamente con el resultado y puede resolver problemas que involucran varios cientos de variables. [3]
Ejemplo
Considere el circuito electrónico de la Figura 3.
Suponga que a partir de diferentes medidas, sabemos que
Del circuito, tenemos las siguientes ecuaciones
Después de realizar la propagación del intervalo, obtenemos
Referencias
- ^ Jaulin, L .; Braems, I .; Walter, E. (2002). Métodos de intervalo para identificación no lineal y control robusto (PDF) . En Actas de la 41ª Conferencia IEEE sobre Decisión y Control (CDC).
- ^ Cleary, JL (1987). Aritmética lógica . Futuros sistemas informáticos.
- ^ Jaulin, L. (2006). Localización de un robot submarino mediante la propagación de restricciones de intervalo (PDF) . En Actas de CP 2006.