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