test d'égalité en double

Citation:

---

Envoyé par 1337cclean

Dans ce cas j'ajouterais volontier à nouveau une lazzy-method identique à celle que je mentionne [brouillonnement], mais cette fois-ci bornées sur les itérations "stagnantes"|"non stagnantes" ce qui revient à éviter une éventuelle étude d'une fonction ulp(x), par nature dépendante de la plateforme, ce que je cherche à éviter dans ma proposition. :aie:

---

Il reste à déterminer quand on considère qu'il y a stagnation...
C'est ce qui est fait dans les solveurs linéaire de Matlab... malheureusement.
C'est très critiqué.
En fait, tu connais rarement la solution exacte de ton problème, donc tu peux seulement vérifier si les résidus convergent/divergent/stagnent.
C'est d'ailleurs pour cela que l'analyse d'erreur vers l'arrière a été développée.
Le problème c'est que tes résidus peuvent (quasi)-stagner alors que l'erreur sur la solution continue bien de décroître.
Par ailleurs, à partir de combien d'itérations considère-t-on qu'il y a stagnation?
En croyant simplifier un problème, tu le complexifies.

Citation:

---

Envoyé par 1337cclean

:: Pour des calculs d'algèbre linéaire, matriciels, bien que les problèmes mentionnés soient les mêmes concernant la précision, la NASA (par exemple) utilise encore plutôt le FORTRAN que le C++, mais si on est sous gcc, à priori on change de langage mais pas la problèmatique lié à la-dites précision.
- intuitif -

---

C'est la norme (IEEE) qui détermine la manière dont sont représentés les nombres mais le langage intervient pour fournir les fonctions qui permettent d'identifier automatiquement la représentation (précision machine, limites pour l'underflow/l'overflow, etc).

[...]

Je complexifie sans complexe dans une étude (labo),
uniquement pour savoir ensuite où je puis simplifier,
notamment est-ce qu'il n'y aurait pas un paramètre extérieur
que je n'aurait pas considérer dans un algo qui "stagne",
soit un "non invariant" ? - disont que c'est l'une
des question que je me poserait alors, dans une situation
de recherche/étude.

Pour les bornes,
c'est le système lazzy qui me viendrait en premier à l'esprît.
Ensuite bien sûr il faut approfondir/changer/reprendre, etc.
- je ne fait plus de numérique depuis des siècles :aie: ... -

Je vois en effet que "L'analyse d’erreur vers l’arrière", admet un prix Turing décerné à James H.Wilkinson en 1970, en plus il avait eu la chance de travailler avec Turing Alan en personne, semble-t'il.

Je dois m'instruire sur le sujet :)

Pour IEEE, .... ben oui :)

Je ne suis pas tellement dépendant des catégories de langages en fait... Fonctionnels, Classes&Objets, Modulaires, Cobol, asm (argh! 2x), HP41CV (amusante :), pgm génétique, neuronale, DSP, symbolique, Prolog, Scheme, Logo (gag!), vieux L4G, etc.

:: Pour le moment je me cantonne à Java/C++ pour le "sérieux" et PHP (en shell) et SQL pour dépanner certaines situations... LOL: Le lambda calcul avec les chaines de PHP - gymnastes, ne pas s'abstenir de rire -...

Issont assez avare d'info chez wiki, à propos de cette "analyse d'erreur vers l'arrière" (retroaction) ...

aurait-il de la transformée en Z dans l'air ?

Merci à 1337cclean d'avoir relancé ce sujet.
On peut, et on doit l'étudier d'une façon théorique, mail il ne faut surtout pas oublier l'application pratique. Je vais essayer de le décrire sans m'appuyer sur un exemple précis.
Soit un alogorithme où on doit tester à un moment si telle résultat est "égal" à telle donnée. J'appelle "égal" la condition que la différence en valeur absolue est inférieure à epsilon. Le problème se ramène donc à calculer epsilon.
La notion de convergence dépend de l'algorithme mis en oeuvre et non pas de la perte de précision dû à la relation réel -> flottant. En effet la valeur limité d'arrêt doit être largement supérieure à la précision résultante.

