Erreurs numériques et stabilité

Quelle est l'erreur relative si $x=1000$ et $\tilde x = 1000{,}5$ ?

Erreur absolue $=|1000{,}5-1000|=0{,}5$. Erreur relative $=\dfrac{0{,}5}{1000}=0{,}0005=0{,}05\%$.

Vrai ou faux : l'erreur relative est toujours plus pertinente que l'erreur absolue pour juger de la qualité d'une approximation.

Vrai (dans la quasi-totalité des cas pratiques). L'erreur relative tient compte de l'ordre de grandeur de la quantité approchée, contrairement à l'erreur absolue qui peut être trompeuse (négligeable pour un grand nombre, énorme pour un petit nombre).

Le phénomène de cancellation catastrophique se produit typiquement lors de :

La cancellation catastrophique survient lors de la soustraction de deux nombres très proches en valeur : l'erreur absolue (petite) reste similaire, mais le résultat (petit) fait que l'erreur relative explose.

Un algorithme dont l'erreur est multipliée par $\lambda=0{,}3$ à chaque étape est-il stable ?

Oui, l'algorithme est stable car $|\lambda|=0{,}3<1$ : l'erreur décroît à chaque étape, elle ne s'amplifie pas.

Calculer le conditionnement $\kappa(x) = |xf'(x)/f(x)|$ pour $f(x)=x^2$.

$f'(x)=2x$. $\kappa(x) = \left|\dfrac{x\times2x}{x^2}\right| = \left|\dfrac{2x^2}{x^2}\right| = 2$. Le conditionnement est constant (égal à $2$) : élever au carré amplifie modérément (et de façon constante) les erreurs relatives.

Reformuler $f(x) = \dfrac{1-\cos(x)}{x^2}$ pour $x$ proche de $0$ afin d'éviter la cancellation (indication : utiliser $1-\cos x = 2\sin^2(x/2)$).

En utilisant $1-\cos x = 2\sin^2(x/2)$, on obtient $f(x) = \dfrac{2\sin^2(x/2)}{x^2}$. En écrivant $x^2=4(x/2)^2$, $f(x) = \dfrac{2\sin^2(x/2)}{4(x/2)^2} = \dfrac12\left(\dfrac{\sin(x/2)}{x/2}\right)^2$. Cette formule évite complètement la soustraction $1-\cos(x)$ (qui souffre de cancellation pour $x$ proche de $0$, car $\cos(x)\approx1$), en la remplaçant par une expression utilisant uniquement le sinus, numériquement stable.

Vrai ou faux : le conditionnement d'un problème dépend de l'algorithme utilisé pour le résoudre.

Faux. Le conditionnement est une propriété intrinsèque du problème mathématique (la sensibilité de la solution exacte aux perturbations des données), indépendante de l'algorithme. C'est la stabilité, en revanche, qui dépend de l'algorithme choisi.

Calculer $f(x)=\sqrt{x+1}-\sqrt x$ pour $x=10^8$ par la formule directe et par la formule reformulée $\dfrac{1}{\sqrt{x+1}+\sqrt x}$, et comparer la fiabilité.

Formule directe : $\sqrt{10^8+1}\approx10000{,}00005$ et $\sqrt{10^8}=10000$. Leur différence théorique est $\approx5\times10^{-5}$, mais en représentation flottante (environ $15$-$16$ chiffres significatifs), $10000{,}00005$ ne conserve que quelques chiffres significatifs après la virgule utiles, ce qui peut dégrader fortement la précision relative du résultat de la soustraction. Formule reformulée : $\dfrac{1}{\sqrt{10^8+1}+\sqrt{10^8}} \approx \dfrac{1}{20000{,}00005} \approx 5\times10^{-5}$, calculée comme une simple division de deux quantités bien représentées, sans aucune soustraction dangereuse : le résultat est numériquement fiable. Cet exemple illustre concrètement l'intérêt de la reformulation algébrique pour la stabilité numérique.

