Durağan ve Gevşetme Yöntemleri
Durağan iteratif yöntemler, bir lineer sistemi matrisi bölerek ve sabit bir güncelleme kuralını tekrar tekrar uygulayarak çözmektedir; klasik Jacobi, Gauss-Seidel ve ardışık aşırı gevşetme şemaları bu yöntemlerin temel örneklerini oluşturmaktadır.
Tanım
Durağan bir iteratif yöntem, her adımda aynı iterasyon matrisini uygulayan, katsayı matrisinin kolayca tersi alınabilir bir kısım ile bir kalan kısma ayrılmasından türetilen bir yöntemdir; yakınsama, ortaya çıkan iterasyon matrisinin spektral yarıçapı tarafından belirlenmektedir.
Kapsam
Bu konu, matris bölme çerçevesini, Jacobi ve Gauss-Seidel iterasyonlarını, ardışık aşırı gevşetmeyi ve optimal gevşetme parametresinin seçimini, yakınsama için spektral yarıçap kriterini ve bu basit iterasyonların günümüzde çoklu ızgara (multigrid) içinde düzeltici (smoother) olarak ve ön koşullandırıcı (preconditioner) olarak oynadığı rolü kapsamaktadır.
Temel sorular
- Matrisi bölmek, lineer sistem için sabit nokta iterasyonunu nasıl sağlamaktadır?
- Jacobi ve Gauss-Seidel yöntemleri nasıl farklılaşmaktadır ve Gauss-Seidel neden genellikle daha hızlıdır?
- Aşırı gevşetme yakınsamayı nasıl hızlandırmaktadır ve optimal parametre nasıl seçilmektedir?
- Matris üzerindeki hangi koşullar altında bu iterasyonlar yakınsamaktadır?
Temel kuramlar
- Matris bölme ve spektral yarıçap kriteri
- Matrisi kolayca tersi alınabilir bir kısım eksi bir kalan olarak yazmak, hatası her adımda bir iterasyon matrisi ile çarpılan durağan bir iterasyon tanımlamaktadır; iterasyon, yalnızca o iterasyon matrisinin spektral yarıçapı birden küçükse her başlangıç tahmini için yakınsamaktadır.
- Ardışık aşırı gevşetme
- Gauss-Seidel düzeltmesini bir gevşetme faktörü ile aşırı atlayarak, ardışık aşırı gevşetme spektral yarıçapı büyük ölçüde azaltabilmektedir; belirli yapılandırılmış matrisler için optimal bir gevşetme parametresi analitik olarak bilinmekte ve önemli bir hızlanma sağlamaktadır.
Mekanizmalar
Jacobi yöntemi, her bilinmeyeni yalnızca önceki taramadan (sweep) gelen değerleri kullanarak eş zamanlı olarak güncellemektedir; bu, matrisin köşegen kısmının ayrılmasına eşdeğerdir. Gauss-Seidel ise aynı tarama içinde en son güncellenen değerleri kullanmaktadır ve alt üçgensel kısmı ayırmaktadır, bu da genellikle daha hızlı yakınsamaktadır. Ardışık aşırı gevşetme, eski değer ile bir gevşetme parametresi tarafından yönetilen Gauss-Seidel güncellemesinin ağırlıklı ortalamasını oluşturmaktadır; bu parametrenin birden büyük seçilmesi, uygun matrisler için yakınsamayı hızlandırmaktadır. Her üç yöntem için de yakınsama, kesinlikle köşegen baskın veya simetrik pozitif tanımlı matrisler gibi sınıflar için garanti edilmekte olup, iterasyon matrisinin spektral yarıçapı ile nicel olarak ifade edilmektedir.
Klinik önem
Büyük sistemler için genellikle rekabetçi bağımsız çözücüler olarak çok yavaş olsalar da, durağan yöntemler çoklu ızgaranın (multigrid) kalbindeki düzelticiler (smoother) olarak, Krylov yöntemleri için basit ön koşullandırıcılar (preconditioner) olarak ve kolayca paralelleştirilebilir yapı taşları olarak önemini korumaktadır; özellikle Gauss-Seidel ve ağırlıklı Jacobi, modern çok seviyeli çözücülerin içinde yaygın olarak kullanılmaktadır.
Tarihçe
Jacobi ve Gauss-Seidel iterasyonları on dokuzuncu yüzyıla dayanmaktadır; ardışık aşırı gevşetme ve onun titiz yakınsama teorisi ise 1950'lerde David Young ve Richard Varga tarafından geliştirilmiştir. Daha sonra Krylov ve çoklu ızgara (multigrid) yöntemleri tarafından birincil çözücüler olarak gölgede bırakılmış olsalar da, bu iterasyonlar çok seviyeli ve ön koşullandırılmış şemaların temel bileşenleri olarak yeniden canlandırılmıştır.
Öne çıkan isimler
- Carl Friedrich Gauss
- Philipp Ludwig von Seidel
- David M. Young
- Richard S. Varga
İlgili konular
Temel eserler
- saad2003
- varga2000
Sıkça sorulan sorular
- Gauss-Seidel neden genellikle Jacobi'den daha hızlıdır?
- Gauss-Seidel, aynı tarama içinde güncellenmiş değerleri hemen kullanmaktadır, bu nedenle bilgi bilinmeyenler arasında daha hızlı yayılmaktadır ve genellikle yalnızca önceki taramadan gelen değerleri kullanan Jacobi'ye kıyasla iterasyon sayısını yarıya indirmektedir.
- Bu yöntemler yavaşsa, neden hala incelenmektedir?
- Bunlar mükemmel düzelticiler (smoother) ve basit ön koşullandırıcılardır (preconditioner). Çoklu ızgara (multigrid) içinde, birkaç Gauss-Seidel veya ağırlıklı Jacobi taraması, salınımlı hatayı verimli bir şekilde ortadan kaldırmaktadır; bu da çoklu ızgaranın tam olarak ihtiyaç duyulan roldür, bu nedenle bu klasik iterasyonlar hızlı modern çözücülerin bileşenleri olarak varlığını sürdürmektedir.