Iterative Solution of Large Sparse Systems of Equations

Wolfgang Hackbusch (Autor)

Buch | Softcover

432 Seiten

2011 | Softcover reprint of the original 1st ed. 1994
Springer-Verlag New York Inc.
978-1-4612-8724-7 (ISBN)

Infos

C. F. GauS in a letter from Dec. 26, 1823 to Gerling: 3c~ empfe~le 3~nen biegen IDlobu9 aur 9tac~a~mung. ec~werlic~ werben eie ie wieber bi- reet eliminiren, wenigftens nic~t, wenn eie me~r als 2 Unbefannte ~aben. :Da9 inbirecte 93erfa~ren 109st sic~ ~alb im ec~lafe ausfii~ren, ober man fann wo~renb be9gelben an anbere :Dinge benfen. [CO F. GauS: Werke vol. 9, Gottingen, p. 280, 1903] What difference exists between solving large and small systems of equations? The standard methods well-known to any student oflinear algebra are appli- cable to all systems, whether large or small. The necessary amount of work, however, increases dramatically with the size, so one has to search for algo- rithms that most efficiently and accurately solve systems of 1000, 10,000, or even one million equations. The choice of algorithms depends on the special properties the matrices in practice have. An important class of large systems arises from the discretisation of partial differential equations. In this case, the matrices are sparse (i. e. , they contain mostly zeros) and well-suited to iterative algorithms.
Because of the background in partial differential equa- tions, this book is closely connected with the author's Theory and Numerical Treatment of Elliptic Differential Equations, whose English translation has also been published by Springer-Verlag. This book grew out of a series of lectures given by the author at the Christian-Albrecht University of Kiel to students of mathematics.

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.

Produkt-Details

• Reihe/Serie: Applied Mathematical Sciences ; 95
• Zusatzinfo: XXII, 432 p.
• Verlagsort: New York, NY
• Sprache: englisch
• Maße: 155 x 235 mm
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Mathematik / Informatik ► Mathematik ► Arithmetik / Zahlentheorie
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• ISBN-10: 1-4612-8724-3 / 1461287243
• ISBN-13: 978-1-4612-8724-7 / 9781461287247
• Zustand: Neuware