Annulation catastrophique

En analyse numérique, l'annulation catastrophique 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 $L_{1}=253.51\,{\text{cm}}$ et l'autre de longueur $L_{2}=252.49\,{\text{cm}}$, 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 ${\tilde {L}}_{1}=254\,{\text{cm}}$ et ${\tilde {L}}_{2}=252\,{\text{cm}}$. 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 : $|L_{1}-{\tilde {L}}_{1}|/|L_{1}|<2\%$.

Cependant, si on fait la soustraction des longueurs approximatives, la différence sera ${\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}$, alors que la véritable différence entre les longueurs est de $L_{1}-L_{2}=253.51\,{\text{cm}}-252.49\,{\text{cm}}=1.02\,{\text{cm}}$. La différence des approximations, $2\,{\text{cm}}$, a une erreur relative de près de 100 % de la valeur de la différence des valeurs vraies, $1.02\,{\text{cm}}$.

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 $52\,{\text{cm}}$ à $54\,{\text{cm}}$ avec comme approximations $52.49\,{\text{cm}}$ et $53.51\,{\text{cm}}$, ou en soustrayant $2.00052\,{\text{km}}$ depuis $2.00054\,{\text{km}}$ en partant des approximations $2.0005249\,{\text{km}}$ et $2.0005351\,{\text{km}}$.

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 ${\tilde {x}}=x(1+\delta _{x})$ et ${\tilde {y}}=y(1+\delta _{y})$ ont des erreurs relatives $|\delta _{x}|=|x-{\tilde {x}}|/|x|$ et $|\delta _{y}|=|y-{\tilde {y}}|/|y|$ faibles par rapport aux vraies valeurs $x$ et $y$, l'erreur relative de la différence ${\tilde {x}}-{\tilde {y}}$ des approximations par rapport à la différence des vraies valeurs est inversement proportionnelle à la différence des vraies valeurs :$${\begin{aligned}{\tilde {x}}-{\tilde {y}}&=x(1+\delta _{x})-y(1+\delta _{y})=x-y+x\delta _{x}-y\delta _{y}\\&=(x-y)\left(1+{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right).\end{aligned}}$$Ainsi, l'erreur relative de la différence exacte ${\tilde {x}}-{\tilde {y}}$ des approximations à partir de la différence $x-y$ des vraies valeurs vaut$$\left|{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right|.$$qui peut être arbitrairement grand si les vraies valeurs $x$ et $y$ 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 $x$ et $y$, la tentative naïve de calculer la fonction mathématique $x^{2}-y^{2}$ par l'arithmétique à virgule flottante $\operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))$ est sujette à une annulation catastrophique lorsque $x$ et $y$ sont proches en amplitude, car la soustraction peut exposer les erreurs d'arrondi dans la mise au carré. La factorisation alternative $(x+y)(x-y)$, évaluée par l'arithmétique à virgule flottante $\operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (x-y))$, évite une annulation catastrophique car elle évite d'introduire une erreur d'arrondi conduisant à la soustraction.

Par exemple, si $x=1+2^{-29}\approx 1.0000000018626451$ et $y=1+2^{-30}\approx 1.0000000009313226$, alors la vraie valeur de la différence $x^{2}-y^{2}$ est $2^{-29}\cdot (1+2^{-30}+2^{-31})\approx 1.8626451518330422\times 10^{-9}$. En arithmétique IEEE 754 binary64, évaluer la factorisation alternative $(x+y)(x-y)$ donne exactement le résultat correct (sans arrondi), mais en évaluant l'expression naïve $x^{2}-y^{2}$, on a le nombre à virgule flottante $2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}$, dont moins de la moitié des chiffres sont corrects et les autres chiffres (soulignés) reflètent les termes manquants $2^{-59}+2^{-60}$, 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 :$$\arcsin(z)=\mathrm {i} \log \left({\sqrt {1-z^{2}}}-\mathrm {i} z\right).$$Cependant, supposons $z=\mathrm {i} y$ pour $y\ll 0$. Alors ${\sqrt {1-z^{2}}}\approx -y$ et $\mathrm {i} z=-y$ ; on note la différence entre ces deux valeurs $\varepsilon$ — qui est donc une très petite différence, presque nulle. Si ${\sqrt {1-z^{2}}}$ est évalué en arithmétique à virgule flottante donnant$$\operatorname {fl} \left({\sqrt {\operatorname {fl} (1-\operatorname {fl} (z^{2}))}}\right)={\sqrt {1-z^{2}}}(1+\delta )$$avec une erreur quelconque $\delta \neq 0$, où $\operatorname {fl} (\cdots )$ désigne un arrondi à virgule flottante, puis avec le calcul de la différence$${\sqrt {1-z^{2}}}(1+\delta )-\mathrm {i} z$$de deux nombres proches, tous deux très proches de $-y$, peut amplifier l'erreur $\delta$ en une entrée par un facteur de $1/\varepsilon$ — un facteur très important parce que $\varepsilon$ était presque nul. Par exemple, si $z=-1234567\mathrm {i}$, la valeur exacte de $\arcsin(z)$ est d'environ $-14.71937803983977\mathrm {i}$, mais l'utilisation de la formule logarithmique naïve dans l'arithmétique binary64 IEEE 754 peut donner $-14.719{\underline {644263563968}}\mathrm {i}$, avec seulement cinq chiffres sur seize corrects et le reste (souligné) tous incorrects.

Dans le cas où $z=\mathrm {i} y$ pour $y<0$, en utilisant l'identité $\arcsin(z)=-\arcsin(-z)$ évite l'annulation parce que ${\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$ mais $\mathrm {i} (-z)=-\mathrm {i} z=y$, 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, $1.000000000000001$ n'est pas un nombre binaire64 à virgule flottante ; le plus proche, auquel x sera initialisé dans ce fragment, est $1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}$. 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 $1.000000000000002-1.000000000000001$ est $0.000000000000001=1.0\times 10^{-15}$. Les erreurs relatives de x de $1.000000000000001$ et de y de $1.000000000000002$ sont tous les deux ci-dessous $10^{-15}=0.0000000000001\%$, 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 ${\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}$ a une erreur relative de plus de $11\%$ de la différence $1.0\times 10^{-15}$ 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 $\log(1+x)$, si elle est évaluée naïvement pour des valeurs $0<x\lll 1$, perdra la plupart des chiffres de $x$ en arrondi $\operatorname {fl} (1+x)$. Cependant, la fonction $\log(1+x)$ elle-même est bien conditionné aux entrées proches de $0$. La réécrire comme$$\log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}$$exploite l'annulation dans ${\hat {x}}:=\operatorname {fl} (1+x)-1$ pour éviter l'erreur de $\log(1+x)$ évalué directement. Cela fonctionne car l'annulation au numérateur $\log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})$ et l'annulation au dénominateur ${\hat {x}}=\operatorname {fl} (1+x)-1$ se contrecarrer; la fonction $\mu (\xi )=\log(1+\xi )/\xi$ est suffisamment bien conditionnée près de zéro pour que $\mu ({\hat {x}})$ donne une bonne approximation de $\mu (x)$, Et ainsi $x\cdot \mu ({\hat {x}})$ donne une bonne approximation de $x\cdot \mu (x)=\log(1+x)$.

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