Mengapa metode Runge – Kutta tingkat tinggi tidak digunakan lebih sering?

17

Saya hanya ingin tahu mengapa metode tingkat tinggi (yaitu lebih dari 4) metode Runge-Kutta hampir tidak pernah dibahas / dipekerjakan (setidaknya setahu saya). Saya mengerti ini membutuhkan waktu komputasi yang lebih besar per langkah (misalnya RK14 dengan langkah tertanam urutan ke-12 ), tetapi apakah ada kelemahan lain dari menggunakan metode Runge-Kutta tingkat tinggi (misalnya masalah stabilitas)? Ketika diterapkan pada persamaan dengan solusi berosilasi tinggi pada skala waktu ekstrem, bukankah metode tingkat tinggi seperti itu biasanya lebih disukai?

ode runge-kutta Mathews24
sumber
2
Saya pikir ini adalah pertanyaan yang sangat subyektif. Kelemahan terbesar seperti yang telah Anda catat adalah biaya perhitungan. Secara umum kami mencoba menyeimbangkan antara akurasi dan waktu komputasi. Dalam PDE ketika orang berbicara tentang tatanan yang lebih tinggi, mereka umumnya memikirkan tatanan ke-3 atau ke-4. Dan loncatan waktu juga disimpan dalam urutan yang sama.
Vikram
3
Dalam PDE, skema akurasi urutan tinggi untuk ketergantungan temporal tidak masuk akal jika akurasi spasial lebih buruk. Bahkan, akurasi ketergantungan spasial sebagian besar tentang urutan ke-2 atau ke-3, terutama ketika mengerjakan jerat yang tidak terstruktur. Orang-orang perlu mengendalikan pemotongan kesalahan global dengan biaya terendah, karenanya, mempertimbangkan Runge-Kutta dengan urutan akurasi yang cukup tinggi dalam kasus-kasus tertentu.
tqviet
@tqviet Jika menggunakan perkiraan perbedaan ke belakang atau pusat hingga urutan 8 untuk turunan spasial, RK8 akan cocok, bukan? Secara umum, adakah masalah keakuratan atau stabilitas dengan menggunakan pendekatan beda hingga hingga tingkat tinggi dari turunan spasial?
Mathews24
1
@ Mathews24: Saya tidak menyebutkan stabilitas, yang sangat bergantung pada persamaan. Ketika skema yang sangat akurat diterapkan ketergantungan spasial, kita mengadopsi RK ketergantungan duniawi dengan setidaknya urutan yang sama akurasi, namun kondisi stabilitas mungkin memerlukan nilai yang lebih kecil dari . Δt
tqviet

Jawaban:

17

Ada ribuan makalah dan ratusan kode di luar sana menggunakan metode Runge-Kutta urutan kelima atau lebih tinggi. Perhatikan bahwa integrator eksplisit yang paling umum digunakan di MATLAB adalah ODE45, yang memajukan solusi menggunakan metode Runge-Kutta orde 5.

Contoh metode Runge-Kutta orde tinggi yang banyak digunakan

The kertas Dormand & Pangeran memberikan metode-5-order memiliki lebih dari 1700 kutipan menurut Google Scholar . Kebanyakan dari mereka adalah makalah yang menggunakan metode mereka untuk memecahkan beberapa masalah. Makalah metode Cash-Karp memiliki lebih dari 400 kutipan . Mungkin metode pesanan yang paling banyak digunakan di atas 5 adalah metode urutan ke-8 Prince-Dormand yang memiliki lebih dari 400 kutipan di Google Cendekia . Saya bisa memberikan banyak contoh lain; dan perlu diingat bahwa banyak (jika tidak sebagian besar) orang yang menggunakan metode ini tidak pernah mengutip makalah.

Perhatikan juga bahwa ekstrapolasi tingkat tinggi dan metode koreksi yang ditangguhkan adalah metode Runge-Kutta .

Metode tingkat tinggi dan kesalahan pembulatan

Jika akurasi Anda dibatasi oleh kesalahan pembulatan maka Anda harus menggunakan metode tingkat tinggi . Ini karena metode tingkat tinggi memerlukan lebih sedikit langkah (dan lebih sedikit evaluasi fungsi, meskipun ada lebih banyak evaluasi per langkah), sehingga mereka melakukan lebih sedikit kesalahan pembulatan. Anda dapat dengan mudah memverifikasi ini sendiri dengan eksperimen sederhana; ini adalah masalah pekerjaan rumah yang baik untuk kursus pertama dalam analisis numerik.

