TABLE OF CONTENTS Currently, there is a lot of interest in iterative regularization methods based on the CG method. This method was originally designed for solving large sparse systems of equations with a symmetric positive definite coefficient matrix, and there is a wealth of literature about this method, its implementation, and its convergence properties; see, e.g., [12], [154, 10.2 10.3], [345], and the references therein. An understanding of the CG method's behavior in finite precision arithmetic is also emerging; cf. [158].
In connection with least squares problems and regularization problems, the CG method is applied to the normal equations A TAx = A Tb whose coefficient matrix A TA is symmetric and positive semidefinite.
An essential property of the CG iter ates x ( k) with residual vectors r ( k) = b ? Ax ( k) is that the corresponding residual vectors A Tr ( k) = A Tb ? A TAx ( k) for the normal equations are orthogonal. An important consequence of this is that if the starting vector x (0) is zero, then the solution norm ? x ( k) ? 2 increases monotonically with k. This follows from the following theorem due to Hestenes and Stiefel, formulated here in terms of the normal equations.
Let ?( x ( k)) denote the CG error function
