An Interval Extension Based on Occurrence Grouping: Method and Properties

Ignacio Araya 1 Bertrand Neveu 2 Gilles Trombettoni 3, 4, *
* Corresponding author
3 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
4 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
Abstract : In interval arithmetics, special care has been brought to the definition of interval extension functions that compute narrow interval images. In particular, when a function f is monotonic w.r.t. a variable in a given domain, it is well-known that the monotonicity-based interval extension of f computes a sharper (interval) image than the natural interval extension does. This paper presents a so-called ''occurrence grouping'' interval extension [f]_{og} of a function f. When f is not monotonic w.r.t. a variable x in a given domain, we try to transform f into a new function f^{og} that is monotonic w.r.t. two subsets x_a and x_b of the occurrences of x: f^{og} is increasing w.r.t. x_a and decreasing w.r.t. x_b. [f]_{og} is the interval extension by monotonicity of f^{og} and produces a sharper interval image than the natural extension does. For finding a good occurrence grouping, we propose a linear program and an algorithm that minimize a Taylor-based over-estimate of the image diameter of [f]_{og}. Experiments show the benefits of this new interval extension for solving systems of nonlinear equations.
Document type :
Reports
Liste complète des métadonnées

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00642819
Contributor : Gilles Trombettoni <>
Submitted on : Friday, November 18, 2011 - 7:28:44 PM
Last modification on : Monday, November 5, 2018 - 3:48:02 PM
Document(s) archivé(s) le : Friday, November 16, 2012 - 11:30:23 AM

File

RR-7806.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00642819, version 1

Citation

Ignacio Araya, Bertrand Neveu, Gilles Trombettoni. An Interval Extension Based on Occurrence Grouping: Method and Properties. [Research Report] RR-7806, INRIA. 2011, pp.26. ⟨hal-00642819⟩

Share

Metrics

Record views

660

Files downloads

638