Beberapa buku yang lebih tua yang pernah saya lihat mengatakan bahwa jumlah minimum tahapan metode Runge-Kutta eksplisit dari pesanan tertentu tidak diketahui untuk pesanan . Apakah ini masih benar?$\geq 9$

Perpustakaan apa yang ada untuk bekerja secara otomatis dengan metode Runge-Kutta tingkat tinggi?

Batas

Itu masih benar. Dalam buku Butcher , halaman 196, dikatakan sebagai berikut: Dalam sebuah makalah tahun 1985, Butcher menunjukkan bahwa Anda memerlukan 11 tahap untuk mendapatkan urutan 8 , dan ini tajam. Untuk pesanan 10, Hairer mendapatkan keluarga metode 17-tahap , tetapi tidak diketahui apakah ada yang bisa melakukan lebih baik. Informasi yang sama diberikan dalam Bagian II.5 dari Hairer, Norsett, & Wanner vol. Aku . Referensi terakhir juga membahas beberapa teknik untuk mengembangkan pasangan tingkat tinggi (hingga 8).

Ada batas atas jumlah minimum tahapan yang diperlukan untuk pesanan apa pun, karena Anda dapat membangunnya dengan ekstrapolasi. Ini sudah lama diketahui; lihat makalah saya baru-baru ini untuk penjelasan. Namun, ikatan ini bersifat kuadratik dalam urutannya dan tentu saja cukup pesimistis. Perangkat lunak nodepy yang dibahas di bawah ini dapat menghasilkan koefisien yang tepat untuk metode ini, dan juga untuk metode koreksi yang ditangguhkan (yang merupakan metode Runge-Kutta) dari pesanan apa pun.

Saya percaya @tienne benar dalam mengatakan bahwa metode urutan tertinggi yang telah dibangun dengan tangan adalah karena Terry Feagin. Mengenai komentarnya yang lain, makalah ini memuat sekitar 9 (8) pasangan:

JH Verner, High-order eksplisit Runge-Kutta berpasangan dengan urutan tahap rendah, Matematika Numerik Terapan, Volume 22, Masalah 1-3, November 1996, Halaman 345-357

Berikut adalah tabel jumlah (kumulatif) kondisi pemesanan diperlukan untuk setiap pesanan ; tabel ini lebih jauh dari yang disediakan dalam literatur dan diproduksi menggunakan nodepy:$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

Perangkat lunak

Untuk metode pesanan sangat tinggi, jumlah dan kompleksitas kondisi pesanan menjadi tidak mungkin untuk ditangani dengan tangan. Beberapa paket simbolis (Mathematica, setidaknya) memiliki kemampuan untuk menghasilkan kondisi pesanan Runge-Kutta. Mungkin ada beberapa paket lain di luar sana, tetapi saya menyadari hal berikut (keduanya saya tulis):

• nodepy : paket Python yang dapat menghasilkan ekspresi simbolik dan kode untuk kondisi pesanan ke pesanan sewenang-wenang. Ini juga termasuk kode Python untuk memeriksa kondisi tersebut, menghitung koefisien kesalahan, dll.
• RK-Opt : Paket MATLAB yang, di antara banyak hal lainnya, dapat menemukan metode Runge-Kutta tingkat tinggi dengan koefisien yang dioptimalkan untuk beberapa tujuan berbeda. Saat ini tidak dapat menangani RK eksplisit urutan ke-9 (naik ke urutan 8 untuk metode tahap-orde-satu, urutan kesepuluh untuk metode dengan urutan tahap yang lebih tinggi). Jika itu adalah sesuatu yang Anda minati, saya bisa menambahkan kondisi urutan ke-9 (dan lebih tinggi) dengan cukup mudah.

Catatan lain yang menarik tentang kondisi pesanan, yang menjadi signifikan pada pesanan tinggi, adalah bahwa ada dua cara untuk menurunkannya, dan mereka memberikan Anda kondisi yang berbeda (tetapi secara kolektif setara): satu disebabkan oleh Jagal, yang lain ke Albrecht .

@ DavidKetcheson menjawab hal-hal besar: Anda selalu dapat membangun metode pesanan cukup tinggi menggunakan ekstrapolasi, itu adalah ikatan yang sangat pesimistis dan Anda selalu dapat melakukan jauh lebih baik, semua yang bagus diperoleh dengan tangan (dengan bantuan beberapa komputer) alat aljabar), tidak ada batas bawah yang diketahui, dan metode urutan tertinggi adalah karena Feagin. Diberikan beberapa komentar, saya ingin melengkapi jawabannya dengan diskusi tentang tableaus canggih saat ini di lapangan.

