Metode Stasioner dan Relaksasi

Metode iteratif stasioner menyelesaikan sistem linear dengan membagi matriks dan berulang kali menerapkan aturan pembaruan tetap; skema Jacobi klasik, Gauss-Seidel, dan relaksasi berurutan adalah contoh-contoh dasarnya.

Definition

Metode iteratif stasioner adalah metode yang pembaruannya menerapkan matriks iterasi yang sama pada setiap langkah, yang berasal dari pembagian matriks koefisien menjadi bagian yang mudah dibalik dan sisanya; konvergensi diatur oleh radius spektral dari matriks iterasi yang dihasilkan.

Scope

Topik ini mencakup kerangka pembagian matriks, iterasi Jacobi dan Gauss-Seidel, relaksasi berurutan dan pemilihan parameter relaksasi optimal, kriteria radius spektral untuk konvergensi, dan peran iterasi sederhana ini saat ini sebagai penghalus dalam multigrid dan sebagai prakondisioner.

Core questions

• Bagaimana pembagian matriks menghasilkan iterasi titik tetap untuk sistem linear?
• Bagaimana metode Jacobi dan Gauss-Seidel berbeda, dan mengapa Gauss-Seidel umumnya lebih cepat?
• Bagaimana over-relaksasi mempercepat konvergensi, dan bagaimana parameter optimal dipilih?
• Dalam kondisi matriks apa iterasi ini konvergen?

Key theories

Pembagian matriks dan kriteria radius spektral

Menulis matriks sebagai bagian yang mudah dibalik dikurangi sisa mendefinisikan iterasi stasioner yang kesalahannya dikalikan dengan matriks iterasi setiap langkah; iterasi konvergen untuk setiap tebakan awal jika dan hanya jika radius spektral dari matriks iterasi tersebut kurang dari satu.

Relaksasi berurutan

Dengan melampaui koreksi Gauss-Seidel dengan faktor relaksasi, relaksasi berurutan dapat sangat mengurangi radius spektral; untuk matriks terstruktur tertentu, parameter relaksasi optimal diketahui secara analitis dan menghasilkan percepatan yang dramatis.

Mechanisms

Metode Jacobi memperbarui setiap variabel yang tidak diketahui secara bersamaan hanya menggunakan nilai dari sapuan sebelumnya, setara dengan memisahkan diagonal. Gauss-Seidel menggunakan nilai yang paling baru diperbarui dalam sapuan yang sama, memisahkan bagian segitiga bawah, yang umumnya konvergen lebih cepat. Relaksasi berurutan membentuk rata-rata tertimbang dari nilai lama dan pembaruan Gauss-Seidel yang diatur oleh parameter relaksasi; memilih parameter ini lebih besar dari satu mempercepat konvergensi untuk matriks yang sesuai. Konvergensi untuk ketiga metode ini dijamin untuk kelas-kelas seperti matriks dominan diagonal ketat atau matriks definit positif simetris, dan dikuantifikasi oleh radius spektral dari matriks iterasi.

Clinical relevance

Meskipun umumnya terlalu lambat untuk menjadi pemecah mandiri yang kompetitif untuk sistem besar, metode stasioner tetap penting sebagai penghalus di jantung multigrid, sebagai prakondisioner sederhana untuk metode Krylov, dan sebagai blok bangunan yang mudah diparalelkan; Gauss-Seidel dan Jacobi berbobot khususnya sangat umum di dalam pemecah multilevel modern.

History

Iterasi Jacobi dan Gauss-Seidel berasal dari abad kesembilan belas, sementara relaksasi berurutan dan teori konvergensi yang ketat dikembangkan oleh David Young dan Richard Varga pada tahun 1950-an; meskipun kemudian dikalahkan oleh metode Krylov dan multigrid sebagai pemecah utama, iterasi ini dihidupkan kembali sebagai komponen penting dari skema multilevel dan prakondisi.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Mengapa Gauss-Seidel umumnya lebih cepat daripada Jacobi?

Gauss-Seidel segera menggunakan nilai yang diperbarui dalam sapuan yang sama, sehingga informasi menyebar lebih cepat melalui variabel yang tidak diketahui, umumnya mengurangi separuh jumlah iterasi dibandingkan dengan Jacobi, yang hanya menggunakan nilai dari sapuan sebelumnya.

Jika metode ini lambat, mengapa masih dipelajari?

Metode ini adalah penghalus yang sangat baik dan prakondisioner sederhana. Di dalam multigrid, beberapa sapuan Gauss-Seidel atau Jacobi berbobot secara efisien menghilangkan kesalahan osilasi, yang persis seperti peran yang dibutuhkan multigrid, sehingga iterasi klasik ini tetap hidup sebagai komponen pemecah modern yang cepat.