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
6 - M-Matrices, Convergent Splittings, and the SOR Method
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
A crucial task in the construction of efficient basic iterative methods is the choice of a splitting of the given matrix, A = C − R, into two matrices, C and R. At each iteration step of such a method, we must solve a linear system with C. This matrix is sometimes called a preconditioning matrix; it must be simple (in a certain respect) but still effective for the increase of the rate of convergence. The case where the corresponding preconditioning matrix is triangular or block-triangular and A is a so-called M-matrix is of particular importance because it appears frequently in practice. Let us first study some general properties of M-matrices and general families of convergent splittings. Several principles for comparing the rate of convergence of different splittings are also presented.
Even if a given matrix is not a M-matrix, we show next that any symmetric positive definite matrix can be reduced to a Stieltjes matrix by using a method of diagonal compensation of reduced positive entries. Splittings for the reduced matrix can be used as splittings for the original matrix.
By introducing a relaxation parameter (ω) as in the successive overrelaxation (SOR) method, we show that a proper choice of this parameter sometimes can speed up the rate of convergence by an order of magnitude. It turns out that the theory for this method can be based on some of the results already derived in the previous chapter.
- Type
- Chapter
- Information
- Iterative Solution Methods , pp. 200 - 251Publisher: Cambridge University PressPrint publication year: 1994