Ce document est une traduction automatique ; le texte original est en anglais. Lire l'original
Diviser le pas par deux devrait diviser l'erreur par deux. L'outil indique 1,73.
La page affiche le rapport lui-même : 0,000405 pour h = 0,2, et 0,000234 pour la moitié de cette valeur. Divisez-les et vous obtenez 1,73, et non 2, et rien n'est cassé.
La méthode d'Euler est du premier ordre. Tous les manuels l'affirment, et cela signifie que l'erreur est proportionnelle au pas h — ainsi, diviser h par deux devrait diviser l'erreur par deux.
Ouvrez Euler's method avec ses réglages par défaut : y′ = x − y, y(0) = 1, quarante pas de h = 0,2, pour finir à x = 8. La page indique une erreur globale de 0,000405, puis fait quelque chose d'inhabituellement honnête — elle réexécute l'ensemble avec h/2 et affiche également cette erreur, 0,000234, ainsi que leur rapport :
Eh / Eh/2 = 0,000405 / 0,000234 = 1,731285
Et non 2. La méthode est du premier ordre, l'arithmétique est exacte, et diviser le pas par deux a apporté une réduction de 42 % plutôt que de 50 %.
Faites un balayage, ne vous contentez pas d'échantillonner
Deux nombres ne peuvent donner qu'une tendance ; calculez donc le rapport sur toute la plage, en maintaining le point final fixe à x = 8 et en doublant le nombre de pas chaque fois que h est divisé par deux :
- h = 0,4 → rapport 1,475764
- h = 0,2 → rapport 1,731285
- h = 0,1 → rapport 1,865689
- h = 0,05 → rapport 1,933036
- h = 0,025 → rapport 1,966586
Le 2 promis est une limite, et voici à quoi ressemble la convergence vers celle-ci. Mais la colonne la plus intéressante n'est pas celle du rapport, c'est celle du déficit — à savoir l'écart qui sépare chaque mesure de 2 :
0,524 → 0,269 → 0,134 → 0,067 → 0,033
Celui-ci diminue de moitié chaque fois que h est divisé par deux. L'écart entre le « premier ordre » et ce que le premier ordre produit réellement est lui-même du premier ordre en h.
D'où vient la moitié manquante
L'ordre provient d'une troncature. Euler conserve le premier terme du développement de Taylor de la solution et élimine tout à partir de la dérivée seconde, ce que Taylor tool rend visible : les termes ignorés comportent des puissances h², h³ et ainsi de suite.
Ainsi, l'erreur globale n'est pas C·h. Elle vaut
E(h) = C₁h + C₂h² + C₃h³ + ⋯
et le rapport de deux sommes de ce type est
E(h) / E(h/2) = (C₁h + C₂h² + ⋯) / (C₁h/2 + C₂h²/4 + ⋯)
ce qui tend vers 2 lorsque h diminue et que le terme en h² décroît plus rapidement que le terme en h — mais pour tout h fini, le second terme est toujours présent et contribue au dénominateur de façon plus que proportionnelle. Le « premier ordre » désigne le terme qui subsiste le plus longtemps, non l'unique terme présent. Pour h = 0,4, la contribution en h² est suffisamment importante pour absorber un quart de l'amélioration attendue.
On peut observer le même phénomène dans la colonne des erreurs du tableau des pas sur la page. Les erreurs locales à chaque pas ne s'accumulent pas de manière régulière : elles grimpent jusqu'à environ 0,0804 pour x = 0,8, puis diminuent à mesure que la solution s'aplanit. L'erreur globale est la somme d'erreurs locales qui se compensent partiellement, et cette somme n'a aucune raison d'être un multiple exact de h pour une taille de pas utilisable en pratique.
Pourquoi ce point importe, et ce n'est pas du pédantisme
La méthode usuelle pour estimer une erreur que l'on ne peut pas calculer est l'extrapolation de Richardson, et elle fonctionne en supposant connu ce rapport. Effectuez un calcul avec h, puis avec h/2 : si la méthode est d'ordre p, la différence entre les deux résultats vaut environ (2p − 1) fois l'erreur du pas le plus fin. Pour la méthode d'Euler, p = 1, la différence est donc à peu près égale à l'erreur restante.
Appliquez ce raisonnement avec h = 0,4, et vous aurez supposé un rapport de 2 là où le rapport réel vaut 1,476. Faites le calcul : l'estimation obtenue vaut 0,476 de l'erreur réellement restante, ce qui la sous-estime d'un facteur d'environ deux — et, c'est là le point crucial, elle la sous-estime au lieu de la surestimer. Vous penserez que le résultat est meilleur qu'il ne l'est en réalité, et cette confiance sera d'autant plus forte que le pas est grossier, soit précisément quand cela est le moins souhaitable.
La parade est celle que montre la page : ne supposez pas le rapport, mesurez-le. Deux exécutions vous donnent le rapport ; trois vous donnent la tendance de ce rapport. Si le rapport n'est pas proche de 2p pour la valeur de p escomptée, alors soit le pas est trop grossier pour le régime asymptotique, soit la méthode n'est pas de l'ordre imaginé, soit la solution présente une caractéristique que l'analyse n'avait pas anticipée. Dans les trois cas, il vaut mieux le savoir avant d'avancer un résultat numérique.
Ce qui plaide pour une meilleure méthode, et non pour un pas plus petit
Diviser le pas par deux double le travail. Pour une méthode du premier ordre, cela permet d'obtenir, à terme, un facteur deux d'amélioration. C'est un échange peu avantageux, et c'est pourquoi pratiquement aucun logiciel en production n'intègre avec Euler.
Simpson's rule est du quatrième ordre : diviser son pas par deux divise l'erreur par environ 16, de sorte que le même doublage d'effort apporte huit fois plus de précision que le doublage pour Euler. Les méthodes de Runge et Kutta font l'équivalent pour les équations différentielles, et l'historique rétrospectif de Butcher cité en référence montre à quel point les praticiens ont rapidement délaissé le premier ordre dès qu'une alternative a été disponible.
L'idée générale est à retenir : pour une méthode d'ordre p, le gain est de 2p en précision pour chaque doublage de l'effort, et p est une propriété de l'algorithme plutôt que du problème. Choisir la méthode fixe ce rapport. Choisir la taille du pas ne fait que vous déplacer le long de ce rapport — et, comme le montre le balayage ci-dessus, il ne le fait même pas au rythme annoncé tant que h n'est pas suffisamment petit pour que l'annonce soit devenue vraie.