Niektóre starsze książki, które widziałem, mówią, że minimalna liczba etapów jawnej metody Runge-Kutta określonego zamówienia jest nieznana dla zamówień . Czy to nadal prawda?$\geq 9$

Jakie biblioteki są dostępne do automatycznego działania przy użyciu wysokiej klasy metod Runge-Kutta?

Miedza

To wciąż prawda. W książce Butchera , na stronie 196, czytamy: W artykule z 1985 roku Butcher pokazał, że potrzebujesz 11 etapów, aby otrzymać zamówienie 8 , a to jest ostre. Dla rzędu 10 Hairer opracował rodzinę 17-etapowych metod , ale nie wiadomo, czy można lepiej. Te same informacje podano w sekcji II.5 Hairer, Norsett i Wanner vol. Ja . To ostatnie odniesienie obejmuje również niektóre techniki tworzenia par wysokiego rzędu (do rzędu 8).

Istnieje górna granica minimalnej liczby etapów wymaganych dla dowolnego zamówienia, ponieważ można je zbudować przez ekstrapolację. Jest to znane od bardzo dawna; zobaczyć tę ostatnią papier kopalni o wyjaśnienia. Jednak ta granica jest kwadratowa w kolejności i na pewno dość pesymistyczna. Oprogramowanie nodepy omówione poniżej może generować dokładne współczynniki dla tych metod, a także dla metod odroczonej korekty (które są metodami Runge-Kutta) dowolnego rzędu.

Uważam, że @Etienne ma rację twierdząc, że metody najwyższego rzędu, które zostały zbudowane ręcznie, pochodzą od Terry'ego Feagina. Jeśli chodzi o jego inny komentarz, ten artykuł zawiera około 9 (8) par:

JH Verner, jawne pary Runge-Kutta wysokiego rzędu o niskim stopniu zaawansowania, Applied Numerical Mathematics, tom 22, numery 1–3, listopad 1996, strony 345-357

Oto tabela (skumulowanej) liczby warunków zamówienia $N$ wymagane do każdego zamówienia $p$; ta tabela wykracza poza podane w literaturze i została opracowana przy użyciu nodepy:

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

Oprogramowanie

W przypadku metod bardzo wysokich zamówień liczba i złożoność warunków zamówienia staje się niemożliwa do opanowania ręcznie. Niektóre pakiety symboliczne (przynajmniej Mathematica) mają możliwości generowania warunków zamówienia Runge-Kutta. Prawdopodobnie istnieją jeszcze inne pakiety, ale zdaję sobie sprawę z następujących (oba napisałem):

• nodepy : pakiet Python, który może generować wyrażenia symboliczne i kod dla warunków zamówienia do dowolnego zamówienia. Zawiera również kod Pythona do sprawdzania tych warunków, obliczania współczynników błędów itp.
• RK-Opt : Pakiet MATLAB, który między innymi może znaleźć wysokiej klasy metody Runge-Kutta ze współczynnikami zoptymalizowanymi do kilku różnych celów. Obecnie nie jest w stanie obsłużyć jawnego RK 9. rzędu (zwiększa się do 8. rzędu w przypadku metod etap-jeden-jeden, dziesiątego rzędu w przypadku metod o wyższym stopniu). Jeśli jesteś tym zainteresowany, mógłbym dość łatwo dodać warunki 9. rzędu (i wyższe).

Kolejną interesującą uwagą na temat warunków zamówienia, które stają się znaczące przy tak wysokich zamówieniach, jest to, że istnieją dwa sposoby ich uzyskania i dają one inne (ale zbiorczo równoważne) warunki: jedno jest związane z Butcherem, drugie z Albrechtem .

@ Odpowiedź Davida Ketchesona uderza w najważniejsze kwestie: zawsze możesz konstruować metody o wystarczająco wysokim porządku za pomocą ekstrapolacji, co jest bardzo pesymistyczne i zawsze możesz zrobić o wiele lepiej, wszystkie dobre wyprowadza się ręcznie (przy pomocy jakiegoś komputera narzędzia algebry), żadna dolna granica nie jest znana, a metody najwyższego rzędu wynikają z Feagina. Biorąc pod uwagę niektóre komentarze, chciałem uzupełnić odpowiedź dyskusją na temat aktualnych rozwiązań w tej dziedzinie.

