Mengapa RK4 lebih baik daripada integrasi Euler? [Tutup]

20

Pada akhir slide yang hebat ini , penulis membandingkan semua integrator berbeda yang disajikan. Salah satu cara atau yang lain, mereka semua gagal kecuali untuk Integrasi Peningkatan Euler dan Integrasi Runge Kutta 4 , yang keduanya lulus semua tes.

Saya kira saya harus menyebutkan bahwa saya sedang mengerjakan game 2D yang tidak terlalu intensif secara fisika. Saya hanya ingin tahu di mana Improved Euler Integration akan gagal dan RK4 harus digunakan sebagai gantinya.

Permainan saya sebagian besar terdiri dari gravitasi sederhana (melompat dan turun), gerakan di sepanjang sumbu X dan Y, dan tabrakan kotak pembatas. Apakah layak untuk mengimplementasikan RK4 atau akankah Peningkatan Euler mencukupi? Saya melihat banyak diskusi di mana pengguna Euler Integration dihukum, tetapi dari apa yang saya lihat, Improved Euler adalah quivalen dalam masalah 2D sederhana. Saya membayangkan itu juga akan lebih cepat.

physics rk4 integration John Tyler
sumber
offtopic, tetapi slide area besar, sangat jelas dengan contoh dan semua. Terima kasih untuk tautannya!
Roy T.
Jika ini memang di luar topik di sini mungkin akan cocok di Ilmu Komputasi .
David Z
Juga: Integrasi Verlet yang Diperbaiki Waktu - terlihat mirip dengan Peningkatan Euler: terlalu malas untuk mencari tahu apakah itu persis sama. TCV sangat bagus karena Anda dapat bersikap lunak dengan langkah waktu tetap Anda (integrator lain menginginkan langkah waktu tetap yang dijamin).
Jonathan Dickinson
1
Tidak dapat mengedit: Saya melihat dia menyebutkannya. Saya tidak yakin apakah implementasinya disadap dalam hal persyaratan kondisi awal sebagaimana diuraikan dalam artikel: tapi saya belum pernah melihat masalah gravitasi dengan implementasi TCV saya jika saya menghitung kondisi awal dengan benar.
Jonathan Dickinson

Jawaban:

15

Saya pribadi lebih suka Velocity Verlet untuk sebagian besar simulasi. Dalam pengalaman saya dengan metode ini, sangat cocok untuk persamaan yang cukup kaku. Sepertinya metode "Euler yang ditingkatkan" ini sangat mirip dengan Velocity Verlet dan mengandalkan kelas metode integrasi yang dikenal sebagai prediktor-korektor . Anda dapat membaca banyak hal tentang metode ini saat ini, dimulai dengan "Langkah besar dalam simulasi kain" karya David Baraff di mana kekuatan metode implisit benar-benar bersinar. Kejatuhan mereka adalah Anda:

  1. harus mendekati Jacobians atau Hessians dan kemudian harus,
  2. menghitung jumlah invers matriks yang adil per frame.

Jadi, jika Anda bukan guru matematika, jari-jari Anda bisa tersangkut. Hanya bereksperimen dengan metode apa pun yang Anda inginkan dan kemudian puas dengan metode yang tampaknya paling baik untuk Anda. Sederhana tidak selalu lebih baik, tetapi untuk framerates interaktif, saya hanya tahu satu kata: kompromi.

Beberapa sumber tambahan yang mungkin ingin Anda lihat:

Jakobsen adalah semacam jenius untuk datang dengan ide sederhana untuk masalah pretentious (spesialisasinya adalah Kriptografi jika tidak salah, tetapi ia berhasil membuktikan kesetaraan matematika dari metodenya ke kelas algoritma iteratif Gauss-Seidel, yang konvergen ). Untuk mempermudah, lakukan ini terlebih dahulu sebelum mempelajari metode implisit.

EDIT KEMUDIAN : Baru-baru ini saya mendapatkan makalah tentang masalah ini dengan menggunakan integrator eksplisit untuk simulasi bodi lunak atau semi-kaku dan apa dampak kinerja dan kualitasnya. Makalah ini harus berfungsi sebagai panduan untuk memilih integrator tertentu, tergantung pada skenario.