Une récurrence vérifie $e_{n+1} = -3e_n$ sur l'erreur (où $e_n$ est l'écart entre la valeur calculée et la valeur exacte). Si $e_0 \approx 10^{-10}$ (erreur d'arrondi initiale), estimer $e_{20}$ et conclure sur la stabilité.

$e_{20} = (-3)^{20} e_0 = 3^{20}\times10^{-10}$ (le signe disparaît car l'exposant est pair). $3^{20} = (3^{10})^2 = 59049^2 \approx 3{,}49\times10^9$. Donc $e_{20} \approx 3{,}49\times10^9\times10^{-10} \approx 0{,}35$. Une erreur initiale microscopique ($10^{-10}$, de l'ordre de la précision machine) est devenue, après seulement $20$ étapes, de l'ordre de $0{,}35$ — totalement inacceptable. L'algorithme est fortement instable (facteur d'amplification $|\lambda|=3>1$ à chaque étape).

Vrai ou faux : un problème bien conditionné, résolu par un algorithme instable, peut tout de même donner des résultats numériquement faux.

Vrai. Le conditionnement (propriété du problème) et la stabilité (propriété de l'algorithme) sont des notions distinctes. Même si le problème mathématique est peu sensible aux perturbations, un algorithme mal conçu peut amplifier les erreurs d'arrondi à chaque étape de calcul et produire un résultat final très imprécis, voire absurde.

Pour résoudre $x^2-10^6x+1=0$, expliquer pourquoi la formule usuelle des racines $x=\dfrac{10^6\pm\sqrt{10^{12}-4}}{2}$ pose un problème pour l'une des deux racines, et proposer une meilleure méthode de calcul.

$\sqrt{10^{12}-4} \approx 10^6$ (la correction due au $-4$ est négligeable face à $10^{12}$). Donc la racine $x_2 = \dfrac{10^6-\sqrt{10^{12}-4}}{2}$ est le quotient par $2$ d'une soustraction de deux quantités quasi identiques ($10^6$ et $\approx10^6$) : cancellation catastrophique, perte de précision relative importante. En revanche $x_1 = \dfrac{10^6+\sqrt{10^{12}-4}}{2}$ (addition) est calculée sans problème. Méthode stable : calculer $x_1$ par la formule directe (fiable), puis utiliser la relation produit des racines $x_1 x_2 = \dfrac{c}{a}=1$ (ici $c=1,a=1$ dans $ax^2+bx+c$) pour obtenir $x_2 = \dfrac{1}{x_1}$, qui ne comporte qu'une division, sans cancellation.

Vrai ou faux : la précision machine (de l'ordre de $10^{-16}$ pour le type double) signifie qu'aucun calcul numérique ne peut jamais avoir d'erreur supérieure à $10^{-16}$.

Faux. La précision machine $\varepsilon_{\text{machine}}\approx10^{-16}$ est l'ordre de grandeur de l'erreur d'arrondi à chaque opération élémentaire. Mais ces erreurs peuvent s'accumuler ou être amplifiées au fil de nombreuses opérations (en particulier avec un algorithme instable), conduisant à des erreurs finales bien supérieures à $10^{-16}$ — voire à des résultats complètement faux, comme illustré par l'exemple de la suite $I_n$ du cours.

Soit $f(x) = e^x - 1$, calculée près de $x=0$ par la formule directe (calcul de $e^x$ puis soustraction de $1$). Pourquoi cela pose-t-il un problème, et comment l'éviter (mention du développement en série) ?

Pour $x$ proche de $0$, $e^x \approx 1$, donc le calcul $e^x-1$ est une soustraction de deux quantités très proches : cancellation catastrophique, perte de précision relative importante sur le résultat (qui devrait être proche de $x$, une petite quantité). Solution : utiliser directement le développement en série $e^x-1 = x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\cdots$, qui ne comporte aucune soustraction de grandes quantités, ou (en pratique informatique) la fonction dédiée souvent appelée \"expm1\" dans les bibliothèques numériques, spécifiquement conçue et implémentée pour rester stable près de $x=0$.

Donner la définition du conditionnement absolu (plutôt que relatif) d'un problème $f$ en un point $x$, et expliquer en quoi il diffère du conditionnement relatif.

Le conditionnement absolu est $\kappa_{\text{abs}}(x) = |f'(x)|$ : il mesure directement de combien une petite erreur absolue $\delta$ sur $x$ se traduit en erreur absolue sur $f(x)$, via l'approximation $f(x+\delta)-f(x)\approx f'(x)\delta$. Le conditionnement relatif $\kappa_{\text{rel}}(x) = \left|\dfrac{xf'(x)}{f(x)}\right|$ normalise cette sensibilité par les ordres de grandeur de $x$ et $f(x)$ eux-mêmes, ce qui le rend indépendant des unités de mesure choisies et généralement plus pertinent pour juger de la difficulté intrinsèque d'un problème (une grande sensibilité absolue peut être anodine si $x$ et $f(x)$ sont eux-mêmes très grands).

Expliquer pourquoi, pour calculer $n!$ pour $n$ grand, on préfère souvent travailler avec $\ln(n!)$ (ou la formule de Stirling) plutôt que de calculer $n!$ directement, du point de vue de la stabilité/représentation numérique.

$n!$ croît extrêmement vite (plus vite que toute exponentielle) et dépasse la plage représentable par un nombre flottant standard (overflow) pour des valeurs de $n$ relativement modestes (par exemple $n!$ dépasse $10^{308}$, la limite du type double, vers $n\approx171$). En revanche, $\ln(n!) = \sum_{k=1}^n \ln(k)$ croît beaucoup plus lentement (de l'ordre de $n\ln n$ par la formule de Stirling), restant dans une plage de valeurs numériquement représentable sans dépassement de capacité, même pour des $n$ très grands. De nombreux calculs pratiques (rapports de factorielles, coefficients binomiaux, vraisemblances en statistique) peuvent alors se faire en passant par les logarithmes (additions au lieu de multiplications, soustractions au lieu de divisions) puis en repassant à l'exponentielle seulement à la fin si nécessaire, évitant ainsi tout débordement intermédiaire.