COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Iterative Solution of Large Linear Systems - 1st Edition - ISBN: 9780127730509, 9781483274133

Iterative Solution of Large Linear Systems

1st Edition

0.0 star rating Write a review
Author: David M. Young
Editor: Werner Rheinboldt
eBook ISBN: 9781483274133
Imprint: Academic Press
Published Date: 28th July 1971
Page Count: 598
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


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.

Table of Contents




List of Fundamental Matrix Properties

List of Iterative Methods

1. Introduction

1.1. The Model Problem

Supplementary Discussion


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


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


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


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


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


7. Norms of the SOR Method

7.1. The Jordan Canonical Form of ℒ ω

7.2. Basic Eigenvalue Relation

7.3. Determination of ∥ℒ ω∥D1/2

7.4. Determination of ∥ℒm ωb∥D1/2

7.5. Determination of ∥ℒ ω∥A1/2

7.6. Determination of ∥ℒm ωb∥A1/2

7.7. Comparison of ∥ℒm ωb∥D1/2 and ∥ℒm ωb∥A1/2

Supplementary Discussion


8. The Modified SOR Method: Fixed Parameters

8.1. Introduction

8.2. Eigenvalues of ℒω, ω1

8.3. Convergence and Spectral Radius

8.4. Determination of ∥ℒω, ω1∥D1/2

8.5. Determination of ∥ℒω, ω1∥A1/2

Supplementary Discussion


9. Nonstationary Linear Iterative Methods

9.1. Consistency, Convergence, and Rates of Convergence

9.2. Periodic Nonstationary Methods

9.3. Chebyshev Polynomials

Supplementary Discussion


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


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


12. Extensions of the SOR Theory: Stieltjes Matrices

12.1. The Need for Some Restrictions on A

12.2. Stieltjes Matrices

Supplementary Discussion


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


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


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


16. Second-Degree Methods

Supplementary Discussion


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


18. Selection of Iterative Method




No. of pages:
© Academic Press 1971
28th July 1971
Academic Press
eBook ISBN:

About the Author

David M. Young

About the Editor

Werner Rheinboldt

Ratings and Reviews