headlogo

  Arithmétique d’intervalless

Some programming libraries

Interval computation library for ocaml, version 1.3, release date 26/05/2017. The download link is here:Librairie de programmation par intervalle, version 1.3, en date du 26/05/2017. Le lien de téléchargement se trouve ci-dessous:
interval_1.3.tgz.
This library uses assembly code to compute all operations with proper roundings (high/low), and currently ONLY works on intel processors. The package has been developped for linux systems but it looks like it is now working properly with Windows and MacOs, and with gcc and clang.Cette librairie est écrite majoritairement en assembleur et implante correctement la totalité des opérations arithmétiques et transcendentales; elle a été développée et testée principalement sous Linux avec gcc, mais devrait fonctionner maintenant sous Linux, Windows et MacOs, avec gcc et clang.
Documentation is available in the doc/ directory in html, pdf and dvi formats. It is extremely wise to read the whole documentation, even if you intend to only use the interval module, because of the "strange behavior" of the x87 coprocessor. La documentation est disponible dans le répertoire doc/ de l'archive en format html, pdf et dvi. Il est très fortement conseillé de la lire, en raison en particulier du "comportement étrange" du coprocesseur x87.
To build and test, read the README file in the main directory.Pour compiler et lancer les programmes de tests, lire le fichier README dans le répertoire principal
Tests are available in the TESTS/ directory. They are mainly for debugging purpose and quite complicated. You may run them to check that everything is working properly for your machine. The test program runs also a speed test program for your particular architecture. Des tests sont disponibles dans le répertoire TESTS. Ils sont avant destinés à débugger le programme. Vous pouvez les lancer pour vérifier que tout foncionne correctement sur votre machine. Ils comprennent également un programme qui évaluera la vitesse de la libraire sur votre architecture.
Examples are available in the EXAMPLES/ directory. There is a B_AND_B sub-directory with an example of a branch-and-bound algorithm that uses interval arithmetics for function optimization (the example is for the Griewank function, but you can substitute any function you like). Des exemples sont disponibles dans le répertoire EXAMPLES/. On y trouve en particulier un répertoire B_AND_B qui contient une example d'algorithme d'optimisation par branch-and-bound qui utilise l'intervalle d'arithémtique pour la fonction de Griewank (elle peut être remplacée par la fonction de votre choix).
For more information, read our paper at OUD: Pour plus d'information, lire notre papier à OUD:
oud2012.pdf
All bug reports should be sent to:Tous les rapports de bug doivent êtr envoyés à:
jean-marc.alliotATirit.fr
gottelanATrecherche.enac.fr
Happy interval programming...Bonne programmation (par intervalle).

Here you will find ocaml bindings for MPFR and MPFI. They are based on these two excellent multi-precision libraries. The MPFI library is slower than our interval library (see above) because it is more general. Moreover its semantic is quite far from the ocaml semantics. However, it is not limited to double precision. Vous trouverez ci-dessous des bindings ocaml pour les librairies MPFR et MPFI. Ils sont basés sur les deux excellentes librairies que sont MPFR et MPFI. Notre librairie est plus rapide que MPFI, mais MPFI est plus général (la précision peut être augmentée autant que nécessaire alors que nous sommes limités par la précision du processeur). Ceci dit, la sémantique MPFI est très éloignée de la sémantique OCAML.
These bindings are currently preliminaries (some functions are not implemented, and the serialization/deserialization functions are not present, making these objects impossible to Marshall). See the README file inside the archive. Ces bindings sont très préliminaires, certaines fonctions ne sont pas implantées et le fonction de serialization/deserialization n'ont pas été écrites, ce qui fait que les objets de la librairie ne peuvent pas être "Marshallés". Lire le fichier README dans l"archive.
mpfrmpfi_0.1.tgz.
Bug reports should be sent to: Les rapports de bugs doivent être envoyés à:
jean-marc.alliotATirit.fr

If you want to learn more about intervall programming and can read french, the next lines introduce some fundamental (but very basic) notions. Some example on how to use interval programming for Branch and Bound optimizations are available in these slides, either in ppsx or in pdf format. Les paragraphes suivants sont une introduction en français à la programmation par intervalle. On peut également trouver des éléments dans les supports de cours suivants, ppsx et en pdf:
format ppsx
format pdf

1.1  Introduction

Rédigé avec Nicolas Durand

1.1.1  Origine

