Conjugate Gradient Method for Linear Systems
Ayrıca şöyle bilinir: CG method, Krylov subspace method
Tam matrisi depolamak ve yoğun işlemler kullanmak yerine, CG matris A'ya göre ortogonal (eşlenik) olan bir dizi arama yönü oluşturur. Her iterasyon, önceki adımlar için ayarlanmış en dik iniş yönü boyunca hareket eder ve eski yönlerin tekrar ziyaret edilmemesini sağlar. Bu eşleniklik, matris tersini hesaplamadan sonlu adımlarda yakınsamayı garanti eder.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
n × n matrisler için en fazla n iterasyonda yakınsar (teorik sınır pratikte sıklıkla karşılanır)
Güçlü yönler & sınırlılıklar
- Bellek verimliliği: matris için O(n²) yerine yalnızca vektörler için O(n) depolama gerektirir
- Yakınsama oranı koşul sayısına bağlıdır; ön koşullandırma yakınsamayı önemli ölçüde hızlandırabilir
- İyi paralelleşir; matris-vektör çarpımları hesaplamaya hakimdir ve işlemciler arasında ölçeklenir
- Simetrik pozitif-tanımlı matrisler gerektirir; diğer durumlar için varyantlar (MINRES, GMRES) gereklidir
- Sonlu hassasiyette yuvarlama hatalarına duyarlıdır; ortogonalliğin kaybı yakınsamayı yavaşlatabilir
- İyi ön koşullandırma olmadan, kötü koşullandırılmış sistemler (büyük koşul sayıları) yavaş yakınsar
- Yalnızca lineer sistemler için uygundur; lineer olmayan problemler başka yaklaşımlar gerektirir
- A'nın pozitif-tanımlılığını kontrol etmez; CG belirsiz matrislerde başarısız olur veya ıraksar
SSS
İki vektör p_i ve p_j, p_i^T A p_j = 0 ise A'ya göre eşleniktir. Bu, her arama yönünün kendi altuzayında hatayı en aza indirmesini sağlar, gereksiz iterasyonları önler ve sonlu yakınsamayı garanti eder.
Neden ön koşullandırma CG için bu kadar kritik?
CG'nin yakınsama oranı O(√κ)'dır, burada κ, A'nın koşul sayısıdır. Ön koşullandırma, daha düşük koşul sayısına sahip eşdeğer bir problemi çözer, genellikle iterasyonları O(κ)'dan O(√κ)'ya düşürür. Kötü koşullandırılmış sistemler için ön koşullandırıcı seçimi, CG'nin kendisi kadar önemlidir.
CG ile doğrudan çarpanlara ayırma (LU) ne zaman kullanılmalı?
Küçük yoğun sistemler (n < 5000) için doğrudan yöntemler daha hızlı ve daha kararlıdır. Büyük seyrek sistemler için CG ve ön koşullandırılmış CG üstündür: iterasyon başına O(nnz) maliyetle O(n²) veya O(n^1.5) iterasyon, O(n³) yoğun çarpanlara ayırmayı yener. Bellek de CG'yi destekler.
Sonlu hassasiyette ortogonalliğin kaybı nasıl tespit edilir?
Gerçek kalanı r = b - Ax periyodik olarak hesaplayın, yalnızca tekrarlama ilişkisini değil. Eğer ||r_true|| >> ||r_recurrence|| ise, ortogonallik kaybolmuş demektir; CG'yi yeniden başlatın veya yeniden ortogonalizasyon kullanın.
Compute true residual r = b - Ax periodically, not just the recurrence relation. If ||r_true|| >> ||r_recurrence||, orthogonality is lost; restart CG or use reorthogonalization.
Kaynaklar
- Hestenes, M. R., & Stiefel, E. (1952). Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6), 409–436. DOI: 10.6028/jres.049.044 ↗
- Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM. DOI: 10.1137/1.9780898718003 ↗
- Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer. DOI: 10.1007/978-0-387-40065-5 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Conjugate Gradient Method for Linear Systems. ScholarGate. https://scholargate.app/tr/numerical-methods/conjugate-gradient-method
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- GMRESSayısal yöntemler↔ karşılaştır