Contents PREFACE TO THE CLASSICS EDITION xi PREFACE xiii ||1|| INTRODUCTION 2 1.1 Problems to be considered 2 1.2 Characteristics of“real-world" problems 5 1.3 Finite-precision arithmetic and measurement of error 10 1.4 Exercises 13 ||2|| NONLINEAR PROBLEMS IN ONE VARIABLE 15 2.1 What is not possible 15 2.2 Newton's method for solving one equation in one unknown 16 2.3 Convergence of sequences of real numbers 19 2.4 Convergence of Newton's method 21 2.5 Globally convergent methods for solving one equation in one unknown 24 2.6 Methods when derivatives are unavailable 27 2.7 Minimization of a function of one variable 32 2.8 Exercises 36 ||3|| NUMERICAL LINEAR ALGEBRA BACKGROUND 40 3.1 Vector and matrix norms and orthogonality 41 3.2 Solving systems of linear equations-- matrix factorizations 47 3.3 Errors in solving linear systems 51 3.4 Updating matrix factorizations 55 3.5 Eigenvalues and positive definiteness 58 3.6 Linear least squares 60 3.7 Exercises 66 ||4|| MULTIVARIABLE CALCULUS BACKGROUND 69 4.1 Derivatives and multivariable models 6 4.2 Multivariable finite diference derivatives 77 4.3 Necessary and suficient conditions for unconstrained minimization 80 4.4 Exercises 83 ||5|| NEWTON'S METHOD FOR NONLINEAR EQUATIONS AND UNCONSTRAINED MINIMIZATION 86 5.1 Newton's method for systems of nonlinear equations 86 5.2 Local convergence of Newton's method 89 5.3 The Kantorovich and contractive mapping theorems 92 5.4 Finite diference derivative methods for systems of nonlinear equations 94 5.5 Newton's method for unconstrained minimization 99 5.6 Finte-iference derivative methods for unconstrained minimization 103 5.7 Exercises 107 ||6|| GLOBALLY CONVERGENT MODIFICATIONS OF NEWTON'S METHOD 111 6.1 The quasi-Newton framework 112 6.2 Descent directions 113 6.3 Line searches 116 6.3.1 Convergence results for properly chosen steps 120 6.3.2 Step selection by backtracking 126 6.4 The model-trust region approach 129 6.4.1 The locally constrained optimal “hook ") step 134 6.4.2 The double dogleg step 139 6.4.3 U pdating the trust region 143 6.5 Global methods for systems of nonlinear equations 147 6.6 Exercises 152 ||7|| STOPPING, SCALING, AND TESTING155 7.1 Scaling 155 7.2 Stopping criteria 159 7.3 Testing 161 7.4 Exercises 164 ||8|| SECANT METHODS FOR SYSTEMS OF NONLINEAR EQUATIONS 168 8.1 Broyden's method 165 8.2 Local convergence analysis of Broyden's method 174 8.3 Implementation of quasi-Newton algorithms using Broyden's update 186 8.4 Other secant updates for nonlinear equations 189 8.5 Exercises 190 ||9|| SECANT METHODS FOR UNCONSTRAINED MINIMIZATION 194 9.1 The symmetric secant update of Powell 195 9.2 Symmetric positive definite secant updates 198 9.3 Local convergence of positive definite scant methods 203 9.4 Implementation of quasi-Newton algorithms using the positive definite secant update 208 9.5 Another convergence result for the positive definite secant method 210 9.6 Other secant updates for unconstrained minimization 211 9.7 Exercises 212 ||10|| NONLINEAR LEAST SQUARES 218 10.1 The nonlincar least-squares problem 218 10.2 Gauss-Newton-type methods 221 10.3 Full Newton-type methods 228 10.4 Other considerations in solving nonlinear least-squares problems 233 10.5 Exercises 236 ||11|| METHODS FOR PROBLEMS WITH SPECIAL STRUCTURE 239 11.1 The sparse finite diference Newton method 240 11.2 Sparse secant methods 242 11.3 Deriving least change secant updates 246 11.4 Analyzing least-change secant methods 251 11.5 Exercises 250 ||A|| APPENDIX: A MODULAR SYSTEM OF ALGORITHMS FOR UNCONSTRAINED MINIMIZATION AND NONLINEAR EQUATIONS (by Robert Schnabel) 259 ||B|| APPENDIX: TEST PROBLEMS (by Robert Schnabel) 361 REFERENCES 364 AUTHOR INDEX 371 SUBJECT INDEX 373