Arithmétique d'intervalles

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,999396 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⁻¹⁶ 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].

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.

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

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

${\displaystyle \left(\left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)\geq 0\right):=\left(x_{\mathrm {inf} }\geq 0\right)}$

Test si certainement strictement positif

${\displaystyle \left(\left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)>0\right):=\left(x_{\mathrm {inf} }>0\right)}$

Test si certainement négatif ou nul

${\displaystyle \left(\left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)\leq 0\right):=\left(x_{\mathrm {sup} }\leq 0\right)}$

Test si certainement strictement négatif

${\displaystyle \left(\left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)<0\right):=\left(x_{\mathrm {sup} }<0\right)}$

Test si possiblement nul

${\displaystyle \left(0\in \left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)\right):=\left(x_{\mathrm {inf} }\leq 0\land x_{\mathrm {sup} }\geq 0\right)}$

Changement de signe

${\displaystyle -\left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right):=\left(-x_{\mathrm {sup} },-x_{\mathrm {inf} }\right)}$

Addition

${\displaystyle \left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)+\left(y_{\mathrm {inf} },y_{\mathrm {sup} }\right):=\left(x_{\mathrm {inf} }+_{\mathrm {inf} }y_{\mathrm {inf} },x_{\mathrm {sup} }+_{\mathrm {sup} }y_{\mathrm {sup} }\right)}$

Multiplication de nombres certainement positifs ou nuls

${\displaystyle \left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)*\left(y_{\mathrm {inf} },y_{\mathrm {sup} }\right):=\left(x_{\mathrm {inf} }*_{\mathrm {inf} }y_{\mathrm {inf} },x_{\mathrm {sup} }*_{\mathrm {sup} }y_{\mathrm {sup} }\right)}$

Multiplication de nombres certainement négatifs ou nuls

${\displaystyle \left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)*\left(y_{\mathrm {inf} },y_{\mathrm {sup} }\right):=\left(-\left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)\right)*\left(-\left(y_{\mathrm {inf} },y_{\mathrm {sup} }\right)\right):=\left(x_{\mathrm {sup} }*_{\mathrm {inf} }y_{\mathrm {sup} },x_{\mathrm {inf} }*_{\mathrm {sup} }y_{\mathrm {inf} }\right)}$

Multiplication d'un nombre x possiblement nul par un nombre y certainement positif

${\displaystyle \left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)*\left(y_{\mathrm {inf} },y_{\mathrm {sup} }\right):=\left(x_{\mathrm {inf} }*_{\mathrm {inf} }y_{\mathrm {sup} },x_{\mathrm {sup} }*_{\mathrm {sup} }y_{\mathrm {sup} }\right)}$

Multiplication de nombres possiblement nuls

${\displaystyle \left(x_{\mathrm {inf} },x_{\mathrm {sup} }\right)*\left(y_{\mathrm {inf} },y_{\mathrm {sup} }\right):=\left(\min \left(x_{\mathrm {inf} }*_{\mathrm {inf} }y_{\mathrm {sup} },x_{\mathrm {sup} }*_{\mathrm {inf} }y_{\mathrm {inf} }\right),\max \left(x_{\mathrm {inf} }*_{\mathrm {sup} }y_{\mathrm {inf} },x_{\mathrm {sup} }*_{\mathrm {sup} }y_{\mathrm {sup} }\right)\right)}$

É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 ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }$ sur un intervalle [x₁ , x₂], si elle est croissante (resp. décroissante) alors pour tout y₁, y₂ ∈ [x₁ , x₂] tels que y₁ ≤ y₂, on a f(y₁) ≤ f(y₂) (resp. f(y₁) ≥ f(y₂)). De plus pour tout intervalle [y₁, y₂] ⊆ [x₁ , x₂], on peut calculer

$${\displaystyle f([y_{1},y_{2}])=[\min\{f(y_{1}),f(y_{2})\},\max\{f(y_{1}),f(y_{2})\}]}$$

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

