An Interval Extension Based on Occurrence Grouping: Method and Properties - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

An Interval Extension Based on Occurrence Grouping: Method and Properties

Résumé

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.
L'analyse d'intervalles a proposé plusieurs extensions aux intervalles qui essaient de calculer des images étroites des fonctions. En particulier, quand une fonction f est monotone par rapport à une variable sur un domaine donné, il est bien connu que l'extension aux intervalles par monotonie de f permet de calculer un intervalle image plus étroit que l'extension naturelle. Cet article présente une nouvelle extension aux intervalles d'une fonction f appelée regroupement d'occurrences et notée [f]_{og}. Quand f n'est pas monotone par rapport à une variable x sur un domaine donné, nous essayons de transformer f en une nouvelle fonction f^{og} qui est monotone par rapport à deux sous-ensembles x_a et x_b des occurrences de x : f^{og} est croissante par rapport à x_a et décroissante par rapport à x_b. [f]_{og} est l'extension aux intervalles par monotonie de f^{og} et produit une image plus étroite que l'extension naturelle. Pour trouver un bon regroupement d'occurrences, nous proposons un programme linéaire et un algorithme qui minimisent une surestimation du diamètre de l'image de [f]_{og} basée sur une forme de Taylor de f. Finalement, des expérimentations montrent les avantages de cette nouvelle extension pour la résolution de systèmes d'équations non linéaires.
Fichier principal
Vignette du fichier
RR-7806.pdf (549.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00642819 , version 1 (18-11-2011)

Identifiants

  • HAL Id : hal-00642819 , version 1

Citer

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⟩
331 Consultations
635 Téléchargements

Partager

Gmail Facebook X LinkedIn More