teko teh
sumber
1
+1 Ini sebenarnya jawaban kualitas yang sangat bagus dalam hal konten: tapi itu agak sulit untuk dicerna (dinding teks). Saya menemukan bahwa pemformatan yang baik selalu membantu mendapatkan suara. Saya memperbaikinya dan mudah-mudahan Anda mendapatkan suara yang layak Anda dapatkan.
Jonathan Dickinson
Terima kasih Jonathan, saya sudah melakukannya dengan tergesa-gesa, mengabaikan prosedur "ramah pembaca", tetapi saya harus menyebutkan beberapa sumber karena mereka benar-benar sangat sering digunakan bahkan hari ini).
teodron
10

T: Mengapa menggunakan Runge Kutta canggih?
A: Karena itu sangat tepat.

T: Kenapa tidak?
A: Karena Anda membuat game dan mesin fisika yang sangat tepat tidak masalah, itu hanya harus cukup baik untuk menipu pemain.

Ngomong-ngomong, jika Anda mengalami sedikit tabrakan pada tabrakan, seperti kebanyakan platformer, Euler sederhana baik-baik saja.

Saya sangat menyarankan agar Anda tidak seperti kode dalam presentasi menggunakan fisika langkah tetap, yang menyelamatkan Anda dari beberapa potensi gangguan, dan memungkinkan Anda memecahkan masalah mendapatkan bola atau kehilangan energi dengan cara yang sangat sederhana. Coba saja jalan tengah antara integrasi eksplisit dan implisit:

velocity += 0.5 * acceleration;
position += velocity;
velocity += 0.5 * acceleration;

Apa yang presentasi tidak perlihatkan adalah bagaimana menangani tabrakan sehingga objek tampaknya tidak melampaui batas. Solusi sederhana untuk masalah itu adalah dengan menggunakan frekuensi pembaruan tinggi. Solusi yang lebih kompleks tetapi berpotensi melakukan lebih baik adalah untuk memindahkan objek kembali pada saat tabrakan, implementasi yang tepat tergantung pada perilaku fisika yang diinginkan.

aaaaaaaaaaaa
sumber
1
1 untuk "membodohi pemain" - tetapi saya secara pribadi memiliki sistem yang 'sangat sederhana' meledak karena integrasi euler.
Jonathan Dickinson
@JonathanDickinson Saya akan mengatakan bahwa itu bukan karena integrasi Euler, melainkan karena campuran keadaan, integrasi Euler menjadi salah satunya. Jika Anda memiliki contoh, saya yakin saya dapat menemukan cara menghindari sistem yang meledak.
aaaaaaaaaaaa
Oh itu pada beberapa hal yang sangat lama VB6 (ketika saya benar-benar sekitar 14) saya sebelum saya belajar tentang RK / Verlet - Saya bahkan tidak memiliki kode lagi: yang memberikan kepercayaan tinggi pada kenyataan bahwa itu mungkin sesuatu yang lain dalam campuran :).
Jonathan Dickinson
1
Saya kira saya harus menambahkan bahwa segera setelah Anda mulai mengacaukan tarik-menarik antara objek daripada hanya gravitasi sederhana itu tampaknya masuk akal bagi saya untuk meningkatkan metode integrasi, mungkin tidak sepenuhnya diperlukan, tetapi jika Anda sudah mendapatkan kekuatan pemrosesan Satunya downside adalah kode sedikit lebih kompleks.
aaaaaaaaaaaa
1

Presentasi memiliki kesalahan. Metode yang disebut oleh presenter sebagai "Improved Euler" sebenarnya adalah metode Velocity Verlet!

Lihat di sini untuk sumber yang lebih resmi: http://www.physics.udel.edu/~bnikolic/teaching/phys660/numerical_ode/node5.html

Persamaan yang sama juga ada di Wikipedia .

Sebuah perbaikan langsung umum atas metode Euler adalah metode Midpoint yang mungkin dipikirkan oleh presenter tetapi akhirnya salah mengira Velocity Verlet sebagai Euler yang ditingkatkan. Satu-satunya perbedaan antara metode Midpoint dan Velocity Verlet adalah bahwa kecepatan adalah rata-rata akselerasi terakhir dan selanjutnya, bukan hanya bergantung pada akselerasi terakhir.

Shital Shah
sumber