Epsilon d'une machine

L'epsilon d'un microprocesseur (abrégé en eps) donne la limite supérieure de l'erreur d'approximation relative causé par l'arrondi des calculs de ce microprocesseur en arithmétique à virgule flottante. Cette valeur est une caractéristique de l'arithmétique des ordinateurs dans le domaine de l'analyse numérique, et par extension dans le sujet du calcul scientifique. L'epsilon est aussi appelé macheps ou unité d'arrondi. Il est parfois noté à l'aide du symbole grec epsilon ou gras Romain u.^{[Information douteuse]}

Valeur pour les unités matérielles standard d'arithmétique à virgule flottante

Les valeurs d'epsilon standards suivantes s'appliquent pour le matériel implémentant les normes IEEE de calcul en virgule flottante:

IEEE 754 - 2008	Nom usuel	type de donnée C++	Base $b$	Précision $p$	Epsilon$b^{-(p-1)}/2$	Epsilon$b^{-(p-1)}$
binary16	demi-précision	short	2	11 (un des bits est implicite)	2−11 ≈ 4.88e-04	2−10 ≈ 9.77e-04
binary32	simple précision	float	2	24 (un des bits est implicite)	2−24 ≈ 5.96e-08	2−23 ≈ 1.19e-07
binary64	double précision	double	2	53 (un des bits est implicite)	2−53 ≈ 1.11e-16	2−52 ≈ 2.22e-16
?	précision étendue (en)	_float80	2	64	2−64 ≈ 5.42e-20	2−63 ≈ 1.08e-19
binary128	quadruple précision	_float128	2	113 (un des bits est implicite)	2−113 ≈ 9.63e-35	2−112 ≈ 1.93e-34
decimal32	simple précision décimale	_Decimal32	10	7	5 × 10−7	10−6
decimal64	double précision décimale	_Decimal64	10	16	5 × 10−16	10−15
decimal128	quadruple précision décimale	_Decimal128	10	34	5 × 10−34	10−33

Définition formelle

Une procédure d'arrondi est une procédure de choix de la représentation d'un nombre réel dans un système de numération en virgule flottante. Étant donné ce système de numération et une procédure d'arrondi, l’epsilon est le maximum de l'erreur d’approximation relative de la procédure d'arrondi choisie.

D’autres définitions et informations permettent de calculer l’epsilon à partir de l'erreur relative. Un système de numération à virgule flottante est caractérisé par une base $b$ et par une précision $p$, qui donne le nombre de chiffres de composant la mantisse (y compris les éventuels bits implicites). Les nombres représentés avec un exposant $e$ sont espacés d'une valeur de $b^{e-(p-1)}$. L'espacement change aux nombres qui sont des puissances entières de $b$; l'espacement du côté de plus grande magnitude est $b$ fois plus grand que l'espacement du côté de plus petite magnitude.

L'epsilon étant une borne pour l'erreur d'approximation relative, il ne dépend pas de l’exposant. Pour le déterminer, il suffit donc de considérer le cas ou l’exposant est nul. Il suffit également de considérer les nombres positifs. Pour l'arrondi usuel, c’est-à-dire l’arrondi vers le nombre le plus proche, l'erreur d'approximation absolue est au plus la moitié de l'espacement, c'est-à-dire $b^{-(p-1)}/2$. Cette valeur est la plus grande valeur possible pour le numérateur de l'erreur relative. Le dénominateur de la formule est le nombre à arrondir, qui devrait être aussi petit que possible pour que l'erreur relative soit grande. La pire erreur relative se produit donc quand l'arrondi est appliqué à des nombres de la forme $1+a$, où $a$ est compris entre $0$ et $b^{-(p-1)}/2$. Tous ces nombres sont arrondis vers $1$ avec l'erreur relative $a/(1+a)$. Le maximum est atteint pour $a$ à l'extrémité haute de cet intervalle. Le dénominateur, de valeur $1+a$, est négligeable en comparaison du numérateur, on peut donc l’ignorer par commodité; l'epsilon est donc donné parla formule $b^{-(p-1)}/2$. L'erreur relative est la plus grande pour les nombres qui s'arrondissent vers $1$, ce qui permet de nommer l'epsilon aussi parfois unité d'arrondi pour dénoter de manière informelle « l’erreur relative maximale possible lors de l'arrondi vers l'unité ».

Ainsi, l'espacement maximal entre nombre à virgule flottante normalisé x et un nombre normalisé adjacent est $2\epsilon \times |x|$.

Modèle arithmétique

L'analyse numérique utilise l'epsilon de la machine pour étudier les effets de l'erreur d'arrondi. Les valeurs réelles des erreurs de l'arithmétique de la machine sont en général bien trop compliquées pour être étudiées directement ; un modèle simple est donc utilisé. La norme arithmétique de l'IEEE  définit que toutes les opérations en virgule flottante sont calculées en supposant qu'il est possible d'effectuer les opérations avec une précision infinie, puis en supposant que le résultat soit arrondi à un nombre à virgule flottante. Supposons que $x,y$ sont des nombres à virgule flottante, que $\bullet$ est une opération arithmétique sur des nombres à virgule flottante, telle que l'addition ou la multiplication, et que $\circ$ est l'opération effectuée avec une précision infinie. Selon la norme, l'ordinateur calcule $x\bullet y={\mbox{round}}(x\circ y)$ Par définition de l'epsilon, l'erreur relative de l'arrondi est au plus de sa magnitude, de sorte que $x\bullet y=(x\circ y)(1+z)$où $z$, en magnitude absolue, est égal au plus à epsilon. Les ouvrages de Demmel et Higham dans les références peuvent être consultés pour voir comment ce modèle est utilisé pour l'analyse des erreurs d'algorithmes comme l'élimination de Gauss.

