İteratif Yöntemler
İteratif yöntemler, doğrudan çarpanlara ayırma için çok büyük olan problemleri ele almak amacıyla seyrekliği (sparsity) kullanarak, ardışık olarak daha iyi yaklaşımlar üreten bir dizi oluşturarak büyük lineer (ve nonlineer) sistemleri çözmektedir.
Tanım
İteratif yöntemler, doğrudan bir yöntemin yaptığı gibi sabit ve sonlu sayıda işlemle hesaplamak yerine, çözüme yakınsayan bir dizi iterasyon üreterek bir denklem sisteminin çözümünü yaklaşık olarak bulan algoritmalardır.
Kapsam
Bu kapsam, klasik durağan iterasyonları, eşlenik gradyan (conjugate gradient) ve GMRES algoritmaları gibi Krylov altuzay (Krylov subspace) yöntemlerini, çoklu ızgara (multigrid) yöntemlerini ve yakınsamayı hızlandıran önkoşullandırma (preconditioning) tekniklerini kapsamaktadır. Ayrıca, yakınsama kuramını, spektrum ve koşul sayısının rolünü ve bu yöntemleri ölçeklenebilir kılan matris-serbest, seyrekliği kullanan hesaplamaları ele almaktadır.
Alt konular
Temel sorular
- İteratif yöntemler doğrudan yöntemlere ne zaman tercih edilir ve seyrek yapı neden onları destekler?
- Krylov altuzay yöntemleri, yalnızca matris-vektör çarpımlarından en uygun yaklaşımları nasıl oluşturur?
- Matrisin spektrumu veya koşul sayısı yakınsama hızını nasıl belirler?
- Önkoşullandırma ve çoklu ızgara, yavaş yakınsayan bir iterasyonu hızlı bir iterasyona nasıl dönüştürür?
Temel kuramlar
- Krylov altuzay yaklaşımı
- Krylov yöntemleri, kalana uygulanan ardışık matris-vektör çarpımlarının gerdiği altuzay içinde çözüme en iyi yaklaşımı aramaktadır; bu yöntemler yalnızca matrisin etkisini gerektirmekte ve matrisin spektral özelliklerine bağlı bir adım sayısında yakınsamaktadır.
- Yakınsama ve koşullandırma
- İteratif çözücülerin yakınsama hızı, (önkoşullandırılmış) matrisin özdeğer dağılımına ve koşul sayısına bağlıdır; özdeğerleri kümelemek veya önkoşullandırma yoluyla koşul sayısını azaltmak yakınsamayı önemli ölçüde hızlandırmaktadır.
- Çok seviyeli hızlandırma
- Çoklu ızgara yöntemleri, ince ızgaralardaki düzeltmeyi kaba ızgara düzeltmeleriyle birleştirerek hatanın tüm ölçeklerdeki bileşenlerini ortadan kaldırmakta ve birçok eliptik problem için problem boyutundan bağımsız yakınsama hızları elde etmektedir.
Klinik önem
İteratif yöntemler, mühendislik ve fizik simülasyonlarında kısmi diferansiyel denklemlerin ayrıklaştırılmasından kaynaklanan devasa seyrek lineer sistemler için, ayrıca optimizasyon, makine öğrenimi, ağ analizi ve görüntü yeniden yapılandırma alanlarında vazgeçilmezdir. Düşük bellek ayak izleri ve matris-serbest çalışma prensipleri, sistemler milyonlarca veya milyarlarca bilinmeyene ulaştığında onları tek uygulanabilir yaklaşım haline getirmektedir.
Tarihçe
Klasik gevşetme (relaxation) yöntemleri Gauss, Seidel ve daha sonra Southwell tarafından incelenmiştir. Hestenes ve Stiefel'in (1952) eşlenik gradyan yöntemi ile yirminci yüzyılın sonlarında GMRES ve diğer Krylov yöntemlerinin, çoklu ızgara (Fedorenko, Brandt) ve modern önkoşullandırmanın geliştirilmesi, iteratif çözücüleri büyük seyrek sistemler için standart haline getirmiştir.
Öne çıkan isimler
- Magnus Hestenes
- Eduard Stiefel
- Yousef Saad
- Achi Brandt
İlgili konular
Temel eserler
- saad2003
- greenbaum1997
Sıkça sorulan sorular
- İteratif bir yöntem, doğrudan bir yöntem yerine ne zaman kullanılmalıdır?
- İteratif yöntemler, doğrudan çarpanlara ayırmanın doluluk (fill-in) nedeniyle aşırı bellek gerektireceği çok büyük, seyrek sistemler için tercih edilmektedir. Yalnızca matrisi vektörlere uygulamaları yeterlidir, bu nedenle seyrekliği kullanır ve milyonlarca bilinmeyene sahip problemlere ölçeklenebilirler.
- Önkoşullandırma neden bu kadar önemlidir?
- İteratif çözücülerin yakınsama hızı, matrisin spektrumuna güçlü bir şekilde bağlıdır. Bir önkoşullandırıcı, sistemi daha uygun bir spektruma sahip eşdeğer bir sisteme dönüştürmekte, genellikle pratik olmayan yavaş bir iterasyonu hızla yakınsayan bir iterasyona dönüştürmektedir.