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:
- Mulai dengan masalah grid halus
- Proyeksikan ke grid kasar (juga dikenal sebagai batasan )
- Perkirakan solusi pada grid kasar (menggunakan beberapa pemecah lain)
- Proyeksikan solusi grid kasar ke grid yang lebih halus (juga dikenal sebagai perpanjangan )
- 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.
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.
Briggs, Tutorial Multigrid , SIAM, 2000 (Anda dapat mengunduh slide di sini dan sini ) Ini adalah sumber kasual, memberikan pengantar lembut tentang prinsip-prinsip multigrid, sebagian besar untuk masalah elips.
Brandt, Teknik Multigrid , edisi revisi, SIAM 2011 , (atau unduh pdf ). Ini adalah pengembangan filosofi multigrid dan pemodelan multiskala yang besar dan memiliki peluang bagus untuk mengubah cara berpikir Anda tentang pemecah implisit. Situs web Achi Brandt memuat lebih banyak referensi, termasuk Reviewnya tahun 2000 tentang Multiscale Scientific Computation .
Trottenberg, Oosterlee, dan Schueller, Multigrid , Academic Press, 2001 Ini memiliki lebih banyak contoh daripada Brandt, termasuk banyak percobaan dan detail tentang metode spesifik, terutama dalam konteks dinamika fluida.
Hackbusch, Metode dan Aplikasi Multigrid , Springer, 1985 Ini memberikan teori konvergensi yang ketat, termasuk "multigrid dari jenis kedua" untuk operator integral Fredholm.
sumber
Klasik lain:
Kode contoh dapat ditemukan di MGNet
sumber