Contrôler la propagation des erreurs de calculs numériques

Voice un petit article que j'ai écrit il y a deux jours sur la méthode CESTAC. Comme à mon habitude, je ne disposais pas d'un clavier avec des accents, ce qui sera corrigé assez vite.

Le contenu me semble terminé (hors Atelier, à discuter), le plan également. J'attends donc vos retours sur cela.

Je m'atèle désormais à la mise en page, des liens vers Wikipédia pour certains concepts, orthographe, style et typographie. Je ferai signe lorsque j'aurais besoin d'un retour sur ces points là.

J'ai commencé (jeudi 26 novembre 2015 à 15h06) la rédaction d'un article au doux nom de « Contrôler la propagation des erreurs de calculs numériques » et j'ai dans l'objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limite pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l'adresse suivante :

Merci !

Merci pour l'article ! Un début de remarques :

Introduction

Abuu

Aabu

Rappels d'arithmétique flottante

Avec $\frac 1b \leq m < 1$

Je ne comprends pas cela.

Or, quelque soit la base b choisie, il existe un nombre infini de nombre dont la represensation comporte une mantisse ayant un nombre infini de chiffres.

Ca se prouve facilement ?

On peut donc écrire M en base b par

Ca se comprend facilement, mais ça fait un peu bizarre d'avoir la même expression qu'au-dessus, c'est-à-dire d'avoir dans les deux cas une somme allant de $i=1$ à $n$. Comme ce n'est pas le même $n$, peut-être en remplacer un histoire de balayer toute confusion ?

On considère l'opération d'affectation (:=) : \mathbb{R} \to \mathcal{F}$, ou \mathcal{F}

Erreur Markdown.

Si l'on pose r=m−M le résidu, c'est à dire la partie perdue de la mantisse, on a α=−rM avec un encadrement du résidu selon que l'on se trouve en arithmétique d'arrondi ou de troncature :

Tu pourrais détailler ça. Mais bon, il est tard, donc peut-être qu'en réfléchissant deux secondes demain matin, ça passera mieux.

Les différents problèmes du numéricien

Pour le numericien : comment pour un algorithme donne ET un materiel et systeme de representation des reels donnes, obtenir une meilleure approximation de la solution ? Reponse : reorganiser l'algorithme pour limiter la propagation des erreurs de calculs tout en ne changeant pas la vitesse de convergence !

Je ne comprends pas trop ce que tu entends par "reorganiser l'algorithme". Je me doute que c'est différent du problème du mathématicien, à savoir chercher une algorithme plus performant, mais je ne vois pas concrètement en quoi.

Pour le numericien : comment determiner le nombre optimal d'iteration a effectuer pour un algorithme, quelque soit les donnees en entree ?

Et pour une représentation des réels donnée ?

C'est principalement ce dernier probleme que s'attache a resoudre CESTAC qui l'on présentera dans la section suivante.

Le "C" s'incline donc au profit du "E" ?

Comme d'habitude, c'est du travail de qualité. Je te ferai un retour sur le plan une fois l'article lu en entier.

Je le mets maintenant que j'y pense, bien que ce ne serait pas nécessairement à faire tout de suite, mais tu pourrais améliorer la présentation de la liste des quatre problèmes. Actuellement, elle est très dense, et tu pourrais notamment mettre "Réponse" en gras, ou passer à la ligne :

1
2
3

* Pour machin : question.  (deux espaces)
Réponse :
* etc.

Bonne soirée.

Avec $\frac 1b \leq m < 1$

Je ne comprends pas cela.

Multiplie par $b$, cela devrait t'aider. C'est la présentation usuelle en calcul numérique qui veut cela à cause de la norme IEEE-754 qui veut que le premier digit est non-nul.

Or, quelque soit la base b choisie, il existe un nombre infini de nombre dont la represensation comporte une mantisse ayant un nombre infini de chiffres.

Ca se prouve facilement ?

Oui. Je n'ai pas le temps de détailler ce soir, mais tu peux t'amuser toi même à en faire une infinité en base 10 avec a $\frac {a}{9 \times 10^{n}} où $n$ sera la longueur de la période et $a$ un réel.

On peut donc écrire M en base b par

