Annexe
A.3 Arithmétique des intervalles
A.3.3 Hiérarchie d'intervalles
L'utilisation d'une hiérarchie d'intervalles qui consiste à découper en deux un intervalle de manière récursive, a fait apparaître certaines aberrations lors de simples multiplications par exemple. Admettons que nous définissions une hiérarchie d'intervalles sur l'intervalle et que l'on effectue une multiplication par l'intervalle . Au niveau le plus élevé de la hiérarchie, le résultat donne . Au niveau suivant, nous obtenons pour deux intervalles : et d'où les deux nouveaux résultats : et . On remarque qu'il y a un recouvrement de ces deux résultats qui correspondra à un double balayage inutile de l'intervalle . On peut définir un taux de recouvrement correspondant à la largeur de l'intervalle balayé inutilement sur la largeur de l'intervalle résultat au niveau le plus élevé, dans notre cas ce taux = . Si l'on effectue les mêmes multiplications au niveau inférieurs (4 multiplications), le taux de recouvrement passe à .
Les pertes de temps de calcul sont donc importantes. Nous avons essayé de modifier l'opérateur de multiplication de l'équation 129 mais on obtient un résultat encore plus gênant avec des zones non-recouvertes. La seule solution consiste en la mise en place d'un nouvel opérateur spécifique à la multiplication d'une hiérarchie d'intervalles. Nous proposons de prendre la moyenne de la borne haute de et de la borne basse de . Plus formellement, si et , alors :
|
(131) |
Et l'on peut dans ce cas obtenir la même borne intermédiaire, d'où les deux résultats : et . Cette nouvelle multiplication ne nécessite qu'une division par deux supplémentaire pour deux résultats.