This brief book on Newton's method is a user-oriented guide to algorithms and implementation. In just over 100 pages, it shows, via algorithms in pseudocode, in MATLAB, and with several examples, how one can choose an appropriate Newton-type method for a given problem, diagnose problems, and write an efficient solver or apply one written by others. Solving Nonlinear Equations with Newton's Method contains trouble-shooting guides to the major algorithms, their most common failure modes, and the likely causes of failure. It also includes many worked-out examples (available on the SIAM website) in pseudocode and a collection of MATLAB codes, allowing readers to experiment with the algorithms easily and implement them in other languages.

C. T. Kelley is Drexel Professor of Mathematics at the Center for Research in Scientific Computation, North Carolina State University.

Preface

xi

How to Get the Software

xiii

1 Introduction

1

(26)

1.1 What Is the Problem?

1

(1)

1.1.1 Notation

1

(1)

1.2 Newton's Method

2

(3)

1.2.1 Local Convergence Theory

3

(2)

1.3 Approximating the Jacobian

5

(2)

1.4 Inexact Newton Methods

7

(2)

1.5 Termination of the Iteration

9

(2)

1.6 Global Convergence and the Armijo Rule

11

(1)

1.7 A Basic Algorithm

12

(3)

1.7.1 Warning!

14

(1)

1.8 Things to Consider

15

(2)

1.8.1 Human Time and Public Domain Codes

15

(1)

1.8.2 The Initial Iterate

15

(1)

1.8.3 Computing the Newton Step

16

(1)

1.8.4 Choosing a Solver

16

(1)

1.9 What Can Go Wrong?

17

(3)

1.9.1 Nonsmooth Functions

17

(1)

1.9.2 Failure to Converge

18

(1)

1.9.3 Failure of the Line Search

19

(1)

1.9.4 Slow Convergence

19

(1)

1.9.5 Multiple Solutions

20

(1)

1.9.6 Storage Problems

20

(1)

1.10 Three Codes for Scalar Equations

20

(4)

1.10.1 Common Features

21

(1)

1.10.2 newtsol.m

21

(1)

1.10.3 chordsol.m

22

(1)

1.10.4 secant.m

23

(1)

1.11 Projects

24

(3)

1.11.1 Estimating the q-order

24

(1)

1.11.2 Singular Problems

25

(2)

2 Finding the Newton Step with Gaussian Elimination

27

(30)

2.1 Direct Methods for Solving Linear Equations

27

(1)

2.2 The Newton-Armijo Iteration

28

(1)

2.3 Computing a Finite Difference Jacobian

29

(4)

2.4 The Chord and Shamanskii Methods

33

(1)

2.5 What Can Go Wrong?

34

(1)

2.5.1 Poor Jacobians

34

(1)

2.5.2 Finite Difference Jacobian Error

35

(1)

2.5.3 Pivoting

35

(1)

2.6 Using nsold.m

35

(2)

2.6.1 Input to nsold.m

36

(1)

2.6.2 Output from nsold.m

37

(1)

2.7 Examples

37

(13)

2.7.1 Arctangent Function

38

(1)

2.7.2 A Simple Two-Dimensional Example

39

(2)

2.7.3 Chandrasekhar H-equation

41

(2)

2.7.4 A Two-Point Boundary Value Problem

43

(4)

2.7.5 Stiff Initial Value Problems

47

(3)

2.8 Projects

50

(1)

2.8.1 Chandrasekhar H-equation

58

2.8.2 Nested Iteration

50

(1)

2.9 Source Code for nsold.m

51

(6)

3 Methods

57

(23)

3.1 Krylov Methods for Solving Linear Equations

57

(4)

3.1.1 GMRES

58

3.1.2 Low-Storage Krylov Methods

50

(10)

3.1.3 Preconditioning

60

(1)

3.2 Computing an Approximate Newton Step

61

(2)

3.2.1 Products

61

(1)

3.2.2 Preconditioning Nonlinear Equations

61

(1)

3.2.3 Choosing the Forcing Term

62

(1)

3.3 Preconditioners

63

(1)

3.4 What Can Go Wrong?

64

(1)

3.4.1 Failure of the Inner Iteration

64

(1)

3.4.2 Loss of Orthogonality

64

(1)

3.5 Using nsoli.m

65

(1)

3.5.1 Input to nsoli.m

65

(1)

3.5.2 Output from nsoli.m

65

(1)

3.6 Examples

66

(8)

3.6.1 Chandrasekhar H-equation

66

(1)

3.6.2 The Ornstein-Zernike Equations

67

(4)

3.6.3 Equation

71

(2)

3.6.4 Time-Dependent Convection-Diffusion Equation

73

(1)

3.7 Projects

74

(2)

3.7.1 Krylov Methods and the Forcing Term

74

(1)

3.7.2 Left and Right Preconditioning

74

(1)

3.7.3 Two-Point Boundary Value Problem

74

(1)

3.7.4 Making e Movie

75

(1)

3.8 Source Code for nsoli.m

76

(4)

4 Broyden's Method

80

(17)

4.1 Convergence Theory

86

(1)

4.2 An Algorithmic Sketch

86

(1)

4.3 Computing the Broyden Computing Step and Update

87

(2)

4.4 What Can Go Wrong?

89

(1)

4.4.1 Failure of the Line Search

89

(1)

4.4.2 Failure to Converge

89

(1)

4.5 Using brsola.m

89

(1)

4.5.1 Input to brsola.m

90

(1)

4.5.2 Output from brsola.m

90

(1)

4.6 Examples

90

(3)

4.6.1 Chandrasekhar H-equation

91

(1)

4.6.2 Convection-Diffusion Equation

91

(2)

4.7 Source Code for brsola.m

93

(4)

Bibliography

97

(6)

Index

103

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.