Arithmétique d'intervalles

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.

MotivationsModifier

Calcul numériqueModifier

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 techniqueModifier

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.

Preuve de programmesModifier

Dans la mesure où lorsqu'on travaille en intervalles on sait avec précision les limitations de ce qu'on traite, cette représentation permet d'élargir le domaine des preuves de programmes[1],[2].

ReprésentationModifier

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érationsModifier

Opérations arithmétiques de baseModifier

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émentairesModifier

 
É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'intervalleModifier

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 variablesModifier

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 complexeModifier

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 en nombres réels, les calculs en nombres complexes introduisent en général des erreurs de calculs et d'arrondis, dus au fait qu'on les représente avec une précision limitée. On définit donc un type de nombre "intervalle", correspondant à un intervalle mathématique fermé.

Dans le cas d'un entier, par exemple, 18±2, dans le cas d'un réel 3.14±0.01. Le cas des nombres complexes est plus délicat, leur "flou" n'étant pas le même selon qu'on les représente en cartésien (réel et imaginaire) ou en polaire (angle et module). Néanmoins, on peut le majorer.

L'arithmétique d'intervalles peut ainsi être étendue, via des nombres d'intervalle réels ou complexes[3], pour déterminer les zones d'incertitude dans le calcul. Ce qui compte est que le résultat soit garanti se trouver dans la zone d'incertitude d'une part, et pour l'analyste numérique de choisir la méthode de calcul laissant cette zone aussi petite que possible d'autre part.

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. L’arithmétique complexe d’intervalles ressemble à l’arithmétique complexe ordinaire, chaque nombre convoyant son flou avec lui dans les calculs. Ce type d'intervalle est reconnu par des langages comme NARS2000, en nombres entiers dans sa version actuelle (avril 2020) et en flottants de précision arbitraire réels ou complexes dans sa version "alpha".


Il n'existe pas de distributivité entre l'addition et la multiplication de nombres d'intervalles réels ni complexes, en général. Les éléments inverses n'existent pas toujours non plus 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. Cela exige de sacrifier d'autres propriétés utiles de l'arithmétique ordinaire.

Utilisation de l'arithmétique d'intervallesModifier

Exemple d'un calcul simpleModifier

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 = [5,7] et x = [2,3] 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 NickelModifier

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érablesModifier

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'extervalleModifier

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 pratiqueModifier

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 axeModifier

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.

HistoireModifier

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. 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[4].

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[5].

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.

Certains langages comme APL dans son implémentation NARS2000 permettent les calculs en arithmétique d'intervalles, y compris avec des matrices de nombres hypercomplexes[6].

IEEE Std 1788-2015 – standard IEEE pour l'arithmétique d'intervallesModifier

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

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[11].

Notes et référencesModifier

  1. https://www.lri.fr/~melquion/doc/06-these.pdf
  2. https://www.irif.fr/~tasson/doc/cours/cours_pp.pdf
  3. Similitude et différence entre arithmétique d'intervalle et plage d'incertitude numérique
  4. Sunaga, Teruo, « Theory of interval algebra and its application to numerical analysis », RAAG Memoirs,‎ , p. 29-46
  5. (de) Ralph Pape, « Hauptseminar: Differentialgleichungen », sur fam-pape.de,
  6. http://wiki.nars2000.org/index.php/Ball_Arithmetic
  7. « IEEE Standard for Interval Arithmetic »
  8. (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])
  9. « C++ implementation of the preliminary IEEE P1788 standard for interval arithmetic »
  10. « GNU Octave interval package »
  11. « "IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)" »

Voir aussiModifier