Iterative Solution of Large Sparse Systems of Equations

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 Metho