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.

Zur Zeit liegt uns keine Inhaltsangabe vor.

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.1.1 Nonordered Index Sets.- 2.1.2 Notations.- 2.1.3 Star Notation.- 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.6.1 Vector Norms.- 2.6.2 Equivalence of All Norms.- 2.6.3 Corresponding Matrix Norms.- 2.7 Scalar Product.- 2.8 Normal Forms.- 2.8.1 Schur Normal Form.- 2.8.2 Jordan Normal Form.- 2.8.3 Diagonalisability.- 2.9 Correlation Between Norms and the Spectral Radius.- 2.9.1 Corresponding Matrix Norms as Upper Bound for the Eigenvalues.- 2.9.2 Spectral Norm.- 2.9.3 Matrix Norm Approximating the Spectral Radius.- 2.9.4 Geometrical Sum (Neumann's Series) for Matrices.- 2.9.5 Numerical Radius of a Matrix.- 2.10 Positive Definite Matrices.- 2.10.1 Definition and Notations.- 2.10.2 Rules and Criteria for Positive Definite Matrices.- 2.10.3 Remarks Concerning Positive Definite Matrices.- 3. Iterative Methods.- 3.1 General Statements Concerning Convergence.- 3.1.1 Notations.- 3.1.2 Fixed Points.- 3.1.3 Consistency.- 3.1.4 Convergence.- 3.1.5 Convergence and Consistency.- 3.2 Linear Iterative Methods.- 3.2.1 Notations, First Normal Form.- 3.2.2 Consistency, Second and Third Normal Form.- 3.2.3 Representation of the Iterates xm.- 3.2.4 Convergence.- 3.2.5 Convergence Speed.- 3.2.6 Remarks Concerning the Matrices M, N, and W.- 3.2.7 Product Iterations.- 3.2.8 Three-Term Recursions (Two-Step Iterations).- 3.3 Effectiveness of Iterative Methods.- 3.3.1 Amount of Computational Work.- 3.3.2 Effectiveness.- 3.3.3 Order of the Linear Convergence.- 3.4 Test of Iterative Methods.- 3.5 Comments Concerning the Pascal Procedures.- 3.5.1 Pascal.- 3.5.2 Concerning the Test Examples.- 3.5.3 Constants and Types.- 3.5.4 Format of the Iteration Procedures.- 3.5.5 Test Environment.- 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.2.1 Jacobi Iteration.- 4.2.1.1 Additive Splitting of the Matrix A.- 4.2.1.2 Definition of the Jacobi Method.- 4.2.1.3 Pascal Procedure.- 4.2.2 Gauß-Seidel Method.- 4.2.2.1 Definition.- 4.2.2.2 Pascal Procedure.- 4.3 Damped Iterative Methods.- 4.3.1 Damped Jacobi Method.- 4.3.1.1 Damping of a General Iterative Method.- 4.3.1.2 Pascal Procedures.- 4.3.2 Richardson Iteration.- 4.3.2.1 Definition.- 4.3.2.2 Pascal Procedures.- 4.3.3 SOR Method.- 4.3.3.1 Definition.- 4.3.3.2 Pascal Procedures.- 4.4 Convergence Analysis.- 4.4.1 Richardson Iteration.- 4.4.2 Jacobi Iteration.- 4.4.3 Gauß-Seidel and SOR Methods.- 4.5 Block Versions.- 4.5.1 Block-Jacobi Method.- 4.5.1.1 Definition.- 4.5.1.2 Pascal Procedures.- 4.5.2 Block-Gauß-Seidel and Block-SOR Method.- 4.5.2.1 Definition.- 4.5.2.2 Pascal Procedures.- 4.5.3 Convergence of the Block Variants.- 4.6 Computational Work of the Methods.- 4.6.1 Case of General Sparse Matrices.- 4.6.2 Amount of Work in the Model Case.- 4.7 Convergence Rates in the Case of the Model Problem.- 4.7.1 Richardson and Jacobi Iteration.- 4.7.2 Block-Jacobi Iteration.- 4.7.3 Numerical Examples for the Jacobi Variants.- 4.7.4 SOR and Block-SOR Iteration with Numerical Examples.- 4.8 Symmetric Iterations.- 4.8.1 General Form of the Symmetric Iteration.- 4.8.2 Convergence.- 4.8.3 Symmetric Gauß-Seidel Method.- 4.8.4 Adjoint and Corresponding Symmetric Iterations.- 4.8.5 SSOR: Symmetric SOR.- 4.8.6 Pascal Procedures and Numerical Results for the SSOR Method.- 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.6.1 Consistently Ordered Matrices.- 5.6.2 Theorem of Young.- 5.6.3 Order Improvement by SOR.- 5.6.4 Practical Handling of the SOR Method.- 5.7 Application to the Model Problem.- 5.7.1 Analysis in the Model Case.- 5.7.2 Gauß-Seidel Iteration: Numerical Examples.- 5.7.3 SOR Iteration: Numerical Examples.- 5.8 Supplementary Remarks.- 5.8.1 p-Cyclic Matrices.- 5.8.2 Modified SOR.- 5.8.3 SSOR in the 2-Cyclic Case.- 5.8.4 Unsymmetric SOR Method.- 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.4.1 Definition.- 6.4.2 Connection Between M-Matrices and Jacobi Iteration.- 6.4.3 Diagonal Dominance.- 6.4.4 Further Criteria.- 6.5 Regular Splittings.- 6.6 Applications.- 7. Semi-Iterative Methods.- 7.1 First Formulation.- 7.1.1 The Semi-Iterative Sequence.- 7.1.2 Consistency and Asymptotical Convergence Rate.- 7.1.3 Error Representation.- 7.2 Second Formulation of a Semi-Iterative Method.- 7.2.1 General Representation.- 7.2.2 Pascal Implementation of the Second Formulation.- 7.2.3 Three-Term Recursion.- 7.3 Optimal Polynomials.- 7.3.1 Minimisation Problem.- 7.3.2 Discussion of the Second Minimisation Problem.- 7.3.3 Chebyshev Polynomials.- 7.3.4 Chebyshev Method.- 7.3.5 Order Improvement by the Chebyshev Method.- 7.3.6 Optimisation over Other Sets.- 7.3.7 Cyclic Iteration.- 7.3.8 Reformulation.- 7.3.9 Multi-Step Iterations.- 7.3.10 Pascal Procedures.- 7.3.11 Amount of Work of the Semi-Iterative Method.- 7.4 Application to Iterations Discussed Above.- 7.4.1 Preliminaries.- 7.4.2 Semi-Iterative Richardson Method.- 7.4.3 Semi-Iterative Jacobi and Block-Jacobi Method.- 7.4.4 Semi-Iterative SSOR and Block-SSOR Method.- 7.5 Method of Alternating Directions (ADI).- 7.5.1 Application to the Model Problem.- 7.5.2 General Representation.- 7.5.3 ADI Method in the Commutative Case.- 7.5.4 ADI Method and Semi-Iterative Methods.- 7.5.5 Pascal Procedures.- 7.5.6 Amount of Work and Numerical Examples.- 8. Transformations, Secondary Iterations, Incomplete Triangular Decompositions.- 8.1 Generation of Iterations by Transformations.- 8.1.1 Already Discussed Techniques for Generating, Iterations.- 8.1.2 Left Transformation.- 8.1.3 Right Transformation.- 8.1.4 Two-Sided Transformation.- 8.2 Kaczmarz Iteration.- 8.2.1 Original Formulation.- 8.2.2 Interpretaton as Gauß-Seidel Method.- 8.2.3 Pascal Procedures and Numerical Examples.- 8.3 Preconditioning.- 8.3.1 Meaning of «Preconditioning».- 8.3.2 Examples.- 8.3.3 Rules of Calculation for Condition Numbers.- 8.4 Secondary Iterations.- 8.4.1 Examples of Secondary Iterations.- 8.4.2 Convergence Analysis in the General Case.- 8.4.3 Analysis in the Symmetric Case.- 8.4.4 Estimate of the Amount of Work.- 8.4.5 Pascal Procedures.- 8.4.6 Numerical Examples.- 8.5 Incomplete Triangular Decompositions.- 8.5.1 Introduction and ILU Iteration.- 8.5.2 Incomplete Decomposition with Respect to a Star Pattern.- 8.5.3 Application to General Five-Point Formulae.- 8.5.4 Modified ILU Decompositions.- 8.5.5 On the Existence and Stability of the ILU Decomposition.- 8.5.6 Properties of the ILU Decomposition.- 8.5.7 ILU Decompositions Corresponding to Other Patterns.- 8.5.8 Approximative ILU Decompositions.- 8.5.9 Blockwise ILU Decompositions.- 8.5.10 Pascal Procedures.- 8.5.11 Numerical Examples.- 8.5.12 Comments.- 8.6 A Superfluous Term: Time-Stepping Methods.- 9. Conjugate Gradient Methods.- 9.1 Linear Systems of Equations as Minimisation Problem.- 9.1…