Convergence of the Conjugate Gradient Method on Singular Systems

2018/09/04 by Ken Hayami, Hayami, Ken · 2 citations
Computer Science · Mathematics · #65F10 #Advanced Optimization Algorithms Research #FOS: Mathematics #G.1.3 #Iterative Methods for Nonlinear Equations #Matrix Theory and Algorithms #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1809.00793

openalex publication_date 2018/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We analyze the convergence of the Conjugate Gradient (CG) method in exact arithmetic, when the coefficient matrix A is symmetric positive semidefinite and the system is consistent. To do so, we diagonalize A and decompose the algorithm into the range and the null space components of A. Further, we apply the analysis to the CGLS and CGNE (CG Normal Error) methods for rank-deficient least squares problems.

Cited by

• Auxiliary space theory for the analysis of iterative methods for semidefinite linear systems
• Rao-Blackwellised Reparameterisation Gradients

Related

• Estimating the error in CG-like algorithms for least-squares and least-norm problems
• The conjugate gradient method with various viewpoints
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• Conjugate Direction Methods Under Inconsistent Systems
• Accurate error estimation in CG