Arithmétique d'intervalles

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En mathématiques et en informatique, l'arithmétique des intervalles est une méthode de calcul consistant à manipuler des intervalles, par opposition à des nombres (par exemple entiers ou flottants), dans le but d'obtenir des résultats plus rigoureux. Cette approche permet de borner les erreurs d'arrondi ou de méthode et ainsi de développer des méthodes numériques qui fournissent des résultats fiables. L'arithmétique des intervalles est une branche de l'arithmétique des ordinateurs.

Motivations[modifier | modifier le code]

Calcul numérique[modifier | modifier le code]

La représentation concrète d'un nombre réel est en général impossible. Par exemple, écrire 2 = 1,414 est faux, puisque 1,414 élevé au carré vaut exactement 1,999 396 et non 2. Dans un ordinateur, les nombres flottants ne sont que des approximations des nombres réels, et les opérations arithmétiques ne sont en général que des approximations des opérations mathématiques associées. Par exemple, avec un processeur utilisant la norme IEEE 754, le calcul « sin(cos-1(-1)) » donne 1,224 61×10-16 et non 0, qui est la véritable valeur attendue (sin(arccos(-1))=0). Plus problématique, l'évaluation de « sin(cos-1(-1)) = 0 » renvoie faux.

L'arithmétique des intervalles est une méthode qui permet d'encadrer avec certitude le résultat des opérations que l'on effectue. Par exemple on pourra écrire 2 ∈ [2;2] puis en déduire 2 ∈ [1,414 ; 1,415].

Calcul technique[modifier | modifier le code]

La conception ou la vérification d'un système peut mener à des calculs avec des valeurs bornées plutôt que connues exactement. Ainsi l'utilisation de composants connus à 1 %, 5 % voire 20 % présuppose de vérifier si leur dispersion est ou non critique.

Représentation[modifier | modifier le code]

Dans l'arithmétique des intervalles, un nombre réel x est représenté par une paire de nombres flottants (xinf , xsup). Dire que x est représenté par cette paire signifie que x appartient à l'intervalle [xinf , xsup], autrement dit que les assertions xinfx et xxsup sont vraies. La notion d'égalité d'un nombre et de sa représentation disparaît, sauf si xinf = xsup.

On appelle largeur de la représentation la quantité w(x) = xsupxinf, qui mesure l'incertitude de la représentation.

Opérations[modifier | modifier le code]

Opérations arithmétiques de base[modifier | modifier le code]

Les opérateurs de base mettent en jeu au minimum les opérateurs arithmétiques flottants suivants, définis dans la norme IEEE 754

  • changement de signe (vers –∞) : –∞
  • addition avec arrondi par défaut (vers –∞) : +inf
  • addition avec arrondi par excès (vers +∞) : +sup
  • multiplication avec arrondi par défaut (vers –∞) : *inf
  • multiplication avec arrondi par excès (vers +∞) : *sup
  • division avec arrondi par défaut (vers –∞) : /inf
  • division avec arrondi par excès (vers +∞) : /sup
Test si certainement positif ou nul
Test si certainement strictement positif
Test si certainement négatif ou nul
Test si certainement strictement négatif
Test si possiblement nul
Changement de signe
Addition
Multiplication de nombres certainement positifs ou nuls
Multiplication de nombres certainement négatifs ou nuls
Multiplication d'un nombre x possiblement nul par un nombre y certainement positif
Multiplication de nombres possiblement nuls

Fonctions élémentaires[modifier | modifier le code]

Évaluation d'une fonction croissante en arithmétique d'intervalles.

L'arithmétique d'intervalle pour être efficace nécessite des propriétés sur les fonctions. En particulier on dispose de propriétés pour les fonctions monotones.

Pour une fonction monotone d'une variable sur un intervalle [x1 , x2], si elle est croissante (resp. décroissante) alors pour tout y1, y2 ∈ [x1 , x2] tels que y1y2, on a f(y1) ≤ f(y2) (resp. f(y1) ≥ f(y2)). De plus pour tout intervalle [y1, y2] ⊆ [x1 , x2], on peut calculer

On peut donc en tirer des propriétés pour certaines fonctions usuelles :

  • Exponentielle : a[x1 , x2] = [ax1 , ax2] pour a > 1
  • Logarithme : loga [x1 , x2] = [loga x1 , loga x2] pour des intervalles positifs


