The theoretical aspects of the generalized conjugate gradient method pplied to least squares problems

Abstract

This paper deals with the theoretical aspects of the Generalized Conjugate Gradient (GCG) method of Concus and Golub (1976) and Widlund (1978) applied to the least squares problems (LSP). The connections with the CG algorithms are given. Thereby the convergence bound given by Eisenstat (1982) is improved in some cases. The AGCG algorithms I and II are developed, which are an adjusted form of the GCG method depending on the initial choice and take approximately half of the work per iteration of the GCG. New stopping criteria are given for the GCG (and AGCG) method. The absolute error stopping criterion is proved theoretically and shown numerically to be better than that suggested by Widlund (1978).

Keywords:

• Generalized Conjugate Gradient (GCG) Method
• Conjugate Gradient (CG) Method
• Least Squares Problems (LSP)

AMS:

• 65F10
• 65N20

C.R. Categories:

• G.1.3
• G.1.6
• G.1.2