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.1 Minimisation Problem.- 9.1.2 Search Directions.- 9.

1.3 Other Quadratic Functionals.- 9.1.4 Complex Case.- 9.2 Gradient Method.- 9.

2.1 Construction.- 9.2.2 Properties of the Gradient Method.- 9.2.3 Numerical Examples.

- 9.2.4 Gradient Method Based on Other Iterations.- 9.2.5 Pascal Procedures and Numerical Examples.- 9.3 The Method of the Conjugate Directions.

- 9.3.1 Optimality with Respect to a Direction.- 9.3.2 Conjugate Directions.- 9.4 Conjugate Gradient Method (cg Method).

- 9.4.1 First Formulation.- 9.4.2 cg Method (Applied to the Richardson Iteration).- 9.4.

3 Convergence Analysis.- 9.4.4 cg Method Applied to Symmetric Iterations.- 9.4.5 Pascal Procedures.- 9.

4.6 Numerical Examples in the Model Case.- 9.4.7 Amount of Work of the cg Method.- 9.4.8 Suitability for Secondary Iterations.

- 9.5 Generalisations.- 9.5.1 Formulation of the cg Method with a More General Bilinear Form.- 9.5.2 Method of Conjugate Residuals.

- 9.5.3 Three-Term Recursion for pm.- 9.5.4 Stabilised Method of the Conjugate Residuals.- 9.5.

5 Convergence Results for Indefinite Matrices A.- 9.5.6 Pascal Procedures.- 9.5.7 Numerical Examples.- 9.

5.8 Method of Orthogonal Directions.- 9.5.9 Solution of Unsymmetric Systems.- 9.5.10 Further Comments.

- 10. Multi-Grid Methods.- 10.1 Introduction.- 10.1.1 Smoothing.- 10.

1.2 Hierarchy of Systems of Equations.- 10.1.3 Prolongation.- 10.1.4 Restriction.

- 10.1.5 Coarse-Grid Correction.- 10.2 Two-Grid Method.- 10.2.1 Algorithm.

- 10.2.2 Modifications.- 10.2.3 Iteration Matrix.- 10.2.

4 Pascal Procedures.- 10.2.5 Numerical Examples.- 10.3 Analysis for a One-Dimensional Example.- 10.3.

1 Fourier Analysis.- 10.3.2 Transformed Quantities.- 10.3.3 Convergence Results.- 10.

4 Multi-Grid Iteration.- 10.4.1 Algorithm.- 10.4.2 Pascal Procedures.- 10.

4.3 Numerical Examples.- 10.4.4 Computational Work.- 10.4.5 Iteration Matrix.

- 10.5 Nested Iteration.- 10.5.1 Algorithm.- 10.5.2 Error Analysis.

- 10.5.3 Amount of Computational Work.- 10.5.4 Pascal Procedures.- 10.5.

5 Numerical Examples.- 10.5.6 Comments.- 10.6 Convergence Analysis.- 10.6.

1 Summary.- 10.6.2 Smoothing Property.- 10.6.3 Approximation Property.- 10.

6.3.1 Formulation.- 10.6.3.2 Galerkin Discretisation.- 10.

6.3.3 Hierarchy of the Systems of Equations.- 10.6.3.4 Canonical Prolongation and Restriction.- 10.

6.3.5 Error Estimate of the Galerkin Solution.- 10.6.3.6 Proof of the Approximation Property.- 10.

6.4 Convergence of the Two-Grid Iteration.- 10.6.5 Convergence of the Multi-G.