Jeśli chcesz kompendium tabel RK, możesz je znaleźć w tym kodzie Julii . Cytaty dla papieru, z którego pochodzą, znajdują się w dokumentacji dla konstruktorów tableau. Dokumentacja programisty dla DifferentialEquations.jl wymienia wszystkie te tablice, które są dostępne do użycia , i możesz zobaczyć, że wszystkie są testowane przy użyciu pakietów ciągłej integracji Travis i AppVeyor, aby upewnić się, że nie tylko warunki zamówienia są spełnione, ale w rzeczywistości osiągnąć wymaganą zbieżność (testy weryfikacyjne). Z nich widać, że są:

• 5 zamówień 9 metod
• 6 zamówień 10 metod
• 2 zamówienia 12 metod
• Metoda 1 zamówienia 14

(że mogłem znaleźć, które zostały opublikowane). Ponownie wszystkie wyprowadzone ręcznie.

Testy konwergencji pokazują, że niektóre wyprowadzenia nie zostały przeprowadzone z wystarczająco wysoką precyzją, aby mogły działać dla liczb więcej niż 64-bitowych (są one tak skomentowane ). Jest to więc interesujące dziwactwo, o którym należy pamiętać: przy tych wysokich zamówieniach zwykle uzyskuje się tylko współczynniki, które „do błędu x” spełniają warunki zamówienia, ale przy użyciu arytmetyki o dowolnej dokładności można faktycznie wykryć te granice. Zatem dokładność, z jaką przeprowadzasz współczynniki, ma znaczenie i powinieneś wybrać ją, aby objąć precyzję, którą chcesz przetestować (/ oczywiście użyć).

Jeśli chcesz mieć wiele wykresów stabilności, możesz po prostu plot(tableau)użyć przepisu Plots.jl. Dobry zestaw notatek, w których jest dużo tego spisanego, można znaleźć na stronie internetowej Petera Stone'a (przejdź poniżej i kliknij powiedz 10 schematów zamówienia, a otrzymasz kilka plików PDF). Tworząc DifferentialEquations.jl, stworzyłem ten zestaw tabel, aby systematycznie je rozwiązywać w przypadku problemów testowych / przeglądać wskaźniki analityczne, aby zobaczyć, które powinny zostać uwzględnione w głównej bibliotece. Zrobiłem tutaj krótkie notatki . Jak widać z algorytmów zawartych w głównej bibliotece, te, które uznałem za wartościowe, to metody Vernera i Feagina. Metoda Verner 9-go rzędu jest metodą najwyższego rzędu z interpolantem dopasowującym również zamówienie. To jest coś, co należy rozpoznać: metody Feagina nie mają pasującego interpolanta (chociaż można uruchomić Hermite, ale to naprawdę nieefektywne).

Ponieważ wszystkie są zaimplementowane przy użyciu bardzo wydajnych implementacji, możesz sam się z nimi bawić i przekonać się, jak ważne są różne funkcje. Oto notatnik Jupyter, który pokazuje używane metody Feagina . Zauważ, że wykres konwergencji naprawdę popełni 1e-48błąd. Metody wyższego rzędu są bardziej wydajne niż metody niższego rzędu, gdy naprawdę potrzebujesz bardzo bardzo niskiej tolerancji. Niektóre testy porównawcze, które wykorzystują niektóre z nich , można znaleźć na stronie DiffEqBenchmarks.jl , chociaż gdy są one używane, zwykle jest to metoda Verner 9 rzędu, i zwykle pokazuje, że test porównawczy nie jest w systemie, w którym ta wysoka kolejność jest skuteczna.

Więc jeśli chcesz się pobawić i pracować z niektórymi metodami wyższego rzędu, RK-Opt jest tym, co znalazłem, jest dobrym narzędziem do uzyskania niektórych (jak wspomniano @DavidKetcheson), a DifferentialEquations.jl ma wszystkie opublikowane metody (myślę, że? ), dzięki czemu można łatwo przetestować / porównać z nimi. Jednak jeśli nie znajdziesz założenia, które można odrzucić, z moich testów nie udało mi się znaleźć czegoś, co przewyższałoby metody Vernera (zamówienia 6-9) i Feagina (zamówienia 10+). YMMV, i chciałbym zobaczyć więcej badań w tym zakresie.