Erreurs et arithmétique flottante

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

distinguer les quatre sources d'erreur d'un calcul scientifique — le modèle, les données, la troncature de la méthode et l'arrondi de la machine — et dire laquelle domine dans une situation donnée;
calculer une erreur absolue et une erreur relative, et compter les chiffres significatifs corrects d'une valeur approchée;
décrire le format IEEE 754 en double précision, situer les nombres représentables sur un axe et justifier que leur espacement double à chaque exposant;
utiliser le modèle d'arrondi $fl (x) = x (1 + δ)$ , $∣ δ ∣ \leq ε_{mach} /2$ , pour majorer l'erreur d'une somme, d'un produit et d'une différence;
reconnaître une annulation catastrophique, en évaluer le facteur d'amplification et réécrire l'expression fautive sous une forme stable;
distinguer le de la , et estimer l'amplification d'une erreur de donnée à travers une fonction dérivable.

Pourquoi un cours d'analyse numérique commence par l'erreur

Un ordinateur ne calcule pas avec des nombres réels. Il calcule avec un ensemble fini de rationnels, à l'intérieur duquel les quatre opérations ne sont ni associatives ni distributives, et il le fait si vite qu'aucune inspection humaine du résultat n'est possible. Toute la discipline consiste à obtenir, malgré cela, des résultats dont on connaît la précision. Un résultat numérique sans estimation de son erreur n'est pas un résultat: c'est une opinion en seize chiffres.

Ce premier chapitre installe le vocabulaire et les deux ou trois inégalités dont les neuf suivants se serviront constamment. Il n'y a ici aucune méthode à proprement parler: il y a l'arithmétique dans laquelle toutes les méthodes du cours vont s'exécuter.

Les quatre sources d'erreur

Considérons une question concrète: quelle est la valeur de

I = \int_{0}^{1} e^{- x^{2}} d x ? (1.1)

Cette intégrale n'a pas de primitive élémentaire — c'est précisément pour des questions de ce genre que le chapitre 8 existe. Pour obtenir un nombre, il faut choisir une méthode, la discrétiser, puis l'exécuter. À chaque étape, un écart apparaît.

L'erreur de modèle. Elle précède le calcul. Si l'intégrale (1.1) représente la probabilité qu'une grandeur physique tombe dans un intervalle, la loi normale sous-jacente est une idéalisation; aucune méthode numérique ne corrigera le choix du modèle. L'analyse numérique ne s'occupe pas de cette erreur, mais elle doit être nommée, car il est absurde de calculer à $1 0^{- 12}$ près un modèle valable à $10 %$ près.
L'erreur sur les données. Les nombres qui entrent dans le calcul proviennent de mesures, de tables ou de calculs antérieurs; ils sont connus avec une incertitude. La question «de combien cette incertitude est-elle amplifiée par mon calcul?» est celle du conditionnement, traitée à la fin de ce chapitre et quantifiée au chapitre 4 pour les systèmes linéaires.
L'erreur de troncature. Elle naît du remplacement d'un objet infini par un objet fini: une série par une somme partielle, une dérivée par un quotient de différences, une intégrale par une somme de trapèzes, une solution d'équation différentielle par une ligne brisée. C'est l'erreur propre à la méthode, et elle existerait même sur une machine arithmétiquement parfaite.
L'erreur d'arrondi. Elle naît du remplacement de chaque réel par le nombre machine le plus proche, à chaque opération. C'est l'erreur propre à la machine, et elle existerait même avec une méthode mathématiquement exacte.

Deux mots à ne jamais confondre, dans les dix chapitres

Cette distinction est la convention de notation la plus utilisée du cours. Au chapitre 8, l'erreur de troncature de la différence avant $(f (x + h) - f (x)) / h$ décroît comme $h$ tandis que son erreur d'arrondi croît comme $1/ h$ : les deux se croisent, et le minimum de leur somme fixe le pas optimal $h^{*} \approx 2 u$ . Le même chapitre montre que la quadrature composite, elle, ne connaît croisement: intégrer est une opération régularisante, et l'erreur d'arrondi y reste tapie au niveau de pendant que la troncature descend de plusieurs ordres de grandeur sans jamais rencontrer de minimum. Le compromis est donc une propriété de l'opération, pas une fatalité du calcul en précision finie. Au chapitre 9, l'ordre d'une méthode de Runge-Kutta est une propriété de troncature pure; au chapitre 10, la stabilité absolue n'est de la troncature de l'arrondi: c'est la récurrence elle-même qui possède une solution croissante, et l'arrondi ne fait que fournir la perturbation qu'elle amplifie. Dire «erreur numérique» sans préciser laquelle rend ces discussions impossibles.

