. 1
( : 26)



. . >>

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 11
2.1 Krylov methods and the minimization property . . . . . . . . . 11
2.2 Consequences of the minimization property . . . . . . . . . . . 13
2.3 Termination of the iteration . . . . . . . . . . . . . . . . . . . . 15
2.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6 CGNR and CGNE . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 Examples for preconditioned conjugate iteration . . . . . . . . 26
2.8 Exercises on conjugate gradient . . . . . . . . . . . . . . . . . . 30

CHAPTER 3. GMRES Iteration 33
3.1 The minimization property and its consequences . . . . . . . . 33
3.2 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 GMRES implementation: Basic ideas . . . . . . . . . . . . . . . 37
3.5 Implementation: Givens rotations . . . . . . . . . . . . . . . . . 43
3.6 Other methods for nonsymmetric systems . . . . . . . . . . . . 46
3.6.1 Bi-CG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6.2 CGS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.6.3 Bi-CGSTAB. . . . . . . . . . . . . . . . . . . . . . . . . 50
vii

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.




viii CONTENTS

3.6.4 TFQMR. . . . . . . . . . . ............. . . . 51
3.7 Examples for GMRES iteration . . ............. . . . 54
3.8 Examples for CGNR, Bi-CGSTAB, and TFQMR iteration . . . 55
3.9 Exercises on GMRES . . . . . . . . ............. . . . 60

CHAPTER 4. Basic Concepts and Fixed-Point Iteration 65
4.1 Types of convergence . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2 Fixed-point iteration . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3 The standard assumptions . . . . . . . . . . . . . . . . . . . . . 68

CHAPTER 5. Newton™s Method 71
5.1 Local convergence of Newton™s method . . . . . . . . . . . . . . 71
5.2 Termination of the iteration . . . . . . . . . . . . . . . . . . . . 72
5.3 Implementation of Newton™s method . . . . . . . . . . . . . . . 73
5.4 Errors in the function and derivative . . . . . . . . . . . . . . . 75
5.4.1 The chord method. . . . . . . . . . . . . . . . . . . . . . 76
5.4.2 Approximate inversion of F . . . . . . . . . . . . . . . . 77
5.4.3 The Shamanskii method. . . . . . . . . . . . . . . . . . 78
5.4.4 Di¬erence approximation to F . . . . . . . . . . . . . . . 79
5.4.5 The secant method. . . . . . . . . . . . . . . . . . . . . 82
5.5 The Kantorovich Theorem . . . . . . . . . . . . . . . . . . . . . 83
5.6 Examples for Newton™s method . . . . . . . . . . . . . . . . . . 86
5.7 Exercises on Newton™s method . . . . . . . . . . . . . . . . . . 91

CHAPTER 6. Inexact Newton Methods 95
6.1 The basic estimates . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.1 Direct analysis. . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.2 Weighted norm analysis. . . . . . . . . . . . . . . . . . . 97
6.1.3 Errors in the function. . . . . . . . . . . . . . . . . . . . 100
6.2 Newton-iterative methods . . . . . . . . . . . . . . . . . . . . . 100
6.2.1 Newton GMRES. . . . . . . . . . . . . . . . . . . . . . . 101
6.2.2 Other Newton-iterative methods. . . . . . . . . . . . . . 104
6.3 Newton-GMRES implementation . . . . . . . . . . . . . . . . . 104
6.4 Examples for Newton-GMRES . . . . . . . . . . . . . . . . . . 106
6.4.1 Chandrasekhar H-equation. . . . . . . . . . . . . . . . . 107
6.4.2 Convection-di¬usion equation. . . . . . . . . . . . . . . 108
6.5 Exercises on inexact Newton methods . . . . . . . . . . . . . . 110

CHAPTER 7. Broyden™s method 113
7.1 The Dennis“Mor´ condition . . . . .
e . . . . . . . . . . . . . . . 114
7.2 Convergence analysis . . . . . . . . . . . . . . . . . . . . . . . . 116
7.2.1 Linear problems. . . . . . . . . . . . . . . . . . . . . . . 118
7.2.2 Nonlinear problems. . . . . . . . . . . . . . . . . . . . . 120
7.3 Implementation of Broyden™s method . . . . . . . . . . . . . . . 123
7.4 Examples for Broyden™s method . . . . . . . . . . . . . . . . . . 127



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.




ix
CONTENTS

7.4.1 Linear problems. . . . . . . . . . . . . . . . . . . . . . . 127
7.4.2 Nonlinear problems. . . . . . . . . . . . . . . . . . . . . 128
7.5 Exercises on Broyden™s method . . . . . . . . . . . . . . . . . . 132

CHAPTER 8. Global Convergence 135
8.1 Single equations . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.2 Analysis of the Armijo rule . . . . . . . . . . . . . . . . . . . . 138
8.3 Implementation of the Armijo rule . . . . . . . . . . . . . . . . 141
8.3.1 Polynomial line searches. . . . . . . . . . . . . . . . . . 142
8.3.2 Broyden™s method. . . . . . . . . . . . . . . . . . . . . . 144
8.4 Examples for Newton“Armijo . . . . . . . . . . . . . . . . . . . 146
8.4.1 Inverse tangent function. . . . . . . . . . . . . . . . . . 146
8.4.2 Convection-di¬usion equation. . . . . . . . . . . . . . . 146
8.4.3 Broyden“Armijo. . . . . . . . . . . . . . . . . . . . . . . 148
8.5 Exercises on global convergence . . . . . . . . . . . . . . . . . . 151

