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.

Autorentext

Wolfgang Hackbusch is a Professor in the Scientific Computing department at Max Planck Institute for Mathematics in the Sciences. His research areas include numerical treatment of partial differential equations, numerical treatment of integral equations, and hierarchical matrices.

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.