Young / Rheinboldt Iterative Solution of Large Linear Systems

1. Auflage 2014
ISBN: 978-1-4832-7413-3
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 598 Seiten, Web PDF

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.

Autoren/Hrsg.

Young, David M.

Rheinboldt, Werner

Inhaltsverzeichnis

1;Front Cover;1
2;Iterative Solution of Large Linear Systems;4
3;Copyright Page;5
4;Table of Contents;8
5;Dedication;6
6;Preface;14
7;Acknowledgments;18
8;Notation;20
9;List of Fundamental Matrix Properties;22
10;List of Iterative Methods;24
11;Chapter 1. Introduction;28
11.1;1.1. The Model Problem;29
11.2;Supplementary Discussion;33
11.3;Exercises;33
12;Chapter 2. Matrix Preliminaries;34
12.1;2.1. Review of Matrix Theory;34
12.2;2.2. Hermitian Matrices and Positive Definite Matrices;45
12.3;2.3. Vector Norms and Matrix Norms;52
12.4;2.4. Convergence of Sequences of Vectors and Matrices;61
12.5;2.5. Irreducibility and Weak Diagonal Dominance;63
12.6;2.6. Property A;68
12.7;2.7. L-Matrices and Related Matrices;69
12.8;2.8. Illustrations;75
12.9;Supplementary Discussion;80
12.10;Exercises;82
13;Chapter 3. Linear Stationary Iterative Methods;90
13.1;3.1. Introduction;90
13.2;3.2. Consistency, Reciprocal Consistency, and Complete Consistency;92
13.3;3.3. Basic Linear Stationary Iterative Methods;97
13.4;3.4. Generation of Completely Consistent Methods;102
13.5;3.5. General Convergence Theorems;104
13.6;3.6. Alternative Convergence Conditions;107
13.7;3.7. Rates of Convergence;111
13.8;3.8. The Jordan Condition Number of a 2 × 2 Matrix;116
13.9;Supplementary Discussion;121
13.10;Exercises;122
14;Chapter 4. Convergence of the Basic Iterative Methods;133
14.1;4.1. General Convergence Theorems;133
14.2;4.2. Irreducible Matrices with Weak Diagonal Dominance;134
14.3;4.3. Positive Definite Matrices;135
14.4;4.4. The SOR Method with Varying Relaxation Factors;145
14.5;4.5. L-Matrices and Related Matrices;147
14.6;4.6. Rates of Convergence of the J and GS Methods for the Model Problem;154
14.7;Supplementary Discussion;159
14.8;Exercises;160
15;Chapter 5. Eigenvalues of the SOR Method for Consistently Ordered Matrices;167
15.1;5.1. Introduction;167
15.2;5.2. Block Tri-Diagonal Matrices;168
15.3;5.3. Consistently Ordered Matrices and Ordering Vectors;171
15.4;5.4. Property A;175
15.5;5.5. Nonmigratory Permutations;180
15.6;5.6. Consistently Ordered Matrices Arising from Difference Equations;184
15.7;5.7. A Computer Program for Testing for Property A and Consistent Ordering;186
15.8;5.8. Other Developments of the SOR Theory;189
15.9;Supplementary Discussion;190
15.10;Exercises;190
16;Chapter 6. Determination of the Optimum Relaxation Factor;196
16.1;6.1. Virtual Spectral Radius;197
16.2;6.2. Analysis of the Case Where All Eigenvalues of B Are Real;198
16.3;6.3. Rates of Convergence: Comparison with the Gauss-Seidel Method;215
16.4;6.4. Analysis of the Case Where Some Eigenvalues of B Are Complex;218
16.5;6.5. Practical Determination of .b General Considerations;227
16.6;6.6. Iterative Methods of Choosing .b;236
16.7;6.7. An Upper Bound for µ;238
16.8;6.8. A Priori Determination of µ: Exact Methods;243
16.9;6.9. A Priori Determination of µ: Approximate Values;249
16.10;6.10. Numerical Results;251
16.11;Supplementary Discussion;254
16.12;Exercises;255
17;Chapter 7. Norms of the SOR Method;260
17.1;7.1. The Jordan Canonical Form of L.;261
17.2;7.2. Basic Eigenvalue Relation;266
17.3;7.3. Determination of || L. ||D;272
17.4;7.4. Determination of || L. ||D;275
17.5;7.5. Determination of || L. ||A;282
17.6;7.6. Determination of || L. ||A;285
17.7;7.7. Comparison of || L.mb ||D and || L.mb IIA;291
17.8;Supplementary Discussion;292
17.9;Exercises;293
18;Chapter 8. The Modified SOR Method: Fixed Parameters;298
18.1;8.1. Introduction;298
18.2;8.2. Eigenvalues of L.,.';300
18.3;8.3. Convergence and Spectral Radius;304
18.4;8.4. Determination of || L.,.' ||D;310
18.5;8.5. Determination of || L.,.' IIA;315
18.6;Supplementary Discussion;318
18.7;Exercises;318
19;Chapter 9. Nonstationary Linear Iterative Methods;322
19.1;9.1. Consistency, Convergence, and Rates of Convergence;322
19.2;9.2. Periodic Nonstationary Methods;327
19.3;9.3. Chebyshev Polynomials;328
19.4;Supplementary Discussion;331
19.5;Exercises;331
20;Chapter 10. The Modified SOR Method: Variable Parameters;333
20.1;10.1. Convergence of the MSOR Method;334
20.2;10.2. Optimum Choice of Relaxation Factors;334
20.3;10.3. Alternative Optimum Parameter Sets;338
20.4;10.4. Norms of the MSOR Method: Sheldon's Method;342
20.5;10.5. The Modified Sheldon Method;346
20.6;10.6. Cyclic Chebyshev Semi-Iterative Method;348
20.7;10.7. Comparison of Norms;354
20.8;Supplementary Discussion;367
20.9;Exercises;368
21;Chapter 11. Semi-Iterative Methods;371
21.1;11.1. General Considerations;372
21.2;11.2. The Case Where G Has Real Eigenvalues;374
21.3;11.3. J, JOR, and RF Semi-Iterative Methods;382
21.4;11.4. Richardson's Method;388
21.5;11.5. Cyclic Chebyshev Semi-Iterative Method;392
21.6;11.6. GS Semi-Iterative Methods;394
21.7;11.7. SOR Semi-Iterative Methods;401
21.8;11.8. MSOR Semi-Iterative Methods;403
21.9;11.9. Comparison of Norms;410
21.10;Supplementary Discussion;412
21.11;Exercises;413
22;Chapter 12. Extensions of the SOR Theory: Stieltjes Matrices;418
22.1;12.1. The Need for Some Restrictions on A;418
22.2;12.2. Stieltjes Matrices;422
22.3;Supplementary Discussion;428
22.4;Exercises;428
23;Chapter 13. Generalized Consistently Ordered Matrices;431
23.1;13.1. Introduction;431
23.2;13.2. CO(q, r)-Matrices, Property Aq,r' and Ordering Vectors;432
23.3;13.3. Determination of the Optimum Relaxation Factor;440
23.4;13.4. Generalized Consistently Ordered Matrices;445
23.5;13.5. Relation between GCO(q, r)-Matrices and CO(q, r)-Matrices;446
23.6;13.6. Computational Procedures: Canonical Forms;449
23.7;13.7. Relation to Other Work;455
23.8;Supplementary Discussion;456
23.9;Exercises;457
24;Chapter 14. Group Iterative Methods;461
24.1;14.1. Construction of Group Iterative Methods;462
24.2;14.2. Solution of a Linear System with a Tri-Diagonal Matrix;468
24.3;14.3. Convergence Analysis;472
24.4;14.4. Applications;479
24.5;14.5. Comparison of Point and Group Iterative Methods;481
24.6;Supplementary Discussion;483
24.7;Exercises;484
25;Chapter 15. Symmetric SOR Method and Related Methods;488
25.1;15.1. Introduction;488
25.2;15.2. Convergence Analysis;490
25.3;15.3. Choice of Relaxation Factor;491
25.4;15.4. SSOR Semi-Iterative Methods: The Discrete Dirichlet Problem;498
25.5;15.5. Group SSOR Methods;501
25.6;15.6. Unsymmetric SOR Method;503
25.7;15.7. Symmetric and Unsymmetric MSOR Methods;505
25.8;Supplementary Discussion;507
25.9;Exercises;508
26;Chapter 16. Second-Degree Methods;513
26.1;Supplementary Discussion;520
26.2;Exercises;520
27;Chapter 17. Alternating Direction Implicit Methods;522
27.1;17.1. Introduction: The Peaceman-Rachford Method;522
27.2;17.2. The Stationary Case: Consistency and Convergence;525
27.3;17.3. The Stationary Case: Choice of Parameters;530
27.4;17.4. The Commutative Case;541
27.5;17.5. Optimum Parameters;545
27.6;17.6. Good Parameters;552
27.7;17.7. The Helmholtz Equation in a Rectangle;558
27.8;17.8. Monotonicity;561
27.9;17.9. Necessary and Sufficient Conditions for the Commutative Case;562
27.10;17.10. The Noncommutative Case;572
27.11;Supplementary Discussion;574
27.12;Exercises;575
28;Chapter 18. Selection of Iterative Method;580
29;Bibliography;583
30;Index;592