Sayısal Doğrusal Cebir
Sayısal doğrusal cebir, doğrusal sistemleri, en küçük kareler problemlerini ve özdeğer problemlerini bilgisayar üzerinde çözmek için algoritmalar geliştirmekte olup, sonlu duyarlıklı aritmetikte doğruluk, kararlılık ve maliyet konularına açıkça dikkat etmektedir.
Tanım
Sayısal doğrusal cebir, doğrusal cebir hesaplamalarını — başlıca doğrusal sistemlerin ve özdeğer/tekil değer problemlerinin çözümünü — gerçekleştirmek için kullanılan algoritmaların incelenmesiyle birlikte, bu algoritmaların sonlu duyarlıklı aritmetikteki doğruluk, kararlılık ve verimlilik analizini kapsayan bir alandır.
Kapsam
Bu alan, bilimsel hesaplamanın çoğunun temelini oluşturan hesaplama çekirdeğini kapsamaktadır: Ax = b'yi çözme, matris çarpanlara ayırmalarını (LU, QR, Cholesky, SVD) hesaplama, özdeğerleri ve tekil değerleri bulma ve yuvarlama hatasının ve problem koşullandırmasının hesaplanan sonucu nasıl etkilediğini analiz etme. Hem yoğun hem de yapılandırılmış matrisleri kapsamakta ve algoritmaların kayan nokta davranışını birinci sınıf bir endişe olarak ele almaktadır.
Alt konular
Temel sorular
- Bir doğrusal sistem Ax = b, nasıl doğru ve verimli bir şekilde çözülebilir ve elde edilen sonuç ne zaman güvenilir kabul edilir?
- Hangi matris çarpanlara ayırmaları, doğrusal sistemleri, en küçük kareler problemlerini ve özdeğer problemlerini çözmek için gereken yapıyı ortaya koymaktadır?
- Problemin koşullandırması ve algoritmanın kararlılığı, sonlu duyarlıklı aritmetikteki hatayı birlikte nasıl belirlemektedir?
- Özdeğerler ve tekil değerler, kötü koşullandırılmış ara nicelikler oluşturmadan nasıl hesaplanabilir?
Temel kuramlar
- Geriye Doğru Hata Analizi
- Hesaplanan bir çözüm, hafifçe bozulmuş bir problemin tam çözümü olarak yorumlanmaktadır; bir algoritma, eğer bu bozulma birim yuvarlama hatası mertebesindeyse geriye doğru kararlıdır, bu da algoritmanın kararlılığını problemin koşullandırmasından ayırmaktadır.
- Koşullandırma ve Koşul Sayısı
- Bir doğrusal cebir probleminin pertürbasyonlara (bozulmalara) karşı duyarlılığı bir koşul sayısı ile nicelendirilmektedir; doğrusal sistemler için göreceli hata, kullanılan algoritmadan bağımsız olarak matrisin koşul sayısı çarpı göreceli pertürbasyon ile sınırlanmaktadır.
- Matris Çarpanlara Ayırma Paradigması
- Çoğu algoritma, bir problemi daha basit (üçgensel, ortogonal, köşegen) çarpanların bir çarpımına indirgemektedir; LU, QR, Cholesky ve SVD, çözümlerin, en küçük kareler uyumlarının ve spektrumların okunabildiği kanonik çarpanlara ayırmalar sağlamaktadır.
Klinik önem
Sayısal doğrusal cebir, neredeyse her nicel disiplin için hesaplama temelini oluşturmaktadır: ayrıklaştırılmış diferansiyel denklemler, optimizasyon, istatistik ve regresyon, makine öğrenimi, sinyal ve görüntü işleme ve ağ analizi gibi alanların hepsi, güvenilirlikleri kararlı matris algoritmalarına bağlı olan büyük doğrusal sistemlere, en küçük kareler problemlerine veya özdeğer hesaplamalarına indirgenmektedir.
Tarihçe
Bu alan, yirminci yüzyılın ortalarında dijital bilgisayarların ortaya çıkışıyla ve James H. Wilkinson'ın pivotlamalı Gauss eliminasyonunun neden güvenilir olduğunu açıklayan geriye doğru hata analiziyle şekillenmiştir. Sonraki on yıllar, özdeğerler için QR algoritmasını, tekil değer ayrışımının sistematik incelenmesini ve genel kullanım için kararlı algoritmaları kodlayan yüksek kaliteli kütüphaneleri (LINPACK, LAPACK) üretmiştir.
Öne çıkan isimler
- James H. Wilkinson
- Gene H. Golub
- Lloyd N. Trefethen
- Nicholas J. Higham
İlgili konular
Temel eserler
- trefethen1997
- golub2013
- higham2002
Sıkça sorulan sorular
- Koşullandırma ve kararlılık arasındaki fark nedir?
- Koşullandırma, problemin bir özelliğidir — verilerin pertürbasyonları altında kesin çözümün ne kadar değiştiğidir — oysa kararlılık, algoritmanın bir özelliğidir — sonlu duyarlıklı aritmetikte ne kadar ek hata tanıttığıdır. Kötü koşullandırılmış bir probleme uygulanan kararlı bir algoritma bile büyük bir hata üretebilmektedir.
- Sayısal doğrusal cebirde neden ortogonal dönüşümler tercih edilmektedir?
- Ortogonal (ve üniter) dönüşümler 2-normunu korur ve yuvarlama hatalarını büyütmez; bu nedenle, Householder yansımaları aracılığıyla QR gibi onlardan oluşturulan çarpanlara ayırmalar geriye doğru kararlı olma eğilimindedir.