La troncature seule s'observe très bien sur le développement de l'exponentielle. En sommant $S_{n} = \sum_{k = 0}^{n} \frac{1}{k !}$ , on obtient, calculé en précision étendue pour isoler la seule erreur de méthode:

$n$	$S_{n}$	$∣ e - S_{n} ∣$
2	2,500000000000000	$2, 18 \cdot 1 0^{- 1}$

L'erreur décroît, très vite, et elle vaut exactement le reste de la série: c'est de la troncature pure, et aucune machine n'y est pour rien. La suite du chapitre s'occupe de l'autre erreur — celle dont la machine, elle, est entièrement responsable.

Question 1.1

Vous approchez $sin (0, 5)$ par les trois premiers termes de sa série de Taylor, sur un ordinateur en double précision. L'écart entre votre résultat et la vraie valeur de $sin (0, 5)$ est-il de la troncature, de l'arrondi, ou les deux?

Erreur absolue, erreur relative, chiffres significatifs

Tout le cours utilise l'erreur relative, et il vaut la peine de dire pourquoi. Une erreur absolue de $1$ mm est excellente sur la longueur d'un pont et catastrophique sur l'épaisseur d'une couche mince; elle ne veut rien dire tant qu'on n'a pas dit sur quoi elle porte. L'erreur relative, elle, voyage: elle se conserve par changement d'unité, elle se compare d'une grandeur à l'autre, et surtout c'est elle que l'arithmétique de la machine borne, comme nous allons le voir. C'est la raison pour laquelle le théorème central de ce chapitre, le modèle d'arrondi, est énoncé en relatif.

Cette définition par l'erreur relative est plus robuste que le comptage naïf des chiffres qui coïncident. Les nombres $0, 99999$ et $1, 00001$ n'ont aucun chiffre en commun dans leur écriture décimale, et pourtant leur erreur relative vaut $2 \cdot 1 0^{- 5}$ : ils s'accordent à cinq chiffres significatifs près, ce qui est la seule lecture utile.

Question 1.2

Un capteur renvoie $2, 470$ m pour une longueur dont la valeur exacte est $2, 4531$ m. Calculez l'erreur relative, exprimée en pour cent.

Les nombres à virgule flottante

Le format IEEE 754 en double précision

Depuis 1985, presque toutes les machines représentent les réels selon la norme IEEE 754. Le format que ce cours utilise partout — celui du type float de Python, du double de C et de Java, du réel par défaut de Matlab et de NumPy — est le format binary64, dit double précision. Il occupe 64 bits, répartis ainsi:

Champ	Bits	Rôle
signe $s$	1	$0$ pour $+$ , $1$ pour $-$
exposant	11	un entier biaisé, donnant $e$ entre $- 1022$ et $1023$
mantisse	52	les bits $b_{1}, \dots, b_{52}$ après la virgule

Trois conséquences immédiates, chiffrées:

Amplitude. Le plus grand élément de $F$ vaut $(2 - 2^{- 52}) \cdot 2^{1023} \approx 1, 797 \cdot 1 0^{308}$ , le plus petit normalisé positif $2^{- 1022} \approx 2, 225 \cdot 1 0^{- 308}$ . Au-delà, on obtient ; en deçà, des nombres jusqu'à , puis zéro. La norme prévoit aussi () pour et .

L'arrondi et son modèle

Un réel $x$ quelconque n'appartient pratiquement jamais à $F$ . La machine lui substitue $fl (x)$ , l'élément de $F$ le plus proche (en cas d'égalité, celui dont le dernier bit de mantisse est pair — c'est l'arrondi au plus proche pair, mode par défaut de la norme, choisi parce qu'il ne biaise pas les sommes). Le théorème suivant est le seul fait dont nous aurons besoin sur $fl$ , et il est remarquable: la borne ne dépend ni de $x$ , ni de son ordre de grandeur.

Démonstration. Supposons $x > 0$ , le cas $x < 0$ s'en déduisant par symétrie puisque $F$ et l'arrondi au plus proche sont symétriques par rapport à $0$ . Soit $e$ l'entier tel que $2^{e} \leq x < 2^{e + 1}$ .

