ISBN: 3-540-66321-5
TITLE: Matrix Iterative Analysis
AUTHOR: Varga, Richard S.
TOC:

1. Matrix Properties and Concepts 1
1.1 Introduction 1
1.2 A Simple Example 3
1.3 Norms and Spectral Radii 7
1.4 Bounds for the Spectral Radius of a Matrix and Directed Graphs 16
1.5 Diagonally Dominant Matrices 22
1.6 Ovals of Cassini 24
2. Nonnegative Matrices 31
2.1 Spectral Radii of Nonnegative Matrices 31
2.2 Cyclic and Primitive Matrices 40
2.3 Reducible Matrices 50
2.4 Nonnegative Matrices and Directed Graphs 53
3. Basic Iterative Methods and Comparison Theorems 63
3.1 The Point Jacobi, Gauss-Seidel, and Successive Overrelaxation Iterative Methods 63
3.2 Average Rates of Convergence 68
3.3 The Stein-Rosenberg Theorem 74
3.4 The Ostrowski-Reich Theorem 81
3.5 Stieltjes Matrices, M-Matrices and H-Matrices 87
3.6 Regular and Weak Regular Splittings of Matrices 94
4. Successive Overrelaxation Iterative Methods 111
4.1 p-Cyclic Matrices 111
4.2 The Successive Overrelaxation Iterative Method for p-Cyclic Matrices 119
4.3 Theoretical Determination of an Optimum Relaxation Factor 123
4.4 Extensions of the 2-Cyclic Theory of Matrices 130
4.5 Asymptotic Rates of Convergence 141
4.6 CO(q, r) and GCO(q, r): Generalized Consistent Orderings 143
5. Semi-Iterative Methods 149
5.1 Semi-Iterative Methods and Chebyshev Polynomials 149
5.2 Relationship of Semi-Iterative Methods to Successive Overrelaxation Iterative Methods 158
5.3 Comparison of Average Rates of Convergence: the Weakly Cyclic Case 165
5.4 Cyclic Reduction and Related Iterative Methods 170
5.5 Semi-Iterative Methods Applied to the Successive Overrelaxation Method 174
6. Derivation and Solution of Elliptic Difference Equations 183
6.1 A Simple Two-Point Boundary-Value Problem 183
6.2 General Second-Order Ordinary Differential Equations 196
6.3 Derivation of Finite Difference Approximations in Higher Dimensions 204
6.4 Factorization Techniques and Block Iterative Methods 219
6.5 Asymptotic Convergence Rates for the Model Problem 226
7. Alternating-Direction Implicit Iterative Methods 235
7.1 The Peaceman-Rachford Iterative Method 235
7.2 The Commutative Case 245
7.3 The Noncommutative Case 255
7.4 Variants of the Peaceman-Rachford Iterative Method 264
8. Matrix Methods for Parabolic Partial Differential Equations 275
8.1 Semi-Discrete Approximation 275
8.2 Essentially Positive Matrices 281
8.3 Matrix Approximations for exp(-tS) 287
8.4 Relationship with Iterative Methods for Solving Elliptic Difference Equations 296
8.5 Chebyshev Rational Approximations for exp(-tS) 304
9. Estimation of Acceleration Parameters 313
9.1 Application of the Theory of Nonnegative Matrices 313
9.2 Application of Isoperimetric Inequalities 321
A. Appendix 329
B. Appendix 333
References 337
Index 355
END