Ca se comprend facilement, mais ça fait un peu bizarre d'avoir la même expression qu'au-dessus, c'est-à-dire d'avoir dans les deux cas une somme allant de $i=1$ à $n$. Comme ce n'est pas le même $n$, peut-être en remplacer un histoire de balayer toute confusion ?

Faut que je relise. A priori les formules sont les même, à la différence que $n$ est toujours fini dans le second cas.

Si l'on pose r=m−M le résidu, c'est à dire la partie perdue de la mantisse, on a α=−rM avec un encadrement du résidu selon que l'on se trouve en arithmétique d'arrondi ou de troncature :

Tu pourrais détailler ça. Mais bon, il est tard, donc peut-être qu'en réfléchissant deux secondes demain matin, ça passera mieux.

Dit moi si c'est pas clair demain. Je relirais aussi.

Je ne comprends pas trop ce que tu entends par "reorganiser l'algorithme". Je me doute que c'est différent du problème du mathématicien, à savoir chercher une algorithme plus performant, mais je ne vois pas concrètement en quoi.

Par exemple, lorsque tu réalises une somme, sommer dans l'ordre croissant permet de limiter les erreurs. Si tu peux connaître pas une étude mathématique les relations entre les termes que tu additionnes ou simplement leur ordre de grandeur, réarranger la somme permettra de limiter la propagation des erreurs.

Pour le numericien : comment determiner le nombre optimal d'iteration a effectuer pour un algorithme, quelque soit les donnees en entree ?

Et pour une représentation des réels donnée ?

Bien sur.

C'est principalement ce dernier probleme que s'attache a resoudre CESTAC qui l'on présentera dans la section suivante.

Le "C" s'incline donc au profit du "E" ?

Pas vraiment. L'estimation permet le controle. Tu controles à partir de l'estimation.

Multiplie par b, cela devrait t'aider. C'est la présentation usuelle en calcul numérique qui veut cela à cause de la norme IEEE-754 qui veut que le premier digit est non-nul.

Effectivement, la multiplication aide. Par contre, quid des formes dénormalisées ?

Faut que je relise. A priori les formules sont les même, à la différence que n est toujours fini dans le second cas.

Ouep. Du coup, comme $n$ est toujours fini dans le second cas, contrairement au premier, peut-être serait-il intéressant de le renommer, histoire qu'on fasse bien la distinction. Mais c'est un détail, puisque le texte explique très bien la différence.

Dit moi si c'est pas clair demain. Je relirais aussi.

Je ne comprends pas comment tu gères le cas $e \neq E$, ni d'où sort l'encadrement du résidu en arithmétique d'arrondi.

Par exemple, lorsque tu réalises une somme, sommer dans l'ordre croissant permet de limiter les erreurs. Si tu peux connaître pas une étude mathématique les relations entre les termes que tu additionnes ou simplement leur ordre de grandeur, réarranger la somme permettra de limiter la propagation des erreurs.

Merci pour cette illustration.

Controle et estimation stochastiques des arrondis de calculs

Je préviens tout de suite : je n'ai probablement pas le niveau mathématique pour comprendre ce qui suit.

La non-associativite de l'algebre F fait que l'image F travaillant sur F d'une procedure f travaillant sur R, n'est pas unique

Je ne comprends pas trop cela. Tu fixes $f$ de $\mathbb R \to \mathcal F$ et tu dis que son image n'est pas unique ?

en permutant une simple operation arithmetique

Je ne comprends pas cela.

on obtient une procedure F′

$f'$, non ?

toute chose egale par ailleurs

Qu'entends-tu par "toute chose" ?

Un facteur qui permet d'agrandir la taille de cette population, c'est le mode d'arrondi ou de troncature utilise, perturbant la mantisse, puisque selon ce mode, le resultat d'une meme procedure sera different.

Je suis désolé, mais je ne comprends pas non plus ce que tu entends par "mode d'arrondi ou de troncature".

Ainsi, a partir d'une meme procedure F

et que l'on notera simplement $P_F$

$f$ ?

Je vais m'arrêter ici, sinon je crois que je vais poser une question à chaque phrase.

Manifestement, je n'ai pas les compétences mathématiques pour suivre cette section. Bien sûr, le choix te revient, mais si tu décides de la rendre plus accessible, tu pourrais le faire en ajoutant des exemples (dans la mesure du possible : de procédure, de permutation, de mode d'arrondi/troncature et de perturbation).

Merci.