Les éléments de $F$ contenus dans $[2^{e}, 2^{e + 1}]$ sont exactement les nombres

v_{m} = 2^{e} (1 + \frac{m}{2 ^{52}}), m = 0, 1, \dots, 2^{52},

d'après (1.4): ils forment une subdivision régulière de l'intervalle, de pas

Δ = v_{m + 1} - v_{m} = 2^{e - 52} .

Comme $v_{0} = 2^{e} \leq x < 2^{e + 1} = v_{2^{52}}$ , il existe un indice avec . L'arrondi au plus proche choisit celui des deux bornes qui est le plus proche de (l'ambiguïté du milieu étant tranchée par la parité, ce qui ne change pas la majoration), donc

∣ fl (x) - x ∣ \leq \frac{Δ}{2} = 2^{e - 53} . (1.7)

Il ne reste qu'à diviser par $x$ . Puisque $x \geq 2^{e}$ ,

∣ δ ∣ = \frac{∣ fl ( x ) - x ∣}{x} \leq \frac{2 ^{e - 53}}{2 ^{e}} = 2^{- 53} = \frac{ε _{mach}}{2},

ce qui est bien (1.6) avec $δ = (fl (x) - x) / x$ . Le point décisif est l'étape (1.7) divisée par $x \geq 2^{e}$ : le pas $Δ$ et la borne inférieure de $x$ contiennent le même facteur $2^{e}$ , qui disparaît. C'est exactement ce que la figure 1.1 montre — l'espacement double avec , donc l'espacement rapporté à ne change pas.

Explorateur 1.1 · Quels réels une mantisse de p bits peut-elle représenter?

Faites varier le nombre de bits de mantisse: chaque bit ajouté double le nombre de valeurs disponibles dans chaque octave et divise par deux l'espacement. Déplacez ensuite le réel x et surveillez l'erreur relative: elle change à chaque pas, mais elle ne dépasse jamais la borne ε/2 — c'est exactement le contenu du modèle d'arrondi, et c'est la seule ligne du tableau qui ne bouge pas quand vous déplacez x.

Bits de mantisse p4 bits

Réel à représenter x2,37

fl(x)

2,375

Erreur relative

2,11e-3

Borne ε/2 = 2^−p−1

3,13e-2

ε = 2^−p

6,25e-2

Valeurs par octave

ε_mach (binary64)

2,22e-16

Question 1.3

Combien y a-t-il de nombres binary64 dans l'intervalle $[1024, 2048 [$ , comparé au nombre de ceux de $[1, 2 [$ ?

Ce que devient une opération

La norme IEEE 754 exige que les quatre opérations et la racine carrée soient correctement arrondies: le résultat machine est l'arrondi du résultat exact. Pour $\circ \in {+, -, \times, /}$ et $x, y \in F$ ,

fl (x \circ y) = (x \circ y) (1 + δ), ∣ δ ∣ \leq \frac{ε _{mach}}{2} . (1.8)

C'est une exigence forte et une excellente nouvelle: chaque opération prise isolément est aussi bonne que le format le permet. Tous les ennuis de ce chapitre viennent de leur enchaînement, et d'une seule d'entre elles.

Produit et quotient: les erreurs s'additionnent, doucement

Si $\overset{x}{^} = x (1 + α)$ et $\overset{y}{^} = y (1 + β)$ sont des valeurs approchées, alors

\overset{x}{^} \overset{y}{^} = x y (1 + α) (1 + β) = x y (1 + α + β + α β),

de sorte que l'erreur relative du produit vaut environ $α + β$ au premier ordre. En ajoutant l'arrondi de l'opération elle-même, on obtient une erreur relative bornée par $∣ α ∣ + ∣ β ∣ + ε_{mach} /2$ à des termes du second ordre près. Le même calcul, avec $(1 + β)^{- 1} \approx 1 - β$ , donne la même borne pour le quotient.

Autrement dit: la multiplication et la division ne détériorent presque rien. Les erreurs relatives s'ajoutent, une par opération, sans facteur d'amplification. C'est pourquoi une longue chaîne de produits reste fiable, et c'est aussi pourquoi, chaque fois qu'on peut remplacer une soustraction par un quotient, il faut le faire.

La somme et la différence: le facteur d'amplification

