Convergence of the Conjugate Gradient Method on Singular Systems

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.

7 pages. NII Technical Report (NII-2018-001E) https://www.nii.ac.jp/TechReports/public_html/18-001E.html p.1, MSC number changed, Introduction, line 6 typo fixed. p. 3, bottom line 5-3: Comment added. p.6 Acknowledgement detail changed. p.7, 4 references added