Le meilleur algorithme pour éviter la perte de précision?

Question

Un devoir que j'ai reçu récemment nous demande de prendre des expressions qui pourraient créer une perte de précision une fois exécutées dans l'ordinateur, et de les modifier de manière à éviter cette perte.

Malheureusement, les instructions pour le faire n'ont pas été très claires. En observant divers exemples en cours, je sais qu’il existe certaines méthodes pour cela: utiliser la série de Taylor, utiliser des conjugués si des racines carrées sont impliquées, ou trouver un dénominateur commun lorsque deux fractions sont soustraites.

Cependant, je ne parviens pas à remarquer le moment exact où la perte de précision va se produire. Pour l’instant, la seule chose dont je suis certain, c’est que lorsque vous soustrayez deux nombres qui sont presque identiques, il se produit une perte de précision car les chiffres les plus élevés sont importants et vous perdez ceux de l’arrondi.

Ma question est la suivante: quelles autres situations courantes devrais-je rechercher et quelles sont les bonnes méthodes pour les aborder?

Par exemple, voici un problème:

f(x) = tan(x) − sin(x)  when x ~ 0

Quel est le meilleur et le pire algorithme pour évaluer cela parmi ces trois choix:

(a) (1/ cos(x) − 1) sin(x),
(b) (x^3)/2
(c) tan(x)*(sin(x)^2)/(cos(x) + 1).

Je comprends que lorsque x est proche de zéro, tan (x) et sin (x) sont presque identiques. Je ne comprends pas comment ni pourquoi aucun de ces algorithmes est meilleur ou pire pour résoudre le problème.

Answer 1

Une autre règle empirique habituellement utilisée est la suivante: lors de l’ajout d’une longue série de nombres, commencez par ajouter des nombres proches de zéro et terminez par les plus grands nombres.

Expliquer pourquoi c'est bon est un peu compliqué. Lorsque vous ajoutez des petits nombres à des nombres élevés, il est possible qu'ils soient complètement ignorés car ils sont plus petits que le chiffre le plus bas dans la mantisse actuelle d'un grand nombre. prenons par exemple cette situation:

a = 1,000,000;
do 100,000,000 time:
   a += 0.01;

si 0.01 est inférieur au chiffre de mantisse le plus bas, la boucle ne fait rien et le résultat final est a = 1 000 000 mais si vous faites ceci comme ceci:

a = 0;
do 100,000,000 time:
   a += 0.01;
a += 1,000,000;

Plus le nombre bas augmente lentement et plus il est probable que vous obtiendrez un résultat proche de 2 000 000 ==, ce qui est la bonne réponse.
C’est bien sûr un exemple extrême, mais j’espère que vous aurez l’idée.

Answer 2

Je devais suivre un cours de calcul quand j'étais étudiant de premier cycle et c'était très douloureux. Quoi qu'il en soit, IEEE 754 est la norme en virgule flottante généralement mise en œuvre par les processeurs modernes. Il est utile de comprendre les bases, car cela vous donne beaucoup d’intuition sur ce qu’il ne faut pas faire. L'explication simplifiée de cela est que les ordinateurs stockent des nombres à virgule flottante dans quelque chose comme la notation scientifique en base 2 avec un nombre fixe de chiffres (bits) pour l'exposant et pour la mantisse. Cela signifie que plus la valeur absolue d'un nombre est grande, moins il peut être représenté avec précision. Pour les flottants 32 bits dans IEEE 754, la moitié des modèles de bits possibles représentent entre -1 et 1, même si des nombres allant jusqu'à environ 10 ^ 38 sont représentables avec un flottant 32 bits. Pour des valeurs supérieures à 2 ^ 24 (environ 16,7 millions), un float de 32 bits ne peut pas représenter tous les entiers avec exactitude.

Cela signifie pour vous que vous souhaitez généralement éviter les problèmes suivants:

1. Les valeurs intermédiaires doivent être grandes lorsque la réponse finale doit être petite.

2. Ajouter / soustraire de petits nombres en grands nombres. Par exemple, si vous avez écrit quelque chose comme:

   pour (float index = 17000000; index < 17000001; index ++) {}

Cette boucle ne se terminerait jamais car 17 000 000 + 1 sont arrondis à 17 000 000. Si vous aviez quelque chose comme:

float foo = 10000000 - 10000000.0001

La valeur de foo serait 0, et non -0,0001, en raison d'une erreur d'arrondi.

Answer 3

  

Ma question est: quels sont les autres   situations courantes que je devrais regarder   pour, et ce qui est considéré comme «bon»   méthodes pour les approcher?

Vous pouvez subir une perte de précision grave, voire catastrophique de plusieurs façons.

La raison principale est que les nombres à virgule flottante ont un nombre limité de chiffres, par exemple, les doubles ont 53 bits. Cela signifie que si vous avez & "Inutile" & "; les chiffres qui ne font pas partie de la solution mais qui doivent être stockés, vous perdez en précision.

Par exemple (nous utilisons des types décimaux pour la démonstration):

2.598765000000000000000000000100 -

2.598765000000000000000000000099

La partie intéressante est la réponse 100-99 = 1. Comme 2.598765 est égal dans les deux cas, il ne modifie pas le résultat, mais perd 8 chiffres. Bien pire, parce que l'ordinateur ne fonctionne pas sachez que les chiffres ne servent à rien, il est obligé de les stocker et bourre 21 zéros après, gaspillage à tous les 29 chiffres. Malheureusement, il n'y a aucun moyen de le contourner pour des différences, mais il y a d'autres cas, par exemple exp (x) -1 qui est une fonction très fréquente en physique.

La fonction exp près de 0 est presque linéaire, mais elle impose un 1 comme chiffre principal. Donc avec 12 chiffres significatifs exp (0.001) -1 = 1.00100050017 - 1 = 1.00050017e-3

Si nous utilisons à la place une fonction expm1 (), utilisons la série taylor:

1 + x + x ^ 2/2 + x ^ 3/6 ... -1 =

x + x ^ 2/2 + x ^ 3/6 =: expm1 (x)

expm1 (0.001) = 1,00500166667e-3

Bien mieux.

Le deuxième problème concerne les fonctions avec une pente très raide, telle que la tangente de x près de pi / 2. tan (11) a une pente de 50000 ce qui signifie que tout petit écart causé par des erreurs d’arrondi avant sera amplifié par le facteur 50000! Ou vous avez des singularités si par exemple le résultat approche 0/0, cela signifie qu'il peut avoir n'importe quelle valeur.

Dans les deux cas, vous créez une fonction de substitution, simplifiant la fonction d'origine. Il est inutile de mettre en évidence les différentes solutions possibles, car sans formation, vous ne serez tout simplement pas & "Voir &"; le problème en premier lieu.

Un très bon livre à apprendre et à former: Forman S. Acton: l'informatique réelle devient réalité

Answer 4

Une autre chose à éviter consiste à soustraire des nombres presque égaux, car cela peut également accroître la sensibilité à l'erreur d'arrondi. Pour les valeurs proches de 0, cos (x) sera proche de 1, donc 1 / cos (x) - 1 est l'une de ces soustractions que vous souhaitez éviter si possible, je dirais donc que (a) doit être évité. .