Pour une addition, la situation change de nature, parce que l'erreur relative du résultat se rapporte à $x + y$ et non plus à $x$ ni à $y$ .

Démonstration. Écrivons l'écart entre la somme approchée et la somme exacte:

(\overset{x}{^} + \overset{y}{^}) - (x + y) = (x (1 + α) + y (1 + β)) - (x + y) = α x + β y .

L'inégalité triangulaire donne $∣ α x + β y ∣ \leq ∣ α ∣ ∣ x ∣ + ∣ β ∣ ∣ y ∣ \leq η (∣ x ∣ + ∣ y ∣)$ . En divisant par $∣ x + y ∣$ , on obtient (1.9).

Si $x$ et $y$ sont de même signe, $∣ x + y ∣ = ∣ x ∣ + ∣ y ∣$ et donc $K = 1$ : l'erreur relative de la somme ne dépasse pas la plus grande des erreurs relatives des termes. Si $x$ et $y$ sont de signes opposés, posons $y = - y^{'}$ avec et ; alors

K = \frac{x + y ^{'}}{∣ x - y ^{'} ∣} y^{'} \to x + \infty.

La borne (1.9) est atteinte: en prenant $α = η$ et $β = - η$ (ce qui est licite, puisque le modèle d'arrondi ne contraint que $∣ α ∣$ et $∣ β ∣$ ), l'écart vaut exactement $η (∣ x ∣ + ∣ y ∣)$ . $□$

Le cas d'école: `0.1 + 0.2`

Le nombre $0, 1$ n'est pas représentable en binaire: son écriture binaire, $0, 0 \overline{0011}_{2}$ , est infinie périodique, exactement comme $1/3$ en décimal. La machine retient le plus proche double, dont la valeur exacte est

fl (0, 1) = \frac{3 602 879 701 896 397}{2 ^{55}} = 0, 1000000000000000055511151231257827 \dots

soit une erreur relative de $5, 55 \cdot 1 0^{- 17}$ , conforme au théorème 1.1 puisque $5, 55 \cdot 1 0^{- 17} \leq 1, 11 \cdot 1 0^{- 16}$ . De même pour et pour . La somme des deux premiers arrondis, une fois arrondie à son tour, ne tombe pas sur l'arrondi de :

>>> 0.1 + 0.2
0.30000000000000004
>>> 0.1 + 0.2 == 0.3
False
>>> (0.1 + 0.2) - 0.3
5.551115123125783e-17

L'écart vaut exactement $2^{- 54} = 5, 551115123125783 \cdot 1 0^{- 17}$ , c'est-à-dire un ulp de $0, 3$ — l'erreur minimale possible. Rien n'a mal fonctionné. Les trois arrondis étaient chacun optimaux; c'est leur composition qui ne l'est pas, et aucune arithmétique de largeur finie n'y échappe.

Le signe égal sur des flottants est un bug

Écrire if x == y: sur deux nombres à virgule flottante calculés est une faute, et ce chapitre est celui qui donne le droit de l'affirmer pour les neuf suivants: un critère d'arrêt, un test de convergence, une détection de pivot nul, une comparaison de résidus ne s'écrivent jamais avec ==. La comparaison correcte est une comparaison à tolérance, mixte pour rester valable près de zéro:

def presque_egal(a, b, tol=1e-12):
    return abs(a - b) <= tol * max(1.0, abs(a), abs(b))

Le facteur max(1.0, abs(a), abs(b)) rend le test relatif pour les grandes valeurs et absolu au voisinage de zéro, où une tolérance purement relative n'a pas de sens. La tolérance se choisit en fonction du problème, jamais en dessous de quelques $ε_{mach}$ multipliés par le nombre d'opérations effectuées.

Question 1.4

Réparez la fonction presque_egal(a, b, tol) pour qu'elle compare deux flottants à une tolérance relative, tout en restant utilisable au voisinage de zéro. Le programme doit afficher False, puis True, puis False.

comparaison.py

L'annulation catastrophique

Le théorème 1.2 dit tout, mais il faut le voir agir. Trois expressions classiques, chacune avec sa forme naïve et sa forme stable.

La différence de deux racines carrées

Évaluons

f (x) = x + 1 - x (1.10)

pour $x$ grand. Mathématiquement, $f (x) \to 0$ comme $1/ (2 x)$ ; numériquement, les deux racines deviennent de plus en plus proches, donc leur différence relève exactement du cas $K \to \infty$ . Le facteur d'amplification vaut

K = \frac{x + 1 + x}{x + 1 - x} = (x + 1 + x)^{2} \approx 4 x,

en utilisant l'identité qui va nous sauver. Avec $η = ε_{mach} /2$ , l'erreur relative attendue est de l'ordre de $4 x \cdot 1, 11 \cdot 1 0^{- 16} \approx 2 x ε_{mach}$ : pour , environ , c'est-à-dire la perte de huit chiffres sur seize.

La cure est algébrique et tient en une ligne — on multiplie par la quantité conjuguée:

x + 1 - x = \frac{( x + 1 - x ) ( x + 1 + x )}{x + 1 + x} = \frac{1}{x + 1 + x} . (1.11)

Le membre de droite ne contient aucune soustraction: c'est une somme de deux quantités positives, puis une division, deux opérations dont on a vu qu'elles n'amplifient rien. Le facteur $K$ a disparu.

Exemple 1.2 · Les chiffres perdus, comptés

Voici, en double précision, les deux évaluations de (1.10). La colonne «chiffres» donne le nombre de chiffres significatifs corrects de la forme naïve, mesuré contre la forme (1.11).

$x$	forme naïve	forme stabilisée	erreur relative de la naïve	chiffres
$1 0^{4}$	0,0049998750062485	0,0049998750062496	$2, 13 \cdot 1 0^{- 13}$	12,7
$1 0^{8}$

Question 1.5

Écrivez difference_racines(x) qui évalue $x + 1 - x$ sans annulation. Le programme affiche, pour trois valeurs de $x$ , la valeur de $x$ puis le résultat en notation scientifique à douze décimales.

annulation.py

La formule du second degré

L'équation $a x^{2} + b x + c = 0$ a pour racines

x_{1, 2} = \frac{- b \pm b ^{2} - 4 a c}{2 a} . (1.12)

Lorsque $b^{2} ≫ 4 a c$ , la racine carrée vaut presque $∣ b ∣$ , et l'une des deux racines est obtenue en soustrayant deux nombres presque égaux: si $b > 0$ , c'est $- b + b^{2} - 4 a c$ qui s'annule; si , c'est . L'autre racine, obtenue par une addition de termes de même signe, est parfaite.

La cure repose sur la relation entre coefficients et racines, $x_{1} x_{2} = c / a$ : on calcule la bonne racine par (1.12), et l'autre par une division.

Question 1.6

Remettez dans l'ordre les étapes du calcul stable des deux racines réelles de $a x^{2} + b x + c = 0$ lorsque $b^{2} ≫ 4 a c$ .

Glissez les éléments pour les mettre dans le bon ordre

Obtenir la racine de plus petit module par la division

x_{2} = c / q

, sans aucune soustraction

Calculer

q = - \frac{1}{2} (b + sgn (b) Δ)

, somme de deux termes de même signe

Contrôler le résultat avec la relation

x_{1} x_{2} = c / a

Calculer le discriminant

Δ = b^{2} - 4 a c

et vérifier qu'il est positif ou nul

Obtenir la racine de plus grand module par

x_{1} = q / a

Question 1.7

Écrivez racines(a, b, c) qui renvoie les deux racines réelles de $a x^{2} + b x + c = 0$ sans annulation, la racine de plus grand module en premier. Le programme les affiche pour $a = 1$ , $b = 1 0^{8}$ , $c = 1$ .

quadratique.py

Le troisième classique: $1 - cos x$

Pour $x$ petit, $cos x$ est proche de $1$ et la différence $1 - cos x$ annule tous les chiffres. La forme stable utilise l'identité $1 - cos x = 2 sin^{2} (x /2)$ :

$x$	$1 - cos x$ (naïf)	$2 sin^{2} (x /2)$	erreur relative de la naïve
$1 0^{- 4}$	4,9999999696126 $\cdot 1 0^{- 9}$

Ce troisième exemple mérite une place à part, et nous y reviendrons: contrairement aux deux précédents, le problème $x \mapsto 1 - cos x$ est ici parfaitement bien posé. C'est l'algorithme, et lui seul, qui est mauvais.

La propagation d'une erreur à travers une fonction

Jusqu'ici, l'erreur venait de la machine. Considérons maintenant une donnée $x$ connue avec une incertitude $Δ x$ — une mesure, une constante physique tabulée, le résultat d'un calcul antérieur — et demandons ce que devient cette incertitude après le calcul de $f (x)$ .

Si $f$ est dérivable au voisinage de $x$ , la formule des accroissements finis (Analyse I, chapitre 8) donne, pour un $ξ$ entre $x$ et $x + Δ x$ ,

f (x + Δ x) - f (x) = f^{'} (ξ) Δ x,

d'où, pour $Δ x$ petit et $f^{'}$ continue,

∣ Δ f ∣ \approx ∣ f^{'} (x)∣ ∣ Δ x ∣ . (1.14)

La dérivée est donc le facteur d'amplification de l'erreur absolue. En passant au relatif, qui est ce qui nous intéresse:

\frac{∣ Δ f ∣}{∣ f ( x )∣} \approx κ_{f} (x) \frac{x f ^{'} ( x )}{f ( x )} \cdot \frac{∣ Δ x ∣}{∣ x ∣} . (1.15)

Question 1.8

Pour $x = 1 0^{8}$ , calculez le facteur d'amplification $K = \frac{x + 1 + x}{∣ x + 1 - x ∣}$ de la différence (1.10). Donnez-le sous forme d'un nombre.

Conditionnement du problème, stabilité de l'algorithme

Nous pouvons maintenant énoncer la distinction qui structure tout le cours, et dont ce chapitre n'a besoin que sous forme qualitative.

Les quatre combinaisons existent, et nous en avons déjà rencontré trois:

	algorithme stable	algorithme instable
problème bien conditionné	résultat précis: $2 sin^{2} (x /2)$	résultat faux: $1 - cos x$
problème mal conditionné	résultat imprécis, inévitablement: $ln x$ pour $x \to 1$	résultat faux pour deux raisons

Le cas $1 - cos x$ est l'exemple à retenir, parce qu'il isole la notion. Le conditionnement du problème vaut

κ_{f} (x) = \frac{x sin x}{1 - cos x} x \to 0 2,

puisque $x sin x \sim x^{2}$ et $1 - cos x \sim x^{2} /2$ . Le problème est donc excellemment conditionné: une donnée à $1 0^{- 16}$ près autorise un résultat à $2 \cdot 1 0^{- 16}$ près. C'est pourtant l'écriture naïve qui perd tout. La faute est entièrement imputable à l'algorithme, et le remède est algébrique — ce qui est la règle: on ne stabilise pas un calcul en le faisant «plus soigneusement», on le stabilise en le réécrivant.

L'erreur d'arrondi accumulée sur une somme

Une somme de $n$ termes est le calcul le plus banal qui soit, et le premier où l'accumulation des arrondis se voit. En sommant de gauche à droite,

s_{1} = x_{1}, s_{k} = fl (s_{k - 1} + x_{k}), k = 2, \dots, n,

chaque étape introduit un facteur $(1 + δ_{k})$ , et l'exercice 1.5 établit la borne

s_{n} - \sum_{i} x_{i} \leq [(1 + u)^{n - 1} - 1] \sum_{i = 1}^{n} ∣ x_{i} ∣ \approx (n - 1) u \sum_{i = 1}^{n} ∣ x_{i} ∣, (1.17)

où $u = ε_{mach} /2$ . Deux lectures. D'abord, la borne croît linéairement en $n$ : sommer un million de termes en double précision peut coûter jusqu'à $1 0^{6} \cdot 1, 11 \cdot 1 0^{- 16} \approx 1 0^{- 10}$ d'erreur relative, ce qui reste acceptable. Ensuite, c'est le rapport qui apparaît dès qu'on passe au relatif: c'est encore le facteur d'amplification du théorème 1.2, généralisé à termes. Une somme de termes de même signe est bien conditionnée; une somme à signes alternés ne l'est pas.

La figure 1.3 dit trois choses. La borne (1.17) n'est presque jamais atteinte: les $δ_{k}$ ne conspirent pas, et l'erreur observée croît plutôt comme $n$ , à la manière d'une marche aléatoire — sauf pour la sommation croissante, qui souffre d'un mal supplémentaire. Quand la somme partielle a atteint $14$ et que le terme courant vaut $1 0^{- 6}$ , ce terme est plus petit que la moitié de l'ulp de en simple précision (): il est , et il le reste pour tous les termes suivants. Sommer en commençant par les plus petits termes évite cela, et gagne ici un facteur 470 à (de à ) pour un coût nul.

On peut faire beaucoup mieux, avec un algorithme dû à Kahan, qui garde trace de ce que chaque arrondi a jeté et le réinjecte au tour suivant:

def somme_kahan(valeurs):
    """Sommation compensee: 4n operations au lieu de n, erreur independante de n."""
    total = 0.0
    compensation = 0.0
    for v in valeurs:
        y = v - compensation
        t = total + y
        compensation = (t - total) - y
        total = t
    return total

La ligne décisive est compensation = (t - total) - y: en arithmétique exacte elle vaudrait zéro, et c'est précisément parce qu'elle ne la vaut pas qu'elle capture l'erreur d'arrondi de l'addition précédente. L'algorithme coûte quatre opérations flottantes par terme au lieu d'une, et sa borne d'erreur est en $2 u + O (n u^{2})$ — indépendante de $n$ au premier ordre. C'est un algorithme stable pour un problème bien conditionné, et la courbe brune de la figure 1.3 est plate, ce qui est la signature de cette situation.

Question 1.9

Remplacez la somme naïve par la sommation compensée de Kahan. Le programme somme 1,0 puis cent mille fois $1 0^{- 16}$ , et doit afficher la valeur exacte $1, 00000000001$ et non $1, 0$ .

somme.py

Troncature contre arrondi: le premier compromis du cours

Les deux erreurs ne se comportent pas de la même manière quand on raffine un calcul, et leur opposition est le motif central des chapitres 8 à 10. L'exemple le plus court est l'approximation de $f^{'} (1)$ pour $f = sin$ , par le quotient de différences $(f (1 + h) - f (1)) / h$ , dont la valeur exacte est $cos 1 = 0, 540302305868140$ .

$h$	erreur totale observée	troncature estimée $h ∣ f^{''} ∣ /2$	arrondi estimé $2 u / h$
$1 0^{- 2}$	$4, 22 \cdot 1 0^{- 3}$

La troncature décroît proportionnellement à $h$ ; l'arrondi, lui, croît comme $1/ h$ , parce que le numérateur $f (1 + h) - f (1)$ est une différence de nombres voisins — c'est encore l'annulation catastrophique de ce chapitre. Le total passe par un minimum vers $h \approx 2 u \approx 2 \cdot 1 0^{- 8}$ , où l'on obtient huit chiffres corrects et pas davantage. Cette courbe en V est le sujet du chapitre 8; elle explique aussi pourquoi un critère d'arrêt trop exigeant, au chapitre 2, fait tourner une méthode indéfiniment.

Question 1.10

Un collègue résout un système linéaire et obtient un résidu $∥ b - A \hat{x} ∥$ de l'ordre de $1 0^{- 15}$ . Il en conclut que sa solution est correcte à quinze chiffres. Que lui répondez-vous?

Synthèse

Un calcul scientifique porte quatre erreurs: celle du modèle, celle des données, l'erreur de troncature (propre à la méthode, elle existerait sur une machine exacte) et l'erreur d'arrondi (propre à la machine, elle existerait avec une méthode exacte). Le cours entier tient dans la maîtrise des deux dernières.
L'erreur relative est la grandeur qui voyage: sans dimension, comparable d'une quantité à l'autre, et c'est elle que l'arithmétique borne. Une erreur relative de $1 0^{- s}$ correspond à environ $s$ chiffres significatifs corrects.
Le format binary64 représente $\pm (1, b_{1} \dots b_{52})_{2} 2^{e}$ avec . Les nombres machine sont régulièrement espacés de dans chaque intervalle : l'espacement à chaque exposant, mais l'espacement relatif reste constant, et vaut au plus .

Série d'exercices du chapitre 1Exercice 1 sur 5

Question 1.11

Quelle est la valeur de $ε_{mach}$ en double précision, dans la convention de ce cours?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 1.1 · Erreurs absolue et relative

La constante $e = 2, 718281828459045$ est approchée par $\overset{x}{^} = 2, 7183$ . Calculer les erreurs absolue et relative, et le nombre de chiffres significatifs corrects.
Une masse mesurée vaut $\overset{m}{^} = 12, 47$ kg avec une erreur relative garantie inférieure à . Dans quel intervalle la masse exacte se trouve-t-elle?

Exercice 1.2 · Dans le format binary64

Écrire $0, 1$ en binaire et expliquer pourquoi il n'est pas représentable exactement, alors que $0, 5$ et $0, 25$ le sont.
Quel est l'espacement des nombres machine autour de $1 0^{6}$ ? Autour de $1 0^{- 6}$ ? En déduire la plus petite quantité qu'on puisse ajouter à $1 0^{6}$ sans que le résultat soit à nouveau .

Exercice 1.3 · Réécrire pour éviter l'annulation

Chacune des expressions suivantes perd des chiffres significatifs dans le régime indiqué. Identifier la soustraction fautive, estimer le facteur d'amplification, et proposer une forme stable.

$\frac{1 - cos x}{x ^{2}}$ pour $x \to 0$ .
$x^{2} + 1 - x$ pour .

Exercice 1.4 · Propagation et conditionnement

Une résistance électrique est mesurée à $R = 470 Ω$ à $\pm 5 %$ et une tension à $U = 12, 0$ V à $\pm 1 %$ . Estimer l'erreur relative sur la puissance $P = U^{2} / R$ .

Exercice 1.5 · Borne d'erreur d'une somme de n termes

Soient $x_{1}, \dots, x_{n}$ des nombres machine (supposés exacts) que l'on somme de gauche à droite:

s_{1} = x_{1}, s_{k} = fl (s_{k - 1} + x_{k}) = (s_{k - 1} + x_{k}) (1 + δ_{k}), ∣ δ_{k} ∣ \leq u,

Références

Quarteroni, A., Sacco, R. et Saleri, F., Méthodes numériques — algorithmes, analyse et applications, Springer, Milan, chap. 2 (les bases de l'analyse numérique matricielle et la stabilité).
Rappaz, J. et Picasso, M., Introduction à l'analyse numérique, Presses polytechniques et universitaires romandes, Lausanne, chap. 1.
Higham, N. J., Accuracy and Stability of Numerical Algorithms, 2e éd., SIAM, Philadelphie, chap. 1 à 4 (la référence sur le modèle d'arrondi et la sommation compensée).
Goldberg, D., «What Every Computer Scientist Should Know About Floating-Point Arithmetic», ACM Computing Surveys, vol. 23, n° 1, 1991.
Burden, R. L. et Faires, J. D., Numerical Analysis, Cengage, Boston, chap. 1.
IEEE Standard for Floating-Point Arithmetic, IEEE Std 754, Institute of Electrical and Electronics Engineers (norme en vigueur, révisée en 2019).

Objectifs du chapitre

Pourquoi un cours d'analyse numérique commence par l'erreur

Les quatre sources d'erreur

Erreur absolue, erreur relative, chiffres significatifs

Les nombres à virgule flottante

Le format IEEE 754 en double précision

L'arrondi et son modèle

Ce que devient une opération

Produit et quotient: les erreurs s'additionnent, doucement

La somme et la différence: le facteur d'amplification

Le cas d'école: `0.1 + 0.2`

L'annulation catastrophique

La différence de deux racines carrées

La formule du second degré

Le troisième classique: $1 - cos x$

La propagation d'une erreur à travers une fonction

Conditionnement du problème, stabilité de l'algorithme

L'erreur d'arrondi accumulée sur une somme

Troncature contre arrondi: le premier compromis du cours

Synthèse

Exercices

Références

Repérer la soustraction dangereuse

La valeur exacte de la petite racine

Ce que la formule naïve produit

Le test de recette

Objectifs du chapitre

Pourquoi un cours d'analyse numérique commence par l'erreur

Les quatre sources d'erreur

Erreur absolue, erreur relative, chiffres significatifs

Les nombres à virgule flottante

Le format IEEE 754 en double précision

L'arrondi et son modèle

Ce que devient une opération

Produit et quotient: les erreurs s'additionnent, doucement

La somme et la différence: le facteur d'amplification

Le cas d'école: 0.1 + 0.2

L'annulation catastrophique

La différence de deux racines carrées

La formule du second degré

Le troisième classique: 1−cosx

La propagation d'une erreur à travers une fonction

Conditionnement du problème, stabilité de l'algorithme

L'erreur d'arrondi accumulée sur une somme

Troncature contre arrondi: le premier compromis du cours

Synthèse

Exercices

Références

Repérer la soustraction dangereuse

La valeur exacte de la petite racine

Ce que la formule naïve produit

Le test de recette

Le cas d'école: `0.1 + 0.2`

Le troisième classique: $1 - cos x$