Introduction to numerical continuation methods / Eugene L. Allgower, Kurt Georg.

Format:

Book

Author/Creator:

Allgower, E. L. (Eugene L.)

Contributor:

Georg, Kurt.

Class of 1924 Book Fund.

Series:

Classics in applied mathematics ; 45.

Classics in applied mathematics ; 45

Language:

English

Subjects (All):

Continuation methods.

Physical Description:

xxv, 388 pages : illustrations ; 26 cm.

Place of Publication:

Philadelphia : SIAM, [2003]

Summary:

For many years, numerical continuation methods have provided important contributions toward the numerical solution of nonlinear systems of equations. The methods may be used not only to compute solutions, which might otherwise be hard to obtain, but also to gain insight into qualitative properties of the solutions. Introduction to Numerical Continuation Methods, originally published in 1979, was the first book to provide easy access to the numerical aspects of predictor-corrector continuation and piecewise linear continuation methods. These seemingly distinct methods share many common features and general principles, and they can be numerically implemented in similar ways. Introduction to Numerical Continuation Methods also features the piecewise linear approximation of implicitly defined surfaces, the algorithms of which are frequently used in computer graphics, mesh generation, and the evaluation of surface integrals. To help potential users of numerical continuation methods create programs adapted to their particular needs, the book presents pseudo-codes and Fortran codes as illustrations. Since it first appeared, many specialized packages for treating such varied problems as bifurcation, polynomial systems, eigenvalues, economic equilibria, optimization, and the approximation of manifolds have been written. The original extensive bibliography has been updated to include more recent references and several URLs so users can look for codes to suit their needs or write their own based on the models included here. Introduction to Numerical Continuation Methods continues to be useful for researchers and graduate students in mathematics, sciences, engineering, economics, and business looking for an introduction to computational methods for solving a large variety of nonlinear systems of equations. A background in elementary analysis and linear algebra is adequate preparation for reading this book; some knowledge from a first course in numerical analysis may also be helpful.

Contents:

2 The Basic Principles of Continuation Methods 7

2.1 Implicitly Defined Curves 7

2.2 The Basic Concepts of PC Methods 13

2.3 The Basic Concepts of PL Methods 15

3 Newton's Method as Corrector 17

3.1 Motivation 17

3.2 The Moore-Penrose Inverse in a Special Case 18

3.3 A Newton's Step For Underdetermined Nonlinear Systems 20

3.4 Convergence Properties of Newton's Method 22

4 Solving the Linear Systems 28

4.1 Using a QR Decomposition 29

4.2 Givens Rotations for Obtaining a QR Decomposition 30

4.3 Error Analysis 31

4.4 Scaling of the Dependent Variables 34

4.5 Using LU Decompositions 35

5 Convergence of Euler-Newton-Like Methods 37

5.1 An Approximate Euler-Newton Method 37

5.2 A Convergence Theorem for PC Methods 38

6 Steplength Adaptations for the Predictor 44

6.1 Steplength Adaptation by Asymptotic Expansion 45

6.2 The Steplength Adaptation of Den Heijer & Rheinboldt 50

6.3 Steplength Strategies Involving Variable Order Predictors 55

7 Predictor-Corrector Methods Using Updating 61

7.1 Broyden's "Good" Update Formula 61

7.2 Broyden Updates Along a Curve 68

8 Detection of Bifurcation Points Along a Curve 75

8.1 Simple Bifurcation Points 75

8.2 Switching Branches Via Perturbation 84

8.3 Branching Off Via the Bifurcation Equation 87

9 Calculating Special Points of the Solution Curve 91

9.2 Calculating Zero Points f(c(s)) = 0 92

9.3 Calculating Extremal Points min[subscript S] f((c(s)) 94

10 Large Scale Problems 96

10.2 General Large Scale Solvers 97

10.3 Nonlinear Conjugate Gradient Methods as Correctors 101

11 Numerically Implementable Existence Proofs 112

11.1 Preliminary Remarks 112

11.2 An Example of an Implementable Existence Theorem 114

11.3 Several Implementations for Obtaining Brouwer Fixed Points 118

11.4 Global Newton and Global Homotopy Methods 123

11.5 Multiple Solutions 128

11.6 Polynomial Systems 132

11.7 Nonlinear Complementarity 141

11.8 Critical Points and Continuation Methods 145

12 PL Continuation Methods 151

12.2 PL Approximations 156

12.3 A PL Algorithm for Tracing H(u) = 0 159

12.4 Numerical Implementation of a PL Continuation Algorithm 163

12.5 Integer Labeling 168

12.6 Truncation Errors 171

13 PL Homotopy Algorithms 173

13.1 Set-Valued Maps 173

13.2 Merrill's Restart Algorithm 181

13.3 Some Triangulations and their Implementations 186

13.4 The Homotopy Algorithm of Eaves & Saigal 194

13.5 Mixing PL and Newton Steps 196

13.6 Automatic Pivots for the Eaves-Saigal Algorithm 201

14 General PL Algorithms on PL Manifolds 203

14.1 PL Manifolds 203

14.3 Lemke's Algorithm for the Linear Complementarity Problem 214

14.4 Variable Dimension Algorithms 218

14.5 Exploiting Special Structure 229

15 Approximating Implicitly Defined Manifolds 233

15.2 Newton's Method and Orthogonal Decompositions Revisited 235

15.3 The Moving Frame Algorithm 236

15.4 Approximating Manifolds by PL Methods 238

15.5 Approximation Estimates 245

16 Update Methods and their Numerical Stability 252

16.2 Updates Using the Sherman-Morrison Formula 253

16.3 QR Factorization 256

16.4 LU Factorization 262

P1 A Simple PC Continuation Method 266

P2 A PL Homotopy Method 273

P3 A Simple Euler-Newton Update Method 288

P4 A Continuation Algorithm for Handling Bifurcation 296

P5 A PL Surface Generator 312

P6 SCOUT

Simplicial Continuation Utilities 326

P6.2 Computational Algorithms 328

P6.3 Interactive Techniques 333

P6.4 Commands 335

P6.5 Example: Periodic Solutions to a Differential Delay Equation 337.

Notes:

Society for Industrial and Applied Mathematics.

Includes bibliographical references (pages 346-382) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Class of 1924 Book Fund.

ISBN:

089871544X

OCLC:

52377653