Apakah mungkin untuk menyelesaikan PDE nonlinier tanpa menggunakan iterasi Newton-Raphson?

Saya mencoba memahami beberapa hasil dan akan menghargai beberapa komentar umum tentang penanganan masalah nonlinier.

Persamaan Fisher (PDE reaksi-difusi nonlinier),

u_{t} = d u_{x x} + β u (1 - u) = F (u)

$u_t = du_{xx} + \beta u (1 - u) = F(u)$

dalam bentuk diskrit,

u_{j}^{'} = L u + β u_{j} (1 - u_{j}) = F (u)

$u_j^{\prime} = \boldsymbol{L}\boldsymbol{u} + \beta u_j (1 - u_j) = F(\boldsymbol{u})$

di mana $\boldsymbol{L}$ adalah operator diferensial dan $\boldsymbol{u}=(u_{j-1}, u_j, u_{j+1})$ adalah stensil diskretisasi.

metode

Saya ingin menerapkan skema implisit karena saya memerlukan stabilitas dan langkah waktu yang tidak dibatasi. Untuk tujuan ini saya menggunakan $\theta$ -metode, (catatan bahwa $\theta=1$ memberikan skema sepenuhnya implisit dan $\theta=0.5$ memberikan trapesium atau "Crank-Nicolson" skema),

u_{j}^{'} = θ F (u^{n + 1}) + (1 - θ) F (u^{n})

$u_{j}^{\prime} = \theta F(\boldsymbol{u}^{n+1}) + (1-\theta) F(\boldsymbol{u}^{n})$

Namun, untuk masalah nonlinier ini tidak dapat dilakukan karena persamaan tidak dapat ditulis dalam bentuk linier.

Untuk mengatasi masalah ini, saya telah menjelajahi dua pendekatan numerik,

Metode IMEX

$u_{j}^{'} = \underset{θ - method diffusion term}{\underset{⏟}{θ L u^{n + 1} + (1 - θ) L u^{n}}} + \underset{Fully explicit reaction term}{\underset{⏟}{β u_{j}^{n} (1 - u_{j}^{n})}}$ $u_j^{\prime} = \underbrace{\theta\boldsymbol{L}\boldsymbol{u^{n+1}} + (1-\theta)\boldsymbol{L}\boldsymbol{u^{n}}}_{\theta-\text{method diffusion term}} + \underbrace{\beta u_j^{n} (1 - u_j^{n})}_{\text{Fully explicit reaction term}}$
Rute yang paling jelas adalah dengan mengabaikan bagian nonlinear dari istilah reaksi dan memperbarui istilah reaksi dengan nilai terbaik, yaitu dari langkah waktu sebelumnya. Ini menghasilkan metode IMEX.
Pemecah Newton

ν^{k + 1} = ν^{k} - (I - θ τ A^{n})^{- 1} (ν^{k} - u_{n} - (1 - θ) τ F (w^{n}) - θ τ F (w^{n + 1}))

$\nu^{k+1} = \nu^{k} - (I - \theta\tau A^{n})^{-1} \left( \nu^{k} - u_{n} - (1-\theta) \tau F(w^n) - \theta\tau F(w^{n+1}) \right)$

Persamaan -metode penuh dapat diselesaikan dengan menggunakan iterasi Newton-Raphson untuk menemukan variabel solusi masa depan. Di mana adalah indeks iterasi ( ) dan adalah matriks Jacobian dari . Di sini saya menggunakan simbol untuk iterasi variabel seperti bahwa mereka dibedakan dari solusi persamaan pada waktu titik nyata . Ini sebenarnya adalah pemecah Newton yang dimodifikasi karena Jacobian tidak diperbarui dengan setiap iterasi. $\theta$ $k$ $k\geq0$ $A^{n}$ $F(w^n)$ $\nu^{k}$ $u^n$

Hasil

Perbandingan persamaan Fisher dari metode numerik.

Hasil di atas dihitung untuk langkah waktu yang cukup besar dan mereka menunjukkan perbedaan antara pendekatan stepping waktu dan pemecah iterasi Newton penuh.

Hal yang tidak saya mengerti:

Saya terkejut bahwa metode loncatan waktu tidak "OK" tetapi akhirnya tertinggal di belakang solusi analitis seiring berjalannya waktu. ( NB jika saya telah memilih langkah waktu yang lebih kecil maka pendekatan loncatan waktu memberikan hasil yang tertutup bagi model analitis). Mengapa pendekatan loncatan waktu memberikan hasil yang masuk akal untuk persamaan nonlinier?
Model Newton melakukan jauh lebih baik, tetapi mulai memimpin model analitis seiring berjalannya waktu. Mengapa keakuratan pendekatan Newton menurun seiring waktu? Bisakah akurasi ditingkatkan?
Mengapa ada fitur umum yang setelah banyak iterasi maka model numerik dan model analitis mulai menyimpang? Apakah ini hanya karena langkah waktu terlalu besar atau akankah ini selalu terjadi?

numerical-analysis nonlinear-equations implicit-methods newton-method explicit-methods Boyfarrell
sumber

Saya sarankan membaca analisis kesalahan dasar pemecah ODE, misalnya di Hairer / Nørsett / Wanner, ditambah beberapa analisis stabilitas. Sebagian besar pertanyaan Anda akan dijawab saat itu.

Guido Kanschat

@boyfarrell, untuk menghindari kebingungan sesama pembaca, Anda harus meletakkan terminologi tepat di tempat menjelaskan metode Anda: 1. IMEX - eksplisit dalam nonlinier dan tersirat di bagian linier. 2. ini adalah skema standar

, yang biasanya membutuhkan metode Newton untuk menyelesaikan pembaruan

θ

$\theta$

Jan

Halo, saya pikir saya punya segalanya. Sekali lagi terima kasih atas bantuan Anda.

boyfarrell

Jawaban:

Saya berasumsi, bahwa Anda telah melakukan diskritisasi ruang, sehingga Anda akan menyelesaikan ODE (bernilai vektor) melalui skema numerik yang memajukan perkiraan pada contoh waktu saat ini ke nilai selanjutnya

{\dot{u}}_{h} (t) = F_{h} (t, u_{h} (t)), on [0,T], u_{h} (0) = α .

$\dot u_h(t) = F_h(t,u_h(t)), \text{ on [0,T] }, u_h(0) = \alpha.$

Φ

$\Phi$

u_{h}^{n}

$u_h^n$

t = t^{n}

$t=t^n$

pada

u_{h}^{n + 1}

$u_h^{n+1}$

t = t^{n + 1} := t^{n} + τ

$t=t^{n+1}:=t^n+\tau$

Kemudian pertanyaan Anda merujuk ke properti eksplisit , di mana pembaruan ditulis sebagai

u_{h}^{n + 1} = u_{h}^{n} + Φ_{e} (t^{n}, τ, u_{h}^{n}),

$u_h^{n+1} = u_h^n + \Phi_e(t^n,\tau,u_h^n),\quad \quad \quad$

u_{h}^{n + 1} = u_{h}^{n} + Φ_{i} (t^{n}, τ, u_{h}^{n + 1}, u_{h}^{n}), (*)

$u_h^{n+1} = u_h^n + \Phi_i(t^n,\tau,u_h^{n+1},u_h^n), \quad \quad \quad (*)$

atau kombinasi keduanya (' IMEX ', lihat jawaban @Jed Brown) skema loncatan waktu satu langkah.

$u_h^{n+1}$ $(*)$

Dan jawaban saya berdasarkan hasil dari analisis numerik metode satu langkah.

$F_h$
Anda dapat menemukan contoh, di mana skema eksplisit berkinerja lebih baik. (Secara teoritis, Anda dapat membalik waktu dalam contoh Anda, mulai dari nilai terminal, dan menemukan implisit dan eksplisit dipertukarkan.) Jika Anda membuat kesalahan Newton cukup kecil, Anda masih dapat meningkatkan akurasi dengan mengurangi langkah-waktu atau dengan menggunakan waktu Skema -langkah lebih tinggi.
$C$ $err \approx C \tau^p$ $p>0$ $\tau$

Beberapa komentar dan jawaban terakhir:

Skema IMEX dapat digunakan untuk memperlakukan hanya bagian linier secara implisit apa yang menghindari pemecahan nonlinier. Lihat jawaban Jed Brown.
$u_{h}^{n + 1} = Φ_{m} (t^{n}, τ, u_{h}^{n + 1}, u_{h}^{n}, u_{h}^{n - 1}) .$ $u_h^{n+1} = \Phi_m(t^n,\tau,u_h^{n+1},u_h^n,u_h^{n-1}).$

$(*)$ seperti iterasi titik tetap atau, dalam kasus tertentu, pemecah aljabar.

Jan
sumber

Ya, saya telah menerapkan stensil perbedaan pusat standar untuk istilah difusi. Saya tidak dapat menggunakan skema eksplisit (untuk masalah nyata yang ingin saya selesaikan) karena langkah waktu yang stabil sangat kecil dan tidak realistis. Inilah sebabnya saya menjelajahi opsi IMEX atau implisit. Mengenai poin ketiga Anda, untuk menghindari akumulasi kesalahan saya harus menggunakan metode multistep. Apakah skema Crank-Nicolson yang saya gunakan di atas (dengan Newton solver) digolongkan sebagai metode multistep (memiliki dua titik waktu)? Saya terkejut kesalahan bertambah seiring waktu ketika menggunakan metode Newton solver.

boyfarrell

Crank-Nicolson adalah metode langkah tunggal, seperti yang tertulis

u_{h}^{n + 1} = u_{h}^{n} + Φ (t^{n}, τ^{n}, u_{h}^{n}, u_{h}^{n + 1})

$u_h^{n+1}=u_h^n + \Phi(t^n,\tau^n,u_h^n,u_h^{n+1})$ . Juga, saya tidak melihat mengapa skema multi-langkah harus menghindari akumulasi kesalahan.

Jan

OK terima kasih sudah menjelaskan tentang metode CN. Ya, itu menarik mengapa metode multistep tampaknya memiliki akumulasi kesalahan yang lebih rendah. Alasan bahwa pemecah Newton memiliki kesalahan membangun adalah karena ini adalah metode langkah tunggal, saya mengerti sekarang. Ngomong-ngomong, aku tahu kamu suka Python. Saya melakukan semua hal di atas menggunakan scipy, numpy dan matplotlib, gist.github.com/danieljfarrell/6353776

boyfarrell

Saya telah menghapus tautan ke kertas oleh Trefethen et. Al. pada integrasi IMEX tingkat tinggi dari jawaban saya karena ada referensi yang lebih baik untuk belajar tentang skema IMEX.

Jan

Jawaban singkat

Jika Anda hanya menginginkan akurasi urutan kedua dan tidak ada estimasi kesalahan yang disematkan, kemungkinan besar Anda akan senang dengan Strang splitting: setengah langkah reaksi, langkah penuh difusi, setengah langkah reaksi.

Jawaban panjang

Difusi-reaksi, bahkan dengan reaksi linier, terkenal karena menunjukkan kesalahan pemisahan. Memang, itu bisa jauh lebih buruk, termasuk "konvergen" ke kondisi mapan yang salah, kondisi mapan salah untuk siklus batas, bingung konfigurasi stabil dan tidak stabil, dan banyak lagi. Lihat Ropp, Shadid, dan Ober (2004) dan Knoll, Chacon, Margolin, dan Mousseau (2003) untuk perspektif fisikawan komputasi dalam hal ini. Untuk analisis matematis dalam hal kondisi pesanan, lihat Hairer dan Wanner buku tentang ODE yang kaku (metode Rosenbrock-W adalah metode IMEX linear-implisit), Kennedy dan Carpenter (2003) untuk aditif IMEX "aditif" non-linear Runge-Kutta, dan halaman Emil Constantinescu untuk metode IMEX yang lebih baru.

Secara umum, metode IMEX memiliki lebih banyak kondisi pesanan daripada metode implisit dan eksplisit yang mendasarinya saja. Pasangan metode IMEX dapat dirancang dengan stabilitas linier dan nonlinier yang diinginkan dan sehingga mereka memenuhi semua kondisi pesanan hingga urutan desain metode. Memuaskan semua kondisi pesanan akan menjaga kesalahan pemisahan asimptotik dari skala yang sama dengan kesalahan dalam setiap skema secara terpisah. Ia mengatakan apa-apa tentang rezim pra-asimptotik (langkah waktu besar / persyaratan akurasi rendah), tetapi jarang lebih ketat daripada resolusi setiap bagian secara terpisah. Dalam setiap kasus, kesalahan pemisahan dapat dilihat oleh penaksir kesalahan tertanam (saat menggunakan kontrol kesalahan adaptif).

PETSc memiliki banyak metode IMEX dari keluarga Rosenbrock-W dan aditif Runge-Kutta , dan akan memiliki ekstrapolasi dan IMEX multistep linier dalam rilis kami berikutnya.

Penafian: Saya menulis banyak dukungan integrasi waktu PETSc dan berkolaborasi dengan Emil (ditautkan di atas).

Jed Brown
sumber

Saya tentu saja mendekati ini dari perspektif fisika sehingga semua detail teknis memerlukan waktu untuk saya ikuti karena saya tidak terbiasa dengan banyak istilah. Saya sebenarnya seorang pencoba! Apakah Anda akan menjelaskan sedikit lebih banyak tentang ketentuan pesanan? IMEX apakah metode multistep ini disebutkan oleh Jan?

boyfarrell

Kondisi pesanan adalah hubungan antara koefisien metode ODE (misalnya, entri dalam tablo Butcher untuk metode Runge-Kutta) yang harus dipenuhi untuk memiliki urutan akurasi. Kondisi pesanan dibahas dalam buku atau kertas apa pun yang merancang metode integrasi ODE, tetapi pada dasarnya sama dengan menerapkan turunan dan istilah yang cocok secara berulang dalam ekspansi Taylor. Jumlah kondisi pesanan tumbuh dengan cepat untuk metode tingkat tinggi, itulah sebabnya mengapa menjadi sulit untuk merancang metode tingkat tinggi. Hambatan dibuat dengan menunjukkan bahwa kondisi pesanan tidak saling kompatibel.

Jed Brown