Jika Anda menginginkan ringkasan dari tableaus RK, Anda dapat menemukannya di kode Julia ini . Kutipan untuk kertas yang mereka berasal ada di dokumen untuk tablo konstruktor. Dokumentasi pengembang untuk DifferentialEquations.jl mencantumkan semua tablo ini sebagai tersedia untuk digunakan , dan Anda dapat melihat di sini bahwa ini semua diuji dengan menggunakan suite integrasi berkelanjutan Travis dan AppVeyor untuk memastikan bahwa tidak hanya kondisi pesanan terpenuhi, tetapi mereka sebenarnya mencapai konvergensi yang diminta (pengujian verifikasi). Dari ini, Anda dapat melihat bahwa ada:

• 5 pesanan 9 metode
• 6 pesan 10 metode
• 2 memesan 12 metode
• Metode 1 pesanan 14

(yang dapat saya temukan yang dipublikasikan). Sekali lagi, semua diturunkan dengan tangan.

Tes konvergensi menunjukkan bahwa beberapa derivasi tidak dilakukan dengan presisi yang cukup tinggi untuk bekerja lebih dari angka 64-bit (mereka berkomentar seperti ini ). Jadi itu adalah hal yang menarik untuk diperhatikan: pada pesanan tinggi ini Anda biasanya hanya mendapatkan koefisien yang "untuk kesalahan x" memenuhi persyaratan pesanan, tetapi ketika menggunakan aritmatika presisi sewenang-wenang Anda benar-benar dapat mendeteksi batas-batas ini. Jadi ketelitian yang Anda lakukan koefisien penting, dan Anda harus memilihnya untuk mencakup ketepatan yang ingin Anda uji (/ gunakan, tentu saja).

Jika Anda ingin banyak plot stabilitas, Anda bisa plot(tableau)menggunakan resep Plots.jl. Seperangkat catatan yang baik yang memiliki banyak catatan ini dapat ditemukan di situs web Peter Stone (buka di bawah dan klik pada katakanlah skema 10 pesanan dan Anda akan mendapatkan banyak PDF). Ketika mengembangkan DifferentialEquations.jl, saya membuat set tableaus untuk secara sistematis mengatasinya pada masalah pengujian / lihat indikator analitis untuk melihat mana yang harus dimasukkan dalam perpustakaan utama. Saya membuat beberapa catatan cepat di sini . Seperti yang Anda lihat dari algoritma yang termasuk dalam perpustakaan utama, yang saya temukan berharga adalah metode Verner dan Feagin. Metode pesanan Verner 9 adalah metode urutan tertinggi dengan interpolant yang cocok dengan pesanan juga. Itu sesuatu yang harus dikenali: metode Feagin tidak memiliki interpolant yang cocok (meskipun Anda dapat mem-bootstrap Hermite, tetapi itu benar-benar tidak efisien).

Karena semuanya diimplementasikan dengan implementasi yang sangat efisien, Anda dapat bermain-main dengan mereka sendiri dan melihat betapa banyak perbedaan fitur yang sebenarnya. Ini adalah notebook Jupyter yang menunjukkan metode Feagin yang digunakan . Perhatikan bahwa plot konvergensi benar-benar 1e-48salah. Metode pesanan tinggi hanya lebih efisien daripada metode pesanan rendah ketika Anda benar-benar membutuhkan toleransi yang sangat sangat rendah. Anda dapat menemukan beberapa tolok ukur yang menggunakan beberapa dari mereka di DiffEqBenchmarks.jl , meskipun ketika mereka digunakan biasanya metode urutan ke-9 Verner, dan biasanya menunjukkan bahwa tolok ukur tidak dalam rezim di mana urutan tinggi ini efisien.

Jadi jika Anda ingin bermain-main dan bekerja dengan beberapa metode tingkat tinggi, RK-Opt adalah apa yang saya temukan adalah alat yang baik untuk menurunkan beberapa (seperti yang disebutkan @DavidKetcheson), dan DifferentialEquations.jl memiliki semua metode yang diterbitkan (saya pikir? ) diimplementasikan sehingga Anda dapat dengan mudah menguji / benchmark terhadap mereka. Namun, kecuali Anda menemukan asumsi yang dapat dibatalkan, dari pengujian saya, saya belum dapat menemukan sesuatu yang mengalahkan metode Verner (pesanan 6-9) dan Feagin (pesanan 10+). YMMV, dan saya ingin melihat lebih banyak penelitian dalam hal ini.