Metode urutan kesepuluh sangat berguna dalam aritmatika presisi ganda. Sebaliknya, jika yang kita miliki hanyalah metode Euler, maka kesalahan pembulatan akan menjadi masalah besar dan kita akan membutuhkan angka floating point berpresisi tinggi untuk banyak masalah di mana solver tingkat tinggi baik-baik saja.

Metode pesanan tinggi bisa sama stabil

AB

Metode tingkat tinggi dalam mekanika langit

Anda bertanya

Ketika diterapkan pada persamaan dengan solusi berosilasi tinggi pada skala waktu ekstrem, bukankah metode tingkat tinggi seperti itu biasanya lebih disukai?

Anda benar sekali! Contoh utama dari ini adalah mekanika selestial. Saya bukan ahli di bidang itu. Tetapi makalah ini , misalnya, membandingkan metode untuk mekanika selestial dan bahkan tidak menganggap urutan lebih rendah dari 5. Ia menyimpulkan bahwa metode urutan 11 atau 12 sering paling efisien (dengan metode Prince-Dormand urutan 8 juga sering sangat efisien).

David Ketcheson
sumber
Ketchson: dapatkah Anda memberikan beberapa bukti atau penjelasan tentang pernyataan ini: "ekstrapolasi tingkat tinggi dan metode koreksi yang ditangguhkan adalah metode Runge-Kutta"? Terutama "metode koreksi tangguhan". Terima kasih.
tqviet
@ David Ketcheson Bisakah Anda mendiskusikan bagaimana jawaban Anda akan berubah jika menggunakan teknik komputasi yang tervalidasi (terverifikasi), seperti interval putaran keluar atau aritmatika radial? Bagaimana jika lebih tinggi dari interval presisi luar bulat atau aritmatika radial digunakan? Apa yang akan terjadi dengan pembungkus dan ketergantungan ketika pesanan Runge-Kutta meningkat, dan hanya untuk bersenang-senang, katakanlah ODE sangat kaku.?
Mark L. Stone
@ MarkL.Stone Itu set pertanyaan yang sangat berbeda. Jika Anda ingin bertanya, silakan posting sebagai pertanyaan terpisah. Namun, saya bukan ahli dalam hal-hal itu dan tidak akan bisa menjawab.
David Ketcheson
1
@tqviet Lihatlah makalah ini untuk penjelasan.
David Ketcheson
12

Selama Anda menggunakan aritmatika floating point presisi ganda standar, metode pesanan sangat tinggi tidak diperlukan untuk mendapatkan solusi dengan akurasi tinggi dalam sejumlah langkah yang masuk akal. Dalam praktiknya saya menemukan bahwa keakuratan solusi biasanya terbatas pada kesalahan relatif 1.0e-16 oleh representasi floating point presisi ganda daripada jumlah / panjang langkah-langkah yang diambil dengan RKF45.

Jika Anda beralih ke beberapa skema aritmatika floating point presisi lebih tinggi dari dua, maka menggunakan metode urutan 10 mungkin bernilai sementara.

Brian Borchers
sumber
5
Saya pikir jawaban ini menyesatkan. Metode tingkat tinggi menyebabkan kesalahan pembulatan jauh lebih sedikit, sedangkan metode tingkat rendah menderita kesalahan pembulatan menjadi dominan ketika akurasi yang dibutuhkan besar atau interval waktu lama; lihat jawaban saya di bawah ini.
David Ketcheson
2
Intinya adalah bahwa dalam floating point presisi ganda Anda bahkan tidak bisa mewakili solusi dengan akurasi relatif lebih baik dari 1.0e-16. Dalam banyak situasi praktis, RKF45 tua yang baik akan membawa Anda ke tingkat akurasi selama periode yang Anda minati tanpa memerlukan langkah-langkah kecil. Ini mungkin bukan pilihan yang baik untuk sistem yang kaku atau situasi di mana integrator symplectic diperlukan, tetapi metode Runge Kutta tingkat tinggi juga bukan solusi yang bagus dalam situasi tersebut. Saya setuju bahwa untuk jangka waktu yang lama metode pesanan Runge Kutta yang lebih tinggi bisa masuk akal.
Brian Borchers
10

