Arithmétique d'intervalles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 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. 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 puis en déduire .

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ès 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 est représenté par une paire de nombres flottants . Dire que est représenté par cette paire signifie que appartient à l'intervalle , autrement dit que les assertions et sont vraies. La notion d'égalité d'un nombre et de sa représentation disparaît, sauf si .

On appelle largeur de la représentation la quantité , qui mesure l'incertitude de la représentation.

Opérations 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 ) :
  • addition avec arrondi par excès (vers ) :
  • multiplication avec arrondi par défaut (vers ) :
  • multiplication avec arrondi par excès (vers ) :
  • division avec arrondi par défaut (vers ) :
  • division avec arrondi par excès (vers ) :
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

Principes de calcul[modifier | modifier le code]

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.

Exemple[modifier | modifier le code]

calcul brut
affectation valeur w
X := [10 20] 10
Y := [1 7] 6
R:= X + Y [11 27] 16
S := X - Y [3 19] 16
T := R*S [33 513] 480
W := R+S [14 46] 32
explicitation des dépendances
T := (X+Y)*(X-Y)
W := (X+Y)+(X-Y)
calcul recommandé
affectation valeur w
X := [10 20] 10
Y := [1 7] 6
R:= X + Y [11 27] 16
S := X - Y [3 19] 16
T := X²-Y² [100 400]-[1 49] = [51 399] 348
W := 2*X [20 40] 20

L'amélioration pour W vient de l'identification des dépendances, et de la simplification Y-Y = 0, qui réduit le résultat de 2 w(Y).

L'amélioration pour T vient de la simplification X*X-X*Y+Y*X-Y*Y= X*X-Y*Y d'une part, et du fait que X² est préférable à X*X au sens ci-après.

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 . 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 :

par et par
par . 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.
par  ; pour un intervalle [-4 5], la première donne [-20 25] et w = 45, la seconde [0 25] de largeur 25.
par .
par .

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 alors , noté en bref avec évidemment .

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 , avec f continue entre les bornes et .

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

Voir aussi[modifier | modifier le code]