L’utilisation de l’informatique pour le calcul numérique est la source de différents type d’erreurs, dont notamment d’erreurs d’arrondis. Le but originel de l’analyse d’intervalles était de borner ces erreurs. Dwyer, Sunuga et Wilkinson furent les premiers à utiliser les intervalles pour majorer les erreurs d’arrondi des calculateurs, mais c’est le livre de Moore qui marque le début des mathématiques d’intervalles. Depuis la parution de son livre, plus d’un millier de publications et une vingtaine de livre consacrés à l’analyse d’intervalles sont parus.

1.1.2  Intérêt

Soit la fonction :

f(x,y)=333.75 y6+x2 (11 x2 y2−y6−121 y4−2)
+
5.5 y8+
x
2 y

Si l’on calcule f(77617,33096) avec diverses précisions (simple, double, étendue) sur un pentium 200, le résultat obtenu a toujours pour premières décimales 1.172603. Hors, la bonne valeur a pour premières décimales −0.827396. En utilisant l’arithmétique d’intervalles avec une précision moyenne, on obtient un intervalle assez large contenant la bonne valeur.

1.2  Arithmétique d’intervalles

1.2.1  Intervalles

L’arithmétique d’intervalles est définie sur les intervalles fermés bornés de ℝ. Un intervalles est dit dégénéré s’il est réduit à un point.

1.2.2  Notations

Définition 1 (Intervalle)   Un intervalle de ℝ noté X=[a,b] est l’ensemble des réels x tels que a≤ x ≤ b. Un intervalle de ℝn ou pavé noté X=(X1,..,Xn) est l’ensemble des éléments x=(x1,..,xn) de ℝn tels que :
∀ i∈[1,n] xi∈ Xi

Par la suite les intervalles seront notés en majuscule et les réels ou les éléments de ℝn en minuscule.

Définition 2 (Matrice d’intervalles)   On appelle matrice d’intervalles une matrice dont les éléments sont des intervalles.
Définition 3   Si A est une matrice réelle de terme général aij, et A I est une matrice d’intervalles de terme général Aij, on dira que A∈ A I si aij∈ Aij pour tout (i,j). Si B I ets une matrice d’intervalles de terme général Bij, on dira que B⊂ A si Bij⊂ Aij pour tout (i,j).
Définition 4 (Intervalle dégénéré)   Un intervalle est dégénéré s’il est réduit à un point.

X=[x,x] pourra alors être noté x. Si X=[a,b], on notera XL la valeur a et XR la valeur b.

Définition 5   Un intervalle X=[a,b] sera dit positif si a≥ 0, strictement positif si a>0, négatif si b≤ 0, strictement négatif si b<0. Deux intervalles X=[a,b] et Y=[c,d] sont égaux si et seulement si a=c et b=d.
Définition 6   Un ordre partiel peut être défini sur les intervalles de la façon suivante : X<Y si et seulement si XR<YL.

Toutes ces définitions s’étendent sans aucune difficuté aux intervalles de ℝn.

1.2.3  Opérations élémentaires

Définition 7   Soient +, −, * et / les opérateurs d’addition, de soustraction, de multiplication et de division de l’arithmétique réelle. Si op désigne une de ces opérations, l’opération correspondante pour l’arithmétique d’intervalles sera :
X op Y={x op y | x∈ X, Y∈ Y}

A partir de cette définition, si X=[a,b] et Y=[c,d] alors :

     
X+Y=[a+c,b+d]    (1)
X−Y=[a−d,b−c]    (2)
X*Y=
⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎩
  [ac, bd]sia≥ 0etc≥ 0
[bc, bd]sia≥ 0et c<0<d
[bc, ad]sia≥ 0etd≤ 0
[ad, bd]sia<0<betc≥ 0
[bc, ac]sia<0<betd≤ 0
[ad, bc]sib≤ 0etc≥ 0
[ad, ac]sib≤ 0etc<0<d
[bd, ac]sib≤ 0etd≤ 0
[min(bc,ad),
    max(ac,bd)]sia<0<betc<0<d
    (3)
       (4)
     
1
Y
=
[
1
d
,
1
c
]
si0∉ Y 
    (5)
X
Y
=
X*(
1
Y
)
si0∉ Y 
    (6)
Xn=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
  [1,1]sin=0
[a n,bn]sia≥ 0
 oua≤ 0≤ betnimpair
[bn,a n]sib≤ 0
[0,max(a n,bn)]sia≤ 0≤ betnpair
    (7)
       (8)

1.2.4  Arithmétique étendue

Si l’on complète ℝ en ajoutant les deux éléments −∞ et +∞, la notion d’intervalle peut se généraliser aux fermés de ℝ. On peut alors définir 1/Y lorsque 0∈ Y. Si X=[a,b] et Y=[c,d] avec a, b, c et d valeurs finies et c≤ 0≤ d, c<d alors :

