Iterative Solution of Large Sparse Systems of Equations

This book presents the description of the state of the modern iterative techniques together with systematic analysis. It discusses classical methods, semi-iterative techniques, incomplete decompositions, conjugate gradient methods, multigrid methods and domain decomposition techniques. Every technique described is illustrated by a Pascal program.

Inhalt

1. Introduction.- 1.1 Historical Remarks Concerning Iterative Methods.- 1.2 Model Problem (Poisson Equation).- 1.3 Amount of Work for the Direct Solution of the System of Equations.- 1.4 Examples of Iterative Methods.- 2. Recapitulation of Linear Algebra.- 2.1 Notations for Vectors and Matrices.- 2.2 Systems of Linear Equations.- 2.3 Permutation Matrices.- 2.4 Eigenvalues and Eigenvectors.- 2.5 Block-Vectors and Block-Matrices.- 2.6 Norms.- 2.7 Scalar Product.- 2.8 Normal Forms.- 2.9 Correlation Between Norms and the Spectral Radius.- 2.10 Positive Definite Matrices.- 3. Iterative Methods.- 3.1 General Statements Concerning Convergence.- 3.2 Linear Iterative Methods.- 3.3 Effectiveness of Iterative Methods.- 3.4 Test of Iterative Methods.- 3.5 Comments Concerning the Pascal Procedures.- 4. Methods of Jacobi and Gauß-Seidel and SOR Iteration in the Positive Definite Case.- 4.1 Eigenvalue Analysis of the Model Problem.- 4.2 Construction of Iterative Methods.- 4.3 Damped Iterative Methods.- 4.4 Convergence Analysis.- 4.5 Block Versions.- 4.6 Computational Work of the Methods.- 4.7 Convergence Rates in the Case of the Model Problem.- 4.8 Symmetric Iterations.- 5. Analysis in the 2-Cyclic Case.- 5.1 2-Cyclic Matrices.- 5.2 Preparatory Lemmata.- 5.3 Analysis of the Richardson Iteration.- 5.4 Analysis of the Jacobi Method.- 5.5 Analysis of the Gauß-Seidel Iteration.- 5.6 Analysis of the SOR Method.- 5.7 Application to the Model Problem.- 5.8 Supplementary Remarks.- 6. Analysis for M-Matrices.- 6.1 Positive Matrices.- 6.2 Graph of a Matrix and Irreducible Matrices.- 6.3 Perron-Frobenius Theory of Positive Matrices.- 6.4 M-Matrices.- 6.5 Regular Splittings.- 6.6 Applications.- 7. Semi-Iterative Methods.- 7.1 First Formulation.- 7.2 Second Formulation of a Semi-IterativeMethod.- 7.3 Optimal Polynomials.- 7.4 Application to Iterations Discussed Above.- 7.5 Method of Alternating Directions (ADI).- 8. Transformations, Secondary Iterations, Incomplete Triangular Decompositions.- 8.1 Generation of Iterations by Transformations.- 8.2 Kaczmarz Iteration.- 8.3 Preconditioning.- 8.4 Secondary Iterations.- 8.5 Incomplete Triangular Decompositions.- 8.6 A Superfluous Term: Time-Stepping Methods.- 9. Conjugate Gradient Methods.- 9.1 Linear Systems of Equations as Minimisation Problem.- 9.2 Gradient Method.- 9.3 The Method of the Conjugate Directions.- 9.4 Conjugate Gradient Method (cg Method).- 9.5 Generalisations.- 10. Multi-Grid Methods.- 10.1 Introduction.- 10.2 Two-Grid Method.- 10.3 Analysis for a One-Dimensional Example.- 10.4 Multi-Grid Iteration.- 10.5 Nested Iteration.- 10.6 Convergence Analysis.- 10.7 Symmetric Multi-Grid Methods.- 10.8 Combination of Multi-Grid Methods with Semi-Iterations.- 10.9 Further Comments.- 11. Domain Decomposition Methods.- 11.1 Introduction.- 11.2 Formulation of the Domain Decomposition Method.- 11.3 Properties of the Additive Schwarz Iteration.- 11.4 Analysis of the Multiplicative Schwarz Iteration.- 11.5 Examples.- 11.6 Multi-Grid Methods as Subspace Decomposition Method.- 11.7 Schur Complement Methods.