Numerical Continuation Methods: An Introduction(13 Springer Series in Computational Mathematics)

Over the past fifteen years two new techniques have yielded extremely important contributions toward the numerical solution of nonlinear systems of equations. This book provides an introduction to and an up-to-date survey of numerical continuation methods (tracing of implicitly defined curves) of both predictor-corrector and piecewise-linear types. It presents and analyzes implementations aimed at applications to the computation of zero points, fixed points, nonlinear eigenvalue problems, bifurcation and turning points, and economic equilibria. Many algorithms are presented in a pseudo code format. An appendix supplies five sample FORTRAN programs with numerical examples, which readers can adapt to fit their purposes, and a description of the program package SCOUT for analyzing nonlinear problems via piecewise-linear methods. An extensive up-to-date bibliography spanning 46 pages is included. The material in this book has been presented to students of mathematics, engineering and sciences with great success, and will also serve as a valuable tool for researchers in the field.

Table of Contents:
1 Introduction.- 2 The Basic Principles of Continuation Methods.- 2.1 Implicitly Defined Curves.- 2.2 The Basic Concepts of PC Methods.- 2.3 The Basic Concepts of PL Methods.- 3 Newton's Method as Corrector.- 3.1 Motivation.- 3.2 The Moore-Penrose Inverse in a Special Case.- 3.3 A Newton's Step for Underdetermined Nonlinear Systems.- 3.4 Convergence Properties of Newton's Method.- 4 Solving the Linear Systems.- 4.1 Using a QR Decomposition.- 4.2 Givens Rotations for Obtaining a QR Decomposition.- 4.3 Error Analysis.- 4.4 Scaling of the Dependent Variables.- 4.5 Using LU Decompositions.- 5 Convergence of Euler-Newton-Like Methods.- 5.1 An Approximate Euler-Newton Method.- 5.2 A Convergence Theorem for PC Methods.- 6 Steplength Adaptations for the Predictor.- 6.1 Steplength Adaptation by Asymptotic Expansion.- 6.2 The Steplength Adaptation of Den Heijer & Rheinboldt.- 6.3 Steplength Strategies Involving Variable Order Predictors.- 7 Predictor-Corrector Methods Using Updating.- 7.1 Broyden's "Good" Update Formula.- 7.2 Broyden Updates Along a Curve.- 8 Detection of Bifurcation Points Along a Curve.- 8.1 Simple Bifurcation Points.- 8.2 Switching Branches Via Perturbation.- 8.3 Branching Off Via the Bifurcation Equation.- 9 Calculating Special Points of the Solution Curve.- 9.1 Introduction.- 9.2 Calculating Zero Points f(c(s)) = 0.- 9.3 Calculating Extremal Points minsf((c(s)).- 10 Large Scale Problems.- 10.1 Introduction.- 10.2 General Large Scale Solvers.- 10.3 Nonlinear Conjugate Gradient Methods as Correctors.- 11 Numerically Implementable Existence Proofs.- 11.1 Preliminary Remarks.- 11.2 An Example of an Implementable Existence Theorem.- 11.3 Several Implementations for Obtaining Brouwer Fixed Points.- 11.4 Global Newton and Global Homotopy Methods.- 11.5 Multiple Solutions.- 11.6 Polynomial Systems.- 11.7 Nonlinear Complementarity.- 11.8 Critical Points and Continuation Methods.- 12 PL Continuation Methods.- 12.1 Introduction.- 12.2 PL Approximations.- 12.3 A PL Algorithm for Tracing H(u) = 0.- 12.4 Numerical Implementation of a PL Continuation Algorithm.- 12.5 Integer Labeling.- 12.6 Truncation Errors.- 13 PL Homotopy Algorithms.- 13.1 Set-Valued Maps.- 13.2 Merrill's Restart Algorithm.- 13.3 Some Triangulations and their Implementations.- 13.4 The Homotopy Algorithm of Eaves & Saigal.- 13.5 Mixing PL and Newton Steps.- 13.6 Automatic Pivots for the Eaves-Saigal Algorithm.- 14 General PL Algorithms on PL Manifolds.- 14.1 PL Manifolds.- 14.2 Orientation and Index.- 14.3 Lemke's Algorithm for the Linear Complementarity Problem.- 14.4 Variable Dimension Algorithms.- 14.5 Exploiting Special Structure.- 15 Approximating Implicitly Defined Manifolds.- 15.1 Introduction.- 15.2 Newton's Method and Orthogonal Decompositions Revisited.- 15.3 The Moving Frame Algorithm.- 15.4 Approximating Manifolds by PL Methods.- 15.5 Approximation Estimates.- 16 Update Methods and their Numerical Stability.- 16.1 Introduction.- 16.2 Updates Using the Sherman-Morrison Formula.- 16.3 QR Factorization.- 16.4 LU Factorization.- P1 A Simple PC Continuation Method.- P2 A PL Homotopy Method.- P3 A Simple Euler-Newton Update Method.- P4 A Continuation Algorithm for Handling Bifurcation.- P5 A PL Surface Generator.- P6 SCOUT - Simplicial Continuation Utilities.- P6.1 Introduction.- P6.2 Computational Algorithms.- P6.3 Interactive Techniques.- P6.4 Commands.- P6.5 Example: Periodic Solutions to a Differential Delay Equation.- Index and Notation.