X
Y
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
[
b
c
,∞]
sib≤ 0etd=0
[−∞,
b
d
]⋃ [
b
c
,∞]
sib≤ 0etc<0<d
[−∞,
b
d
]
sib≤ 0etc=0
[−∞,∞]sia<0<b
[−∞,
a
c
]
sia≥ 0etd=0
[−∞,
a
c
]⋃ [
a
d
,∞]
sia≥ 0etc<0<d
[
a
d
,∞]
sia ≥ 0etc=0

Les règles d’addition et de soustraction d’intervalles étendus sont les suivantes1 :

[a,b]+[−∞,d]=[−∞,b+d]
[a,b]+[c,∞]=[a+c,∞]
[a,b]±[−∞,∞]=[−∞,∞]
[a,b]−[−∞,d]=[a−d,∞]
[a,b]−[c,∞]=[−∞,b−c]

Puisque X/Y peut être l’union de 2 intervalles, la règle de composition :

(V⋃ W) ± Z=(V ± Z) ⋃ (W ± Z)

permet de calculer par exemple X/Y ± Z.

1.2.5  Propriétés

Propriété 1 (Sous-distributibité)  
X (Y+Z)⊆X Y+X Z

Par exemple :

[0,1] (1−1)=0
[0,1] 1−[0,1] 1=[−1,1]
Propriété 2 (Commutativité)  
X+Y=Y+X
X Y=Y X

Propriété 3 (Associativité)  
X+(Y+Z)=(X+Y)+Z
X (Y Z)=(X Y) Z
Propriété 4 (Isotonicité d’inclusion)  
X⊆ W  &  Y⊆ Z→X * Y⊆ W * Z

1.2.6  Le problème de dépendance

Si l’on soustrait X=[a,b] avec a≠ b à lui-même, on obtient :

X−X=[a−b,b−a] ≠ [0,0]

En fait X−X={x−y|x∈ X,y∈ X} et non pas {x−x|x∈ X}. Ainsi, l’opération X−X consiste à retrancher de n’importe quelle variable de X, n’importe quelle autre variable de X et non elle-même. Ceci a pour conséquence d’augmenter la taille de l’intervalle image de façon importante. Il est donc important de limiter dès que possible ce problème de dépendance. Il est par exemple plus avantageux d’utiliser la formule (7) pour calculer X*X que d’utiliser les formules de multiplication (3). Ainsi :

[−1,2]2=[0,4]
[−1,2]*[−1,2]=[−2,4]

1.2.7  Fonctions d’intervalles

Définition 8 (Milieu d’un intervalle)   Si X=[a,b], on définit le milieu de X par
m(X)=
a+b
2
Si X=(X1,..,Xn), alors m(X)=(m(X1),..,m(Xn))
Définition 9 (Largeur d’un intervalle)   Si X=[a,b], on définit la largeur de X par
w(X)=b−a
Si X=(X1,..,Xn), alors w(X)=max(w(X1),..,w(Xn))
Définition 10 (Magnitude d’un intervalle)   Si X=[a,b], on définit la magnitude de X par
|X|=max{|a|,|b|}
Définition 11 (Magnitude d’un intervalle)   Si X=[a,b], on définit la mignitude de X par
mig(X)=min{|a|,|b|}
Définition 12   Soit A une matrice (m× n) d’intervalles. On dira que A est diagonalement dominante si :
mig(Aii)≥
n
∑
j=1,j≠ i
|Aij|
Définition 13 (Fonction d’intervalles)   Soit I l’ensemble des intervalles de ℝ, et plus généralement I n l’ensemble des intervalles de ℝn. Une fonction d’intervalles est une fonction F : I n → I.
Définition 14 (Fonction d’inclusion)   Soit une fonction f :ℝn → ℝ, F :I n → I est une fonction d’inclusion de f si :
F(x1,x2,..,xn)=f(x1,x2,..,xn)
Les termes x1, x2, ..xn de gauche représentent ici les intervalles dégénérés [x1,x1], [x2,x2],..,[xn,xn].

Le théorème suivant découle immédiatement de la définition précédente.

Théorème 1   Soit F(X1,..,Xn) une fonction d’inclusion d’une fonction réelle f(x1,..,xn). Alors :
∀ (x1,..,xn) ∈ (X1,..,Xn), f(x1,..,xn)∈ F(X1,..,Xn)

