metode multigrid untuk menyelesaikan PDE

15

Saya perlu penjelasan sederhana tentang Metode Multigrid atau beberapa literatur tentang ini.

Saya kenal dengan metode iterasi termasuk BiCGStab, CG, GS, Jacobi dan prekondisi, tetapi saya pemula dengan metode multigrid.

Adakah yang bisa menjelaskan hal ini secara terperinci atau setidaknya memberikan pseudocode atau kode sumber yang jelas, bahkan dengan literatur yang bagus untuk pemula? Terima kasih!

Nurlan
sumber

Jawaban:

15

Ide utama di balik multigrid adalah proyeksi. Saya mencoba memikirkannya sebagai berikut:

Misalkan saya ingin menyelesaikan PDE dengan banyak akurasi, jadi saya melanjutkan untuk mendiskritisasi domain (katakanlah, menggunakan metode beda hingga) pada grid yang sangat bagus dengan banyak dan banyak poin. Pada akhirnya, saya mengatur sistem persamaan saya dan saya siap untuk menyelesaikannya. Saya mencoba menggunakan pemecah iteratif favorit saya (jacobi, gauss seidel, konjugasi gradien, dll ...). Saya melanjutkan menunggu lebih dari sehari dan menyadari komputer saya masih mencoba menghitung jawabannya !!!

Alasan mengapa metode berulang ini tidak bekerja dengan cepat adalah karena (biasanya) ketika Anda menyiapkan sistem besar persamaan seperti ini, matriks itu sendiri memiliki nilai eigen yang sangat dekat dengan 1. Mengapa ini penting? Karena laju konvergensi dari banyak metode iteratif berbanding terbalik dengan nilai eigen terbesar (lihat tautan Christian Clason ke Slide Tutorial Multigrid Brigg, bagian 1, halaman 27). Jadi, semakin dekat nilai eigen terbesar adalah 1, semakin lambat metode iteratifnya. (Catatan: ini terlalu menyederhanakan hal, tetapi membantu memotivasi kebutuhan untuk multigrid).

Jelas, selalu lebih cepat untuk menyelesaikan masalah jika ada lebih sedikit yang tidak diketahui (yaitu pada grid kasar dengan lebih sedikit gridpoints). Tetapi yang lebih penting, solusi (atau solusi perkiraan) pada grid yang lebih kasar adalah titik awal yang baik untuk menyelesaikan masalah pada grid yang lebih halus. Ini adalah ide kunci di balik sebagian besar (jika tidak semua) metode multigrid. Mengapa demikian? Secara intuitif, ini masuk akal, tetapi ada cara matematis yang ketat untuk membenarkan hal ini.

Mari kita lihat mode fourier dari kesalahan dalam metode berulang (demi argumen, katakanlah jacobi atau gauss seidel) yang diterapkan pada masalah fine grid asli. Kita akan melihat bahwa dalam beberapa iterasi pertama, sebagian besar kesalahan frekuensi tinggi (sangat berosilasi) dihapus! Ini hebat, tetapi ada kesalahan frekuensi rendah (kurang osilasi) yang masih ada dan tidak hilang dengan cepat. Bahkan, itu adalah kesalahan frekuensi rendah yang mencegah metode iteratif standar dari konvergen dengan cepat.

ketika kita memecahkan masalah pada grid yang lebih kasar (katakanlah, dengan metode iteratif seperti jacobi atau gauss-seidel), kita pada dasarnya dapat menghapus kesalahan frekuensi yang lebih rendah dengan lebih cepat (yaitu dalam iterasi yang lebih sedikit) daripada di grid yang halus . Jadi, jika kita memecahkan masalah grid kasar, kita memiliki solusi yang kesalahan frekuensinya lebih rendah telah dikurangi secara signifikan. Dengan demikian, ini akan berguna sebagai titik awal untuk metode berulang pada kisi yang lebih halus.

Walaupun ada berbagai metode multigrid, kebanyakan dari mereka beroperasi dengan beberapa variasi berikut:

  1. Mulai dengan masalah grid halus
  2. Proyeksikan ke grid kasar (juga dikenal sebagai batasan )
  3. Perkirakan solusi pada grid kasar (menggunakan beberapa pemecah lain)
  4. Proyeksikan solusi grid kasar ke grid yang lebih halus (juga dikenal sebagai perpanjangan )
  5. Menggunakan proyeksi dari 4. sebagai perkiraan awal, pecahkan masalah grid halus dengan metode berulang.

Bagi saya, bagian tersulit dari metode multigrid adalah proyeksi antar kisi. Tutorial Briggs yang disarankan oleh @ChristianClason menangani masalah ini jauh lebih baik daripada yang saya bisa.

Paul
sumber
Terima kasih atas jawaban terinci! Sekarang saya memiliki pengetahuan dasar tentang metode multigrdi. Sekarang saya memiliki pertanyaan spesifik tentang proses pembatasan dan perpanjangan. Saya membaca bahwa beberapa matriks Pembatasan R dan Interpolasi Matriks M dan rumus-rumus seperti A2 = RAI digunakan untuk melakukan proyeksi antar kisi. Tapi saya tidak mengerti bagaimana cara membuat matriks R dan saya .. Apakah ada ide tentang ini?
Nurlan
Lihatlah slide 45-57 dari tutorial multigrid Briggs (bagian 1) yang diposting ChristianClason. Di sana, Briggs menjelaskan proses untuk Metode Geometris Multigrid. Itulah penjelasan paling sederhana yang bisa saya temukan. Jika Anda memiliki pertanyaan lebih lanjut tentang itu, jangan ragu untuk mengirim pertanyaan baru! :)
Paul
15

Situs ini mungkin bukan tempat yang baik untuk meminta penjelasan terperinci dengan pseudocode (sebagaimana dinyatakan dalam FAQ , "Jika Anda dapat membayangkan seluruh buku yang menjawab pertanyaan Anda, Anda terlalu banyak bertanya."), Jadi Anda mungkin ingin untuk memulai dengan salah satu buku klasik tentang topik ini (tercantum di bawah) dan kembalilah dengan pertanyaan spesifik tentang detail konkret yang bermasalah dengan Anda.

Christian Clason
sumber
2
Briggs benar-benar baik!
vanCompute
5

Klasik lain:

  • Wesseling, Pengantar Metode Multigrid, John Wiley & Sons, 1992.

Kode contoh dapat ditemukan di MGNet

chris
sumber