Hanya untuk menambah jawaban sempurna Brian Borcher, banyak aplikasi kehidupan nyata mengakui ODE atau DAE yang sangat kaku. Secara intuitif, masalah-masalah ini mengalami perubahan yang tidak mulus, tiba-tiba berubah seiring waktu, jadi dimodelkan lebih baik dengan menggunakan polinomial tingkat rendah yang tersebar dengan halus pada ukuran langkah pendek, berbeda dengan polinomial tingkat tinggi yang direntangkan pada ukuran langkah yang panjang. Juga, stabilitas sering mengharuskan penggunaan metode implisit , di mana hukuman komputasi metode orde tinggi jauh lebih curam.

Lebih ketat, metode tingkat tinggi kurang stabil daripada metode tingkat rendah untuk masalah kaku. Kami memiliki misalnya, hambatan Dahlquist untuk metode multistep linier.

r≤2

Pernyataan serupa (tapi jauh lebih rumit) dapat dibuat untuk kestabilan L dalam rumus RK. Dalam semua kasus, peningkatan urutan seringkali tidak selalu menghasilkan solusi yang lebih akurat. Berikut ini adalah kutipan dari makalah 1974 seminalis Prothero dan Robinson:

Dalam menggunakan metode satu langkah A-stable untuk menyelesaikan sistem besar persamaan diferensial nonlinear kaku, kami telah menemukan bahwa
(a) beberapa metode A-stable memberikan solusi yang sangat tidak stabil, dan
(b) keakuratan solusi yang diperoleh ketika persamaan tersebut kaku sering tampaknya tidak berhubungan dengan urutan metode yang digunakan.

Untuk perawatan yang lebih teliti dari topik ini, lihat teks klasik oleh Hairer & Wanner, "Memecahkan persamaan diferensial biasa II: Kaku dan Diferensial - Masalah Aljabar", 1991.

Dalam praktiknya, persamaan kaku hampir selalu diselesaikan dengan menggunakan aturan trapesium atau rumus TR-BDF2 (fungsi ode23t dan ode23tb di MATLAB). Keduanya adalah metode orde dua implisit. Tentu saja, di mana stabilitas bukan masalah (yaitu dalam persamaan nonstiff) kita bebas memilih dari sejumlah opsi; RK45 adalah pilihan paling umum.

Richard Zhang
sumber
Sangat menarik. Apakah ada penjelasan (intuitif) mengapa order harus kurang dari atau sama dengan 2 agar itu menjadi metode multistep A-stable? Dan hanya untuk memperjelas, ketika Anda mengatakan pernyataan serupa dapat dibuat untuk formula RK, apakah itu pesanan 2 lagi?
Mathews24
Tetapi untuk metode Runge-Kutta, ada metode A-stable dari pesanan sewenang-wenang.
David Ketcheson
@ Davidvideton Ya, tetapi mereka tidak sangat A-stable (yaitu L-stable). Mereka memiliki banyak masalah ketika digunakan untuk memecahkan DAE, misalnya mensimulasikan rangkaian transistor sederhana. Memang, TR terkenal karena menyebabkan dering buatan di SPICE, yang memotivasi pengembangan TR-BDF2.
Richard Zhang
@DavidKetcheson Untuk referensi, lihat doi.org/10.1090/S0025-5718-1974-0331793-2 . Gagasan tentang stabilitas-A tidak cukup kuat untuk DAE, dan metode-metode stabil-A tingkat tinggi sering menghasilkan hasil yang aneh ketika digunakan untuk memecahkan DAE.
Richard Zhang
Tentu, tetapi pertanyaannya bukan tentang DAE atau tentang metode multistep.
David Ketcheson
9

Pengaturan Benchmark

Dalam perangkat lunak Julia, DifferentialEquations.jl, kami menerapkan banyak metode tingkat tinggi, termasuk metode Feagin. Anda dapat melihatnya di daftar metode kami , dan kemudian ada banyak metode lain yang dapat Anda gunakan sebagai tableaus yang disediakan . Karena semua metode ini disatukan, Anda dapat dengan mudah membandingkannya. Anda dapat melihat tolok ukur yang saya miliki online di sini , dan melihat bahwa sangat mudah untuk membandingkan berbagai algoritma. Jadi, jika Anda ingin mengambil beberapa menit untuk menjalankan benchmark, lakukan. Berikut ringkasan dari apa yang keluar.