Effectivement, la multiplication aide. Par contre, quid des formes dénormalisées ?

Spécificité de la norme IEEE-754. Ce n'est pas important pour la suite, d'autant que cela ne rend pas caduque les hypothèses de CESTAC sur la distribution uniforme des erreurs de calculs. Le fait que la distribution des flottants ne soit pas uniforme n'a pas d'impact ici.

Je ne comprends pas comment tu gères le cas $e \neq E$, ni d'où sort l'encadrement du résidu en arithmétique d'arrondi.

Ce sont des rappels rapides sur le mode arrondi et troncature. Lorsque tu es en troncature, tu prends la mantisse illimitée $m$ et tu supprimes les digits de rang supérieur à $n$, ce que traduit l'inégalité.
En mode arrondi, tu ajoutes $b-1$ au digit de rang $n+1$ de la mantisse $m$ et tu tronques.

Je pense que le tutoriel de Aabu traitera de cela plus en détail.

La non-associativite de l'algebre F fait que l'image F travaillant sur F d'une procedure f travaillant sur R, n'est pas unique

Je ne comprends pas trop cela. Tu fixes $f$ de $\mathbb R \to \mathcal F$ et tu dis que son image n'est pas unique ?

Je fais un exemple débile. Tu as une fonction mathématique $f$ qui somme les éléments d'un vecteur. Tu écriras donc en mathématiques simplement $x = \sum_i^n x_i$ et l'ordre de sommation n'aura pas d'importante.

A contrario, en informatique, selon l'ordre de sommation, le résultat sera différent. Ainsi, pour une fonction $f$ donnée, il y a en théorie autant de $F$ qu'il y a de moyen de permuter les termes utilisés.

Un exemple moins stupide serait celui de l'évaluation d'un polynome en un point. Tu disposes mathématiques d'une fonction $f$ qui prends un polynome et un point en lequel l'évaluer et cette fonction te returne le résultat de l'évaluation. Bon, en mathématique tout est beau et parfait.

Cependant, dans la réalité, l'idée naïve d'évaluer chaque monome et de sommer les monomes est mauvaise et la manière efficace pour limiter la propagation des erreurs est d'utiliser l'évaluation de Horner.

On voit donc que pour une même fonction $f$, il existe plusieurs images de celle-ci par l'application que l'on pourrait bêtement appeler "Implémentation".

en permutant une simple operation arithmetique

Je ne comprends pas cela.

C'est la même chose que ce que je viens d'expliquer plus haut. Permuter l'ordre des opérations permet d'augmenter ou diminuer les erreurs de calculs.

on obtient une procedure F′

$f'$, non ?

Non, $F'$, c'est une autre implémentation de $f$.

toute chose egale par ailleurs

Qu'entends-tu par "toute chose" ?

Même matériel, représentation sous-jacente, etc.

Un facteur qui permet d'agrandir la taille de cette population, c'est le mode d'arrondi ou de troncature utilise, perturbant la mantisse, puisque selon ce mode, le resultat d'une meme procedure sera different.

Je suis désolé, mais je ne comprends pas non plus ce que tu entends par "mode d'arrondi ou de troncature".

Quand tu sommes deux flottants par exemple, il faut bien faire rentrer la mantisse du résultat dans $n$ bit, ce qui n'est pas toujours possible. Du coup, tu peux soit tronquer, soit arrondir (et il existe 4 modes d'arrondis en IEEE 754: Vers moins l'infini Vers plus l'infini Vers zéro Au plus proche)

Ainsi, a partir d'une meme procedure F

et que l'on notera simplement $P_F$

$f$ ?

Nop. C'est la population des implémentations que l'on peut obtenir par la permutation des opérations arithmétiques d'un $F$ particulier. C'est un sous ensemble de la population des implémentations possibles de $f$.

Je ne suis pas sur que ce soit très important au final.

Je vais m'arrêter ici, sinon je crois que je vais poser une question à chaque phrase.

Bonjour les agrumes !

La bêta article « Contrôler la propagation des erreurs de calculs numériques » a été mise à jour et coule sa pulpe à l'adresse suivante :

Merci d'avance pour vos commentaires.

La mise à jour concernce :

• Les accents (pas pour les majuscules notamment).
• Modifications diverses suites aux remarques de Vayel
• Correction d'une erreur factuelle (l'échantillon doit être iid et pas suivre une gaussienne)

