Iterative Methods for Linear and Nonlinear Equations
by C.T. Kelley
Frontiers in Applied Mathematics 16
Table of Contents
How to Get the Software Part I: Linear Equations
Chapter 1: Basic Concepts and Stationary Iterative Methods
Chapter 2: Conjugate Gradient Iteration
Chapter 3: GMRES Iteration
Part II: Nonlinear Equations
Chapter 4: Basic Concepts and Fixed Point Iteration
Chapter 5: Newton's Method
Chapter 6: Inexact Newton Methods
Chapter 7: Broyden's Method
Chapter 8: Global Convergence
This book on iterative methods for linear and nonlinear equations can be used as a tutorial and a reference by anyone who needs to solve nonlinear systems of equations or large linear systems. It may also be used as a textbook for introductory courses in nonlinear equations or iterative methods or as source material for an introductory course in numerical analysis at the graduate level. We assume that the reader is familiar with elementary numerical analysis, linear algebra, and the central ideas of direct methods for the numerical solution of dense linear systems.
Our approach is to focus on a small number of methods and treat them in depth. Though this book is written in a finite-dimensional setting, we have selected for coverage mostly algorithms and methods of analysis which extend directly to the infinite-dimensional case and whose convergence can be thoroughly analyzed. For example, the matrix-free formulation and analysis for GMRES and conjugate gradient is almost unchanged in an infinite-dimensional setting. The analysis of Broyden's method presented in Chapter 7 and the implementations presented in Chapters 7 and 8 are different from the classical ones and also extend directly to an infinite-dimensional setting. The computational examples and exercises focus on discretizations of infinite-dimensional problems such as integral and differential equations.
We present a limited number of computational examples. These examples are intended to provide results that can be used to validate the reader's own implementations and to give a sense of how the algorithms perform. The examples are not designed to give a complete picture of performance or to be a suite of test problems.
The computational examples in this book were done with MATLAB® (version 4.0a on various SUN SPARCstations and version 4.1 on an Apple Macintosh Powerbook 180) and the MATLAB environment is an excellent one for getting experience with the algorithms, for doing the exercises, and for small-to-medium scale production work.¹ MATLAB codes for many of the algorithms are available by anonymous ftp. If the reader has no access to MATLAB or will be solving very large problems, the general algorithmic descriptions or even the MATLAB codes can easily be translated to another language.
Parts of this book are based upon work supported by the National Science Foundation and the Air Force Office of Scientific Research over several years, most recently under National Science Foundation Grant Nos. DMS-9024622 and DMS-9321938. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation or of the Air Force Office of Scientific Research.
Many of my students and colleagues discussed various aspects of this project with me and provided important corrections, ideas, suggestions, and pointers to the literature. I am especially indebted to Jim Banoczi, Jeff Butera, Steve Campbell, Tony Choi, Moody Chu, Andreas Griewank, Laura Helfrich, Ilse Ipsen, Vickie Kearn, Debbie Lockhart, Carl Meyer, Casey Miller, Ekkehard Sachs, Jeff Scroggs, Mike Tocci, Homer Walker, Steve Wright, Zhaqing Xue, Yue Zhang, and an anonymous reviewer for their contributions and encouragement.
Most importantly, I thank Chung-Wei Ng and my parents for over one hundred years of patience and support.
¹MATLAB is a registered trademark of The MathWorks, Inc.
C. T. Kelley Raleigh, North Carolina January, 1995