Pertama, penting untuk dicatat bahwa, jika Anda melihat masing-masing tolok ukur, Anda akan melihat bahwa kami DP5(Dormand-Prince Order 5) dan DP8metode kami lebih cepat daripada kode Hairer Fortran ( dopri5dan dop853), dan implementasi ini dioptimalkan dengan sangat baik . Ini menunjukkan bahwa sebagaimana dicatat di utas lain , penggunaan metode Dormand-Prince yang berlebihan adalah karena metode tersebut sudah ditulis, bukan karena mereka masih yang terbaik. Jadi perbandingan nyata antara implementasi yang paling optimal adalah antara metode Tsitorous, metode Verner, dan metode Feagin dari DifferentialEquations.jl.

Hasil

Secara umum, metode pesanan yang lebih tinggi dari 7 memiliki biaya komputasi tambahan yang biasanya tidak melebihi pesanan, mengingat toleransi yang dipilih. Salah satu alasannya adalah bahwa pilihan koefisien untuk metode pesanan lebih rendah lebih dioptimalkan (mereka memiliki "koefisien kesalahan pemangkasan prinsip" kecil, yang lebih penting ketika Anda tidak kecil secara asimptopik). Anda dapat melihat bahwa dalam banyak masalah seperti di sini metode Verner Efficient 6 dan 7 bekerja sangat baik, tetapi metode seperti Verner Efficient 8 dapat memiliki kemiringan yang lebih rendah. Ini karena "keuntungan" dari tatanan yang lebih tinggi bertambah dengan toleransi yang lebih rendah, sehingga selalu ada toleransi di mana metode tatanan yang lebih tinggi akan lebih efisien.

Namun, pertanyaannya kemudian, seberapa rendah? Dalam implementasi yang dioptimalkan dengan baik, itu menjadi sangat rendah karena dua alasan. Alasan pertama adalah karena metode urutan rendah menerapkan sesuatu yang disebut FSAL (pertama sama dengan yang terakhir). Properti ini berarti bahwa metode urutan rendah menggunakan kembali evaluasi fungsi dari langkah sebelumnya di langkah berikutnya, dan dengan demikian secara efektif memiliki satu evaluasi fungsi yang kurang. Jika ini digunakan dengan benar, maka sesuatu seperti metode urutan ke-5 (Tsitorous atau Dormand-Prince) sebenarnya mengambil 5 evaluasi fungsi daripada 6 yang disarankan oleh tablo. Ini juga berlaku untuk metode Verner 6.

Alasan lainnya adalah karena interpolasi. Salah satu alasan untuk menggunakan metode pesanan sangat tinggi adalah untuk mengambil langkah lebih sedikit dan hanya menginterpolasi nilai perantara. Namun, untuk mendapatkan nilai perantara, fungsi interpolasi mungkin memerlukan lebih banyak evaluasi fungsi daripada yang digunakan untuk mengambil langkah. Jika Anda melihat metode Verner, diperlukan 8 evaluasi fungsi tambahan untuk metode Order 8 untuk mendapatkan interpolant Order 8. Banyak kali metode pesanan rendah memberikan interpolasi "gratis", misalnya, sebagian besar metode pesanan 5 memiliki interpolasi pesanan keempat gratis (tanpa evaluasi fungsi tambahan). Jadi ini berarti bahwa jika Anda memerlukan nilai perantara (yang Anda perlukan untuk plot yang bagus jika Anda menggunakan metode pesanan tinggi), ada beberapa biaya tambahan tersembunyi. Faktor dalam fakta bahwa nilai-nilai yang diinterpolasi ini sangat penting untuk penanganan kejadian dan penyelesaian persamaan diferensial keterlambatan dan Anda melihat mengapa faktor biaya interpolasi tambahan masuk.

Jadi Bagaimana Dengan Metode Feagin?

