Java estimer une dérivée à un point

Question

Je suis en train d'écrire une application de calculatrice. J'essaie d'écrire un estimateur dérivé. La formule ci-dessous est un moyen simple de le faire. Normalement, sur le papier, vous utiliseriez le plus petit h possible pour obtenir l'estimation la plus précise possible. Le problème est que les doubles ne peuvent pas gérer l'ajout de nombres vraiment petits à des nombres comparativement énormes. Tels que 4 + 1E-200 se traduira juste en 4.0. Même si h était juste 1E-16, 4 + 1E16 vous donnera la bonne valeur mais en maths, c'est inexact car tout ce qui se passe après la 16ème place est perdu et l'arrondi ne peut pas se faire correctement. J'ai entendu la règle générale pour les doubles est 1E-8 ou 1E-7. Le problème avec ceci est que les grands nombres ne fonctionneront pas comme 2E231 + 1E-8 sera juste 2E23, le 1E-8 sera perdu en raison des problèmes de taille.

f'(x)=(f(x+h)-f(x))/h as x approaches 0

Lorsque je test f (x) = x^2 au point 4 si f '(4), il doit être exactement 8 Je comprends maintenant que je vais probablement jamais obtenir exactement 8. mais Je le plus précis semble être autour de 1E-7 ou 1E8 la chose drôle est 1E-9 tous les à 1E-11 donnent la même réponse. Voici une liste des h de et les résultats pour f(x)=x^2 at x=4

1E-7 8.000000129015916 
1E-8 7.999999951380232 
1E-9 8.000000661922968 
1E-10 8.000000661922968 
1E-11 8.000000661922968 
1E-12 8.000711204658728 

Voici mes questions:

1. Quelle est la meilleure façon de choisir h, de toute évidence faire sens 1E-8 ou 1E-7, mais comment Puis-je choisir un h basé sur x, de sorte qu'il fonctionnera avec n'importe quel nombre de taille même si x est 3.14E203 ou 2E-231.
2. Combien de décimales de précision devrais-je prendre en compte? Avez-vous une idée de la façon dont Texas Instruments le fait, la TI 83, 84, et Inspire peuvent numériquement comprendre des dérivées à 12 décimales ou précision et presque toujours avoir raison, mais la précision maximale de leurs nombres est de 12 chiffres de toute façon ces calculateurs ne sont pas CAS, donc ils ne dérivent pas réellement
3. Logiquement, il y a un nombre entre 1E-7 et 1E-8 qui me donnera un résultat plus précis, y a-t-il un moyen de trouver ce nombre, ou à au moins s'approcher de lui.

RÉPONDU

Merci beaucoup BobG. L'application est actuellement prévue pour être sous 2 formes, une application PC en ligne de commande. Et une application Android. Vous serez mentionné dans les remerciements spéciaux à des parties de la page À propos de. Si vous souhaitez que ce soit open source, je ne publie pas de liens vers le site du projet tant que je n'ai pas trouvé de très gros bugs. En ce moment je l'ai appelé Mathulator, mais le nom changera probablement parce qu'il y a déjà un copyright dessus et cela semble stupide. Je n'ai aucune idée quand le candidat de release courra, au moment où je n'ai aucune idée quand il sera stable. Mais ce sera très puissant si je peux mettre en œuvre tout ce que je veux aussi. Merci encore. Bonne programmation.

Answer 1

Il y a un livre qui répond à cette question (et d'autres comme lui):

Recettes numériques en C, 2e édition, par la presse, Vetterling, Teukolsky et Flannery. Ce livre est également disponible en versions C++, Fortran et BASIC. Malheureusement, aucune version Java n'existe. De plus, je crois que ce livre est épuisé, mais il est possible d'acheter des versions de certaines saveurs en ligne (au moins via bn.com.)

Section 5.7, «Dérivés numériques», p. 186 explique exactement le problème que vous rencontrez avec les dérivées numériques et la mathématique qui explique pourquoi cela se produit, ainsi qu'une fonction permettant de calculer correctement une dérivée numérique (en C, mais il devrait être facile de la traduire en Java). Un résumé de leur approximation simple est présentée ici:

1) Numériquement, vous êtes mieux calculer la version symétrique:

f '(x) = (f (x + h) - f (x - h))/2h

2) h doit être d'environ (sigma_f)^(1/3) * x_c

où

sigma_f = ~ précision fractionnaire du calcul de f (x) pour fonctions simples

