Bagaimana menetapkan bahwa metode iteratif untuk sistem linear besar dalam praktiknya konvergen?

Dalam ilmu komputasi kita sering menemukan sistem linear besar yang harus kita pecahkan dengan beberapa cara (efisien), misalnya dengan metode langsung atau berulang. Jika kita fokus pada yang terakhir, bagaimana kita dapat menetapkan bahwa metode iteratif untuk menyelesaikan sistem linier yang besar adalah konvergen dalam praktiknya?

Jelas bahwa kita dapat melakukan analisis coba-coba (lih. Mengapa soler linier berulang saya tidak konvergen? ) Dan mengandalkan metode berulang yang menjamin konvergensi dengan bukti atau memiliki basis pengalaman yang baik (misalnya metode ruang bagian Krylov seperti CG dan GMRES untuk sistem simetris dan nonsimetri masing-masing).

Tetapi, apa yang bisa dilakukan untuk membangun konvergensi dalam praktik? dan apa yang dilakukan?

linear-algebra iterative-method convergence krylov-method Allan P. Engsig-Karup
sumber

Pertanyaan bagus! Ketika Anda mengatakan 'membangun konvergensi', apakah maksud Anda 'menetapkan bahwa solusinya sedang konvergen' atau 'menetapkan bahwa konvergensi akan terjadi'? Saya tahu, misalnya, bahwa objek KSS PETSc memiliki beberapa teknik standar untuk menguji konvergensi (norma kesalahan berkurang, jumlah iterasi maksimum). Apakah ini jenis jawaban yang Anda cari?

Aron Ahmadia

@ Harun: Saya pikir akan menarik untuk melihat jawaban mengatasi kedua masalah.

Allan P. Engsig-Karup

Untuk banyak persamaan diferensial parsial yang muncul di alam, khususnya dengan nonlinier atau anisotropi yang kuat, pilihan prekondisi yang tepat dapat memiliki efek besar pada apakah metode iteratif berkonvergensi dengan cepat, lambat, atau tidak sama sekali. Contoh masalah yang diketahui memiliki prekondisi cepat dan efektif termasuk persamaan diferensial parsial sangat elips, di mana metode multigrid sering mencapai konvergensi cepat. Ada sejumlah tes yang dapat digunakan untuk menilai konvergensi; di sini saya akan menggunakan fungsionalitas dari PETSc sebagai contoh, karena ini bisa dibilang perpustakaan tertua dan paling matang untuk iteratif memecahkan sistem linear linear (dan persamaan nonlinier).

PETSc menggunakan objek yang disebut KSPMonitor untuk memantau kemajuan dari pemecah iteratif, dan memutuskan apakah pemecah telah konvergen atau menyimpang. Monitor menggunakan empat kriteria berbeda untuk memutuskan apakah akan berhenti. Rincian lebih lanjut tentang diskusi di sini dapat ditemukan di halaman manual untuk KSPGetConvergedReason () .

$x$

A x = b

$Ax=b$

\hat{x}

$\hat{x}$

\hat{r}

$\hat{r}$

$\left(P^{-1}(Ax − b) \right)$
$\hat{r} = P^{- 1} (A \hat{x} - b)$ $\hat{r}=P^{-1}(A\hat{x}-b)$
$\left(AP^{-1}Px = b \right)$
$\hat{r} = A \hat{x} - b$ $\hat{r}=A\hat{x}-b$

Kriteria Konvergensi

$a_{tol}$ $‖ \hat{r} ‖ \leq a_{t o l}$ $\|\hat{r}\| \le a_{tol}$
Toleransi Relatif - Kriteria toleransi relatif terpenuhi ketika norma residual kurang dari norma sisi kanan dengan faktor konstanta yang telah ditentukan sebelumnya : $r_{tol}$ $‖ \hat{r} ‖ \leq r_{t o l} \cdot ‖ b ‖$ $\|\hat{r}\| \le r_{tol}\cdot \|b\|$
Kriteria Lain - Pemecahan iteratif juga dapat konvergen karena deteksi panjang langkah kecil atau kelengkungan negatif.

Kriteria Penyimpangan

Iterasi Maksimum - Jumlah iterasi yang dapat diambil oleh pemecah dibatasi oleh iterasi maksimum. Jika tidak ada kriteria lain yang terpenuhi ketika jumlah iterasi maksimum tercapai, monitor kembali sebagai berbeda.
Residual NaN - Jika suatu saat residual mengevaluasi ke NaN, solver kembali sebagai menyimpang.
Divergensi Norma Sisa Monitor kembali sebagai menyimpang jika pada suatu titik norma residu lebih besar daripada norma sisi kanan oleh faktor konstanta yang telah ditentukan sebelumnya : $d_{tol}$
$‖ \hat{r} ‖ \geq d_{t o l} \cdot ‖ b ‖$ $\|\hat{r}\| \ge d_{tol}\cdot \|b\|$
Solver Breakdown Metode Krylov sendiri dapat memberi sinyal divergensi jika mendeteksi matriks tunggal atau prekondisi.

Aron Ahmadia
sumber

Bagaimana menetapkan bahwa metode iteratif untuk sistem linear besar dalam praktiknya konvergen?

Jawaban: