On the behavior of the conjugate residual method for singular systems

摘要

Consider applying the Conjugate Residual (CR) method, which is a Krylov subspace type iterative solver, to systems of linear equations A_X = b or least squares problems min_(X ∈ R~n) ‖b - ?A_X‖_2, where A is singular and nonsymmetric. We will show that when R(A)~⊥ = ker A, the CR method can be decomposed into the R(A) and ker A components, and the necessary and sufficient condition for the CR method to converge to the least squares solution without breaking down for arbitrary b and initial approximate solution X_o, is that the symmetric part M(A) of A is semi-definite and rank M(A) = rankA. Furthermore, when X_o ∈ R(A), the approximate solution converges to the pseudo inverse solution. Next, we will also derive the necessary and sufficient condition for the CR method to converge to the least squares solution without breaking down for arbitrary initial approximate solutions, for the case when R(A) ⊕ ker A = R~n and b ∈ R(A).