Metode ODE optimal untuk evaluasi RHS dengan jumlah tetap

14

Dalam praktiknya, runtime penyelesaian IVP numerik

\dot{x} (t) = f (t, x (t)) for t \in [t_{0}, t_{1}]

$\dot{x}(t) = f(t, x(t)) \quad \text{ for } t \in [t_0, t_1]$

x (t_{0}) = x_{0}

$x(t_0) = x_0$ sering didominasi oleh lamanya mengevaluasi sisi kanan (RHS). Karena itu, mari kita asumsikan bahwa semua operasi lain bersifat instan (yaitu tanpa biaya komputasi). Jika runtime keseluruhan untuk menyelesaikan IVP terbatas maka ini sama dengan membatasi jumlah evaluasike beberapa.

f

$f$

f

$f$

N \in N

$N \in \mathbb{N}$

Kami hanya tertarik pada nilai akhir $x(t_1)$ .

Saya mencari hasil teoritis dan praktis yang membantu saya memilih metode ODE terbaik dalam pengaturan seperti itu.

Jika, misalnya, $N = 2$ maka kita bisa menyelesaikan IVP menggunakan dua langkah lebar Euler eksplisit $(t_1 - t_0)/2$ atau satu langkah lebar $t_1 - t_0$ menggunakan metode titik tengah. Tidak segera jelas bagi saya mana yang lebih disukai. Untuk lebih besar $N$ , tentu saja orang juga bisa memikirkan metode multi-langkah, skema Runge-Kutta yang diulang, dll.

Apa yang saya cari adalah hasil yang mirip dengan yang ada, misalnya, untuk aturan kuadratur: Kita dapat memilih $n$ bobot $\{w_i\}$ dan titik terkait $\{x_i\}$ sehingga aturan kuadratur $\sum_{i = 1}^n w_i g(x_i)$ tepat untuk semua polinomial $g$ sedemikian sehingga $deg(g) \le 2n - 1$ .

Oleh karena itu saya mencari batas atas atau bawah pada keakuratan global metode ODE, mengingat sejumlah evaluasi yang diperbolehkan dari RHS $f$ . Tidak apa-apa jika batas hanya berlaku untuk beberapa kelas RHS atau menimbulkan kendala tambahan pada solusi $x$ (seperti hasil untuk aturan quadrature yang hanya berlaku untuk polinomial hingga tingkat tertentu).

EDIT: Beberapa informasi latar belakang: Ini untuk aplikasi waktu nyata yang sulit, yaitu hasil $x(t_1)$ harus tersedia sebelum batas waktu yang diketahui. Oleh karena itu batas jumlah evaluasi RHS $N$ sebagai faktor biaya yang mendominasi. Biasanya masalah kita kaku dan relatif kecil.

EDIT2: Sayangnya saya tidak memiliki persyaratan waktu yang tepat, tetapi aman untuk mengasumsikan bahwa akan menjadi agak kecil (pasti <100, lebih mendekati 10). Mengingat persyaratan real-time kami harus menemukan tradeoff antara akurasi model (dengan model yang lebih baik mengarah ke waktu pelaksanaan RHS yang lebih lama dan karenanya ke lebih rendah ) dan keakuratan metode ODE (dengan metode yang lebih baik membutuhkan lebih tinggi nilai-nilai ). $N$ $N$ $N$

ode numerical-analysis Florian Brucker
sumber

Korespondensi biasa dari metode Runge-Kutta langkah tetap dengan metode Newton-Cotes berlaku untuk kasus metode RK yang diterapkan pada IVP ; misalnya, menerapkan metode orde empat klasik untuk IVP yang setara dengan melakukan aturan Simpson pada .