Bibliography 153

Index 163




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.




x CONTENTS




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.




Preface




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 as described in standard texts such as [7],
[105], or [184].
Our approach is to focus on a small number of methods and treat them
in depth. Though this book is written in a ¬nite-dimensional setting, we
have selected for coverage mostly algorithms and methods of analysis which
extend directly to the in¬nite-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 in¬nite-dimensional
setting. The analysis of Broyden™s method presented in Chapter 7 and
the implementations presented in Chapters 7 and 8 are di¬erent from the
classical ones and also extend directly to an in¬nite-dimensional setting. The
computational examples and exercises focus on discretizations of in¬nite-
dimensional problems such as integral and di¬erential 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.1 MATLAB codes for many of the
algorithms are available by anonymous ftp. A good introduction to the latest
1 MATLAB is a registered trademark of The MathWorks, Inc.

xi

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.




xii PREFACE

version (version 4.2) of MATLAB is the MATLAB Primer [178]; [43] is also
a useful resource. 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 O¬ce of Scienti¬c Research over
several years, most recently under National Science Foundation Grant Nos.
DMS-9024622 and DMS-9321938. Any opinions, ¬ndings, and conclusions or
recommendations expressed in this material are those of the author and do not
necessarily re¬‚ect the views of the National Science Foundation or of the Air
Force O¬ce of Scienti¬c 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, Je¬ Butera,
Steve Campbell, Tony Choi, Moody Chu, Howard Elman, Jim Epperson,
Andreas Griewank, Laura Helfrich, Ilse Ipsen, Lea Jenkins, Vickie Kearn,
Belinda King, Debbie Lockhart, Carl Meyer, Casey Miller, Ekkehard Sachs,
Je¬ Scroggs, Joseph Skudlarek, Mike Tocci, Gordon Wade, 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 and ten years of patience and support.

C. T. Kelley
Raleigh, North Carolina
January, 1998




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.




How to get the software




A collection of MATLAB codes has been written to accompany this book. The
MATLAB codes can be obtained by anonymous ftp from the MathWorks server
ftp.mathworks.com in the directory pub/books/kelley, from the MathWorks
World Wide Web site,
http://www.mathworks.com
or from SIAM™s World Wide Web site
http://www.siam.org/books/kelley/kelley.html
One can obtain MATLAB from
The MathWorks, Inc.
24 Prime Park Way
Natick, MA 01760,
Phone: (508) 653-1415
Fax: (508) 653-2997
E-mail: info@mathworks.com
WWW: http://www.mathworks.com




xiii

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.




Chapter 1

Basic Concepts and Stationary Iterative Methods




1.1. Review and notation
We begin by setting notation and reviewing some ideas from numerical linear
algebra that we expect the reader to be familiar with. An excellent reference
for the basic ideas of numerical linear algebra and direct methods for linear
equations is [184].
We will write linear equations as
(1.1) Ax = b,
where A is a nonsingular N — N matrix, b ∈ RN is given, and
x— = A’1 b ∈ RN
is to be found.
Throughout this chapter x will denote a potential solution and {xk }k≥0 the
sequence of iterates. We will denote the ith component of a vector x by (x)i
(note the parentheses) and the ith component of xk by (xk )i . We will rarely
need to refer to individual components of vectors.
In this chapter · will denote a norm on RN as well as the induced matrix
norm.
Definition 1.1.1. Let · be a norm on RN . The induced matrix norm
of an N — N matrix A is de¬ned by
A = max Ax .
x =1

Induced norms have the important property that
Ax ¤ A x.
Recall that the condition number of A relative to the norm · is
A’1 ,
κ(A) = A
is the lp norm
where κ(A) is understood to be in¬nite if A is singular. If ·
« 1/p
N
|(x)i |p 
=
x p
j=1

3

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.




4 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS

we will write the condition number as κp .
Most iterative methods terminate when the residual

r = b ’ Ax

is su¬ciently small. One termination criterion is

rk
(1.2) < „,
r0

which can be related to the error

e = x ’ x—

in terms of the condition number.
Lemma 1.1.1. Let b, x, x0 ∈ RN . Let A be nonsingular and let x— = A’1 b.

e r
(1.3) ¤ κ(A) .
e0 r0

Proof. Since
r = b ’ Ax = ’Ae

we have
e = A’1 Ae ¤ A’1 Ae = A’1 r

and
r0 = Ae0 ¤ A e0 .

Hence
A’1 r
e r
¤ = κ(A) ,
A ’1 r0
e0 r0

as asserted.
The termination criterion (1.2) depends on the initial iterate and may result
in unnecessary work when the initial iterate is good and a poor result when the
initial iterate is far from the solution. For this reason we prefer to terminate
the iteration when
rk
(1.4) < „.
b

The two conditions (1.2) and (1.4) are the same when x0 = 0, which is a
common choice, particularly when the linear iteration is being used as part of
a nonlinear solver.



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.




5
BASIC CONCEPTS

1.2. The Banach Lemma and approximate inverses
The most straightforward approach to an iterative solution of a linear system
is to rewrite (1.1) as a linear ¬xed-point iteration. One way to do this is to
write Ax = b as

. 1
( : 26)



. . >>