Iterative Methods for Linear and Nonlinear Equations

1 Iterative Methods for Linearand Nonlinear EquationsC. T. KelleyNorth Carolina State UniversitySociety for Industrial and Applied Mathematics Philadelphia 1995 Untitled-19/20/2004, 2:59 PM3To Polly H. Thomas, 1906-1994, devoted mother and grandmother1 Copyright 1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at 1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at 1.

2 Basic Concepts and Stationary Iterative Methods Review and The Banach Lemma and approximate The spectral Matrix splittings and classical stationar yiterative Exercises on stationar yiterative 2. Conjugate Gradient Krylov Methods and the minimization Consequences of the minimization Termination of the CGNR and Examples for preconditioned conjugate Exercises on conjugate 3. GMRES The minimization propert yand its GMRES implementation: Basic Implementation: Givens Other Methods for nonsymmetric 1995 by the Society for Industrial and Applied Mathematics.

3 This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at Examples for GMRES Examples for CGNR, Bi-CGSTAB, and TFQMR Exercises on 4. Basic Concepts and Fixed-Point Types of Fixed-point The standard 5. Newton s Local convergence of Newton s Termination of the Implementation of Newton s Errors in the function and The chord Approximate inversion ofF .. The Shamanskii Difference approximation toF .. The secant The Kantorovich Examples for Newton s Exercises on Newton s 6. Inexact Newton The basic Direct Weighted norm Errors in the Newton- Iterative Newton Other Newton- Iterative Newton-GMRES Examples for Chandrasekhar Convection-diffusion Exercises on inexact Newton 7.

4 Broyden s The Dennis Mor e Convergence Linear Nonlinear Implementation of Broyden s Examples for Broyden s 1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at Linear Nonlinear Exercises on Broyden s 8. Global Single Analysis of the Armijo Implementation of the Armijo Polynomial line Broyden s Examples for Newton Inverse tangent Convection-diffusion Broyden Exercises on global 1995 by the Society for Industrial and Applied Mathematics.

5 This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at 1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at book on Iterative Methods for Linear and Nonlinear Equations can be usedas a tutorial and a reference b yan yone who needs to solve Nonlinear s ystemsof Equations or large Linear systems. It may also be used as a textbook forintroductor ycourses in Nonlinear Equations or Iterative Methods or as sourcematerial for an introductor ycourse in numerical anal ysis at the graduate assume that the reader is familiar with elementar ynumerical anal ysis, Linear algebra, and the central ideas of direct Methods for the numericalsolution of dense Linear systems as described in standard texts such as [7],[105], or [184].

6 Our approach is to focus on a small number of Methods and treat themin depth. Though this book is written in a finite-dimensional setting, wehave selected for coverage mostl yalgorithms and Methods of anal ysis whichextend directl yto the infinite-dimensional case and whose convergence can bethoroughly analyzed. For example, the matrix-free formulation and analysis forGMRES and conjugate gradient is almost unchanged in an infinite-dimensionalsetting. The analysis of Broyden s method presented in Chapter 7 andthe implementations presented in Chapters 7 and 8 are different from theclassical ones and also extend directl yto an infinite-dimensional setting.

7 Thecomputational examples and exercises focus on discretizations of infinite-dimensional problems such as integral and differential present a limited number of computational examples. These examplesare intended to provide results that can be used to validate the reader s ownimplementations and to give a sense of how the algorithms perform. Theexamples are not designed to give a complete picture of performance or to bea suite of test computational examples in this book were done with MATLAB (version on various SUN SPARC stations and version on an AppleMacintosh Powerbook 180) and the MATLAB environment is an excellent onefor getting experience with the algorithms, for doing the exercises, and forsmall-to-medium scale production codes for man yof thealgorithms are available b yanon ymous ftp.

8 A good introduction to the latest1 MATLAB is a registered trademark of The MathWorks, 1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at (version ) of MATLAB is the MATLAB Primer [178]; [43] is alsoa useful resource. If the reader has no access to MATLAB or will be solvingver ylarge problems, the general algorithmic descriptions or even the MATLAB codes can easil ybe translated to another of this book are based upon work supported b ythe NationalScience Foundation and the Air Force Office of Scientific Research overseveral years, most recently under National Science Foundation Grant and DMS-9321938.

9 An yopinions, findings, and conclusions orrecommendations expressed in this material are those of the author and do notnecessaril yreflect the views of the National Science Foundation or of the AirForce Office of Scientific yof m ystudents and colleagues discussed various aspects of thisproject with me and provided important corrections, ideas, suggestions, andpointers to the literature. I am especiall yindebted to Jim Banoczi, Jeff Butera,Steve Campbell, Ton yChoi, Mood yChu, Howard Elman, Jim Epperson,Andreas Griewank, Laura Helfrich, Ilse Ipsen, Lea Jenkins, Vickie Kearn,Belinda King, Debbie Lockhart, Carl Meyer, Casey Miller, Ekkehard Sachs,Jeff Scroggs, Joseph Skudlarek, Mike Tocci, Gordon Wade, Homer Walker,Steve Wright, Zhaqing Xue, Yue Zhang, and an anonymous reviewer for theircontributions and importantly, I thank Chung-Wei Ng and my parents for over onehundred and ten years of patience and T.

10 KelleyRaleigh, North CarolinaJanuary, 1998 Copyright 1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed. Buy this book from SIAM at to get the softwareA collection of MATLAB codes has been written to accompan ythis book. TheMATLAB codes can be obtained b yanon ymous ftp from the MathWorks the directorypub/books/kelley, from the MathWorksWorld Wide Web site, from SIAM s World Wide Web can obtain MATLAB fromThe MathWorks, Prime Park WayNatick, MA 01760,Phone: (508) 653-1415 Fax: (508) 653-2997E-mail: 1995 by the Society for Industrial and Applied Mathematics.