x_c = ~ x, sauf si x est égal à zéro. Cependant, ceci n'aboutit pas à des dérivées optimales, car l'erreur est ~ (sigma_f)^(2/3). Une meilleure solution est l'algorithme de Ridders, qui est présenté comme le programme C dans le livre (Ridders, CJF 1982, Advances in Engineering Software, volume 4, n ° 2, pp 75-76.)

Answer 2

Lisez le document intitulé «Ce que tout programmeur devrait savoir à propos des virgules flottantes» (google for it). Ensuite, vous verrez que la plupart des valeurs flottantes sont représentées approximativement dans le matériel informatique.

Pour effectuer des calculs sans cet inconvénient, utilisez le calcul symbolique. Mais ce n'est pas aussi efficace que l'utilisation de virgule flottante. Pour obtenir des résultats à virgule flottante cohérents, utilisez un arrondi à la puissance la plus proche de 10, par exemple 0,1, 0,01, etc. Pour savoir quand arrêter les approximations, utilisez une sorte de seuil à surveiller pendant les étapes d'approximation. Par exemple, si la prochaine étape d'approximation ne donne que des résultats.001% de changement à la valeur déjà calculée, il n'y a pas de sens de continuer les approximations.

Mise à jour j'avais mes cours de calcul numérique il y a longtemps, mais je me souviens vaguement que retranchant nombres proches est très mauvais, parce que si le nombre est très proche, les chiffres les plus fiables sont annulés et vous avez des chiffres peu fiables. C'est exactement ce qui arrive quand vous diminuez h. Ce qui est suggéré dans ces situations est la soustraction de substitution avec d'autres opérations. Par exemple, vous pouvez passer à une sorte de série à laquelle votre `f (x) se développe.

Je ne comprends pas très bien votre 2ème question, car la réponse dépend de vos besoins - "autant que vous le souhaitez". En passant, vous pourriez avoir plus de chance de trouver des réponses à vos questions sur math.stackexchange.com.

De plus, un lien de visite fourni par thrashgod: Numerical differentiation

Answer 3

J'utilise BigDecimal classe pour ce genre de calculs, mais il ne constitue pas une réponse à vos questions, mais il va vraiment améliorer la précision des arithmétique en virgule flottante.

Answer 4

1 La précision des nombres à virgule flottante (flottants et doubles) dépend de la valeur absolue du nombre. Les doubles ont ~ 15 chiffres de précision, donc vous pouvez ajouter 1 + 1e-15, mais 10 + 1e-15 sera probablement encore 10, donc vous devrez faire 10 + 1e-14. Pour obtenir un résultat significatif, je vous recommande de multiplier ce 1e-8 par la valeur absolue du nombre original, cela vous donnera environ 7 chiffres corrects dans la dérivée.Quelque chose comme:

double h = x * 1e-8; 
double derivative = (f(x+h) - f(x))/h; 

Quoi qu'il en soit c'est une approximation, par exemple, si vous essayez de calculer la dérivée de sin (x) x = 1e9, vous obtiendrez h = 10 et le résultat sera tout faux. Mais pour les fonctions "régulières" qui ont la partie "intéressante" proche de zéro, cela fonctionnera bien.

2. Moins "h" est important, plus le point d'échantillonnage de la dérivée est précis, mais moins vous obtenez de chiffres corrects. Je ne peux pas le prouver mais mon intuition est qu'avec h = x * 1e-8 vous obtenez 7 = 15 - 8 chiffres corrects où 15 est la précision double.

En outre, ce serait une bonne idée d'utiliser un « plus symétrique » formule, il donne une réponse tout à fait correcte sur polynômes du second ordre:

double derivative = (f(x+h) - f(x-h))/(2*h); 

Answer 5

Selon le Javadoc, 11 bits représentent l'exposant et 52 bits représentent les chiffres significatifs. Sans tenir compte de l'exposant, il semble que vous ayez 52 bits à jouer. Donc, si vous choisissez h = x * 2^-40, vous avez utilisé 40 bits ici, et la précision que vous allez voir est 2^-12. Ajustez ce rapport à vos besoins.

Answer 6

Ma question est ce qui est le plus approprié h, et comment peut-il être mis à l'échelle à toutes les tailles.

Comme indiqué dans Numerical Differentiation, un choix approprié pour h est sqrt (ɛ) * x, où ɛ est le machine epsilon.