Ce texte est une traduction automatique ; la version originale 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 directement le rapport : 0,000405 pour h = 0,2, et 0,000234 pour la moitié de ce pas. Divisez ces deux valeurs et vous obtenez 1,73, non 2, sans que rien ne soit défaillant.
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 ; diviser h par deux devrait donc diviser l'erreur par deux.
Ouvrez Euler's method avec ses paramètres par défaut : y′ = x − y, y(0) = 1, quarante pas avec h = 0,2, pour aboutir à x = 8. La page indique une erreur globale de 0,000405, puis fait preuve d'une honnêteté inhabituelle : elle recalcule l'ensemble avec h/2 et affiche également cette erreur, 0,000234, ainsi que le rapport entre les deux :
Eh / Eh/2 = 0,000405 / 0,000234 = 1,731285
Pas 2. La méthode est du premier ordre, le calcul arithmétique est exact, et diviser le pas par deux n'a apporté qu'une réduction de 42 % au lieu de 50 %.
Balayer plutôt qu'échantillonner
Deux valeurs ne peuvent donner qu'une tendance ; calculons donc le rapport sur tout l'intervalle, en maintenant l'extrémité fixée à x = 8 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 de l'écart : de combien chaque mesure se situe en dessous de 2 :
0,524 → 0,269 → 0,134 → 0,067 → 0,033
Cet écart est divisé par deux chaque fois que h est divisé par deux. La différence entre le « premier ordre » et ce que le premier ordre fournit réellement est elle-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 néglige tout ce qui suit à partir de la dérivée seconde, ce que le Taylor tool met en évidence : les termes écartés comportent h², h³, etc. Un pas perd ainsi une quantité d'ordre h², et en faire jusqu'à x = 8 en demande 8/h ; ainsi, h² par pas devient h dans l'erreur totale. Le mot « premier » dans premier ordre qualifie donc déjà une somme.
L'erreur globale n'est donc pas C·h. Elle s'écrit
E(h) = C₁h + C₂h² + C₃h³ + ⋯
et le rapport de deux telles sommes vaut
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 vite que le terme en h. Mais pour tout h non nul, le deuxième terme subsiste et contribue au dénominateur de manière plus que proportionnelle. Le terme « premier ordre » désigne le terme qui subsiste le plus longtemps, et non l'unique terme en présence. Pour h = 0,4, la contribution en h² absorbe un quart du facteur deux promis, et le rapport s'établit à 1,476.
On constate la même chose dans la colonne des erreurs du tableau des pas sur la page. L'erreur cumulée ne progresse pas de manière régulière : elle monte jusqu'à environ 0,0804 à x = 0,8, puis diminue lorsque la solution s'aplanit, pour finir au 0,000405 mentionné dans le récapitulatif. L'erreur globale est la somme d'erreurs locales qui se compensent en partie, et cette somme n'a aucune raison d'être un multiple exact de h pour un pas utilisé en pratique.
Pourquoi cela importe, et ce n'est pas de la pédanterie
La méthode usuelle pour estimer une erreur impossible à calculer est l'extrapolation de Richardson, qui fonctionne en postulant ce rapport. On effectue le calcul avec un pas h, puis avec un pas 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 calcul le plus fin. Pour 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 est de 1,476. Faites le calcul : l'estimation obtenue représente 0,476 de l'erreur réellement restante, la sous-estimant ainsi d'un facteur d'environ deux — et elle la sous-estime au lieu de la surestimer. Vous croirez le résultat meilleur qu'il ne l'est, et cette confiance sera d'autant plus grande que le pas est grossier, ce qui est précisément le moment où l'on en a le moins besoin.
La parade est celle que montre la page : ne présumez pas du rapport, mesurez-le. Deux calculs vous donnent le rapport ; trois vous donnent son évolution. Si le rapport n'est pas proche de 2p pour le p escompté, c'est soit que le pas est trop grand pour le régime asymptotique, soit que la méthode n'est pas de l'ordre attendu, soit que la solution présente une particularité que l'analyse n'avait pas prévue. Dans les trois cas, il vaut mieux le savoir avant d'avancer un chiffre.
Ce qui plaide pour une meilleure méthode, et non pour un pas plus petit
Diviser le pas par deux double le volume de calcul. Pour une méthode du premier ordre, cela finit par faire gagner un facteur deux, avec le temps. Le compromis est médiocre, et c'est pourquoi presque aucun code 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 ; le même doublement du travail procure donc huit fois plus de précision que le doublement chez Euler. Les méthodes de Runge et Kutta réalisent l'équivalent pour les équations différentielles, et l'historique de Butcher cité en référence fait remonter cette lignée à Runge en 1895 et à Kutta en 1901.
L'idée générale mérite d'être retenue : pour une méthode d'ordre p, le gain est d'un facteur 2p en précision pour chaque doublement de l'effort, et p est une propriété de l'algorithme plutôt que du problème. Le choix de la méthode fixe ce taux de rendement. Le choix du pas ne fait que déplacer le curseur le long de cette relation, et comme le montre le balayage ci-dessus, il ne le fait même pas au rythme promis tant que h n'est pas devenu suffisamment petit pour que la promesse soit tenue.