y^{'} = f (x)

$y^\prime=f(x)$

f (x)

$f(x)$

JM

@ JK: Saya tahu itu. Saya hanya bermaksud menggunakan aturan kuadratur sebagai contoh karakterisasi keakuratan metode numerik untuk serangkaian input tertentu ketika jumlah evaluasi fungsi terbatas. Selain itu saya tertarik pada ODE "benar", yaitu yang tidak mengurangi integrasi standar.

Florian Brucker

1

Ini semakin menarik. Sekarang angka dengan sendirinya tidak berarti apa-apa. Yang mungkin bisa membantu adalah mengetahui , di mana adalah panjang interval integrasi dan adalah konstanta Lipschitz dari sehubungan dengan . Ini akan memberi tahu kami seberapa kaku masalahnya sebenarnya. Dengan asumsi itu kaku, kandidat yang mungkin adalah metode BDF urutan ke-2.

N

$N$

λ N / T

$\lambda N/T$

T

$T$

λ

$\lambda$

f

$f$

x

$x$

David Ketcheson

@ Davidvideteson: Saya lebih tertarik pada pendekatan umum untuk memilih metode yang cocok untuk masalah yang diberikan daripada dalam metode optimal untuk masalah tertentu. Kami memiliki sejumlah besar model yang sangat bervariasi dalam persyaratan kekakuan dan waktu.

Florian Brucker

Anda mengatakan bahwa

sangat mahal untuk dievaluasi. Bisakah Anda menghitung Jacobian sama sekali? Bagaimana dengan beberapa pendekatan yang dapat memperbaiki kekakuan prinsip? Anda tidak dalam kondisi yang baik jika masalah Anda sangat kaku dan Anda tidak punya cara untuk memperbaikinya.

f

$f$

Jed Brown

7

Saya pikir referensi kunci untuk menjawab pertanyaan Anda adalah makalah ini oleh Hosea dan Shampine . Sekarang saya akan memberikan latar belakang.

Secara umum, ukuran langkah yang dapat Anda gunakan saat mengintegrasikan IVP secara numerik dapat dibatasi oleh stabilitas atau akurasi. Jika Anda ingin memilih pemecah terbaik dalam hal stabilitas, Anda perlu mempertimbangkan wilayah stabilitas absolut . Untuk metode satu langkah ini

S = {z \in C : | P (z) | \leq 1} .

$S = \{ z \in {\mathbb C} : |P(z)|\le 1\}.$

Di sini adalah fungsi stabilitas dari metode; lihat misalnya teks Hairer et. Al. Kondisi yang diperlukan untuk stabilitas adalah bahwa mana berkisar pada nilai eigen dari jacobian dan adalah ukuran langkah. Ini tidak selalu merupakan kondisi yang cukup untuk masalah nonlinear tetapi biasanya merupakan aturan praktis yang baik dan digunakan dalam praktik. $P(z)$ $\lambda h \in S$ $\lambda$ $f$ $h$

Untuk perawatan yang ekstensif dari masalah menemukan metode (eksplisit) yang memungkinkan ukuran langkah besar yang stabil, lihat makalah ini tentang polinomial stabilitas dan yang ini tentang optimasi metode Runge-Kutta untuk simulasi fluida kompresibel .

Stabilitas adalah masalah yang relevan jika Anda menemukan bahwa ukuran step stabil terbesar sudah memberi Anda cukup akurasi. Di sisi lain, ukuran langkah mungkin dibatasi oleh persyaratan akurasi Anda. Apa yang biasanya dilakukan adalah kontrol kesalahan lokal. Solusinya dihitung dengan menggunakan dua metode, dan perbedaannya digunakan sebagai estimasi kesalahan yang kurang akurat. Ukuran langkah dipilih secara adaptif untuk mencapai sedekat mungkin toleransi yang ditentukan.

Dua ukuran teoritis adalah kunci untuk memprediksi efisiensi akurasi. Yang pertama adalah urutan akurasi metode, yang menggambarkan tingkat di mana kesalahan mendekati nol ketika ukuran langkah diturunkan. Yang kedua adalah indeks efisiensi akurasi (lihat kertas Hosea dan Shampine terkait dalam kalimat pertama di atas) yang memperhitungkan konstanta yang muncul dalam istilah kesalahan dan memungkinkan perbandingan antara metode dengan urutan yang sama.

Keakuratan dan efisiensi stabilitas dari berbagai metode dapat dihitung dengan cara yang sederhana dan otomatis menggunakan NodePy (disclaimer: NodePy dikembangkan oleh saya).

David Ketcheson
sumber

Terima kasih. Makalah karya Hosea dan Shampine ini memang sangat menarik. Apakah Anda tahu hasil yang sama untuk masalah kaku? Saya sadar bahwa orang biasanya menggunakan metode implisit untuk itu, tetapi ini tidak memiliki apriori terikat pada jumlah evaluasi RHS, sehingga mereka tidak banyak berguna dalam kasus saya.

Florian Brucker

Saya tidak tahu hal seperti ini untuk masalah yang sulit, tetapi saya curiga ada sesuatu. Seperti yang Anda katakan, pertanyaannya lebih halus ketika menggunakan metode implisit. Salah satu pendekatan mungkin menggunakan metode Rosenbrock, yang menangani masalah kaku dengan baik tetapi memiliki sejumlah evaluasi RHS.

David Ketcheson

6

Tidak ada banyak hasil dalam arah ini karena lebih sulit daripada hanya memperbaiki akurasi, karena pertimbangan stabilitas seringkali mengharuskan Anda untuk memilih langkah-langkah waktu yang lebih kecil daripada yang Anda perlukan untuk akurasi yang Anda inginkan. Jadi hasilnya dibagi antara kasus yang kaku dan yang tidak kaku. Kasus pertama, langkah-langkah waktu dan persyaratan evaluasi RHS umumnya tidak diatur oleh keakuratan, dan dalam kasus yang terakhir itu.

Saya akan fokus pada metode eksplisit, karena kasus implisit jauh lebih jelas berapa banyak evaluasi RHS yang perlu Anda gunakan .. itu sepenuhnya tergantung pada bagaimana Anda memutuskan untuk menyelesaikan sistem yang dihasilkan.

Untuk sistem yang tidak kaku:

Ada batasan tahapan untuk metode Runge-Kutta eksplisit yang mengatakan berapa banyak tahapan (evaluasi RHS) yang diperlukan untuk mencapai urutan akurasi tertentu. Setelah urutan keempat jumlah tahap melebihi urutan akurasi, dan kesenjangan terus bertambah. Buku ODE besar Butcher: http://books.google.com/books/about/Numerical_Methods_for_Ordinary_Different.html?id=opd2NkBmMxsC

melakukan pekerjaan dengan baik menjelaskan beberapa bukti 'tidak ada' ini.

Contoh aturan kuadratur Anda mengarah ke metode tipe multistep seperti Adams-bashforth, atau apa yang sekarang disebut metode koreksi spektral-tangguhan. Untuk adams-bashforth, Anda hanya memerlukan satu evaluasi RHS per langkah, tetapi karena wilayah stabilitas pada umumnya kecil untuk metode ini, Anda biasanya melakukan pekerjaan yang sama dalam hal evaluasi RHS seperti metode Runge-Kutta dengan metode yang sama. memesan.

Berikut adalah makalah tentang koreksi tangguhan spektral:

https://www.google.com/search?q=spectral+deferred+correction&aq=f&oq=spectral+deferred+correction&aqs=chrome.0.57j0l2j62.3336j0&sourceid=chrome&ie=UTF-8

Saya tidak yakin bagaimana metode integrasi ini bermain melawan metode eksplisit standar, mereka sering membutuhkan lebih banyak memori untuk menyimpan status solusi pada node quadrature dan jadi saya tidak pernah menggunakannya sendiri.

Untuk sistem yang kaku:

$S$ $2S^2$ $S-1$ $S$

Reid.Atcheson
sumber

2

Dapat terjadi bahwa menggunakan metode langkah variabel (atau bahkan urutan variabel) mungkin lebih efisien daripada berpegang teguh pada metode langkah tetap. Misalnya, seseorang dapat mempertimbangkan untuk menggunakan metode ekstrapolatif seperti Bulirsch-Stoer: melakukan beberapa evaluasi pada beberapa langkah, dan kemudian membangun (seolah-olah) perkiraan yang lebih akurat dari hasil langkah-langkah tersebut.

JM

Benar. Sebenarnya banyak metode optimal yang setara dalam beberapa hal dengan versi langkah variabel dari stepper waktu lain. Runge-Kutta-Chebshev misalnya dapat dilihat sebagai forward Euler yang diterapkan dengan variabel time-step menjadi poin Chebyshev.

Reid.Atcheson

@ JM: Tepat. Tetapi apakah ada cara untuk menilai keakuratan pendekatan ini dengan jumlah evaluasi RHS, selain dari eksperimen numerik (yang akan sangat terlibat, mengingat banyaknya kemungkinan pendekatan)?

Florian Brucker

@Florian, tidak secara umum. Anda pernah mendengar tentang persamaan Lorenz, saya kira?

JM

1

@ JP: Ya :) Itu sebabnya saya menyebutkan contoh quadrature, di mana akurasi diukur dengan subset (polinomial) dari ruang masalah asli. Saya akan senang dengan hasil yang hanya bekerja untuk sebagian masalah.