On peut admettre que les erreurs dues aux opérations sur des réels avec des flottants sont des erreurs accidentelles, c'est à dire des erreurs avec une distribution aléatoire. Si ce n'était pas le cas, on pourrait quantifier ces erreurs, et/ou les corriger, par exemple, quand on lit un flottant arrondi à une certaine décimale, il est normal d'ajouter 0.5 à cette décimale, si on veut la transformer en entier sans perdre de précision.
La loi de composition des erreurs accidentelles indiquent que si la mesure résulte de n mesures élémentaires, l'erreur sur le résultat sera e . racine( n).
A noter que si on n'admet pas cette composition des erreurs accidentelles toute discussion à ce sujet est stérile.

Le problème est compliqué : quelle décision prendre au moment du test
1- soit la différence est inférieure à epsilon
a- on continue le calcul
b- on modifie la "valeur" pour la rendre "égale" à la donnée.
2- soit la différence est supérieure à epsilon, alors "Valeur" est différent de "donnée", et la suite des opérations est faite en conséquence.

Le cas 1a va donc conserver "valeur" en l'état et cette valeur va probablement être réutilisée dans d'autres calculs et on sera amené à refaire un test d'"égalité" comparable, avec composition des erreurs suivant le principe ci dessus.
Le cas 1b est intéressant, car "valeur" va maintenant est égal à "donnée" et ou continue avec une valeur de départ "juste". Mais ce n'est pas toujours applicable et cela peut même avoir des effets secondaires inattendus.

Mon avis personnel.
Dans le cas où ce problème peut être posé et décrit de façon précise, je crois que la meilleure méthode est de faire un bonne centaine de simulations avec de paramètres aléatoires et de noter et classer les écarts constatés, vérifier que leur répartition est conforme à celle de la loi de Gauss, et en déduire l'écart maximum.

Pas de quoi Pierre, en fait je suis là pour apprendre.

J'ajoute que ce qui se cachait derrière mes "approches" de problèmes numériques, et en particulier de représentation discrète, que la notion de "robustesse" m'avait été enseignée, notamment pour la programmation RT (real time), dans les années 80, et que les conditions fesaient que cette considération était encore clairement de mise.

Maintenant en mathématique, je ne suis que très jeune étudiant, mais comprends par mon parcours hybride que c'est assez rare qu'une seule porte soit à "essayer" pour étudier une structure abstraite qui peux se cacher derrière un système dynamique discrèt, et par définition de l'étude, je dois chercher (et certainement ouvrir plusieurs portes) pour en comprendre ce qui est sous-jacent.

La recherche du point fix en quelque sorte 8O

:: Ah ben y fait très plaisir ce forum pro. Les échanges y sont constructifs.

:ccool:

Citation:

---

Envoyé par 1337cclean

[...]
Je complexifie sans complexe dans une étude (labo),
uniquement pour savoir ensuite où je puis simplifier,
notamment est-ce qu'il n'y aurait pas un paramètre extérieur
que je n'aurait pas considérer dans un algo qui "stagne",
soit un "non invariant" ? - disont que c'est l'une
des question que je me poserait alors, dans une situation
de recherche/étude.

---

Pour reprendre l'exemple de GMRES, c'est un problème ouvert.
Il y a plusieurs papiers là-dessus (google->stagnation of gmres).
On ne sait même pas déterminer les paramètres qui influent sur sa convergence.
Beaucoup pensaient que les valeurs propres déterminaient le comportement du solveur mais il a été démontré que non en 1996 et depuis personne n'a réussi à produire un résultat concret sur le sujet (il y a bien la théorie des pseudospectres mais c'est très approximatif) :
http://citeseerx.ist.psu.edu/viewdoc...10.1.1.38.4540

Tu auras sûrement le problème dans bien d'autres cas.
De plus, les paramètres influents, pour peu que tu les détermines, peuvent être plus chers à calculer que ton problème initial.

Citation:

---

Envoyé par 1337cclean

