NII Technical Report (NII-2004-009E)：On the Convergence of the GCR(k) Method for Singular Systems

Consider applying the restarted Generalized Conjugate Residual (GCR (k) ) method to systems of linear equations A x = b or least squares problems minₓ || b - A x ||₂, where A is a n x n real matrix which may be singular and/or nonsymmetric and x, b are real vectors of size n. Let R (A) and N (A) be the range and null space of A, respectively. First, we prove that the necessary and sufficient condition for the method to converge to a least squares solution without breakdown for arbitrary b and initial approximate solution x₀, is that A is definite in R (A), and that R (A) and N (A) are orthogonal to each other. Next, we show that the necessary and sufficient condition for the method to converge to a solution without breakdown for arbitrary b in R (A) and arbitrary x₀, is that A is definite in R (A). The main idea of the proofs is to decompose the algorithm into the R (A) and its orthogonal complement components. Finally, we will give examples arising in the finite difference discretization of two-point boundary value problems of an ordinary differential equation, corresponding to the above two cases.