Jadi, Anda akan melihat bahwa metode Feagin secara mencurigakan hilang dari tolok ukur. Mereka baik-baik saja, tes konvergensi bekerja pada angka presisi yang berubah-ubah, dll., Tetapi untuk benar-benar membuatnya bekerja dengan baik, Anda perlu meminta toleransi yang sangat rendah. Sebagai contoh, saya menemukan dalam tolok ukur yang tidak dipublikasikan bahwa Feagin14kinerjanya lebih baik Vern9(urutan ke-9 Verner Efficient Method) pada toleransi seperti 1e-30. Untuk aplikasi dengan dinamika kacau (seperti pada Pleides atau masalah astrofisika 3-tubuh), Anda mungkin menginginkan jumlah akurasi ini karena ketergantungan yang sensitif (kesalahan dalam sistem kacau bertambah cepat). Namun, kebanyakan orang mungkin menghitung dengan angka floating point presisi ganda, dan saya belum menemukan patokan di mana mereka mengungguli dalam domain toleransi ini.

Selain itu, tidak ada interpolant untuk mengikuti metode Feagin. Jadi apa yang saya lakukan adalah hanya menempatkan interpolasi Hermite urutan ketiga pada mereka sehingga ada satu (dan itu bekerja dengan sangat baik). Namun, jika tidak ada fungsi interpolasi standar, Anda dapat melakukan metode Hermite rekursif (gunakan interpolasi ini untuk mendapatkan titik tengah, kemudian lakukan interpolasi urutan ke-5, dll.) Untuk mendapatkan interpolasi urutan tinggi, tetapi ini sangat mahal dan hasilnya interpolasi tidak harus memiliki istilah kesalahan pemangkasan prinsip yang rendah (jadi bagus jika dtbenar-benar kecil, yang merupakan kebalikan dari kasus yang kita inginkan!). Jadi jika Anda membutuhkan interpolasi yang benar-benar bagus untuk mencocokkan keakuratan Anda, Anda harus setidaknya kembali ke sesuatu seperti Vern9.

Catatan Tentang Ekstrapolasi

Perhatikan bahwa metode ekstrapolasi hanyalah algoritma untuk menghasilkan metode Runge-Kutta pesanan acak. Namun, untuk pesanan mereka, mereka mengambil lebih banyak langkah daripada yang diperlukan dan memiliki koefisien kesalahan pemangkasan prinsip tinggi, sehingga mereka tidak seefisien metode RK yang dioptimalkan dengan baik pada pesanan tertentu. Tetapi mengingat analisis sebelumnya, ini berarti bahwa ada domain dengan toleransi sangat rendah di mana metode ini akan melakukan lebih baik daripada metode RK "dikenal". Tapi di setiap benchmark yang saya jalankan, sepertinya saya belum mendapatkan yang terendah.

Catatan Tentang Stabilitas

Pilihannya benar-benar tidak ada hubungannya dengan masalah stabilitas. Bahkan, jika Anda pergi melalui tableaus DifferentialEquations.jl (Anda bisa hanya plot(tab)untuk daerah stabilitas) Anda akan melihat bahwa sebagian besar metode memiliki daerah stabilitas yang mencurigakan serupa. Ini sebenarnya pilihan. Biasanya ketika mendapatkan metode, penulis biasanya melakukan hal berikut:

  1. Temukan koefisien kesalahan pemotongan prinsip terendah (yaitu, koefisien untuk istilah pesanan berikutnya)
  2. Tunduk pada batasan pesanan
  3. Dan membuat wilayah stabilitas dekat dengan metode Dormand-Prince Order 5.

Kenapa kondisi terakhir? Yah, karena metode itu cenderung selalu stabil dengan cara pilihan langkah-langkah adaptif yang dikontrol PI dilakukan, jadi itu bar yang bagus untuk wilayah stabilitas "cukup baik". Jadi bukan kebetulan kalau daerah stabilitas cenderung sama.

Kesimpulan

Ada pengorbanan dalam setiap pilihan metode. Metode RK urutan tertinggi tidak seefisien pada toleransi yang lebih rendah baik karena lebih sulit untuk mengoptimalkan pilihan koefisien, dan karena jumlah fungsi mengevaluasi senyawa (dan tumbuh lebih cepat ketika interpolasi terlibat). Namun, jika toleransi menjadi cukup rendah mereka menang, tetapi toleransi yang diperlukan bisa jauh di bawah aplikasi "standar" (yaitu benar-benar hanya berlaku untuk sistem yang kacau).

Chris Rackauckas
sumber