Je vois en effet que "L'analyse d’erreur vers l’arrière", admet un prix Turing décerné à James H.Wilkinson en 1970, en plus il avait eu la chance de travailler avec Turing Alan en personne, semble-t'il.

---

Turing est le père fondateur de la notion de conditionnement (entre autres).
Wilikinson est le père fondateur de l'analyse d'erreur vers l'arrière.
De nos jours, on peut considérer Higham comme leur digne successeur mais beaucoup participent ou ont participé au développement de l'analyse numérique moderne (Bjorck, Reid, Golub entre autres).

Citation:

---

Envoyé par 1337cclean

Je dois m'instruire sur le sujet :)

---

Wilkinson : [ame="http://www.amazon.com/Algebraic-Eigenvalue-Mathematics-Scientific-Computation/dp/0198534183"]Amazon.com: The Algebraic Eigenvalue Problem (Numerical Mathematics and Scientific Computation) (9780198534181): the late J. H. Wilkinson: Books@@AMEPARAM@@http://ecx.images-amazon.com/images/I/410F4BFCFFL.@@AMEPARAM@@410F4BFCFFL[/ame]
Higham : [ame="http://www.amazon.com/Accuracy-Stability-Numerical-Algorithms-Nicholas/dp/0898715210"]Amazon.com: Accuracy and Stability of Numerical Algorithms (9780898715217): Nicholas J. Higham: Books@@AMEPARAM@@http://ecx.images-amazon.com/images/I/41XPQM3KKRL.@@AMEPARAM@@41XPQM3KKRL[/ame]

Le deuxième est plus facile d'accès.

Citation:

---

Envoyé par 1337cclean

aurait-il de la transformée en Z dans l'air ?

---

Pas nécessairement mais peut-être que cela intervient pour analyser certains algorithmes, je n'en sais rien. En général, c'est très algébrique. La partie "analyse" intervient plutôt à la fin quand on introduit une métrique pour mesurer l'erreur et faire des majorations.

Citation:

---

Envoyé par Aleph69

[...]

---

Merci beaucoup beaucoup pour ces références.
Cela me rassure de savoir que ce soit encore des problèmes ouverts.
- Donc certainement assez loin de ma portée du point de vue mathématiques -

Dans mes reprises d'études de ces dernières années, études que j'ai dû interrompre, mais que je n'abandonnent pas et me réoriente vers les mathématiques pures [y a du boulot!], je me souviens avoir eu toujours une sorte d'appréhension à l'étude de l'ALGEBRE LINEAIRE, en particulier par une sorte de dégoût infondé des calculs matriciels,

Mais c'est ALORS qu'un Professeurs anglais (es Mathematics), avait, après 6 mois de cours, commencer à nous parler de VALEUR PROPRE et c'est LÀ, que j'ai commencé à y voir un sens sérieusement intéressant, à ce cours d'ALG.LIN 8O , mon intuition avait allumé ENFIN un source de motivation concrète à ce cours particulier.

Du coup il me faudra reprendre, mais cette fois-ci en connaissance de cette motivation "vivante", l'étude complète de l'alg.lin. à l'époque je ne m'intéressait qu'à l'analyse et surtout à ses composantes "symbolique" justement.