Variantes de la définition

La norme IEEE ne définit pas les termes de machine epsilon (epsilon de la machine) ni d'unit roundoff (unité d'arrondi). Il en résulte qu'il existe des variantes pour les définitions qui sont parfois utilisées en pratique, ce qui peut mener à une certaine confusion.

La définition donnée ici pour machine epsilon est celle du professeur James Demmel dans ses notes de cours et son logiciel d'algèbre linéaire LAPACK package, et par des articles de recherche scientifique sur le calcul numérique et de certains logiciels de calcul scientifique. La plupart des analystes numériques utilisent les termes (en anglais) machine epsilon et unit roundoff comme des termes synonymes, ayant la définition présentée ici.

La définition suivante est beaucoup plus répandue en-dehors du milieu universitaire : l'epsilon est défini comme le plus petit nombre qui, ajouté à un, donne un résultat différent de un. Avec cette définition, l'epsilon est égal à la valeur de l'unité à la dernière place (en) par rapport à 1, c'est-à-dire pour la procédure d'arrondi au plus proche u. La prévalence de cette définition vient de son utilisation dans la norme ISO du langage C, en particulier la définition des constantes concernant les types à virgule flottante et celles équivalentes d'autres langages de programmation. Elle est également largement utilisée dans le monde des logiciels de calcul scientifique, dans la littérature sur les nombres et le calcul et dans d'autres ressources académiques.

Comment déterminer l'epsilon

Le langage Fortran dispose, depuis la norme Fortran 90, de la fonction epsilon(x) qui renvoie l'epsilon correspond au type de réel de x.

Dans les cas où les bibliothèques standard ne fournissent pas de valeurs pré-calculées (comme <float.h (en)> le fait avec FLT_EPSILON, DBL_EPSILON et LDBL_EPSILON en C et <limits> avec std::numeric_limits<T>::epsilon() en C++), la meilleure manière de déterminer l'epsilon d'une machine est de se référer à la table ci-dessus, et utiliser la formule de puissance appropriée. Le calcul est souvent donné comme un exercice dans les manuels d'apprentissage. Les exemples suivants utilisent la définition de la distance des nombres à virgule flottante à 1 plutôt que celle d'unité d'arrondi.

Notez que les résultats dépendent du type de nombre à virgule flottante (comme float, double, long double, ou types équivalents dans d'autres langages de programmation), du compilateur et des bibliothèques utilisés, et finalement de la plateforme où sera exécuté le programme.

Certains formats pris en charge par le microprocesseur peuvent ne pas être pris en charge par le compilateur choisi ou par le système d'exploitation. D'autres types sont parfois émulés par la bibliothèque d'exécution, y compris l'arithmétique à précision arbitraire, disponible dans certains langages et bibliothèques.

Au sens strict, le terme d'epsilon désigne la précision 1+eps directement prise en charge par le processeur (ou le coprocesseur), et non une précision 1+eps prise en charge par un compilateur spécifique pour un système d'exploitation spécifique, sauf s'il est connu pour utiliser le meilleur format disponible.

Les types à virgule flottante de la norme IEEE 754 ont la propriété, lorsqu'ils sont réinterprétés comme des entiers codés en complément à deux entier de la même taille, de croître de manière monotone sur les valeurs positives et de décroître de manière monotone sur les valeurs négatives (voir la représentation binaire des floats 32 bits (en)). De plus, si f(x) est l'interprétation de x en complément à 2 susmentionnée, alors 0 < |f(x)| < ∞, et |f(x+1) − f(x)| ≥ |f(x) − f(x-1)|. Dans les langages qui permettent la réinterprétation de type (en) tout en utilisant IEEE 754-1985, nous pouvons exploiter tout ceci pour calculer un epsilon en temps constant. Par exemple, en C:

typedef union {
  long long i64;
  double d64;
} dbl_64;
double machine_eps (double value)
{
    dbl_64 s;
    s.d64 = value;
    s.i64++;
    return s.d64 - value;
}

Le résultat est de même signe que value. Si l'on souhaite obtenir un résultat toujours positif, l'instruction de retour de cette routine peut être remplacée par :

    return (s.i64 < 0 ? value - s.d64 : s.d64 - value);

Pour les nombres à double précision en 64 bits, la valeur retournée par machine_eps avec en entrée 1.0 est $2^{-52}$ soit approximativement 2.220446e-16.

Approximation

L'algorithme suivant, très simple, peut être utilisé pour trouver une approximation de l'epsilon d'une machine, un facteur deux (un ordre de grandeur) de sa valeur réelle, par une recherche linéaire.

epsilon = 1.0;

tant que (1.0 + 0.5 * epsilon) ≠ 1.0:
   epsilon = 0.5 * epsilon

Voir aussi

• Virgule flottante, discussion générale sur les questions relatives à l'exactitude dans l'arithmétique à virgule flottante
• Unité du dernier emplacement (en) (ULP)

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Machine epsilon » (voir la liste des auteurs).

Liens externes

• MACHAR, une routine (en C et Fortran) pour le "calcul dynamique des constantes d'une machine" (algorithme ACM 722)
• Le diagnostic de précision des calculs en virgule flottante, la mise en Œuvre de MACHAR en Component Pascal (en) et Oberon basé sur la version Fortran 77 de MACHAR publié dans Numerical Recipes (Press et al., 1992).