2023/10/25 by Sugihara, Kota, Hayami, Ken
#15A06 #15A09 #65F08 #65F10 #FOS: Mathematics #G.1.3 #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2310.16442
Brown and Walker (1997) showed that GMRES determines a least squares solution of A x = b where A ∈ \bf Rn × n without breakdown for arbitrary b, x0 ∈ \bf Rn if and only if A is range-symmetric, i.e. \cal R (A\rm T) = \cal R (A) , where A may be singular and b may not be in the range space \cal R A) of A. In this paper, we propose applying GMRES to A C A\rm T z = b , where C ∈ \bf Rn × n is symmetric positive definite. This determines a least squares solution x = CA\rm T z of A x = b without breakdown for arbitrary (singular) matrix A ∈ \bf Rn × n and b ∈ \bf Rn . To make the method numerically stable, we propose using the pseudoinverse with an appropriate threshold parameter to suppress the influence of tiny singular values when solving the severely ill-conditioned Hessenberg systems which arise in the Arnoldi process of GMRES when solving inconsistent range-symmetric systems. Numerical experiments show that the method taking C to be the identity matrix and the inverse matrix of the diagonal matrix whose diagonal elements are the diagonal of A A\rm T gives a least squares solution even when A is not range-symmetric, including the case when \rm index(A) >1.