Doğrusal Sistemler için Doğrudan Yöntemler
Doğrudan yöntemler, bir Ax = b doğrusal sistemini sonlu sayıda aritmetik adımda çözmektedir; bu genellikle matrisin çarpanlara ayrılması ve ardından üçgensel sistemlerin yerine koyma (substitution) yöntemiyle çözülmesiyle gerçekleştirilmektedir.
Tanım
Doğrudan bir yöntem, bir doğrusal sistemin kesin çözümünü — yuvarlama hatasına kadar — önceden belirlenmiş sonlu sayıda işlemde hesaplayan bir algoritmadır; bu, bir dizi yaklaşım üreten yinelemeli (iterative) bir yöntemin aksinedir.
Kapsam
Bu konu, Gauss eliminasyonunu, bunun bir LU çarpanlara ayırma (factorization) olarak ifadesini, hata büyümesini kontrol etmede pivotlamanın rolünü, üçgensel sistemler için ileri ve geri yerine koymayı (forward and back substitution) ve doğrudan çözücüleri yoğun (dense) ve bantlı (banded) matrisler için pratik hale getiren işlem sayımlarını kapsamaktadır.
Temel sorular
- Gauss eliminasyonu bir sistemi nasıl üçgensel forma indirger ve bu neden bir LU çarpanlara ayırma (factorization) ile eşdeğerdir?
- Pivotlama neden gereklidir ve kısmi (partial) ile tam (complete) pivotlama yuvarlama hatasının büyümesini nasıl kontrol eder?
- Doğrudan bir çözümün hesaplama maliyeti nedir ve yapıdan (simetri, bantlılık (bandedness), seyreklik (sparsity)) faydalanmak bu maliyeti nasıl azaltır?
- Kısmi pivotlama ile Gauss eliminasyonu pratikte hangi koşullar altında geriye doğru kararlıdır (backward stable)?
Temel kuramlar
- Kısmi pivotlama ile LU çarpanlara ayırma (factorization)
- Satır değişimleri (row interchanges) içeren Gauss eliminasyonu, bir matrisi PA = LU olarak çarpanlara ayırmaktadır; burada L birim alt üçgensel (unit lower-triangular) ve U üst üçgenseldir (upper-triangular); kısmi pivotlama çarpanları sınırlar ve yöntemi pratikte karşılaşılan hemen hemen tüm matrisler için güvenilir kılmaktadır.
- Büyüme faktörü ve geriye doğru kararlılık (backward stability)
- Gauss eliminasyonunun geri hatası (backward error), eliminasyon sırasında girdilerin büyüme faktörü tarafından yönetilmektedir; yapay durumlarda üstel büyüme mümkün olsa da, kısmi pivotlama büyümeyi yeterince küçük tutarak yöntemin neredeyse tüm gerçek problemler için geriye doğru kararlı (backward stable) olmasını sağlamaktadır.
Mekanizmalar
Gauss eliminasyonu sütun sütun ilerlemektedir: her adımda bir pivot seçilmektedir (kısmi pivotlama (partial pivoting) mevcut sütundaki en büyük büyüklükteki adayı seçmektedir), sıfırları oluşturmak için pivot satırının katları aşağıdaki satırlardan çıkarılmakta ve çarpanlar L'yi oluşturmak üzere saklanmaktadır. Ortaya çıkan üst üçgensel U, geri yerine koyma (back substitution) ile çözülmekte ve sağ taraf ileri yerine koyma (forward substitution) ile işlenmektedir. n-e n yoğun bir matris için çarpanlara ayırma yaklaşık olarak n-küp işlemin üçte ikisi kadar maliyetliyken, her bir üçgensel çözüm n-kare mertebesinde maliyetlidir.
Klinik önem
Doğrudan çözücüler, sonlu eleman montajında (finite-element assembly), devre simülasyonunda, kontrolde ve daha büyük sayısal şemaların iç çözümü olarak orta büyüklükte yoğun veya bantlı bir sistemin tam doğrulukla çözülmesi gerektiğinde varsayılan işgücüdür; ayrıca tek bir çarpanlara ayırma, birçok sağ tarafı ucuza çözmek için yeniden kullanılabilmektedir.
Tarihçe
Eliminasyon yöntemleri Gauss'a ve daha öncesine dayanmaktadır, ancak sonlu hassasiyetli aritmetikteki davranışları, 1960'larda Wilkinson'ın geri hata analizi (backward error analysis) ile açıklığa kavuşmuştur; bu analiz, kısmi pivotlamanın hata büyümesini kontrol ettiğini ve erken dönem bilgisayarlarda uzun süredir gözlemlenen yöntemin deneysel güvenilirliğini açıkladığını göstermiştir.
Öne çıkan isimler
- Carl Friedrich Gauss
- James H. Wilkinson
- Nicholas J. Higham
İlgili konular
Temel eserler
- trefethen1997
- golub2013
- higham2002
Sıkça sorulan sorular
- Doğrudan bir yöntem, yinelemeli bir yönteme ne zaman tercih edilmelidir?
- Doğrudan yöntemler, matris yoğun (dense) veya orta büyüklükte olduğunda, birçok sağ tarafın tek bir matrisi paylaştığı durumlarda (böylece tek bir çarpanlara ayırma yeniden kullanılır) veya garantili sonlu, tam doğrulukta bir çözüm gerektiğinde tercih edilmektedir. Çok büyük seyrek (sparse) sistemler genellikle yinelemeli yöntemleri tercih etmektedir.
- Pivotlama her zaman küçük bir hatayı garanti eder mi?
- Kısmi pivotlama, pratikte hemen hemen tüm matrisler için geriye doğru kararlılığı (backward stability) garanti etmektedir, ancak kötü koşullanmayı (ill-conditioning) aşmamaktadır: eğer matrisin kendisi neredeyse tekil (singular) ise, geriye doğru kararlı bir çözüm bile büyük bir ileri hata (forward error) ile sonuç döndürebilmektedir.