Iterative Solution of Large Linear Systems
David M. Young(Author)
Werner Rheinboldt(Editor)
Academic Press
Published on 23. September 1971
Book
Hardback
598 pages
978-0-12-773050-9 (ISBN)
Description
Iterative Solution of Large Linear Systems describes the systematic development of a substantial portion of the theory of iterative methods for solving large linear systems, with emphasis on practical techniques. The focal point of the book is an analysis of the convergence properties of the successive overrelaxation (SOR) method as applied to a linear system where the matrix is "consistently ordered". Comprised of 18 chapters, this volume begins by showing how the solution of a certain partial differential equation by finite difference methods leads to a large linear system with a sparse matrix. The next chapter reviews matrix theory and the properties of matrices, as well as several theorems of matrix theory without proof. A number of iterative methods, including the SOR method, are then considered. Convergence theorems are also given for various iterative methods under certain assumptions on the matrix A of the system. Subsequent chapters deal with the eigenvalues of the SOR method for consistently ordered matrices; the optimum relaxation factor; nonstationary linear iterative methods; and semi-iterative methods. This book will be of interest to students and practitioners in the fields of computer science and applied mathematics.
More details
Language
English
Place of publication
San Diego
United States
Publishing group
Elsevier Science Publishing Co Inc
Target group
College/higher education
Professional and scholarly
Weight
970 gr
ISBN-13
978-0-12-773050-9 (9780127730509)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions

David M. Young | Werner Rheinboldt
Iterative Solution of Large Linear Systems
E-Book
05/2014
Academic Press
€70.95
Available for download
Content
Preface
Acknowledgments
Notation
List of Fundamental Matrix Properties
List of Iterative Methods
1. Introduction
1.1. The Model Problem
Supplementary Discussion
Exercises
2. Matrix Preliminaries
2.1. Review of Matrix Theory
2.2. Hermitian Matrices and Positive Definite Matrices
2.3. Vector Norms and Matrix Norms
2.4. Convergence of Sequences of Vectors and Matrices
2.5. Irreducibility and Weak Diagonal Dominance
2.6. Property A
2.7. L-Matrices and Related Matrices
2.8. Illustrations
Supplementary Discussion
Exercises
3. Linear Stationary Iterative Methods
3.1. Introduction
3.2. Consistency, Reciprocal Consistency, and Complete Consistency
3.3. Basic Linear Stationary Iterative Methods
3.4. Generation of Completely Consistent Methods
3.5. General Convergence Theorems
3.6. Alternative Convergence Conditions
3.7. Rates of Convergence
3.8. The Jordan Condition Number of a 2 x 2 Matrix
Supplementary Discussion
Exercises
4. Convergence of the Basic Iterative Methods
4.1. General Convergence Theorems
4.2. Irreducible Matrices with Weak Diagonal Dominance
4.3. Positive Definite Matrices
4.4. The SOR Method with Varying Relaxation Factors
4.5. L-Matrices and Related Matrices
4.6. Rates of Convergence of the J and GS Methods for the Model Problem
Supplementary Discussion
Exercises
5. Eigenvalues of the SOR Method for Consistently Ordered Matrices
5.1. Introduction
5.2. Block Tri-Diagonal Matrices
5.3. Consistently Ordered Matrices and Ordering Vectors
5.4. Property A
5.5. Nonmigratory Permutations
5.6. Consistently Ordered Matrices Arising from Difference Equations
5.7. A Computer Program for Testing for Property A and Consistent Ordering
5.8. Other Developments of the SOR Theory
Supplementary Discussion
Exercises
6. Determination of the Optimum Relaxation Factor
6.1. Virtual Spectral Radius
6.2. Analysis of the Case Where All Eigenvalues of B Are Real
6.3. Rates of Convergence: Comparison with the Gauss-Seidel Method
6.4. Analysis of the Case Where Some Eigenvalues of B Are Complex
6.5. Practical Determination of ?b: General Considerations
6.6. Iterative Methods of Choosing ?b
6.7. An Upper Bound for ?
6.8. A Priori Determination of ?: Exact Methods
6.9. A Priori Determination of ?: Approximate Values
6.10. Numerical Results
Supplementary Discussion
Exercises
7. Norms of the SOR Method
7.1. The Jordan Canonical Form of L ?
7.2. Basic Eigenvalue Relation
7.3. Determination of ?L ??D1/2
7.4. Determination of ?Lm ?b?D1/2
7.5. Determination of ?L ??A1/2
7.6. Determination of ?Lm ?b?A1/2
7.7. Comparison of ?Lm ?b?D1/2 and ?Lm ?b?A1/2
Supplementary Discussion
Exercises
8. The Modified SOR Method: Fixed Parameters
8.1. Introduction
8.2. Eigenvalues of L?, ?1
8.3. Convergence and Spectral Radius
8.4. Determination of ?L?, ?1?D1/2
8.5. Determination of ?L?, ?1?A1/2
Supplementary Discussion
Exercises
9. Nonstationary Linear Iterative Methods
9.1. Consistency, Convergence, and Rates of Convergence
9.2. Periodic Nonstationary Methods
9.3. Chebyshev Polynomials
Supplementary Discussion
Exercises
10. The Modified SOR Method: Variable Parameters
10.1. Convergence of the MSOR Method
10.2. Optimum Choice of Relaxation Factors
10.3. Alternative Optimum Parameter Sets
10.4. Norms of the MSOR Method: Sheldon's Method
10.5. The Modified Sheldon Method
10.6. Cyclic Chebyshev Semi-Iterative Method
10.7. Comparison of Norms
Supplementary Discussion
Exercises
11. Semi-Iterative Methods
11.1. General Considerations
11.2. The Case Where G Has Real Eigenvalues
11.3. J, JOR, and RF Semi-Iterative Methods
11.4. Richardson's Method
11.5. Cyclic Chebyshev Semi-Iterative Method
11.6. GS Semi-Iterative Methods
11.7. SOR Semi-Iterative Methods
11.8. MSOR Semi-Iterative Methods
11.9. Comparison of Norms
Supplementary Discussion
Exercises
12. Extensions of the SOR Theory: Stieltjes Matrices
12.1. The Need for Some Restrictions on A
12.2. Stieltjes Matrices
Supplementary Discussion
Exercises
13. Generalized Consistently Ordered Matrices
13.1. Introduction
13.2. CO(q, r)-Matrices, Property Aq,r, and Ordering Vectors
13.3. Determination of the Optimum Relaxation Factor
13.4. Generalized Consistently Ordered Matrices
13.5. Relation Between GCO(q, r)-Matrices and CO(q, r)-Matrices
13.6. Computational Procedures: Canonical Forms
13.7. Relation to Other Work
Supplementary Discussion
Exercises
14. Group Iterative Methods
14.1. Construction of Group Iterative Methods
14.2. Solution of a Linear System with a Tri-Diagonal Matrix
14.3. Convergence Analysis
14.4. Applications
14.5. Comparison of Point and Group Iterative Methods
Supplementary Discussion
Exercises
15. Symmetric SOR Method and Related Methods
15.1. Introduction
15.2. Convergence Analysis
15.3. Choice of Relaxation Factor
15.4. SSOR Semi-Iterative Methods: The Discrete Dirichlet Problem
15.5. Group SSOR Methods
15.6. Unsymmetric SOR Method
15.7. Symmetric and Unsymmetric MSOR Methods
Supplementary Discussion
Exercises
16. Second-Degree Methods
Supplementary Discussion
Exercises
17. Alternating Direction Implicit Methods
17.1. Introduction: The Peaceman-Rachford Method
17.2. The Stationary Case: Consistency and Convergence
17.3. The Stationary Case: Choice of Parameters
17.4. The Commutative Case
17.5. Optimum Parameters
17.6. Good Parameters
17.7. The Helmholtz Equation in a Rectangle
17.8. Monotonicity
17.9. Necessary and Sufficient Conditions for the Commutative Case
17.10. The Noncommutative Case
Supplementary Discussion
Exercises
18. Selection of Iterative Method
Bibliography
Index
Acknowledgments
Notation
List of Fundamental Matrix Properties
List of Iterative Methods
1. Introduction
1.1. The Model Problem
Supplementary Discussion
Exercises
2. Matrix Preliminaries
2.1. Review of Matrix Theory
2.2. Hermitian Matrices and Positive Definite Matrices
2.3. Vector Norms and Matrix Norms
2.4. Convergence of Sequences of Vectors and Matrices
2.5. Irreducibility and Weak Diagonal Dominance
2.6. Property A
2.7. L-Matrices and Related Matrices
2.8. Illustrations
Supplementary Discussion
Exercises
3. Linear Stationary Iterative Methods
3.1. Introduction
3.2. Consistency, Reciprocal Consistency, and Complete Consistency
3.3. Basic Linear Stationary Iterative Methods
3.4. Generation of Completely Consistent Methods
3.5. General Convergence Theorems
3.6. Alternative Convergence Conditions
3.7. Rates of Convergence
3.8. The Jordan Condition Number of a 2 x 2 Matrix
Supplementary Discussion
Exercises
4. Convergence of the Basic Iterative Methods
4.1. General Convergence Theorems
4.2. Irreducible Matrices with Weak Diagonal Dominance
4.3. Positive Definite Matrices
4.4. The SOR Method with Varying Relaxation Factors
4.5. L-Matrices and Related Matrices
4.6. Rates of Convergence of the J and GS Methods for the Model Problem
Supplementary Discussion
Exercises
5. Eigenvalues of the SOR Method for Consistently Ordered Matrices
5.1. Introduction
5.2. Block Tri-Diagonal Matrices
5.3. Consistently Ordered Matrices and Ordering Vectors
5.4. Property A
5.5. Nonmigratory Permutations
5.6. Consistently Ordered Matrices Arising from Difference Equations
5.7. A Computer Program for Testing for Property A and Consistent Ordering
5.8. Other Developments of the SOR Theory
Supplementary Discussion
Exercises
6. Determination of the Optimum Relaxation Factor
6.1. Virtual Spectral Radius
6.2. Analysis of the Case Where All Eigenvalues of B Are Real
6.3. Rates of Convergence: Comparison with the Gauss-Seidel Method
6.4. Analysis of the Case Where Some Eigenvalues of B Are Complex
6.5. Practical Determination of ?b: General Considerations
6.6. Iterative Methods of Choosing ?b
6.7. An Upper Bound for ?
6.8. A Priori Determination of ?: Exact Methods
6.9. A Priori Determination of ?: Approximate Values
6.10. Numerical Results
Supplementary Discussion
Exercises
7. Norms of the SOR Method
7.1. The Jordan Canonical Form of L ?
7.2. Basic Eigenvalue Relation
7.3. Determination of ?L ??D1/2
7.4. Determination of ?Lm ?b?D1/2
7.5. Determination of ?L ??A1/2
7.6. Determination of ?Lm ?b?A1/2
7.7. Comparison of ?Lm ?b?D1/2 and ?Lm ?b?A1/2
Supplementary Discussion
Exercises
8. The Modified SOR Method: Fixed Parameters
8.1. Introduction
8.2. Eigenvalues of L?, ?1
8.3. Convergence and Spectral Radius
8.4. Determination of ?L?, ?1?D1/2
8.5. Determination of ?L?, ?1?A1/2
Supplementary Discussion
Exercises
9. Nonstationary Linear Iterative Methods
9.1. Consistency, Convergence, and Rates of Convergence
9.2. Periodic Nonstationary Methods
9.3. Chebyshev Polynomials
Supplementary Discussion
Exercises
10. The Modified SOR Method: Variable Parameters
10.1. Convergence of the MSOR Method
10.2. Optimum Choice of Relaxation Factors
10.3. Alternative Optimum Parameter Sets
10.4. Norms of the MSOR Method: Sheldon's Method
10.5. The Modified Sheldon Method
10.6. Cyclic Chebyshev Semi-Iterative Method
10.7. Comparison of Norms
Supplementary Discussion
Exercises
11. Semi-Iterative Methods
11.1. General Considerations
11.2. The Case Where G Has Real Eigenvalues
11.3. J, JOR, and RF Semi-Iterative Methods
11.4. Richardson's Method
11.5. Cyclic Chebyshev Semi-Iterative Method
11.6. GS Semi-Iterative Methods
11.7. SOR Semi-Iterative Methods
11.8. MSOR Semi-Iterative Methods
11.9. Comparison of Norms
Supplementary Discussion
Exercises
12. Extensions of the SOR Theory: Stieltjes Matrices
12.1. The Need for Some Restrictions on A
12.2. Stieltjes Matrices
Supplementary Discussion
Exercises
13. Generalized Consistently Ordered Matrices
13.1. Introduction
13.2. CO(q, r)-Matrices, Property Aq,r, and Ordering Vectors
13.3. Determination of the Optimum Relaxation Factor
13.4. Generalized Consistently Ordered Matrices
13.5. Relation Between GCO(q, r)-Matrices and CO(q, r)-Matrices
13.6. Computational Procedures: Canonical Forms
13.7. Relation to Other Work
Supplementary Discussion
Exercises
14. Group Iterative Methods
14.1. Construction of Group Iterative Methods
14.2. Solution of a Linear System with a Tri-Diagonal Matrix
14.3. Convergence Analysis
14.4. Applications
14.5. Comparison of Point and Group Iterative Methods
Supplementary Discussion
Exercises
15. Symmetric SOR Method and Related Methods
15.1. Introduction
15.2. Convergence Analysis
15.3. Choice of Relaxation Factor
15.4. SSOR Semi-Iterative Methods: The Discrete Dirichlet Problem
15.5. Group SSOR Methods
15.6. Unsymmetric SOR Method
15.7. Symmetric and Unsymmetric MSOR Methods
Supplementary Discussion
Exercises
16. Second-Degree Methods
Supplementary Discussion
Exercises
17. Alternating Direction Implicit Methods
17.1. Introduction: The Peaceman-Rachford Method
17.2. The Stationary Case: Consistency and Convergence
17.3. The Stationary Case: Choice of Parameters
17.4. The Commutative Case
17.5. Optimum Parameters
17.6. Good Parameters
17.7. The Helmholtz Equation in a Rectangle
17.8. Monotonicity
17.9. Necessary and Sufficient Conditions for the Commutative Case
17.10. The Noncommutative Case
Supplementary Discussion
Exercises
18. Selection of Iterative Method
Bibliography
Index