Simultan ruang-waktu solusi wavelet adaptif

Simultan ruang-waktu solusi wavelet adaptif
persamaan diferensial nonlinier parabolik
Jahrul M. Alam sebuah, Nicholas K.-R. Kevlahan sebuah, *, Oleg V. Vasilyev b
Abstrak
Dinamis adaptif metode numerik telah dikembangkan untuk secara efisien menyelesaikan persamaan diferensial yang solusi
yang terputus-putus di kedua ruang dan waktu. Metode ini menggabungkan langkah waktu disesuaikan dengan grid spasial yang menyesuaikan dengan
spasial intermittency pada waktu yang tetap. Langkah waktu yang sama digunakan untuk semua lokasi spasial dan semua skala: pendekatan ini jelas
tidak sepenuhnya mengeksploitasi intermittency ruang-waktu. Kami mengusulkan metode wavelet kolokasi adaptif untuk memecahkan sangat
intermittent masalah (turbulensi misalnya) pada domain komputasi simultan ruang-waktu yang secara alami beradaptasi baik
resolusi ruang dan waktu untuk mencocokkan solusi. Selain menghasilkan grid yang optimal dekat untuk solusi ruang-waktu penuh,
pendekatan ini juga memungkinkan integrasi global time error harus dikontrol. Efisiensi dan keakuratan metode ini
ditunjukkan dengan menerapkannya pada beberapa sangat intermittent (t 1D +)-dimensi dan (2D + t) masalah uji-dimensi.
Secara khusus, kami menemukan bahwa metode ruang-waktu menggunakan sekitar 18 kali lebih sedikit titik ruang-waktu grid dan kira-kira 4
kali lebih cepat dari waktu yang jelas dinamis adaptif berbaris metode, sedangkan mencapai akurasi global serupa.
? 2005 Elsevier Inc All rights reserved.
Kata kunci: wavelet, skema Lifting; wavelet generasi kedua; persamaan diferensial parsial, masalah Elliptic, grid Adaptif; Numerik
metode; Multi-level metode; Multi-metode grid
1. Pengantar
Pemodelan matematika masalah dalam sains dan teknik (turbulensi misalnya, reaktif atau non-reaktif
arus [1]) biasanya melibatkan memecahkan persamaan diferensial parsial nonlinier (PDEs). Beragam spasial
dan skala temporal seringkali harus diselesaikan dalam rangka untuk benar memecahkan persamaan [2]. Namun, di banyak
situasi timbangan spasial kecil sangat lokal, dan dengan demikian solusi yang efisien dari masalah memerlukan
grid adaptasi lokal. Sebuah grid seragam baik jelas tidak efisien untuk masalah seperti itu. Turbulensi adalah terkenal
contoh masalah dengan intermittency tinggi [3,4]. Dalam turbulensi bilangan Reynolds yang tinggi jumlah
skala derajat kebebasan seperti kubus bilangan Reynolds, Re3, dalam sebuah mesh seragam yang menyelesaikan struktur aktif terkecil dalam ruang dan waktu [5]. Karena turbulensi biasanya terjadi pada bilangan Reynolds yang tinggi (misalnya Re? 106
untuk aliran penerbangan khas), jelas bahwa setiap simulasi numerik sukses langsung (DNS) dari turbulensi
harus mengambil keuntungan dari aliran? s intermittency tinggi [6,7]. Karena intermittency ini, kami berharap bahwa
jumlah minimum elemen komputasi yang dibutuhkan adalah sebenarnya jauh lebih kecil dari Re3.
Baru-baru ini telah ada peningkatan minat mengembangkan adaptif [8-15] metode numerik untuk memecahkan
eliptik [16-20] dan waktu bergantung [21-35] persamaan diferensial parsial. Ada metode numerik adaptif
jatuh ke dalam dua kelas: indikator kesalahan berdasarkan (dimana grid yang disempurnakan untuk menyelesaikan gradien dari fisik yang relevan
kuantitas), dan kontrol kesalahan berdasarkan (di mana kesalahan diperkirakan dan grid yang disempurnakan untuk memastikan kesalahan ini kurang
dari toleransi yang ditentukan). Strategi menunjukkan kesalahan-kesalahan tidak mengendalikan secara langsung, melainkan kontrol
mesh pengkasaran dan halus. Strategi kesalahan memperkirakan meminimalkan kesalahan yang diukur dalam
sesuai norma, yang mengarah ke distribusi ukuran mesh yang optimal.
Wavelet telah terbukti menjadi alat yang efisien dalam pengembangan metode numerik adaptif yang mengendalikan
global (biasanya L2) kesalahan aproksimasi [17,18,21,24,26,35]. Tujuan dari gabungan kata-kata wavelet nonlinear berbasis
pendekatan adalah untuk memperoleh pendekatan yang terbaik dari suatu fungsi pada grid optimal dekat. kolokasi ini
pendekatan memiliki korespondensi satu-ke-satu antara koefisien wavelet ekspansi dan titik-titik grid.
Dengan demikian, nonlinier penyaringan koefisien wavelet secara otomatis memurnikan komputasi grid. Karena fungsi
dan operator dapat dihitung dengan akurasi yang diberikan, metode wavelet adaptif menyediakan kontrol kesalahan global
adaptif untuk solusi persamaan diferensial.
Liandrat dan Tchamitchian [21] mengusulkan metode adaptif pertama berbasis wavelet diferensial parsial
persamaan. Sampai karya Sweldens [36], upaya penelitian difokuskan pada penekanan kedua diferensial
operator dan solusi menggunakan proyeksi Galerkin. Pekerjaan awal yang ditemukan [37-39] mendemonstrasikan
penggunaan wavelet untuk mencari solusi numerik dari PDEs dengan kondisi batas periodik. Galerkin berbasis
wavelet metode untuk masalah linear eliptik dipelajari dalam [16,40-42]. Schneider [43] digunakan handal dan efisien
kesalahan aposteriori perkiraan untuk adaptif skema wavelet-Galerkin multi-skala untuk PDEs elips linier.
Kesalahan dicapai dengan skema wavelet adaptif [16,17,19] adalah sebanding dengan error terkecil diwujudkan dengan
aproksimasi wavelet, yaitu skema ini adalah asimtotik optimal untuk masalah eliptik [20]. Selain itu,
metode wavelet adaptif yang cepat (setidaknya untuk masalah besar) karena skala kompleksitas komputasi
seperti jumlah wavelet dipertahankan dalam pendekatan, OðNÞ.
Skema Adaptive wavelet juga telah digunakan untuk menyelesaikan persamaan waktu tergantung diferensial parsial
[21,22]. Sebuah penurunan yang lebih rinci yang cepat dan algoritma adaptif, proyeksi dari solusi dan spasial
derivatif pada ruang wavelet, hubungan antara kekurangan dari sistem diskretisasi dan menghilang
saat milik wavelet dikembangkan oleh Beylkin dan [29] Keiser. Debussche et al. [44] mengembangkan
multi-level-Galerkin fourier metode untuk turbulensi homogen. Kesulitan utama dari Galerkin berbasis
wavelet adalah perhitungan efisien operator nonlinier, dan penerapan umum
kondisi batas. Kesulitan-kesulitan ini menyebabkan pengembangan metode kolokasi berbasis metode wavelet adaptif,
misalnya [25,26,28]. Setelah pendekatan multi-resolusi kedua-generasi Sweldens [45], tingkat multi-
wavelet metode kolokasi adaptif dikembangkan oleh Vasilyev dan Bowman [34], yang diterapkan pada
berbagai masalah masalah nilai awal [35]. The kolokasi adaptif metode wavelet (AWCM)
sejak itu telah digunakan untuk membangun pemecah multi-level eliptik adaptif [46], simulasi dua dan tiga dimensi
cairan-struktur interaksi [47-49], dan alternatif wavelet berbasis simulasi eddy besar [50].
Untuk yang terbaik dari pengetahuan kami, semua metode wavelet yang ada untuk masalah waktu tergantung mengadaptasi spasial
grid dinamis di wilayah intermittency. Ini berarti bahwa perbaikan mesh atau pengkasaran otomatis jika
solusi mengembangkan gradien kuat, atau jika gradien menyebar. Jika solusi itu intermiten dalam ruang baik
dan waktu, satu adaptasi mesh spasial untuk solusi pada waktu yang tetap dan menggunakan langkah waktu disetel untuk mengendalikan
kesalahan lokal dalam waktu [22]. Pendekatan ini memberlakukan langkah waktu yang sama untuk semua lokasi spasial, yang jelas
tidak optimal untuk masalah-masalah yang intermiten secara simultan di kedua ruang dan waktu.
Setelah waktu klasik marching teknik, metode wavelet adaptif discretizes PDE untuk menghasilkan
sistem Odes dengan koefisien wavelet sebagai tidak diketahui tergantung waktu (dalam formulasi Galerkin), atau
nodal perkiraan sebagai tidak diketahui bergantung waktu dalam pendekatan kolokasi. Metode ini mengadaptasi spasial
grid sebagai guncangan atau struktur lokal mengembangkan atau bergerak dalam larutan tergantung waktu. Waktu dinamis disesuaikan melangkah prosedur menentukan langkah waktu maksimum untuk grid spasial diadaptasi,
atau untuk semua mode wavelet, pada setiap instan. Namun, meskipun kesalahan spasial dikontrol oleh wavelet pendekatan adaptif, kesalahan global dalam waktu yang tidak terkontrol. Tidak ada jaminan bahwa pemotongan temporal
kesalahan tidak akan terakumulasi dari waktu ke waktu dan akhirnya melebihi toleransi kesalahan yang diinginkan. Seringkali kita perlu
mengintegrasikan PDE untuk periode waktu yang panjang secara sewenang-wenang. Pengaruh palsu dari akumulasi kesalahan dapat menyebabkan
hasil perhitungan menjadi tidak dapat diandalkan, meskipun kesalahan spasial dikendalikan pada setiap langkah waktu.
Dua pendekatan telah diusulkan untuk mengendalikan kesalahan global dalam waktu. Yang pertama adalah integrator variasional
Pendekatan yang dikembangkan oleh Marsden dan rekan kerja [51-56], dimana time error integrasi global
berkurang secara signifikan sehingga undang-undang konservasi yang sesuai puas dalam toleransi yang diinginkan
untuk kali sewenang-wenang. Contoh dari pendekatan kedua adalah karya terbaru Tremblay et al. [57] yang menggunakan
formulasi ruang-waktu waktu-kontinu elemen hingga. Namun cara ini, tidak menggunakan grid otomatis
adaptasi dalam domain komputasi ruang-waktu.
Dalam tulisan ini, kami mengembangkan AWCM ruang-waktu simultan untuk PDEs tergantung waktu. Tujuan kami adalah untuk
mengatasi dua kelemahan metode numerik saat ini disebutkan di atas: ketidakefisienan menggunakan satu
langkah waktu untuk semua lokasi spasial, dan kurangnya kontrol dari kesalahan global dalam waktu. Ruang simultan-
solusi wavelet waktu adaptif harus menghasilkan solusi yang akurat untuk kali sewenang-wenang pada ruang dekat-optimal-
waktu grid.
Makalah ini disusun sebagai berikut. Pada Bagian 2, kita meninjau secara singkat AWCM tersebut. Bagian 3 menjelaskan diusulkan
metode numerik. Ide dibalik teknik integrasi waktu wavelet berbasis Odes dan
ruang-waktu integrasi teknik untuk PDEs dijelaskan dalam Bagian 3.2 dan 3.3. Bagian 3.6 menguraikan wavelet-
berdasarkan kerangka aproksimasi penuh (FAS) kami telah dikembangkan untuk memecahkan masalah aljabar nonlinier
yang dihasilkan dari diskritisasi penuh dari PDE tergantung waktu. Pada Bagian 3.8, kami menjelaskan cara membelah
domain ruang-waktu ke dalam subdomain dalam dimensi waktu. Hal ini memungkinkan untuk perhitungan lebih lama sewenang-wenang
kali mengingat sumber daya komputasi yang tersedia. Dalam Pasal 4, kami mempresentasikan hasil eksperimen numerik
menggunakan persamaan (1D + t) Burgers dan (2D + t) persamaan vortisitas untuk memverifikasi efisiensi
dan akurasi metode numerik yang diusulkan. Kami meringkas kertas dan mendiskusikan arah penelitian masa depan
dalam Bagian 5.
2. adaptif generasi kedua wavelet diskritisasi dari PDEs
AWCM kami didasarkan pada wavelet generasi kedua yang dikembangkan oleh Sweldens [45,58,59], dan kami akan mempertimbangkan
nilai umum masalah batas dalam bentuk:
Lu ¼ f di X; ð1Þ
Bu ¼ g oX; ð2Þ
dimana L adalah operator diferensial parsial umum dan B merupakan operator yang mendefinisikan kondisi batas yang tepat.
X adalah domain ruang-waktu seperti yang
X ¼ D? D0; Þ T; ð3Þ
di mana D? Rn, T 2 r, X adalah terbuka, terhubung, dan dibatasi diset dengan batas oX, yaitu X ¼ X [oX.? Titik di
? X
dilambangkan dengan x ¼ FX1, x2;. . . , Xn; xnþ1gT. Jika n = 0, maka X ¼ ½ 0;? T? adalah suatu interval tertutup. Ketika n = 1, kita akan
menggunakan (x, t) 2 X untuk menunjukkan poin dalam X. Kami akan menganggap bahwa semua fungsi dari L2 fungsi ruang (X)
kecuali dinyatakan lain.
2.1. Multi-skala dekomposisi
Dalam pendekatan multi-resolusi generasi kedua, fungsi yang didekati menggunakan produk tensor
wavelet generasi kedua yang dibangun pada himpunan bersarang (GJ GJ +1?) titik kolokasi
GJ ¼ xj
k 2 X:? xj
k ¼ xjþ1
2k; k 2 Kj; j 2 Z
? ?
; Ð4Þ
dimana k menunjukkan posisi, j menunjukkan tingkat atau skala, dan xj
k adalah poin kolokasi dalam? X dengan n = 0.
Berikut Z dan Kj adalah beberapa set indeks yang sesuai. Perhatikan bahwa titik kolokasi xj
k dapat didistribusikan secara merata,
xj
¼ k 2 jk,? atau non-seragam [34].
Dengan demikian, metode wavelet adaptif menggabungkan wavelet generasi kedua cepat mengubah dengan beda hingga
aproksimasi turunan. Untuk fungsi intermiten, jumlah pointsNis gabungan kata-kata yang aktif
minimal (lihat [19,60,20]). Biaya komputasi menghitung derivatif hanya OðNÞ, yang sama
sebagai biaya komputasi transformasi wavelet. Ketepatan dan efisiensi adaptif mengangkat interpolasi
diferensiasi wavelet diperiksa oleh Vasilyev [35]. Pada grid seragam, teknik ini konsisten dengan
standar stensil beda hingga.
2.4. Analytical kesalahan estimasi
Mari kita memotong jumlah (5) di tingkat J dan menentukan sisa pemotongan oleh
RJ ðxÞ ¼ uðxÞ? UJ ðxÞ. ð10Þ
Dalam multi-level wavelet aproksimasi fungsi dan turunannya, kesalahan tergantung pada wavelet thresholding
Parameter? dan urutan wavelet [61]. Karena korespondensi satu-ke-satu antara wavelet
dan titik kolokasi, seseorang dapat berhubungan error dengan titik-titik grid aktif. Fitur yang paling penting
adalah bahwa kesalahan aproksimasi memiliki kontrol global di seluruh domain. Untuk fungsi cukup mulus
u (x), kita bisa menemukan? sehingga jdj
k <j? 8j PJ dan sehingga sisa pendekatan di tingkat atas J
dibatasi sebagai [61]
jrJ ðxÞj? ;?? ! 0. ð11Þ
Eq. (11) tidak tergantung pada dimensi masalah. Karena jumlah poin gabungan kata-kata yang aktif
tergantung pada dimensi dan urutan wavelet yang digunakan, kita dapat menunjukkan bahwa jumlah koefisien aktif
memenuhi
N? ?? N = p;?! 0; ð12Þ
dimana p adalah urutan wavelet digunakan dan n adalah dimensi tersebut. Dengan kata lain, kesalahan pemotongan terkait
dengan jumlah saldo istilah
krJ ðxÞk2 N p = n??;?! 0. ð13Þ
Ketepatan prosedur diferensiasi telah diperiksa oleh Vasilyev dan Bowman [34] untuk satu dimensi
kasus dan oleh Vasilyev [35] untuk kasus multi-dimensi. Kesalahan dalam pendekatan adaptif wavelet
instrumen ini
kDmx
iuðxÞ? Dmx
iuj
???? ÐxÞk2 N Dp mth n =;?! 0; ð14Þ
dimana DMX
i singkatan turunan dari m urutan arah xi.
3. Usulan metode numerik
3.1. Latar belakang dan motivasi
Mari kita mempertimbangkan masalah nilai umum parabola awal:
du
dt
¼ Fðu; ke-/; u 2 Rn; t 2 D0; T Þ; ð15Þ
uð0Þ ¼ u0; ð16Þ
dimana F merupakan fungsi apapun (biasanya nonlinier). Dalam skema waktu-berbaris klasik, kami membagi
interval [0, T] ke N-interval sub seperti yang NDT = tn, di mana Dt adalah lebar dari masing-masing sub-interval.
Kami mempertimbangkan [tn, tn +1] sub-interval tunggal, untuk n beberapa, dan menganggap u bahwa pada t = tn dikenal. Menggunakan cocok
metode numerik (misalnya maju perbedaan waktu), kita dapat menghitung u pada t = tn +1 dan ulangi untuk selang berikutnya
[Tn +1, +2 tn]. Dengan demikian, dimulai dengan nilai awal, kami berbaris maju dalam waktu untuk menghitung solusi di
setiap lokasi temporal diskrit. Dengan kata lain, kita memecahkan urutan masalah aljabar, masing-masing
yang didefinisikan sebuah sub-interval [0, T] Dua kesulitan utama timbul. dalam waktu berbaris skema. Pertama, kesalahan pemotongan terakumulasi dalam waktu.
Mari kita berasumsi bahwa kesalahan pemotongan lokal skema adalah O (DTA). Kemudian kesalahan global setelah langkah waktu N
adalah O (DTA 1?), dimana diasumsikan bahwa N? 1/Dt. Namun, mudah untuk melihat bahwa kesalahan global dapat menjadi sewenang-wenang
besar jika N? 1/Dt. Mengurangi langkah waktu mengurangi kesalahan secara lokal, tapi tidak memberikan error control global
[62]. Sebagai contoh, jika kita mempertimbangkan skema dengan 2 = dan Dt = 10? 2, kami berharap kesalahan global pada akhir
102 langkah waktu (yakni N? 1/Dt) menjadi O (10? 2). Kesalahan ini akan O (1) setelah 104 langkah waktu-, jika kita terus berjalan.
Jelas, mengurangi langkah waktu akan mengurangi kesalahan hanya lokal: kesalahan integrasi waktu akan terus
menumpuk. Kedua, proses ini menggunakan langkah waktu yang sama untuk semua komponen u 2 Rn meskipun masalah
mungkin memiliki beberapa skala waktu. Ketika masalah (15) - (16) tidak linier, tidak ada cara sederhana untuk mengadopsi
melangkah sehingga komponen yang berbeda langkah-langkah menggunakan u waktu yang berbeda tidak seragam waktu. Konvensional
dinamis disesuaikan waktu prosedur melangkah hanya menentukan langkah waktu maksimum pada setiap tertentu
waktu; itu tidak menyelesaikan skala waktu alami dari sistem dinamik yang mengatur. Tujuan kami di
berikut ini adalah untuk mengembangkan metode AWCM berbasis alamat kedua masalah: error control global
dalam waktu dan waktu setempat melangkah.
3.2. Wavelet adaptif berbasis integrasi
Kita sekarang mengusulkan suatu teknik berbasis wavelet untuk menangani kesulitan yang berhubungan dengan waktu klasik melangkah
skema di bagian sebelumnya. Berbeda dengan waktu berjalan, dimana urutan submasalah aljabar diskrit
dipecahkan, kami mengusulkan untuk mengurangi PDE untuk masalah aljabar tunggal dalam domain waktu seluruh
[0, T]. Jadi, untuk mengembangkan sebuah teknik AWCM integrasi untuk memecahkan Persamaan. (15), kami mempertimbangkan batas semu
masalah nilai dalam [0, T] dengan kondisi Dirichlet pada t = 0 dan kondisi terminal yang sesuai pada t = T. Karena
Masalah (15) baik-berpose (yaitu solusi secara unik ditentukan dari data batas yang tersedia), menambahkan
kondisi terminal membuat masalah overdetermined. Namun, metode numerik membutuhkan informasi untuk
benar berevolusi solusi pada t = T batas dari data awal yang diberikan pada t = 0 batas. Yang benar
prosedur adalah untuk menentukan nilai koefisien wavelet pada t = batas T menggunakan tetangga terdekat
sehingga gradien dari solusi benar dihitung pada t = T. Hal ini memastikan bahwa solusi
u (x, T) ditentukan dari u (x, t <T). Kami menyebutnya masalah membangun masalah nilai batas semu
karena kondisi terminal yang diusulkan
du
dt
ðTÞ Fðu;? ke-/ ¼ 0 ð17Þ
adalah suatu kondisi yang dinamis pada T t =, yang kita sebut kondisi evolusi. Kondisi batas tidak membuat
masalah overdetermined dan tidak diperlukan untuk keberadaan atau keunikan dari solusi. Hal ini di
Berbeda dengan kondisi batas buatan atau numerik yang kadang-kadang digunakan untuk menentukan interior
solusi dalam sistem hiperbolik [63].
Pertimbangkan wavelet generasi kedua bi-ortogonal pada grid diad dari [0, T], yaitu tj
k ¼ 2? jk untuk semua P j 0. Membiarkan
Nj + 1 menjadi jumlah total poin kotak pada tingkat j.We sekarang memperluas u (t) dan du / dt dalam basis wavelet multi-skala di
skala 2 j untuk mendapatkan berikut ini?:
uðtj
0Þ ¼ u0ðtj
0Þ ðleft boundaryÞ;
du
dt
ðtj
k? Fðuðtj
k; tj
k ¼ 0; 1 6 k 6 Nj? 1 ðinternal pointsÞ;
du
dt
ðtj
k? Fðuðtj
k; tj
k ¼ 0; k ¼ Nj ðright boundaryÞ.
Karena kita menggunakan pendekatan berdasarkan metode kolokasi-sisa tertimbang fungsi dalam basis wavelet, yang
turunan dari u (t) pada masing-masing metode kolokasi poin tj
k dihitung dari aproksimasi u (t) menurut
untuk beberapa stensil beda (dijelaskan kemudian). Menggunakan Persamaan. (9), sistem persamaan di atas perbedaan sehingga
mengurangi terhadap masalah aljabar berikut:
LjUj ¼ F j; ð18Þ