Manifestement, je n'ai pas les compétences mathématiques pour suivre cette section. Bien sûr, le choix te revient, mais si tu décides de la rendre plus accessible, tu pourrais le faire en ajoutant des exemples (dans la mesure du possible : de procédure, de permutation, de mode d'arrondi/troncature et de perturbation). Source:Vayel

Tu as tout a fait les competences pour suivre. En fait, c'est moi qui ait tres mal explique la partie la plus cruciale pour comprendre.

De plus, avec des illustrations et un exemple cela passera tout seul.

L'idee est tres simple :

Lorsque j'ai un resultat mathematique exact $x$, il est exact, point. Tandis que lorsque j'ai le resultat d'un calcul numerique $X$ (genre X = (b + c) / (d - e)), ce dernier n'est pas exact, certes, il n'y a aucune raison que je lui prefere un arrondi vers un infini plutot qu'un autre, vers zero, ou une troncature basse ou haute. L'erreur d'affectation depend de cela et sera differente selon ce mode. De ce fait, un reel a plusieures representations possibles en machine (tout comme la reciproque est vraie : un flottant represente plusieurs reels), meme au sein de la norme IEEE-754, qui n'ont pas plus de legitimite l'une par rapport a l'autre.

Je perturbe le dernier chiffre de la mantisse de maniere aleatoire (selon un mode particulier). La perturbation represente le fait que a priori je n'ai pas plus de legitimite a choisir un mode plutot qu'un autre.

En perturbant $X$ un certain nombre de fois $N$ j'obtiens un echantillon sur lequel je peux effectuer un test statistique (ici Student par rapport aux hypotheses et contraintes - mais peu importe en fait) pour essayer d'estimer la moyenne et l'ecart type de cette perturbation.

La partie qui ne varie pas au sein de l'echantillon, la partie commune a toutes ces representation, est la partie significative. Evidemment, cette partie significative est estimee et donc avec un risque d'erreur, fixe a l'avance.

Note qu'il existe des methodes deterministes (notamment via l'artithmetique d'intervalle) mais que ces methodes conduisent souvent a des calculs inextricables et surtout une surestimation monstrueuse de l'erreur.

J'ai aussi commis une petite erreur dans la methode synchrone en disant que l'on affecte a $X$ la valeur de l'estimateur $\bar X$, ce qui est une mauvaise idee puisque comme il n'est pas robuste (moyenne), on risque en moyenne de faire augmenter les erreurs. Du coup en theorie on affecte un element de l'echantillon, et en pratique on affecte le premier (vu que $N$ vaut 2 ou 3, on s'embete pas).

Merci, c'est plus clair. Par contre, je ne comprends pas trop cette histoire de perturbation aléatoire. Aurais-tu un cas de figure, par exemple en prenant $X = 0.1$ en base 10 ?

Pour un réel donné $x$, il existe un flottant $X^+$ et un flottant $X^-$ tels que $X^- \leq x \leq X^+$.

Si $x$ est représentable sous notre représentation (c'est à dire que la mantisse est exprimable en moins de $n$ digit, et l'exposant dans la plage), alors on a égalité entre les trois termes.

Si ce n'est pas le cas, il faut choisir entre l'un ou l'autre, qui n'ont pas plus de légitimité l'un par rapport à l'autre à priori.

Selon le mode d'arrondi choisi, le représentant flottant ne sera pas le même.

• Arrondi vers $+\infty$ : on retourne $X^+$ sauf si $x = X^-$.
• Arrondi vers $-\infty$ : on retourne $X^-$ sauf si $x = X^+$.
• Arrondi vers $0$ : retourne $X^-$ pour les positifs et $X^+$ pour les négatifs.
• Arrondi au plus proche : retourne le nombre machine le plus proche de $x$.

Une propriété essentielle de la norme IEEE-754 c'est qu'elle garantit qu'une opération en virgule flottante soit égale à l'opération réelle dont on applique un mode d'arrondi à la suite.

Dans CESTAC, au lieu de choisir un mode d'arrondi, on considère que $X^+$ et $X^-$ doivent sortir de manière uniforme. Le but c'est de propager les erreurs d'arrondis de différentes manières pour pouvoir estimer le nombre de chiffres significatifs du résultats.

Dans les fait, la perturbation de la mantisse c'est simplement l'opération qui fait passer d'un $X$ à l'autre.

Merci beaucoup, ça va mieux.

Tu pourrais, dans le tutoriel, renseigner ces quatres modes d'arrondi.

Le but c'est de propager les erreurs d'arrondis de différentes manières pour pouvoir estimer le nombre de chiffres significatifs du résultats.

Je ne comprends pas tellement cela, mais j'imagine que c'est normal : tu ne peux pas non plus expliquer CESTAC en une phrase.

Encore merci pour tes explications. Souhaites-tu des retours sur la suite, ou est-il préférable que j'attende que tu modifies le tutoriel pour y incorporer les explications que tu m'as fournies ?

Je suis d'avis d'attendre, ne serait-ce que pour economiser ton temps.

Merci de tes remarques.

Bonjour les agrumes !

La bêta article « Contrôler la propagation des erreurs de calculs numériques » a été mise à jour et coule sa pulpe à l'adresse suivante :

Merci d'avance pour vos commentaires.

Merci d'avoir pris en compte mes remarques précédentes.

Rappels d'arithmétique flottante

Avec $\frac 1b ≤ m < 1$

Peut-être pourrais-tu illustrer cette inégalité dans l'exemple qui suit, en disant qu'on écrit $x = 0,1 \times 10^0$ et non $x = 1 \times 10^1$ ?

Pour un réel donné x, il existe un flottant X+ et un flottant X− tels que X−≤x≤X+.

Si x est représentable de manière exacte, alors on a égalité entre les trois termes

La seconde phrase n'est valable que si on prend $X^-$ maximal et $X^+$ minimal.

et l'opération d'affectation X:=x

Tu l'as définie de $\mathbb R$ dans $\mathcal F$, donc c'est l'inverse. Et histoire d'être bien clair, tu pourrais indiquer qui est $X$, même si on comprend aisément.

Cette propriété, dite d'arrondi correct, est essentielle car elle permet de faire des preuves sur un algorithme numérique ou d'obtenir des bornes prouvées pour des résultats numériques.

Le terme technique est intéressant à connaître, mais, en l'état, la phrase me semble trop vague pour être utile. Tu pourrais te contenter de nommer la propriété, mais aussi laisser comme ça, en donnant un bref exemple, fût-il sous forme de lien.

Cette section est très claire maintenant. Merci.

Les différents problèmes du numéricien

Lorsqu'un algorithme est fini, ou fini s'entend comme un nombre d'étapes fini pour trouver la solution à un probleme, alors l'erreur numérique est le résultat de la propagation des erreurs d'arrondis ou de troncature lors des opérations en virgule flottante.

Détrompe-moi au besoin, mais il me semble qu'on peut avoir des erreurs dues à l'algorithme en lui-même, comme avec la méthode d'Euler. Après, peut-être n'ai-je pas compris ce que tu appelais erreur numérique.

Dans le cas d'algorithmes itératifs, par exemple la méthode de Newton présentée par Holosmos dans son cours sur les développements limités, il est aussi nécessaire d'arrêter l'algorithme

Je ne comprends pas tellement le "aussi". Tu pourrais procéder comme suit :

• Dans le cas d'algorithmes itératifs, il ne faut pas s'arrêter trop tard, sinon lesdites erreures fausseront complètement le résultat
• Mais pas trop tôt non plus, sinon…

Prenons un cas pathologique extrêmement simple : xn=axn−1+b

C'est $-b$ dans l'implémentation.

Merci, je regarde la suite plus tard.

Avec $\frac 1b ≤ m < 1$

Peut-être pourrais-tu illustrer cette inégalité dans l'exemple qui suit, en disant qu'on écrit $x = 0,1 \times 10^0$ et non $x = 1 \times 10^1$ ?

La mantisse c'est 0,1. Tu considères $M = 0,1$ qui est bien sur compris entre $\frac 1 10$ et $1$. Imaginons une mantisse de $0,09$, cela ne rentre pas dans notre définition, la mantisse correcte serait $0,9$ et l'exposant serait décalé d'un facteur 10 ($b$ généralement).

Si x est représentable de manière exacte, alors on a égalité entre les trois termes

La seconde phrase n'est valable que si on prend $X^-$ maximal et $X^+$ minimal.

Oui évidement. Je parlais de l'encadrement de $x$ par des flottants.

Tu l'as définie de $\mathbb R$ dans $\mathcal F$, donc c'est l'inverse. Et histoire d'être bien clair, tu pourrais indiquer qui est $X$, même si on comprend aisément.

C'est bien comme cela si tu réfléchis. Je prends un $x \in \mathbb{R}$ et je l'affecte, ce qui me donne $X \in mathcal{F}$.
Lorsque j'écris double x = 0.1 c'est bien $x$ le flottant et $0.1$ le réel. Il s'agit juste de conserver la même notation plutôt qu'une notation habituelle en mathématique.

Cette propriété, dite d'arrondi correct, est essentielle car elle permet de faire des preuves sur un algorithme numérique ou d'obtenir des bornes prouvées pour des résultats numériques.

Le terme technique est intéressant à connaître, mais, en l'état, la phrase me semble trop vague pour être utile. Tu pourrais te contenter de nommer la propriété, mais aussi laisser comme ça, en donnant un bref exemple, fût-il sous forme de lien.

Elle est expliquée un peu plus loin il me semble. Mais typiquement, comme la norme t'assure que pour un mode d'arrondi choisi, une opération entre flottant donne le même résultat que le résultat mathématique exact que tu arrondis ensuite selon ce mode, et bien tu peux commencer à raisonner de manière formelle sur ton algorithme et garantir le résultat obtenu.

Lorsqu'un algorithme est fini, ou fini s'entend comme un nombre d'étapes fini pour trouver la solution à un probleme, alors l'erreur numérique est le résultat de la propagation des erreurs d'arrondis ou de troncature lors des opérations en virgule flottante.

Détrompe-moi au besoin, mais il me semble qu'on peut avoir des erreurs dues à l'algorithme en lui-même, comme avec la méthode d'Euler. Après, peut-être n'ai-je pas compris ce que tu appelais erreur numérique.

La méthode d'Euler est une méthode itérative.

Je ne comprends pas tellement le "aussi". Tu pourrais procéder comme suit :

La méthode de Newton et toutes les méthodes itératives convergent vers la solution. Elles ne l'atteignent pas en un nombre d'itérations données (c'est pour ça que j'ai précisé ma taxinomie car on peut aussi considérer qu'une méthode est itérative à partir du moment où tu as une relation de récurrence, mais ce n'est pas adapté au problème ici.) mais ne font que se rapprocher. Du coup, numérique il faut s'arrêter à un moment donné !

• Dans le cas d'algorithmes itératifs, il ne faut pas s'arrêter trop tard, sinon lesdites erreures fausseront complètement le résultat
• Mais pas trop tôt non plus, sinon…

Si tu t'arrêtes trop tôt tu seras loin du résultat ! Imagine une recherche dichotomique sur un segment de la droite des réelles. Tu sais que tu convergeras vers l'entier que tu recherches, et tu diviseras par deux à chaque itération la distance à cette valeur cherchée. Tu vas donc devoir t'arrêter. Si tu fais que deux itérations tu seras bien plus loin que 100 itérations. A voir si deux itérations fournissent une approximation acceptable pour ton problème, mais tu dois voir que ce n'est pas nécessairement le cas.

La mantisse c'est 0,1. Tu considères $M = 0,1$ qui est bien sur compris entre $\frac 1 10$ et $1$. Imaginons une mantisse de $0,09$, cela ne rentre pas dans notre définition, la mantisse correcte serait $0,9$ et l'exposant serait décalé d'un facteur 10 ($b$ généralement).

Ouep, c'est ce que tu m'as expliqué suite à mon premier message. Mais comme certains lecteurs risquent de ne pas comprendre ce $\frac 1b$, tu pourrais l'expliciter dans l'exemple que tu donnes, en indiquant que l'inégalité signifie qu'on prend $0,1$ et non $1$ ou $0,01$ comme mantisse.

C'est bien comme cela si tu réfléchis. Je prends un $x \in \mathbb{R}$ et je l'affecte, ce qui me donne $X \in mathcal{F}$.
Lorsque j'écris double x = 0.1 c'est bien $x$ le flottant et $0.1$ le réel. Il s'agit juste de conserver la même notation plutôt qu'une notation habituelle en mathématique.

Autant pour moi, je me coucherai moins bête.

