Skip to main content
main-content

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Continuation, embedding or homotopy methods have long served as useful tools in modern mathematics. Their use can be traced back at least to such venerated works as those of Poincaré (1881–1886), Klein (1882–1883) and Bernstein (1910). Leray & Schauder (1934) refined the tool and presented it as a global result in topology viz. the homotopy invariance of degree. The use of deformations to solve nonlinear systems of equations may be traced back at least to Lahaye (1934). The classical embedding methods may be regarded as a forerunner of the predictor-corrector methods which we will treat extensively in this book.
Eugene L. Allgower, Kurt Georg

Chapter 2. The Basic Principles of Continuation Methods

Abstract
In the introduction some contexts were described in which underdetermined systems of nonlinear equations H(x, λ) = 0 arose. We saw that in general, such a system implicitly defines a curve or one-manifold of solution points. The theme of this book is to describe methods for numerically tracing such curves. In this chapter, we begin by describing some basic ideas. To make the context of our discussion precise, let us make the following
(2.1.1) Assumption. H : R N+1 R N is a smooth map.
Eugene L. Allgower, Kurt Georg

Chapter 3. Newton’s Method as Corrector

Abstract
Let zero be a regular value of the smooth map H : RN+1 R N . We again consider the solution curve c contained in H™1(0) defined by the initial value problem (2.1.9), where the initial point c(0) = u0 such that H(u0) = 0 is assumed to be given.
Eugene L. Allgower, Kurt Georg

Chapter 4. Solving the Linear Systems

Abstract
As has been seen in the preceding chapters, the numerical tracing of c(s) will generally involve the frequent calculation of both the tangent vectors and the execution of the corrector steps. This will require a sufficient amount of linear equation solving to warrant that it be done in an efficient and carefully considered manner. Here too, we shall treat the details of numerical linear algebra only in the context which concerns us viz. the calculation of tangent vectors t(A), and performing the operations w = A+b where A is an N × (N + 1) matrix with rank (A) = N which arise in the corrector steps. Readers interested in further background concerning numerical linear algebra may consult such textbooks on the subject as that of Golub & Van Loan.
Eugene L. Allgower, Kurt Georg

Chapter 5. Convergence of Euler-Newton-Like Methods

Abstract
In this chapter we analyze the convergence properties of an Euler-Newton method under the simplifying assumption that a sufficiently small uniform steplength is maintained.
Eugene L. Allower, Kurt Georg

Chapter 6. Steplength Adaptations for the Predictor

Abstract
The convergence considerations of section 5.2 were carried out under the assumption that the steplength of the algorithm (5.1.1) was uniformly constant throughout. This is of course not efficient for any practical implementation. The discussion in chapter 5 did not indicate any means of choosing the steplength h > 0. To some extent of course, the steplength strategy depends upon the accuracy with which it is desired to numerically trace a solution curve. In any case, an efficient algorithm for this task needs to incorporate an automatic strategy for controlling the steplength. In this respect the PC methods are similar to the methods for numerically integrating initial value problems in ordinary differential equations. Indeed, one expedient way of tracing an implicitly defined curve c is to merely use a numerical initial value problem solver on the defining initial value problem (2.1.9). Although such an approach has been successfully used by some authors to solve a large variety of practical problems in science and engineering (for some examples, see the bibliography), the general opinion is that it is preferable to exploit the contractive properties of the zero set H−1(0) relative to such iterative methods as those of Newton type.
Eugene L. Allower, Kurt Georg

Chapter 7. Predictor-Corrector Methods Using Updating

Abstract
In iterative methods for numerically finding zero-points of a smooth map F : R N R N it is often preferable to avoid the costly recalculation and decomposition of the Jacobian F′ at each iteration by using an approximation to F′. This results in sacrificing quadratic convergence in exchange for a superlinear convergence which is nearly as good, or a rather fast rate of linear convergence. When N is of at least moderate size, or F′ is otherwise cumbersome to calculate, this trade-off is usually to be preferred. It is reasonable to expect that the same situation should also hold in the corrector step of the predictor-corrector methods for numerically tracing H−1(0) where H : RN+1R N is a smooth map. Indeed, since the corrector process needs to be performed essentially at every predicted point, the possibility of saving computational effort in the corrector process becomes even more attractive for the predictor-corrector curve tracing methods.
Eugene L. Allgower, Kurt Georg

Chapter 8. Detection of Bifurcation Points Along a Curve

Abstract
Up to this point we have always assumed that zero is a regular value of the smooth mapping H : RN+1R N . In the case that H represents a mapping arising from a discretization of an operator of the form ℌ : E1 × RE2 where E1 and E2 represent appropriate Banach spaces, it is often of interest to approximate bifurcation points of the equation ℌ = 0. It is often possible to choose the discretization H in such a way that also the resulting discretized equation H = 0 has a corresponding bifurcation point. Under reasonable non-degeneracy assumptions it is possible to obtain error estimates for the bifurcation point of the original problem ℌ = 0. We shall not pursue such estimates here and refer the reader to the papers of Brezzi & Rappaz & Raviart and Beyn.
Eugene L. Allower, Kurt Georg

Chapter 9. Calculating Special Points of the Solution Curve

Abstract
One of the main purposes of numerical continuation methods concerns the accurate determination of certain points on a smooth curve c(s) in H−1(0), which are of special interest.
Eugene L. Allower, Kurt Georg

Chapter 10. Large Scale Problems

Abstract
As has been pointed out occasionally in the previous chapters, one of the primary applications of continuation methods involves the numerical solution of nonlinear eigenvalue problems. Such problems are likely to have arisen from a discretization of an operator equation in a Banach space context, and involving an additional “eigenvalue” parameter. Some examples were touched upon in Chapter 8. As a result of the discretization and the wish to maintain a reasonably low truncation error, the corresponding finite dimensional problem H(u) = 0 where H : RN+1R N , may require that N be quite large. This then leads to the task of solving large scale continuation problems.
Eugene L. Allower, Kurt Georg