Il existe bien évidemment plusieurs fonction d’inclusions pour une même fonction réelle. Ainsi, la fonction f :x→ x2 a pour fonction d’inclusion :

F1 :X→ X*X
F2 :X→ X2

On vérifiera que F1([−1,1])=[−1,1]≠ F2([−1,1])=[0,1]. Ce ne sont pas les deux seules fonctions d’inclusion, en fait, on peut en fabriquer une infinité. Ainsi :

Fc :X→ (X−c)*(X−c)+2 c X−c2

où c est une constante est encore une fonction d’inclusion de f. De plus, si 0<c<1 Fc([−1,1])=[−1−2 c,1+4 c].

Propriété 5 (Monotonicité d’inclusion)   Si op désigne un des quatre opérateurs arithmétiques précédemment définis et X, Y, W et Z sont des intervalles, alors :
X⊆ W  &  Y⊆ Z→X  op Y⊆ W op Z
Définition 15 (Intervalle image de f)   On notera I[f(X)] le plus petit intervalle contenant l’ensemble {y|∃ x∈ X ,y=f(x)}2.
Définition 16 (Extension naturelle de f)   Soit f une fonction analytique définie à partir des opérateurs arithmétiques +, −, * et /, on notera f(X) la fonction d’inclusion de f définie en remplaçant chaque occurence de xi par un intervalle Xi.

La façon dont est factorisée une fonction f modifie son extension naturelle.

Ainsi, f(x)=xx2 peut s’ecrire f(x)=(x−1/2)2−1/4 et définit ainsi deux extensions naturelles :

F1(X)=X2−X
F2(X)=
(X−
1
2
)2−
1
4

On remarque que F1([0,2])=[−2,4] alors que F2([0,2]=[−1/4,2]=I[f([0,2])]. Il est clair que la deuxième expression de f permet de réduire le problème de dépendance.

Le lecteur trouvera différentes méthodes permettant de produire des fonctions d’inclusion sur un intervalle les meilleures qui soient.

Définition 17 (Qualité d’une fonction d’inclusion)   Soit F une fonction d’inclusion de la fonction f. On notera :
E[f(X1,..,Xn)]=w(F(X))−w(I[f(X)])
Si il existe deux constantes K et є telles que :
∀ X∈ I/w(X)<є , E[f(X1,..,Xn)]≤ K w(X)α 
alors, F est une fonction d’inclusion de f à l’ordre α.
α=1→fonction d’inclusion du premier ordre
α=2→fonction d’inclusion du second ordre

On trouvera la preuve que si f est une fonction rationnelle :

E[f(X)]=O(w(X))

On trouvera la preuve que si f est une fonction rationnelle et peut s’ecrire :

fc(x1,..,xn)=f(c1,..,cn)+g(x1−c−1,..,xn−cn)

où g est une fonction rationnelle et ci=m(Xi) alors

E[fc(X)]=O(w(X)2)

En fait, en utilisant des développement au bon ordre, on peut trouver des formes centrées fc pour lesquelles :

E[fc(X)]=O(w(X)k)

pour tout k fixé dans ℕ.

Ce type de développement n’a d’intérêt que si w(X) est petit.

1.2.8  Fonctions monotones

Si f est monotone, on peut obtenir une fonction d’inclusion telle que E[f(X)]=0 pour tout intervalle X. En effet, si X=[a,b] et f est croissante (resp décroissante) alors f(X)=[f(a),f(b)] (resp [f(b),f(a)]).

Dans le cas de fonctions de plusieurs variables, on peut également utiliser la monotonie de la fonction pour améliorer la qualité de sa fonction d’inclusion. Si f est croissante suivant une variable xi, et si Xi=[ai,bi], alors :

f(X)=[f(X1,..,[ai,ai],..Xn)L, f(X1,..,[bi,bi],..Xn)R]

Si f est dérivable, on peut tester la monotonie de f en utilisant ses dérivées partielles. Par exemple, si :

∂
∂ xi
f(X1,..,Xn)
≥0

alors f est croissante suivant la variable i.

1.2.9  Fonctions fines ou larges

Définition 18   On dira que f est une fonction fine si l’image d’un intervalle dégénéré est un intervalle dégéneré. f sera dite large si l’image d’un intervalle dégénéré est un intervalle non dégénéré.

Par exemple, f(X)=X+[1,2] est une fonction dite large car f(0)=[1,2]

1
a ou c peut valoir −∞ et b ou d peut valoir +∞
2
On remarquera que si f est continue, I[f(X)] est l’image de X par f

Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 09:48, 22/02/2024