Plus généralement on peut dire que pour des fonctions monotones par morceaux il suffit de considérer les bornes de l'intervalle [x1 , x2] ainsi que les extremum (ou points critiques) de la fonction sur cet intervalle pour obtenir une évaluation de cette fonction en termes d'intervalles.
Pour les fonctions sinus et cosinus, les points critiques sont les points (12 + n ou nπ pour tout entier n.

Raffinement de l'intervalle[modifier | modifier le code]

Il est parfois utile pour gagner en précision dans l'évaluation de fonction, de réécrire l'intervalle de base sous la forme d'une union d'intervalles. Concrètement pour un intervalle [x , y], on le découpe de la manière suivante :

avec x = x0 et y = xn+1.

Extension aux fonctions de plusieurs variables[modifier | modifier le code]

En général, il est difficile de trouver une description simple de la sortie pour un large spectre de fonctions. En revanche, il est quand même possible d'étendre les fonctions à l'arithmétique d'intervalle. Si est une fonction d'un vecteur réel donnant un réel, alors est appelé l'extension à un intervalle de f si

La définition donnée ne donne cependant pas un résultat précis. Par exemple, [f]([x1 , x2]) = [ex1 , ex2] et [g]([x1 , x2]) = [–∞ , +∞] sont toutes les deux, deux extensions à un intervalle possible de la fonction exponentielle. L'extension la plus précise possible est voulue, tout en prenant en compte les coûts de calcul et les imprécisions. Dans ce cas on choisit [f] de sorte à garder le résultat le plus précis possible.

L'extension naturelle à un intervalle résulte des règles de calcul classiques sur f(x1, ..., xn) et des règles de calcul classiques pour l'arithmétique d'intervalles et les fonctions élémentaires.

L'extension du développement de Taylor à un intervalle (de degré k) est une fonction f k+1 fois différentiable :

pour tout y ∈ [x], où est la i-ème différentielle de f au point y et [r] est l'extension à un intervalle du reste de Taylor :

Valeur moyenne d'une forme

Le vecteur ξ fait le lien entre x et y avec x , y ∈ [x] et ξ est protégé par [x]. D'ordinaire, on choisit y de sorte qu'il soit le milieu de l'intervalle et on utilise l'extension naturel à un intervalle pour évaluer le reste. Le cas spécial de la formule précédente quand k = 0 est connu comme la valeur moyenne d'une forme. Pour l'extension d'intervalle du Jacobien [Jf]([x]) :

Une fonction non linéaire peut être définie à l'aide de propriétés linéaires.

Arithmétique d'intervalles complexe[modifier | modifier le code]

Un intervalle peut également être vu comme un ensemble de points à une distance donnée du centre, et cette définition peut être étendue aux nombres complexes. Comme c'est le cas quand on calcule avec des nombres réelles, les calculs avec des nombres complexes peuvent introduire des erreurs de calculs et d'arrondis. Donc, étant donné qu'un "nombre d'intervalle" est un véritable intervalle fermé et qu'un nombre complexe est une paire ordonnée de nombres réels, il n'y a aucune raison de limiter l'application de l'arithmétique d'intervalles à la mesure des incertitudes dans les calculs avec des nombres réels. L'arithmétique d'intervalles peut ainsi être étendue, via des nombres d'intervalles complexes, pour déterminer les zones d'incertitude dans le calcul avec des nombres complexes.

Les opérations algébriques de base pour les nombres d'intervalles réels (intervalles fermés réels) peuvent être étendues aux nombres complexes. Il n’est donc pas surprenant que l’arithmétique complexe d’intervalles ressemble à l’arithmétique complexe ordinaire, sans toutefois être la même. On peut montrer que, comme dans le cas de l'arithmétique par intervalles réels, il n'y a pas de distributivité entre l'addition et la multiplication de nombres d'intervalles complexes, à l'exception de certains cas particuliers, et que les éléments inverses n'existent pas toujours pour les nombres d'intervalles complexes. Deux autres propriétés utiles de l'arithmétique complexe classique n'existent pas dans l'arithmétique d'intervalle complexe : les propriétés additives et multiplicatives, des conjugués complexes ordinaires, n'existent plus pour les conjugués complexes d'intervalles.

L'arithmétique d'intervalles peut être étendue, de manière analogue, à d'autres systèmes de nombres multidimensionnels tels que les quaternions et les octonions, mais cela a un coût : nous devons sacrifier d'autres propriétés utiles de l'arithmétique ordinaire.

Utilisation de l'arithmétique d'intervalles[modifier | modifier le code]

Exemple d'un calcul simple[modifier | modifier le code]

Avec les définitions données précédemment il est déjà possible de calculer certains intervalles dans lesquels se trouve le résultat de l'évaluation de certaines fonctions.

Par exemple avec la fonction f(a,b,x) = a × x + b et a = [1,2], b = [1,2] et x = [1,2] on obtient :

Il est aussi possible de résoudre des équations avec des intervalles. En reprenant la même fonction f et les mêmes valeurs pour a et b on a :
Ainsi les valeurs d'annulation possibles de la fonction sont dans l'intervalle [-7, -2.5].

Règle de Karl Nickel[modifier | modifier le code]

L'évaluation directe d'une expression n'est exacte en calcul d'intervalles que si chaque variable n'a qu'une occurrence, ces variables étant indépendantes.

Observer la règle indiquée est critique, toute évaluation trop large nuisant à l'intérêt du résultat.

Par exemple, on considère la fonction f définie par f(x) = x2 + x. Les valeurs de cette fonction sur l'intervalle [–1 ; 1] sont [–14, 2 ]. Avec les règles de calcul sur les intervalles on aurait en revanche obtenu [–1, 2] qui est plus large.

Une autre expression peut être utilisée pour calculer cette valeur :

et on obtient cette fois le résultat premièrement énoncé :

Il peut être montré que le résultat peut être exact si chaque valeur apparaît exactement une fois dans l'expression de la fonction et si f est continu dans l'intervalle d'évaluation. Toutefois il n'est pas possible de réécrire toutes les fonctions de cette manière.

Expressions préférables[modifier | modifier le code]

Lorsque, pour des valeurs isolées, on a f(x) = g(x), on trouve souvent en termes d'intervalles que f(x) ⊇ g(x). Alors, g(x) est dite préférable à ou plus fine que f(x). Et c'est la forme préférable si elle satisfait la règle de Nickel. En ce sens, on remplacera :

xx par 0 et x/x par 1
x * y/(x+y) par 1/(1/x + 1/y). En effet, soit x = [1 ; 2] et y = [3 ; 5]. Avec la première formule, le produit vaut [3 10], la somme [4 ; 7] et leur quotient [0,42 ; 2,5], avec une largeur de 2,08. La seconde formule donne 1/[0,7 1,33] = [0,75 1,43]. Toujours licite, cette seconde valeur a une largeur réduite à 0,68.
x * x par x2 ; pour un intervalle [-4 ; 5], la première donne [-20 ; 25] et w = 45, la seconde [0 ; 25] de largeur 25.
x * z + y * z par (x + y) * z.
(x + y)*(xy) par x2y2.

L'avant-dernière formule est typique : la plupart des distributivités classiques entraînent en termes d'intervalles des sous-distributivités, dont chacune fournit une règle d'amélioration.

Notion d'extervalle[modifier | modifier le code]

Des difficultés introduites par la division peuvent être contournées grâce à la notion d' extervalle, inverse d'un intervalle contenant 0. Pour cela, si a < 0 < b alors inv([a \ b]) = (–1 \ 1/a] ∪ [1/b \ + 1), noté en bref < 1/a][1/b>, avec évidemment inv(< a][b>) = [1/a \ 1/b].

Soit à calculer pour x = [10 ; 20] et y =[-2 ; +2].

Alors qui est bien la valeur cherchée.

En pratique[modifier | modifier le code]

Tout calcul en intervalles doit être précédé d'une inspection voire d'une mise en forme, recourant s'il le faut à l'historique de calcul, en vue de n'utiliser que des formes préférables conformes à la règle ci-dessus.

Recherche de zéros sur un axe[modifier | modifier le code]

La recherche des zéros d'une fonction présente avec l'arithmétique ordinaire une difficulté particulière lorsque le nombre de zéros entre deux bornes n'est pas connu. L'arithmétique des intervalles permet d'encapsuler avec certitude les solutions.

Soit à résoudre f(x) = 0, avec f continue entre les bornes xmin et xmax.

  • Si l'intervalle f((xmin,xmax)) ne contient pas zéro, alors on est certain qu'il n'y a pas de racine entre xmin et xmax.
  • Si aucun des deux intervalles f((xmin,xmin)) et f((xmax,xmax)) ne contient zéro et qu'ils sont de signes différents, alors il y a au moins un zéro entre xmin et xmax.
  • Dans les autres cas, ou pour raffiner la recherche, on introduit une borne intermédiaire et on recommence.

Histoire[modifier | modifier le code]

L'arithmétique d'intervalles n'est pas une théorie complètement nouvelle en mathématiques ; elle est apparue plusieurs fois sous différents noms au cours de l'histoire. Par exemple Archimède avait déjà calculé des bornes supérieures et inférieures pour π au 3e siècle av. J.-C. : 223/71 < π < 22/7. Toutefois le calcul avec des intervalles n'a jamais été vraiment aussi populaire que d'autres techniques numériques, mais il n'a jamais non plus été oublié.

Les règles de l'arithmétique d'intervalles ont été publiées en 1931 par Rosalind Cicely Young, une doctorante à Université de Cambridge. D'autres travaux ont été publiés par la suite, dans un livre d'algèbre linéaire en 1951 par Paul Dwyer (Université du Michigan), et permettent d'améliorer la fiabilité de systèmes numériques. Les intervalles étaient utilisés pour mesurer les erreurs d'arrondis dues aux nombres flottants. Un article sur l'algèbre d'intervalles en analyse numérique a été publié par Teruo Sunaga en 1958[1].

La naissance de l'arithmétique d'intervalles moderne est marquée par le livre Interval Anallysis de Ramon E. Moore en 1966. Il a l'idée au printemps 1958, et une année plus tard il publie un article sur l'arithmétique d'intervalles. Son mérite est, à partir d'un principe simple, de donner une méthode générale pour calculer les erreurs de calculs, et pas seulement celles résultant des arrondis.

Indépendamment en 1956, Mieczyslaw Warmus suggère une forme pour le calcul avec des intervalles bien que ce soit Moore qui ait trouvé les premières applications non-triviales.

Dans les vingt années suivantes, des chercheurs allemands ont réalisé des travaux novateurs dans le domaine. Parmi eux Götz Alef et Ulrich Kulisch à l'Université de Karlsruhe. Par exemple, Karl Nickel a exploré de meilleures implémentations, tandis qu'Arnold Neumaier, entre autres, devait améliorer les procédures de confinement de l'ensemble de solutions de systèmes d'équations. Dans les années 1960, Eldon R. Hansen a travaillé sur des extensions de l'arithmétique d'intervalles pour les équations linéaires, puis a apporté des contributions majeures à l'optimisation globale, y compris ce que l'on appelle maintenant la méthode de Hansen, un des algorithmes d'intervalle les plus largement utilisés. Les méthodes classiques dans ce domaine ont souvent des difficultés pour déterminer la plus grande (ou la plus petite) valeur locale, mais elles ne peuvent que trouver un optimum local et échouent à trouver de meilleures valeurs; Helmut Ratschek et Jon George Rokne ont mis au point des méthodes de Séparation et évaluation, qui jusque-là ne s'appliquaient qu'aux entiers, en utilisant des intervalles pour fournir des applications aux valeurs continues.

En 1988, Rudolf Lohner a développé un logiciel en Fortran pour des problèmes de solutions fiables avec valeur initiale en utilisant des équations différentielles ordinaires[2].

La revue Reliable Computing (à l'origine Interval Computations), publiée depuis les années 1990, est consacrée à la fiabilité des calculs assistés par ordinateur. En tant que rédacteur en chef, R. Baker Kearfott, en plus de ses travaux sur l'optimisation globale, a largement contribué à l'unification de la notation et de la terminologie utilisées en arithmétique d'intervalles.

Au cours des dernières années, les travaux portés par l’INRIA à Sophia Antipolis ont porté en particulier sur l’estimation des images préalables de fonctions paramétrées et sur la théorie du contrôle robuste.

IEEE Std 1788-2015 – standard IEEE pour l'arithmétique d'intervalles[modifier | modifier le code]

Une norme pour l'arithmétique d'intervalles a été approuvée en juin 2015[3]. Deux implémentations de référence sont disponibles gratuitement[4]. Celles-ci ont été développées par des membres du groupe de travail de la norme: la bibliothèque libieeep1788[5] pour C ++ et le paquet d'intervalle pour GNU Octave[6].

Un sous-ensemble minimal de la norme, IEEE Std 1788.1-2017, a été approuvé en décembre 2017 et publié en février 2018. Il devrait être plus facile à mettre en œuvre[7].

Notes et références[modifier | modifier le code]

  1. Sunaga, Teruo, « Theory of interval algebra and its application to numerical analysis », RAAG Memoirs,‎ , p. 29-46
  2. (de) Ralph Pape, « Hauptseminar: Differentialgleichungen », sur fam-pape.de,
  3. « IEEE Standard for Interval Arithmetic »
  4. (en) Nathalie Revol, « The (near-)future IEEE 1788 standard for interval arithmetic. 8th small workshop on interval methods. », Small Workshop on Interval Methods (conférence),‎ 9/11 juin 2015 (lire en ligne [PDF])
  5. « C++ implementation of the preliminary IEEE P1788 standard for interval arithmetic »
  6. « GNU Octave interval package »
  7. « "IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)" »

Voir aussi[modifier | modifier le code]