Conjugate Gradient Method for Solving Singular Systems

Abstract

The conjugate gradient method (CG) is an iterative algorithm for solving systems of linear equations with large, sparse, symmetric, positive-definite matrices. It seeks an approximate solution by minimizing the associated quadratic functional. The assumption of positive-definiteness is fundamental; when applied to singular systems, the performance of CG may deteriorate significantly. The thesis presents a detailed motivation and derivation of the CG method, and ex- plores some of its key properties through its connection to Krylov subspaces. An example involving a singular matrix, where divergence of the method is observed, serves as the starting point for an analysis of solving systems with positive semi-definite matrices. The vectors generated by CG are decomposed into components within the kernel and the range of the system matrix, and the behavior in each subspace is examined in detail. A modification of CG for singular systems is recalled from the literature. Finally, nu- merical experiments are presented, investigating the divergence of CG when applied to inconsistent systems with positive semi-definite matrices. 1