Merci GRANDEMENT pour ces références que je notent et tacherais de les soumettre à mon libraire le plus proche. (Heu en général j'évite les achats sur internet, sauf "impasse".)

:ccool:

PS: Alan Turing, dont Appole lui aurait volé "la pomme" [...] est effectivement à l'origine du problème de l'arrêt, même si Chaitin (nombre omega, mathématicien au parcours aussi très hybride et contemporain) y aurait travaillé. Alan Turing, Knuth et Wirth, restent mes pères fondateurs en matière d'approche informatique de résolution/modèlisation de problèmes.

Petite application pratique
On veut calculer l'écart type, appelé aussi erreur moyenne quadratique.
Soit n mesures indépendantes d'une même chose et M la moyenne.
la formule de l'écart type au carré est
(Somme(xi²) - n . M²)/(n-1)
la formule de l'erreur moyenne quadratique au carré est
(Somme((xi - M)²)/(n-1)
pour x de 1 à n
Malgré l'apparence ces 2 formules sont mathématiquement identiques (sauf faute de frappe de ma part)
Dans le cas général le résultat (calculé en double) est différent, voire très différent. Il est vrai que j'ai un bon millier de valeurs.

De mémoire, la deuxième est bien connue pour être plus adaptée au calcul numérique.

Par exemple si vous consultez l'aide d'Excel ?:mouarf:

Citation:

---

Envoyé par Pierre Dolez

Par exemple si vous consultez l'aide d'Excel ?:mouarf:

---

Non, je crois que j'ai vu ca la premiere fois dans le manuel de mon HP-15C, celui qui a été écrit par http://www.cs.berkeley.edu/~wkahan. Que je râle de l'avoir perdu dans un déménagement celui-la.

Bonjour Jean-Marc,

s'agit-il de celui-ci?
http://hp15c.org/hp15c.pdf

A priori c'est plutôt celui-ci :
http://hp15c.org/hp15cAdvanced.pdf ;)

Citation:

---

Envoyé par Aleph69

Bonjour Jean-Marc,

s'agit-il de celui-ci?
http://hp15c.org/hp15c.pdf

---

Non. Il y a aussi un manuel "advanced" qui a toute une section sur l'analyse numerique qui a ete ecrite par Kahan. C'est de celui-la dont je parle. Ce fut ma premiere introduction a l'analyse numerique et mon regret a une bonne part de nostalgie. (Et je ne savais pas a l'epoque qui etait l'auteur). J'ai cherche une ou deux fois s'il etait disponible sur le web, je n'ai pas trouve.

Edit: cherchant a nouveau c'est ceci: http://hp15c.org/hp15cAdvanced.pdf (mais a lire la page des matieres, ce n'est pas la que j'ai lu pour la precision des formules de l'ecart type; et il doit y avoir plus d'un chapitre ou Kahan a eu la main).

Bonjour,
Pour en revenir au sujet très terre à terre de la précision des calculs en flottant (float ou double).

Citation:

---

la formule de l'écart type au carré est
(Somme(xi²) - n . M²)/(n-1)
la formule de l'erreur moyenne quadratique au carré est
(Somme((xi - M)²)/(n-1)
pour x de 1 à n

---

Dans l'exemple cité, le terme écart type est beaucoup plus connu et plus employé. La formule citée est celle que l'on trouve généralement (Excel - Wikipédia en particulier)
Par contre, sa formulation a le gros défaut de calculer la somme de carrés, pour deux listes de valeurs, puis de faire la différence
Mathématiquement, c'est la même chose, mais ici, il s'agit d'informatique, et ce n'est plus le même chose.
La question initiale était d'avoir une estimation de la précision espérée. Ma proposition (racine(n)) n'a apparemment pas plus à certains, y aurait-il d'autre(s) proposition(s).

Desole, je n'avais pas compris que tu cherchais une analyse detaillee. Je n'ai pas le temps de la faire -- et j'avoue que si j'en avais besoin je chercherais d'abord une reference adequate, c'est dans mes limites theoriques mais hors de la zone des choses routinieres et un risque d'erreur n'est pas negligeable.

Une reference peut-etre: http://www.johndcook.com/blog/2008/0...ard-deviation/
qui cite un troisieme algo, qui a l'avantage d'etre incremental comme la methode des carres (c'est pourquoi cette methode est utilisee par pas mal de calculatrice).

Bonjour Jean-Marc,
J'ai du mal m'exprimer.
Ce sujet de précision a été posé (pas par moi). Il se trouve que c'est la quatrième question quasiment identique depuis peu, et toutes ont été très animées, et certaines se sont même terminées par "donc j'ai raison".
Je ne cherche en aucun cas à envenimer quoi que ce soit, mais les FAQ sur ce sujet, bien que différentes (il y en a 3, je crois) disent toutes le même chose, ainsi que un document cité, mais malheureusement, je constate que l'on continue à tourner autour du pot.
Donc je répète mon affirmation (brutale mais claire) "En règle générale il ne faut pas tester l'égalité de 2 flottants, mais la comparaison de la valeur absolue de leur différence avec une constate petite."
Ce calcul d'erreur (écart type ou emq) n'est rien de plus qu'un (autre) exemple.
Ceci dit, d'après des expériences menées dans ce sens, cela me parait assez aléatoire de chercher à quantifier l'erreur maximum, dans la mesure où la valeur de cette erreur maximum aurait une importance pour le traitement.

Citation:

---

Envoyé par Pierre Dolez

Donc je répète mon affirmation (brutale mais claire) "En règle générale il ne faut pas tester l'égalité de 2 flottants, mais la comparaison de la valeur absolue de leur différence avec une constate petite."

---

Et moi je continue a affirmer que ce genre de choses simples simplifient a chaque fois un peut trop le probleme. Quelques points:
- la plupart des gens comprenne le "en general" par "jamais", ce qui change beaucoup de choses;
- entre comparer la difference a un seuil ou comparer la difference relative a un seuil (ce que propose la FAQ), je ne suis pas sur qu'il y ait une regle generale. Le cas ou le c'est la différence relative qu'il faut me semble plus fréquent.
- la détermination même du seuil n'est pas simple.
- une comparaison d'intervalle comme ca implique de ne pas avoir besoin de la transitivité. Et j'affirme que la plupart des gens lisant une telle regle simple ne vont pas s'en rendre compte et supposer dans leur algo que la transitivite tient (rentrer des choses dans un tableau associatif...).
- je dois en passer.

Et quand on cherche a raffiner la regle, quand on cherche a en expliquer le pourquoi pour inciter a reflechir au probleme plutot qu'a appliquer une regle simplifiee en dehors de son domaine de validite, on rentre dans les maths. Et ca passe mal. Desole, mais l'analyse numerique, c'est un champs des mathematiques. Et on ne va pas couvrir suffisemment le champs en 3 questions dans une faq ou un petit tutorial sans equations.

Je vais tout de même répondre, mais ..
- "En général" cela veut dire "Jamais" sauf si on a une bonne raison.
- Je vous ferais remarquer que je n'ai donné aucune indication ni aucune précision sur ce que j'ai appelé une "constante petite". Mais je pense cependant que les cas d'utilisation légitime d'erreur relative sont rares, en tout cas, bien que j'imagine que ce soit possible, je n'ai jamais rencontré ce cas là dans mon domaine d'application. D'ailleurs, en y réfléchissant bien, ce principe me semble assez difficile à justifier. En effet, on cherche à comparer une valeur dont la précision dépend du traitement informatique (mantisse et caractéristique), alors qu'une valeur relative ne dépend que de la chose étudiée. Je crois qu'on est entrain de mélanger ce problème de précision des flottants avec la précision d'un calcul par convergence.
-Vous

Citation:

---

la détermination même du seuil n'est pas simple

---

Moi (dans la précédente réponse)

Citation:

---

cela me parait assez aléatoire de chercher à quantifier l'erreur maximum

---

:mouarf:
- Je pense avoir évoqué le problème de la transitivité de façon suffisamment précise et détaillée.

Alors, que faut-il dire, et surtout ne pas dire?
(Réponse souhaitée)

Je peux vous donner un lien sur des choses invraisemblables qui ont été dites sur ce forum, mais seulement en privé.
Sauf erreur de ma part, il y 3 articles de FAQ. Je crois que l'un d'eux est de vous, Avez-vous lu les deux autres?

Citation:

---

Envoyé par Pierre Dolez

- Je pense avoir évoqué le problème de la transitivité de façon suffisamment précise et détaillée.

---

Je n'en ai pas le souvenir. Une référence?

Citation:

---

Alors, que faut-il dire, et surtout ne pas dire?

---

A qui? Dans quel contexte? Avec combien de temps?

Plusieurs fois, j'ai tenté de rédiger un document reprenant ce qu'il me semblait nécessaire de connaître sur les flottants, jamais je ne suis arrivé à quelque chose qui me convenait, jamais je n'ai pu éviter et le Charybde des explications trop exhaustives qui seront abandonnées ou incomprises et le Scylla des simplifications laissant quelque chose d'important de côté.

Citation:

---

Sauf erreur de ma part, il y 3 articles de FAQ. Je crois que l'un d'eux est de vous, Avez-vous lu les deux autres?

---

Il y a quelques entrées dans la FAQ qui me donnent comme co-auteur. La raison en est vraisemblablement que le rédacteur s'est inspiré plus ou moins fortement d'une réponse ou l'autre que j'ai pu commettre et n'a pas voulu s'attribuer tout le mérite. Je n'en ai relu aucune avant publication. Mais je n'ai jamais non plus prétendu que mon style naturel s'accorde avec une FAQ, les entrées y sont par nature trop simplificatrices à mon goût. Je peut être laconique, mais dans des contextes plus conversationnel. Simplifier est un talent que je n'ai pas, malheureusement je n'ai pas encore vu de tentative convaincante en ce qui concerne les flottants; la plus réussie est encore un lien donné par Joel F il y a quelque temps.

Pour revenir aux entrées sur les flottants, http://cpp.developpez.com/faq/cpp/?p...ions_flottants ne me doit vraisemblablement guère que la formule dans le if qu'il me semble avoir donné en tant que tentative de correction à un message essayant d'utiliser numeric_limit<>::epsilon de manière assez inconsidérée.
Quand aux deux autres entrées, elles ne m'ont pas sauté aux yeux lors d'un survol de la table de matière.

Problème de transitivité, quelques messages plus haut.

Citation:

---

Le problème est compliqué : quelle décision prendre au moment du test
1- soit la différence est inférieure à epsilon
a- on continue le calcul
b- on modifie la "valeur" pour la rendre "égale" à la donnée.
2- soit la différence est supérieure à epsilon, alors "Valeur" est différent de "donnée", et la suite des opérations est faite en conséquence.

Le cas 1a va donc conserver "valeur" en l'état et cette valeur va probablement être réutilisée dans d'autres calculs et on sera amené à refaire un test d'"égalité" comparable, avec composition des erreurs suivant le principe ci dessus.
Le cas 1b est intéressant, car "valeur" va maintenant est égal à "donnée" et ou continue avec une valeur de départ "juste". Mais ce n'est pas toujours applicable et cela peut même avoir des effets secondaires inattendus.

---

Citation:

---

Alors, que faut-il dire, et surtout ne pas dire?
A qui? Dans quel contexte? Avec combien de temps?

---

- A ceux qui utilisent des flottants
- tous, quelque soit le contexte, un flottant sera toujours un flottant, c'est à dire la représentation d'une valeur d'un ensemble infini (non dénombrable) par une valeur d'un ensemble dénombrable.
- pas la peine de faire des km de message, réponses, se faire traiter de Candide etc.
Si la question devient plus précise, du genre comment et à partir de quoi fixer les epsilon, moi, je dirai que je ne sais pas.

Je vais conclure comme j'ai conclu un sujet identique :
Je transforme mes valeurs flottant en long int, je gagne environ deux chiffres en précision (ce qui correspond à la caractéristique). J'ai une unité de base qui est donc la dernière décimale des flottants et donc l'unité des long int. Ma tolérance est généralement 3 unités de base.
Etant donné le nombre considérable de calculs et comparaisons fait avec cette méthode, je peux la conseiller sans risque.

Petit rajout indispensable :

Citation:

---

A priori, en double, ta précision doit être à peu près égale 2,2E-16 si ta machine est standard, respecte la norme IEEE, et si j'ai bonne mémoire! ^^

---

Cela n'a aucun sens en informatique. Ce qu'il fallait répondre
En double, l'intervalle va de 1.7 E-308 à 1.7 E308
La précision est de 15 chiffres significatifs.
Il est indispensable de comprendre qu'un flottant en informatique n'est pas un réel,mais un nombre composé d'une caractéristique et d'une mantisse. C'est la longueur de la mantisse qui caractérise la précision, c'est à dire le nombre de chiffres significatifs, la caractéristique est comparable à l'unité dans laquelle on travaille.