• Exponentielle : a^{[x₁ , x₂]} = [a^x₁ , a^x₂] pour a > 1
• Logarithme : log_a [x₁ , x₂] = [log_a x₁ , log_a x₂] 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 [x₁ , x₂] 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 (¹⁄₂ + n)π ou nπ pour tout entier n.

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 :

$${\displaystyle [x,y]=\bigcup _{i}[x_{i},x_{i+1}]}$$

avec x = x₀ et y = x_n+1.

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 ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ est une fonction d'un vecteur réel donnant un réel, alors ${\displaystyle [f]:[\mathbb {R} ]^{n}\rightarrow [\mathbb {R} ]}$ est appelé l'extension à un intervalle de f si

$${\displaystyle [f]([\mathbf {x} ])\supseteq \{f(\mathbf {y} )|\mathbf {y} \in [\mathbf {x} ]\}}$$

La définition donnée ne donne cependant pas un résultat précis. Par exemple, [f]([x₁ , x₂]) = [e^x₁ , e^x₂] et [g]([x₁ , x₂]) = [–∞ , +∞] 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(x₁, ..., x_n) 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 :

$${\displaystyle [f]([\mathbf {x} ]):=f(\mathbf {y} )+\sum _{i=1}^{k}{\frac {1}{i!}}\mathrm {D} ^{i}f(\mathbf {y} )\cdot ([\mathbf {x} ]-\mathbf {y} )^{i}+[r]([\mathbf {x} ],[\mathbf {x} ],\mathbf {y} )}$$

pour tout y ∈ [x], où ${\displaystyle \mathrm {D} ^{i}f(\mathbf {y} )}$ est la i-ème différentielle de f au point y et [r] est l'extension à un intervalle du reste de Taylor :

$${\displaystyle r(\mathbf {x} ,\xi ,\mathbf {y} )={\frac {1}{(k+1)!}}\mathrm {D} ^{k+1}f(\xi )\cdot (\mathbf {x} -\mathbf {y} )^{k+1}.}$$

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 [J_f]([x]) :

$${\displaystyle [f]([\mathbf {x} ]):=f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot ([\mathbf {x} ]-\mathbf {y} )}$$

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

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 :

$${\displaystyle f(a,b,x)=([1,2]\times [2,3])+[5,7]=[1\times 2,2\times 3]+[5,7]=[7,13]}$$

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 :

$${\displaystyle f([1,2],[5,7],x)=([1,2]\times x)+[5,7]=0\Longleftrightarrow [1,2]\times x=[-7,-5]\Longleftrightarrow x={\frac {[-7,-5]}{[1,2]}}}$$

Ainsi les valeurs d'annulation possibles de la fonction sont dans l'intervalle [-7, -2.5].

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) = x² + x. Les valeurs de cette fonction sur l'intervalle [–1 ; 1] sont [–¹⁄₄, 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 :

$${\displaystyle f(x)=\left(x+{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}}$$

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

$${\displaystyle \left([-1,1]+{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}=\left[-{\frac {1}{2}},{\frac {3}{2}}\right]^{2}-{\frac {1}{4}}=\left[0,{\frac {9}{4}}\right]-{\frac {1}{4}}=\left[-{\frac {1}{4}},2\right]}$$

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.

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 :

x – x 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 x² ; 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)*(x – y) par x² – y².

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.

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 ${\displaystyle {\frac {x+5y}{x+3y}}=1+{\frac {2y}{x+3y}}=1+{\frac {2}{x/y+3}}}$ pour x = [10 ; 20] et y =[-2 ; +2].

Alors ${\displaystyle inv(y)=\langle -1/2][1/2\rangle ;x/y=[10\ 20]*\langle -1/2][1/2\rangle =\langle -5][5\rangle ;x/y+3=\langle -2][8\rangle$ ;{\frac {2}{x/y+3}}=2*[-1/2\ 1/8]=[-1\ 1/4];1+{\frac {2y}{x+3y}}=[0\ 5/4]} qui est bien la valeur cherchée.

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.