E-Book Content
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. To Polly H. Thomas, 1906-1994, devoted mother and grandmother 1 Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html. Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. 2 Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html. Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Contents Preface xi How to Get the Software xiii CHAPTER 1. Basic Concepts and Stationary Iterative Methods 3 1.1 Review and notation . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 The Banach Lemma and approximate inverses . . . . . . . . . . 5 1.3 The spectral radius . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Matrix splittings and classical stationary iterative methods . . 7 1.5 Exercises on stationary iterative methods . . . . . . . . . . . . 10 CHAPTER 2. Conjugate Gradient Iteration 2.1 Krylov methods and the minimization property . 2.2 Consequences of the minimization property . . . 2.3 Termination of the iteration . . . . . . . . . . . . 2.4 Implementation . . . . . . . . . . . . . . . . . . . 2.5 Preconditioning . . . . . . . . . . . . . . . . . . . 2.6 CGNR and CGNE . . . . . . . . . . . . . . . . . 2.7 Examples for preconditioned conjugate iteration 2.8 Exercises on conjugate gradient . . . . . . . . . . CHAPTER 3. GMRES Iteration 3.1 The minimization property and its consequences 3.2 Termination . . . . . . . . . . . . . . . . . . . . . 3.3 Preconditioning . . . . . . . . . . . . . . . . . . . 3.4 GMRES implementation: Basic ideas . . . . . . . 3.5 Implementation: Givens rotations . . . . . . . . . 3.6 Other methods for nonsymmetric systems . . . . 3.6.1 Bi-CG. . . . . . . . . . . . . . . . . . . . . 3.6.2 CGS. . . . . . . . . . . . . . . . . . . . . 3.6.3 Bi-CGSTAB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 11 13 15 19 22 25 26 30 . . . . . . . . . 33 33 35 36 37 43 46 47 48 50 Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. viii CONTENTS . . . . 51 54 55 60 CHAPTER 4. Basic Concepts and Fixed-Point Iteration 4.1 Types of convergence . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Fixed-point iteration . . . . . . . . . . . . . . . . . . . . . . . . 4.3 The standard assumptions . . . . . . . . . . . . . . . . . . . . . 65 65 66 68 CHAPTER 5. Newton’s Method 5.1 Local convergence of Newton’s method 5.2 Termination of the iteration . . . . . . 5.3 Implementation of Newton’s method . 5.4 Errors in the function and derivative . 5.4.1 The chord method. . . . . . . . 5.4.2 Approximate inversion of F . . 5.4.3 The Shamanskii method. . . . 5.4.4 Difference approximation to F . 5.4.5 The secant method. . . . . . . 5.5 The Kantorovich Theorem . . . . . . . 5.6 Examples for Newton’s method . . . . 5.7 Exercises on Newton’s method . . . . 3.7 3.8 3.9 3.6.4 TFQMR. . . . . . . . . . . Examples for GMRES iteration . . Examples for CGNR, Bi-