Elle est expliquée un peu plus loin il me semble. Mais typiquement, comme la norme t'assure que pour un mode d'arrondi choisi, une opération entre flottant donne le même résultat que le résultat mathématique exact que tu arrondis ensuite selon ce mode, et bien tu peux commencer à raisonner de manière formelle sur ton algorithme et garantir le résultat obtenu.

Merci pour l'explication.

La méthode de Newton et toutes les méthodes itératives convergent vers la solution. Elles ne l'atteignent pas en un nombre d'itérations données (c'est pour ça que j'ai précisé ma taxinomie car on peut aussi considérer qu'une méthode est itérative à partir du moment où tu as une relation de récurrence, mais ce n'est pas adapté au problème ici.) mais ne font que se rapprocher. Du coup, numérique il faut s'arrêter à un moment donné !

Je comprends qu'il faille s'arrêter, mais pourquoi "il est aussi nécessaire de" ?

En fait, je ne comprends pas l'enchainement logique entre les deux paragraphes suivants.

Comme mentionné précédemment, tout algorithme effectuant des calculs en virgule flottante donne un résultat entâchée d'erreurs. Lorsqu'un algorithme est fini, ou fini s'entend comme un nombre d'étapes fini pour trouver la solution à un probleme, alors l'erreur numérique est le résultat de la propagation des erreurs d'arrondis ou de troncature lors des opérations en virgule flottante.

Dans le cas d'algorithmes itératifs, par exemple la méthode de Newton présentée par Holosmos dans son cours sur les développements limités, il est aussi nécessaire d'arrêter l'algorithme après un certain nombre, optimal, d'itérations, ce qui est un problème considerant que :

Contrôle et estimation stochastiques des arrondis de calculs

L'algèbre F sur le corps des nombres flottant n'est pas associative ni distributive. Autrement dit, l'ordre dans lequel on effectue nos opérations arithmétiques a un impact sur le résultat.

Aurais-tu une explication à ce sujet, à la limite un lien ?

À partir de maintenant, considérons f, une procédure qui travaille sur R et son image F, une procédure travaillant sur F.

L'exemple permet de comprendre, donc ce n'est pas très important, mais au début, je croyais que $F = f(\mathbb R)$, donc je ne comprenais pas. Que signifie le terme image ici ?

S'ajoute à cela une perturbation du résultat par le mode d'arrondi choisi qui vient encore grossir le pire des cas.

Je comprends ce que tu veux dire, mais le lecteur n'ayant pas lu tes explications dans ce sujet risque, je pense, de bloquer sur le terme "perturbation". Tu pourrais brièvement introduire $F_{1^-}$, par exemple.

L'espérance μ représente le résultat attendu de l'algorithme, c'est-à-dire le nombre à virgule flottante qui code notre solution réelle r.

C'est une définition ? Dans le cas contraire, pourrais-tu expliciter la raisonnement que tu as eu pour en déduire cela ?

Je n'ai pas les connaissances nécessaires pour comprendre les détails de la partie théorique, donc je passe à la construction de l'échantillon.

La version synchrone consiste cette fois à réaliser l'échantillon à chaque opération d'affectation et utiliser comme résultat la moyenne.

Je ne suis pas sûr de comprendre. Si on fait une moyenne, $R$ n'est plus un $N$-uplet, si ?

C'est beaucoup plus clair à présent. Beau travail.

Avant toute chose, j'ai une autre demonstration a te proposer sur l'impossibilite de representer les reels. Cela se passe avec Borel-Cantelli normalement et je te livre la conclusion.

• Un nombre normal est un nombre tel que toute suite fini de bit apparait une nombre infini de fois dans les decimales de ce nombre. Il est normal en toute base si quelque soit la base il est normal.
• Grace a Borel-Cantelli on prouve que l'ensemble des nombres non-normaux en toute base est de mesure nulle.
• En tirant un nombre au hasard sur R, quelque soit la base consideree, la probabilite que le nombre soit normal est 1.

Aurais-tu une explication à ce sujet, à la limite un lien ?

Le tutoriel d'Aabu en parlera a coup sur. page 9 | grep associativite

À partir de maintenant, considérons f, une procédure qui travaille sur R et son image F, une procédure travaillant sur F.

L'exemple permet de comprendre, donc ce n'est pas très important, mais au début, je croyais que $F = f(\mathbb R)$, donc je ne comprenais pas. Que signifie le terme image ici ?

Il manque probablement une virgule.

