Adakah heuristik untuk mengoptimalkan metode suksesi relaksasi berlebihan (SOR)?

Seperti yang saya pahami, berturut-turut daripada relaksasi bekerja dengan memilih parameter dan menggunakan kombinasi linear dari iterasi (kuasi) Gauss-Seidel dan nilai pada catatan waktu sebelumnya ... yaitu $0\leq\omega\leq2$

${u}^{k+1} = (\omega){u_{gs}}^{k+1} + (1-\omega)u^{k}$

Saya nyatakan 'kuasi' karena termasuk informasi terbaru yang diperbarui sesuai dengan aturan ini, di setiap catatan waktu. (perhatikan bahwa pada , ini persis gauss-seidel). ω=${u_{gs}}^{k+1}$$\omega=1$

Dalam setiap kasus, saya telah membaca bahwa pada pilihan optimal untuk $\omega$ (sehingga iterasi konvergen lebih cepat daripada yang lain) mendekati 2 untuk masalah poisson sebagai resolusi spasial mendekati nol. Apakah ada kecenderungan yang serupa untuk masalah simetris, dominan diagonal lainnya? Artinya, apakah ada cara untuk memilih omega secara optimal tanpa menyematkannya ke dalam skema optimasi adaptif? Apakah ada heuristik lain untuk jenis masalah lain? Jenis masalah apa yang akan di bawah relaksasi ( $\omega<1$ ) menjadi optimal?

Jacobi basah

Misalkan matriks memiliki diagonal . Jika spektrum terletak pada interval dari sumbu nyata positif, maka matriks iterasi Jacobi dengan faktor redaman memiliki spektrum dalam kisaran , jadi meminimalkan jari-jari spektrum dengan memberikan faktor konvergensi dari Jika , maka faktor konvergensi ini sangat buruk, seperti yang diharapkan. Perhatikan bahwa relatif mudah untuk memperkirakanD D - 1 A [ a , b ] ω B Jacobi = I - ω D - 1 A [ 1 - ω b , 1 - ω a ] ω opt = $A$$D$$D^{-1}A$$[a,b]$$\omega$

$$B_\text{Jacobi} = I - \omega D^{-1} A$$ $[1 - \omega b,1 - \omega a]$ ρopt=1-2 $$\omega_{\text{opt}} = \frac 2 {a + b}$$ a≪bb $$\rho_\text{opt} = 1 - \frac{2a}{a+b} = \frac{b-a}{a+b}.$$ $a \ll b$$b$menggunakan metode Krylov, tetapi cukup mahal untuk memperkirakan .$a$

Successive over-relaxation (SOR)

Muda (1950) membuktikan hasil yang optimal untuk SOR diterapkan untuk matriks dengan apa yang disebut properti A , pemesanan konsisten , dan nilai eigen real positif dari . Diberi nilai eigen maksimal dari matriks iterasi Jacobi yang tidak ( dijamin oleh asumsi dalam kasus ini), faktor peredam optimal untuk SOR adalah yang menghasilkan tingkat konvergensi dari Perhatikan bahwa mendekati 2 ketika .$D^{-1}A$$\mu_\max$$I - D^{-1} A$$\mu_\max < 1$

$$\omega_\text{opt} = 1 + \left( \frac{\mu_\max}{1 + \sqrt{1 - \mu_\max^2}} \right)^2$$ $$\rho_\text{opt} = \omega_\text{opt} - 1.$$ $\omega_\text{opt}$$\mu_\max \to 1$

Komentar

Ini bukan tahun 1950 lagi dan itu benar-benar tidak masuk akal untuk menggunakan metode berulang stasioner sebagai pemecah. Sebagai gantinya, kami menggunakannya sebagai smoothers untuk multigrid. Dalam konteks ini, kami hanya peduli untuk menargetkan ujung atas spektrum. Mengoptimalkan faktor relaksasi dalam SOR menyebabkan SOR menghasilkan sangat sedikit redaman frekuensi tinggi (dengan imbalan konvergensi yang lebih baik pada frekuensi yang lebih rendah), jadi biasanya lebih baik menggunakan standar Gauss-Seidel, sesuai dengan di SOR. Untuk masalah nonsimetris dan masalah dengan koefisien yang sangat bervariasi, SOR yang kurang santai ( ) mungkin memiliki sifat redaman yang lebih baik.$\omega = 1$$\omega <1$

Memperkirakan kedua nilai eigen itu mahal, tetapi nilai eigen terbesar dapat diperkirakan dengan cepat menggunakan beberapa iterasi Krylov. Polinomial smoothers (prekondisi dengan Jacobi) lebih efektif daripada beberapa iterasi Jacobi teredam dan lebih mudah dikonfigurasikan, sehingga lebih disukai. Lihat jawaban ini untuk informasi lebih lanjut tentang pasangan polinomial.$D^{-1}A$

Kadang-kadang diklaim bahwa SOR tidak boleh digunakan sebagai prekondisi untuk metode Krylov seperti GMRES. Ini berasal dari pengamatan bahwa parameter relaksasi optimal harus menempatkan semua nilai eigen dari matriks iterasi pada lingkaran berpusat pada titik asal. Spektrum operator prakondisi(

$$B_\text{SOR} = 1 - \left(\frac 1 \omega D + L\right)^{-1} A$$ $(\frac 1 \omega D + L)^{-1} A$memiliki nilai eigen pada lingkaran dengan jari-jari yang sama, tetapi berpusat pada 1. Untuk operator yang tidak terkondisikan, jari-jari lingkaran cukup dekat dengan 1, sehingga GMRES melihat nilai eigen dekat dengan asal pada berbagai sudut, yang biasanya tidak baik untuk konvergensi. Dalam praktiknya, GMRES dapat bertemu secara wajar ketika dikondisikan sebelumnya dengan SOR, terutama untuk masalah yang sudah dikondisikan dengan cukup baik, tetapi para pengkondisi lain seringkali lebih efektif.