Certains livres plus anciens que j'ai vus disent que le nombre minimum d'étapes d'une méthode Runge-Kutta explicite d'un ordre spécifié est inconnu pour les ordres . Est-ce toujours vrai?$\geq 9$

Quelles bibliothèques existe-t-il pour travailler automatiquement avec des méthodes Runge-Kutta d'ordre élevé?

Bornes

C'est toujours vrai. Dans le livre de Butcher , page 196, il dit ce qui suit: Dans un article de 1985, Butcher a montré que vous avez besoin de 11 étapes pour obtenir la commande 8 , et c'est net. Pour la commande 10, Hairer a dérivé une famille de méthodes en 17 étapes , mais on ne sait pas si l'on peut faire mieux. La même information est donnée dans la section II.5 de Hairer, Norsett et Wanner vol. Je . Cette dernière référence passe également en revue certaines des techniques de développement de paires d'ordre élevé (jusqu'à l'ordre 8).

Il y a une limite supérieure sur le nombre minimum d'étapes requises pour toute commande, car vous pouvez les construire par extrapolation. Cela est connu depuis très longtemps; voir mon récent article pour une explication. Cependant, cette borne est quadratique dans l'ordre et est certainement assez pessimiste. Le logiciel nodepy décrit ci-dessous peut générer des coefficients exacts pour ces méthodes, ainsi que pour les méthodes de correction différée (qui sont des méthodes de Runge-Kutta) de n'importe quel ordre.

Je crois qu'Etienne a raison de dire que les méthodes de premier ordre qui ont été construites à la main sont dues à Terry Feagin. Concernant son autre commentaire, cet article contient 9 (8) paires:

JH Verner, Paires Runge-Kutta explicites d'ordre élevé avec ordre d'étage bas, Mathématiques numériques appliquées, Volume 22, numéros 1 à 3, novembre 1996, pages 345-357

$N$$p$

p | N
-----
1 | 1
2 | 2
3 | 4
4 | 8
5 | 17
6 | 37
7 | 85
8 | 200
9 | 486
10| 1205
11| 3047
12| 7813
13| 20300
14| 53264

Logiciel

Pour les méthodes de commande très élevées, le nombre et la complexité des conditions de commande deviennent impossibles à traiter à la main. Certains packages symboliques (Mathematica, au moins) ont des capacités pour générer des conditions d'ordre Runge-Kutta. Il existe probablement d'autres packages, mais je suis au courant des éléments suivants (que j'ai écrits tous les deux):

• nodepy : un package Python qui peut générer des expressions symboliques et du code pour les conditions d'ordre à ordre arbitraire. Il comprend également du code Python pour vérifier ces conditions, calculer les coefficients d'erreur, etc.
• RK-Opt : un package MATLAB qui, parmi beaucoup d'autres choses, peut trouver des méthodes Runge-Kutta d'ordre élevé avec des coefficients optimisés pour quelques objectifs différents. Il ne peut actuellement pas gérer le RK explicite du 9e ordre (il monte jusqu'au 8e ordre pour les méthodes de niveau un, dixième pour les méthodes avec un niveau supérieur). Si c'est quelque chose qui vous intéresse, je pourrais ajouter assez facilement les conditions du 9ème ordre (et plus).

Une autre remarque intéressante sur les conditions de commande, qui devient importante pour des commandes aussi élevées, est qu'il y a deux façons de les dériver, et elles vous donnent des conditions différentes (mais collectivement équivalentes): l'une est due à Butcher, l'autre à Albrecht .

@ La réponse de DavidKetcheson frappe les gros points: vous pouvez toujours construire des méthodes d'un ordre suffisamment élevé en utilisant l'extrapolation, c'est une limite très pessimiste et vous pouvez toujours faire beaucoup mieux, toutes les bonnes sont dérivées à la main (à l'aide d'un ordinateur) outils d'algèbre), aucune limite inférieure n'est connue, et les méthodes d'ordre le plus élevé sont dues à Feagin. Compte tenu de certains commentaires, je voulais compléter la réponse par une discussion sur les tableaux de l'état actuel de la technique dans le domaine.

Si vous voulez un recueil de tableaux RK, vous pouvez en trouver un dans ce code Julia . Les citations pour le papier dont ils sont issus sont dans les docstrings pour les constructeurs de tableaux. La documentation du développeur pour DifferentialEquations.jl répertorie tous ces tableaux comme disponibles pour utilisation , et vous pouvez voir ici qu'ils sont tous testés à l'aide des suites d'intégration continue Travis et AppVeyor pour vous assurer que non seulement les conditions de commande sont remplies, mais elles atteindre la convergence demandée (test de vérification). De ceux-ci, vous pouvez voir qu'il y a:

• 5 méthodes de commande 9
• 6 méthodes de commande 10
• 2 méthodes de commande 12
• 1 méthode d'ordre 14

(que j'ai pu trouver qui ont été publiés). Encore une fois, tous dérivés à la main.

Les tests de convergence montrent que certaines des dérivations n'ont pas été effectuées avec une précision suffisamment élevée pour fonctionner avec des nombres supérieurs à 64 bits (elles sont commentées comme ceci ). C'est donc une bizarrerie intéressante à prendre en compte: à ces ordres élevés, vous n'obtenez généralement que des coefficients qui "à une erreur x" remplissent les conditions de l'ordre, mais lorsque vous utilisez l'arithmétique de précision arbitraire, vous pouvez réellement détecter ces limites. La précision avec laquelle vous effectuez les coefficients importe donc, et vous devez la choisir pour couvrir la précision que vous souhaitez tester (/ utiliser, bien sûr).

Si vous voulez un tas de graphiques de stabilité, vous pouvez simplement plot(tableau)utiliser la recette Plots.jl. Un bon ensemble de notes qui contient une grande partie de cela peut être trouvé sur le site Web de Peter Stone (allez ci-dessous et cliquez sur dire les 10 ordres de commande et vous obtiendrez un tas de PDF). Lors du développement de DifferentialEquations.jl, j'ai créé cet ensemble de tableaux pour les passer systématiquement en revue les problèmes de test / regarder les indicateurs analytiques pour voir ceux qui devraient être inclus dans la bibliothèque principale. J'ai pris quelques notes rapides ici . Comme vous pouvez le voir sur les algorithmes inclus dans la bibliothèque principale, celles que j'ai trouvées intéressantes étaient les méthodes Verner et Feagin. La méthode Verner du 9ème ordre est la méthode d'ordre le plus élevé avec un interpolant correspondant également à l'ordre. C'est quelque chose à reconnaître: les méthodes Feagin n'ont pas d'interpolant correspondant (bien que vous puissiez amorcer Hermite, mais c'est vraiment inefficace).

Puisqu'ils sont tous implémentés avec des implémentations très efficaces, vous pouvez jouer avec eux-mêmes et voir à quel point les différentes fonctionnalités comptent réellement. Voici un cahier Jupyter qui montre les méthodes Feagin utilisées . Notez que le tracé de convergence va vraiment être une 1e-48erreur. Les méthodes d'ordre élevé ne sont plus efficaces que les méthodes d'ordre inférieur lorsque vous avez vraiment besoin d'une tolérance très très faible. Vous pouvez trouver des benchmarks qui en utilisent certains sur DiffEqBenchmarks.jl , bien que lorsqu'ils sont utilisés, il s'agit généralement de la méthode Verner du 9ème ordre, et montrant généralement que le benchmark n'est pas dans le régime où ce haut niveau d'ordre est efficace.

Donc, si vous voulez jouer et travailler avec des méthodes de haut niveau, RK-Opt est ce que j'ai trouvé est un bon outil pour en dériver certaines (comme @DavidKetcheson l'a mentionné), et DifferentialEquations.jl a toutes les méthodes publiées (je pense? ) mis en œuvre afin que vous puissiez facilement les tester / les comparer. Cependant, à moins que vous ne trouviez une hypothèse qui puisse être abandonnée, à partir de mes tests, je n'ai pas pu trouver quelque chose qui bat les méthodes Verner (commandes 6-9) et Feagin (commandes 10+). YMMV cependant, et j'aimerais voir plus de recherche à ce sujet.