Chapter 11. Numerically Implementable Existence Proofs

Abstract
Existence theorems are among the most frequently invoked theorems of mathematics since they assure that a solution to some equation exists. Some of the celebrated examples are the fundamental theorem of algebra, the fixed point theorems of Banach, Brouwer, Leray & Schauder, and Kakutani. With the exception of the Banach fixed point theorem, the classical statements of the above theorems merely assert the existence of a fixed point or a zero point of a map, but their traditional proofs in general do not offer any means of actually obtaining the fixed point or zero point. Many of the classical proofs of fixed point theorems can be given via the concept of the Brouwer degree. We will not need this concept in our subsequent discussions. However, for readers wishing to read up on degree theory we can suggest the books of Amann (1974), Berger (1977), Cronin (1964), Deimling (1974) or Schwartz (1969).
Eugene L. Allower, Kurt Georg

Chapter 12. PL Continuation Methods

Abstract
In previous chapters we assumed that the map H : RN+1R N was smooth, that zero was a regular value, and that H−1 (0) was a collection of disjoint smooth curves which could be numerically traced using PC-methods. Now we will discuss piecewise linear (PL) methods which can again be viewed as curve tracing methods, but the map H can now be arbitrary. The map H is approximated by a piecewise linear map H T which affinely interpolates H at the nodes of a triangulation T of RN+1. The PL methods trace the piecewise linear 1-manifold H T −1 (0). A connected component of the piecewise linear 1-manifold consists of a polygonal path which is obtained by successively stepping through certain “transverse” (N + 1)-dimensional simplices of the triangulation. Although the PL method works for arbitrary maps, only under some smoothness assumptions on H can one obtain truncation error estimates in terms of the meshsize of the underlying triangulation. In order to be able to discuss these methods it is necessary to introduce a few combinatorial ideas. The first notions we need are those of a simplex and a triangulation.
Eugene L. Allower, Kurt Georg

Chapter 13. PL Homotopy Algorithms

Abstract
In the last chapter we discussed the general features of PL continuation methods. In this chapter we will apply them to find a zero point of a map G : R N R N . We will see that it is possible to greatly relax the smoothness hypotheses regarding the map G, which are usually assumed for numerically solving such problems. In fact, the map G may even be set-valued. Eaves (1971) showed that it is possible to calculate by PL algorithms the fixed points which are guaranteed to exist by a theorem of Kakutani (1941). Merrill (1972) gave a more general boundary condition for set-valued maps G, which is similar to the Leray-Schauder condition (11.2.12). In this chapter we present two PL algorithms due to Merrill (1972) and Eaves & Saigal (1972) which can be regarded as PL implementations of the homotopy method which was sketched generally in section 11.2. To insure success of the algorithms, we will follow a presentation of Georg (1982) which used a quite general boundary condition extending somewhat that used by Merrill.
Eugene L. Allgower, Kurt Georg

Chapter 14. General PL Algorithms on PL Manifolds

Abstract
In the last 20 years, a vast variety of algorithms have been developed which are based on the concept of complementary pivoting. Many of these are listed in our bibliography. The PL continuation and homotopy algorithms described in the last two chapters are important examples. In order to give a better idea of the flexibility which is possible and to describe the construction of such algorithms for special purposes, we are now going to cast the notion of PL algorithms into the more general setting of PL manifolds. Eaves (1976) has given a very elegant geometric approach to general PL methods which has strongly influenced the writing of this chapter, see also Eaves & Scarf (1976). In the first two sections we give a general formulation of PL algorithms in the context of PL manifolds which will then allow us to describe and study a variety of sophisticated PL algorithms in a unified framework.
Eugene L. Allgower, Kurt Georg

Chapter 15. Approximating Implicitly Defined Manifolds

Abstract
Up to now we have been discussing ways of numerically tracing a curve ℌ ⊂ H−1(0) where H : RN+1R N . We have outlined both the predictor-corrector methods which rest rather strongly upon smoothness properties of H and the piecewise-linear methods which require less smoothness, but then on the other hand are generally less flexible as far as allowing general step-lengths is concerned. The latter methods are also no longer viable for large N. The behavior of the two methods was also seen to be considerably different in the presence of singular points on the curve.
Eugene L. Allower, Kurt Georg

Chapter 16. Update Methods and their Numerical Stability

Abstract
In numerical continuation methods, we are usually confronted with the problem of solving linear equations such as
$$Ax = y$$
(16.1.1)
at each step. Update methods can be applied when the matrix A is only slightly modified at each subsequent step. This is in particular the case for the update algorithms of chapter 7 and for the PL algorithms of chapters 12–15. As we have noted in those chapters, the modification of A is of the form
$${\tilde A}: = A + (a - Ae)e*,$$
(16.1.2)
where e is some vector of unit length. For example, see (12.4.4), if e denotes the ith unit basis vector, then the above formula indicates that the ith column of A is replaced by the column a. Similar formulae arise via Broyden’s update in chapter 7, see (7.2.3). In order to solve linear equations such as (16.1.1), it is usually necessary to decompose A. In the present chapter we show that by making use of (16.1.2), such a decomposition can be cheaply updated in order to obtain a decomposition of Ã. A simple example is provided by (12.4.6) where a certain right inverse of A was updated at each step. However, as was pointed out there, this update is not always stable, see Bartels & Golub (1968–69). Thus, the question arises whether cheap numerically stable updates of a decomposition are possible.
Eugene L. Allower, Kurt Georg

Backmatter

Weitere Informationen