Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgments
- 1 Direct Solution Methods
- 2 Theory of Matrix Eigenvalues
- 3 Positive Definite Matrices, Schur Complements, and Generalized Eigenvalue Problems
- 4 Reducible and Irreducible Matrices and the Perron-Frobenius Theory for Nonnegative Matrices
- 5 Basic Iterative Methods and Their Rates of Convergence
- 6 M-Matrices, Convergent Splittings, and the SOR Method
- 7 Incomplete Factorization Preconditioning Methods
- 8 Approximate Matrix Inverses and Corresponding Preconditioning Methods
- 9 Block Diagonal and Schur Complement Preconditionings
- 10 Estimates of Eigenvalues and Condition Numbers for Preconditioned Matrices
- 11 Conjugate Gradient and Lanczos-Type Methods
- 12 Generalized Conjugate Gradient Methods
- 13 The Rate of Convergence of the Conjugate Gradient Method
- Appendices
- Index
12 - Generalized Conjugate Gradient Methods
Published online by Cambridge University Press: 05 August 2012
- Frontmatter
- Contents
- Preface
- Acknowledgments
- 1 Direct Solution Methods
- 2 Theory of Matrix Eigenvalues
- 3 Positive Definite Matrices, Schur Complements, and Generalized Eigenvalue Problems
- 4 Reducible and Irreducible Matrices and the Perron-Frobenius Theory for Nonnegative Matrices
- 5 Basic Iterative Methods and Their Rates of Convergence
- 6 M-Matrices, Convergent Splittings, and the SOR Method
- 7 Incomplete Factorization Preconditioning Methods
- 8 Approximate Matrix Inverses and Corresponding Preconditioning Methods
- 9 Block Diagonal and Schur Complement Preconditionings
- 10 Estimates of Eigenvalues and Condition Numbers for Preconditioned Matrices
- 11 Conjugate Gradient and Lanczos-Type Methods
- 12 Generalized Conjugate Gradient Methods
- 13 The Rate of Convergence of the Conjugate Gradient Method
- Appendices
- Index
Summary
As we saw in the previous chapter, there exist two types of methods to solve systems of equations with short recurrence relations: (1) minimization algorithms, such as the conjugate gradient type algorithms, and (2) Lanczos-type algorithms. The short recurrence and the minimization properties have been shown to hold for the conjugate gradient methods for matrices that are selfadjoint and positive definite w.r.t. to the inner product used in the algorithm. The short recurrence holds for the biconjugate gradient-type Lanczos algorithms, also for nonsymmetric matrices, but these algorithms can break down when the matrix is indefinite.
In this chapter, it will first be shown that such short recurrence relations for the conjugate gradient minimization type algorithms exist for a broader class of matrices, the H-normal class w.r.t. the initial vector. This extends the applicability of these methods. However, many matrices occurring in practice belong to still more general classes. On the other hand, the Lanczos-type algorithms do not have a minimization property as a rule and, as just said, can even break down.
We shall also analyze a general class of methods based on minimizing the least square norm of the residual (w.r.t. an inner product) and using a set of search directions (orthogonal w.r.t. another inner product, in general).
- Type
- Chapter
- Information
- Iterative Solution Methods , pp. 504 - 557Publisher: Cambridge University PressPrint publication year: 1994
- 8
- Cited by