À partir de maintenant, considérons f, une procédure qui travaille sur R, et son image F, une procédure travaillant sur F.

f est une fonction qui travaille sur l'algebre $\mathbb R$ et F est l'image de F sur l'algebre $\mathcal F$. En gros c'est le passage de 'je fais des calculs sur le papier avec des reels' a 'je fais les meme calculs mais sur machine avec des flottants'.

L'espérance μ représente le résultat attendu de l'algorithme, c'est-à-dire le nombre à virgule flottante qui code notre solution réelle r.

C'est une définition ? Dans le cas contraire, pourrais-tu expliciter la raisonnement que tu as eu pour en déduire cela ?

Si l'estimateur n'est pas biaise (ce qui est le cas) et sous reserve de symetrie de la loi de la VA (ce qui est le cas vu qu'on a une gausienne), c'est evident par definition. La distribution des flottants que l'on obtient est distribuee symetriquement autour de la valeur exact et represente egalement l'esperance. Notre estimateur converge vers l'esperance, donc vers notre valeur.

La version synchrone consiste cette fois à réaliser l'échantillon à chaque opération d'affectation et utiliser comme résultat la moyenne.

Je ne suis pas sûr de comprendre. Si on fait une moyenne, $R$ n'est plus un $N$-uplet, si ?

C'est beaucoup plus clair à présent. Beau travail.

C'est une erreur, il ne faut pas assigner la moyenne. Si tu fais cela, la methode est inutile et ne fait qu'estimer localement l'erreur d'affectation et trouvera toujours un nombre de CS de 15 voire infini (si le reel est representable).

L'idee est effectivement de maintenir l'echantillon initial, et de continuer la propagation sur cette echantillon a chaque etape du calcul tandis que dans la version asynchrone, on prend comme echantillon juste les resultats finaux de N appels.

Je comprends qu'il faille s'arrêter, mais pourquoi "il est aussi nécessaire de" ?

Aussi parce qu'il y a comme avant une propagation d'erreur a estimer, mais aussi la question de 'quand est-ce que je m'arrete ?'. C'est evidemment relie, mais il faut tout de meme poser la definition d'un zero informatique et modifier nos tests d'arret.

f est une fonction qui travaille sur l'algebre R et F est l'image de F sur l'algebre F. En gros c'est le passage de 'je fais des calculs sur le papier avec des reels' a 'je fais les meme calculs mais sur machine avec des flottants'.

Existe-t-il une définition mathématique de ce passage, ou as-tu simplement employé ce terme parce qu'il était plutôt parlant ?

Si l'estimateur n'est pas biaise (ce qui est le cas) et sous reserve de symetrie de la loi de la VA (ce qui est le cas vu qu'on a une gausienne)

Peut-être pourrais-tu l'indiquer ?

Aussi parce qu'il y a comme avant une propagation d'erreur a estimer, mais aussi la question de 'quand est-ce que je m'arrete ?'.

Tu pourrais reformuler de la sorte "Dans le cas d'algorithmes itératifs, […], en plus de la question de la propagation des erreurs, il faut se poser celle du nombre d'itérations, laquelle n'est pas évidente, considérant que :".

A plus

Bonjour les agrumes !

La bêta de votre article « Contrôler la propagation des erreurs de calculs numériques » a été mise à jour et coule sa pulpe à l'adresse suivante :

Merci d'avance pour vos commentaires.

• Ajout des illustrations pour les deux versions (asynchrone et synchrones)
• Correction orthographique.
• Ajout de quelques exemples.
• Ajout d'une démonstration en note de bas de page.

Je recherche désormais des corrections orthographiques et typographiques (hors évidences comme les apostrophes qui ne sont pas encore françaises). J'accepte évidemment toujours les retours sur le fond.

Merci, j'ai commencé à regarder ça.

Je suis tombé sur pas mal de petites coquilles orthographiques (genre des pluriels). Comment souhaites-tu procéder à ce niveau ? Je les relève toutes ? Tu t'en occupes ? Je m'en occupe (tu me donnes l'accès temporairement) ?

Sinon, tu as pas mal de "quelque soit" au lieu de "quel(le) que soit".

Je te donne l'accès et tu en fais ce que tu veux. Si tu as le temps, tu peux faire les corrections, sinon les indiquer ici une fois par occurrence, et je grep / replacerai.