Annulation catastrophique
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c4/Icone_Puzzle.svg/45px-Icone_Puzzle.svg.png)
Cet article est orphelin. Moins de trois articles lui sont liés ().
Vous pouvez aider en ajoutant des liens vers [[Annulation catastrophique]]
dans les articles relatifs au sujet.
En analyse numérique, l'annulation catastrophique [1],[2] est le phénomène qui peut apparaitre lors du calcul de la différence de bonnes approximations de deux nombres proches et peut alors donner une très mauvaise approximation de la différence des nombres d'origine.
Par exemple, s'il y a deux bâtons , un de longueur et l'autre de longueur , et qu'ils sont mesurés avec une règle qui n'est précise qu'au centimètre près, alors les approximations pourraient être de et . On peut les voir comme de bonnes approximations, en erreur relative, des vraies longueurs : en effet, les approximations sont en erreur de moins de 2% des vraies longueurs : .
Cependant, si on fait la soustraction des longueurs approximatives, la différence sera , alors que la véritable différence entre les longueurs est de . La différence des approximations, , a une erreur relative de près de 100 % de la valeur de la différence des valeurs vraies, .
L’annulation catastrophique n’est pas affectée par la taille des entrées — elle s’applique aussi bien aux entrées grandes comme petites. Cela dépend uniquement de l’amplitude de la différence et de l’erreur commise sur les valeurs d'entrées. Ainsi, on aurait exactement la même erreur qui se produirait en soustrayant à avec comme approximations et , ou en soustrayant depuis en partant des approximations et .
Une annulation catastrophique peut se produire même si la différence est calculée exactement, comme dans l'exemple ci-dessus — ce n'est pas une propriété d'un type particulier d'arithmétique comme l'arithmétique à virgule flottante ; il est plutôt inhérent à la soustraction, lorsque les entrées sont elles-mêmes des approximations. En effet, en arithmétique à virgule flottante, lorsque les entrées sont suffisamment proches, la différence en virgule flottante est calculée exactement, par le lemme de Sterbenz — il n'y a pas d'erreur d'arrondi introduite par l'opération de soustraction en virgule flottante.
Analyse formelle
Formellement, une annulation catastrophique se produit parce que la soustraction est mal conditionnée aux entrées proches : même si les approximations et ont des erreurs relatives et faibles par rapport aux vraies valeurs et , l'erreur relative de la différence des approximations par rapport à la différence des vraies valeurs est inversement proportionnelle à la différence des vraies valeurs :Ainsi, l'erreur relative de la différence exacte des approximations à partir de la différence des vraies valeurs vautqui peut être arbitrairement grand si les vraies valeurs et sont proches.
Dans les algorithmes numériques
La soustraction de nombres proches en arithmétique à virgule flottante ne provoque pas toujours une annulation catastrophique, ni même une erreur — d'après le lemme de Sterbenz, si les nombres sont suffisamment proches, la différence en virgule flottante est exacte. Mais l’annulation peut amplifier les erreurs dans les entrées résultant de l’arrondi d’autres calculs arithmétiques à virgule flottante.
Exemple : Différence de carrés
Etant donnés deux nombres et , la tentative naïve de calculer la fonction mathématique par l'arithmétique à virgule flottante est sujette à une annulation catastrophique lorsque et sont proches en amplitude, car la soustraction peut exposer les erreurs d'arrondi dans la mise au carré. La factorisation alternative , évaluée par l'arithmétique à virgule flottante , évite une annulation catastrophique car elle évite d'introduire une erreur d'arrondi conduisant à la soustraction[2].
Par exemple, si et , alors la vraie valeur de la différence est . En arithmétique IEEE 754 binary64, évaluer la factorisation alternative donne exactement le résultat correct (sans arrondi), mais en évaluant l'expression naïve , on a le nombre à virgule flottante , dont moins de la moitié des chiffres sont corrects et les autres chiffres (soulignés) reflètent les termes manquants , perdus en raison de l'arrondi lors du calcul des valeurs élevées au carré intermédiaires.
Exemple : arc sinus complexe
Lors du calcul de la fonction arc sinus complexe, on peut être tenté d'utiliser directement la formule logarithmique :Cependant, supposons pour . Alors et ; on note la différence entre ces deux valeurs — qui est donc une très petite différence, presque nulle. Si est évalué en arithmétique à virgule flottante donnantavec une erreur quelconque , où désigne un arrondi à virgule flottante, puis avec le calcul de la différencede deux nombres proches, tous deux très proches de , peut amplifier l'erreur en une entrée par un facteur de — un facteur très important parce que était presque nul. Par exemple, si , la valeur exacte de est d'environ , mais l'utilisation de la formule logarithmique naïve dans l'arithmétique binary64 IEEE 754 peut donner , avec seulement cinq chiffres sur seize corrects et le reste (souligné) tous incorrects.
Dans le cas où pour , en utilisant l'identité évite l'annulation parce que mais , donc la soustraction est effectivement une addition avec le même signe qui ne s'annule pas.
Exemple : conversion de base
Les constantes numériques dans les logiciels sont souvent écrites en décimal, comme dans le fragment C double x = 1.000000000000001;
pour déclarer et initialiser une variable binaire64 IEEE 754 nommée x
. Cependant, n'est pas un nombre binaire64 à virgule flottante ; le plus proche, auquel x
sera initialisé dans ce fragment, est . Bien que la conversion de base de la virgule flottante décimale à la virgule flottante binaire n'entraîne qu'une petite erreur relative, une annulation catastrophique peut l'amplifier en une erreur beaucoup plus importante :
double x = 1.000000000000001; // arrondi à 1 + 5*2^{-52} double y = 1.000000000000002; // arrondi à 1 + 9*2^{-52} double z = y - x; // la difference vaut exactement 4*2^{-52}
La différence est . Les erreurs relatives de x
de et de y
de sont tous les deux ci-dessous , et la soustraction à virgule flottante y - x
est calculée exactement par le lemme de Sterbenz.
Mais même si les entrées sont de bonnes approximations, et même si la soustraction est calculée exactement, la différence des approximations a une erreur relative de plus de de la différence des valeurs originales écrites en décimal : une annulation catastrophique a amplifié une petite erreur dans la conversion de base en une grande erreur dans la sortie.
Annulation bénigne
L'annulation est parfois utile et souhaitable dans les algorithmes numériques. Par exemple, les algorithmes 2Sum et Fast2Sum s'appuient tous deux sur une telle annulation après une erreur d'arrondi afin de calculer exactement quelle était l'erreur dans une opération d'addition à virgule flottante en tant que nombre à virgule flottante lui-même.
La fonction , si elle est évaluée naïvement pour des valeurs , perdra la plupart des chiffres de en arrondi . Cependant, la fonction elle-même est bien conditionné aux entrées proches de . La réécrire commeexploite l'annulation dans pour éviter l'erreur de évalué directement[2]. Cela fonctionne car l'annulation au numérateur et l'annulation au dénominateur se contrecarrer; la fonction est suffisamment bien conditionnée près de zéro pour que donne une bonne approximation de , Et ainsi donne une bonne approximation de .
Références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Catastrophic cancellation » (voir la liste des auteurs).
- ↑ Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod, Joldes, Lefèvre, Melquiond, Revol et Torres, Handbook of Floating-Point Arithmetic, Gewerbestrasse 11, 6330 Cham, Switzerland, 2nd, (ISBN 978-3-319-76525-9, DOI 10.1007/978-3-319-76526-6, lire en ligne), p. 102
- ↑ a b et c (en) Goldberg, « What every computer scientist should know about floating-point arithmetic », ACM Computing Surveys, New York, NY, United States, Association for Computing Machinery, vol. 23, no 1, , p. 5–48 (ISSN 0360-0300, DOI 10.1145/103162.103163, S2CID 222008826, lire en ligne, consulté le )
Portail de l'analyse