Arithmétique pour le calcul géométrique

Un problème de précision

Le calcul flottant dans les ordinateurs n'est pas exact, mais arrondi. Le résultat numérique d'un calcul est en général seulement voisin du résultat exact et non égal à celui-ci. Si on recherche une valeur numérique ces imprécisions sont souvent acceptables. Si on cherche à prendre une décision logique (par exemple basée sur le signe d'un calcul) celle-ci sera généralement bonne, mais quelquefois fausse (si la valeur est voisine de zéro, le signe est incertain) et les conséquences peuvent être importantes sur le déroulement des algorithmes.

Un exemple : l'orientation d'un triangle

Trois points p,q,r peuvent définir un triangle orienté dans le sens direct, indirect ou peuvent être alignés.

Ces trois cas correspondent à une valeur positive, négative ou nulle du déterminant :

displaymath11

Le calcul arrondi fait des erreurs

Supposons que l'on dispose d'une machine très peu précise qui ne calcule qu'avec deux chiffres significatifs en base 10 (les vraies machines calculent de la même façon mais en base 2 avec en général 24 ou 53 chiffres).

Prenons comme coordonnées pour les points

  • p = (-94,0)
  • q = (92,68)
  • r = (400,180)
La vraie valeur du déterminant est
(92+94)*180-(400+94)*68=186*180-494*68=33480-33592=-112
La valeur calculée par notre machine est
(92+94)*180-(400+94)*68=190*180-490*68=34000-33000=+1000

Le triangle pqr est en réalité indirect, mais le calcul arrondi se trompe. Ces erreurs peuvent entrainer des problèmes d'incohérence. Mathématiquement, si les triangles pqt, qrt et rpt sont direct alors pqr est également direct.

Ce genre de théorème mathématiquement juste peut se trouver invalidé par des tests en machine à cause des erreurs d'arrondis. L'algorithme qui se basait sur ce théorème risque alors de rentrer dans un boucle infinie ou de planter.


Le calcul arrondi ne fait pas tant d'erreur que ça

On l'a vu le calcul arrondi fait des erreurs, mais heureusement, pas tant que ça. Une erreur ne peut se produire que si la valeur obtenue par le calcul arrondi est assez petite.

La courbe ci contre donne la probabilité que la valeur du determinant soit plus petite qu'une valeur donnée A si les points p, q et r sont pris au hasard uniformément dans un cercle.

On peut utiliser ce résultat pour montrer que si on calcule avec l'arithmétique habituelle en double précision, le test sera faux avec une probabilité inférieure à tex2html_wrap_inline8


On peut calculer exactement

Ce qu'il faut bien comprendre, c'est que fournir le résultat exact du test d'orientation, ou de tout autre prédicat, ne signifie pas calculer exactement le déterminant, mais juste être sur de son signe.

Quand la valeur arrondie calculée par l'arithmétique arrondie est suffisamment grande pour que l'on puisse certifier son signe, on peut utiliser le résultat du test flottant.

Si la valeur calculée est trop proche de zéro il faut faire autre chose. On utilise l'arithmétique arrondie pour filtrer les cas difficiles.

Dans ces cas difficiles, il faut utiliser une méthode de calcul exacte. Soit à l'aide d'une bibliothèque de calcul en grande précision, soit à l'aide d'une méthode spécifiquement géométrique.


Filtres arithmétiques

Afin d'être sur et certain que le signe calculé est bon, il faut préciser ce que «suffisamment grande» veut dire dans le paragraphe précédent.

Cela veut dire qu'il faut accompagner le calcul de notre déterminant d'un calcul d'erreur rigoureux permettant de certifier vraiment le signe calculé. Selon les cas on pourra parler de


Calcul exact «géométrique»

Nous avons développé une telle méthode: pour connaître l'orientation du triangle pqr dans un cas difficile où tex2html_wrap_inline8 on translate r un nombre entier de fois du vecteur qp en un point r' tel que tex2html_wrap_inline10 Cette translation ne change pas l'orientation du triangle, et le nouveau déterminant est plus facile à calculer.

Pour en savoir plus


On peut se passer de calculer exactement

Une autre manière de résoudre ces problèmes consiste à ne plus concevoir des algorithmes utilisant des théorèmes mathématiques tel que celui décrit plus haut.

De tels algorithmes remplacent généralement la cohérence intrinsèque due aux théorèmes mathématiques par une vérification et un maintien explicite de cette cohérence.


Pour en savoir plus

Un exposé d'introduction.



Last modified: Mon Aug 28 10:31:13 MET DST 2000 Olivier Devillers Thèmes Accueil PRISME same page in english