Florian Brucker

3

$10^{-14}$ $f(x)$

Tentu saja ada pengecualian (sistem yang sangat besar, sistem yang sangat kaku) tetapi sentimen umum di masyarakat adalah bahwa pertanyaan merancang pemecah ODE untuk sistem "standar" adalah yang dipecahkan. Akibatnya, saya pikir pertanyaan yang Anda ajukan bukanlah pertanyaan yang sangat menarik - pertanyaan ini membahas komponen desain pemecah ODE yang tidak lagi penting. Ini juga dapat menjelaskan kurangnya literatur tentang masalah ini.

Wolfgang Bangerth
sumber

+1. Setiap kali seseorang bertanya tentang pemecah ODE yang efisien, saya hanya berasumsi mereka tertarik pada sistem ODE besar yang berasal dari semi-diskretisasi PDE atau masalah n-tubuh yang besar.

David Ketcheson

Bisakah Anda jelaskan bagaimana hubungannya dengan pertanyaan saya? Saya tidak melihat hubungannya, karena saya tertarik pada kasus di mana evaluasi f(x)tidak gratis tetapi agak mahal sehingga jumlah evaluasi terbatas.

Florian Brucker

@ Davidvideteson: Ini tidak terjadi di sini. Ini lebih karena kami memiliki persyaratan waktu yang sangat ketat (waktu nyata keras) pada perangkat keras yang lemah (perangkat yang disematkan). Sistem ODE sendiri relatif kecil.

Florian Brucker

N

$N$

N

$N$

N

$N$

N

$N$

N

$N$

N

$N$

N < 1000

$N<1000$

1

$O(\mathit{dim}^3)$ $O(\mathit{dim}^2)$

Jadi poin pertama adalah memastikan apakah RHS Anda benar-benar lebih mahal daripada aljabar linier yang mendasarinya.

Poin kedua: diketahui dari literatur bahwa solver berdasarkan metode "mahal" (yaitu metode RK eksplisit) kadang-kadang berkinerja lebih cepat daripada yang "lebih murah" (metode multistep eksplisit).

Kesimpulannya, saya pikir Anda tidak hanya mempertimbangkan hitungan evaluasi RHS.

faleichik
sumber

N

$N$

Metode ODE optimal untuk evaluasi RHS dengan jumlah tetap

Jawaban: