Numerical continuation
Encyclopedia
Numerical continuation is a method of computing approximate solutions of a system of parameterized nonlinear equations,
The parameter
is usually a real scalar
, and the solution an n-vector. For a fixed parameter value
, 
maps Euclidean n-space into itself.
Often the original mapping
is from a Banach space
into itself, and the Euclidean n-space is a finite dimensional approximation to the Banach space.
A steady state
, or fixed point
, of a parameterized family of flows
or maps
are of this form, and by discretizing
trajectories of a flow or iterating a map, periodic orbits and heteroclinic orbit
s can also be posed as a solution of
.
where
is an n-vector, and its image 
is an n-1 vector.
This formulation, without an explicit parameter space is not usually suitable for the formulations in the following sections, because they refer to parameterized autonomous nonlinear dynamical systems of the form:
However, in an algebraic system there is no distinction between unknowns
and the parameters.
.
The textbook example of a periodic motion is the undamped pendulum
.
If the phase space
is periodic in one or more coordinates, say
, with 
a vector, then there is a
second kind of periodic motions defined by
Here
is a diagonal matrix
of integers that serves as an index of these periodic motions of the second kind.
The first step in writing an implicit system for a periodic motion is to move the period
from the boundary conditions to the ODE
:
The second step is to add an additional equation, a phase constraint, that can be thought of as determining the period. This is necessary because any solution of the above boundary value problem can be shifted in time by an arbitrary amount (time does not appear in the defining equations—the dynamical system is called autonomous).
There are several choices for the phase constraint. If
is a known periodic orbit at a parameter value 
near 
, then, Poincaré used
which states that
lies in a plane which is orthogonal to the tangent vector of the closed curve. This plane is called a
Poincaré section.
For a general problem a better phase constraint is an integral constraint introduced by Eusebius Doedel, which chooses the phase so that the distance between the known and unknown orbits is minimized:
of the nonlinear system 
is a set of points 
which satisfy 
and are connected to the initial solution 
by a path of solutions 
for which 
and
.
This figure shows two solution components, one red and the other blue. Note that these two components may be connected outside the region of interest.
, 
, and produces a set of points on the solution component 
.
is a point 
at which the Jacobian
of
is full rank 
.
Near a regular point the solution component is an isolated curve passing through the regular point (the implicit function theorem
). In the figure above the point
is a regular point.
is a point 
at which the Jacobian
of F is not full rank.
Near a singular point the solution component may not be an isolated curve passing through the regular point. The local structure is determined by higher derivatives of
. In the figure above the point where the two blue curves cross is a singular point.
In general solution components
are branched curves. The branch points are singular points. Finding the solution curves leaving a
singular point is called branch switching, and uses techniques from bifurcation theory
(singularity theory
, catastrophe theory
).
For finite dimensional systems (as defined above) the Lyapunov-Schmidt decomposition may be used to produce two systems to which the Implicit Function Theorem applies. The Lyapunov-Schmidt decomposition uses the restriction of the system to the complement of the null space of the Jacobian and the range of the Jacobian.
If the columns of the matrix
are an orthonormal basis for the null space of
and the columns of the matrix
are an orthonormal basis for the left null space of 
, then
the system
can be rewritten as
where
is in the complement of the null space of 
.
In the first equation, which is parametrized by the null space of the Jacobian (
), the Jacobian with respect to 
is non-singular. So the implicit function theorem states that there is a mapping 
such that 
and 
. The second equation (with 
substituted) is called the bifurcation equation (though it may be a system of equations).
The bifurcation equation has a Taylor expansion which lacks the constant and linear terms. By scaling the equations and the null space of the Jacobian of the original system a system can be found with non-singular Jacobian. The constant term in the Taylor series of the scaled bifurcation equation is called the algebraic bifurcation equation, and the implicit function theorem applied the bifurcation equations states that for each isolated solution of the algebraic bifurcation equation there is a branch of solutions of the original problem which passes through the singular point.
Another type of singular point is a turning point bifurcation, or saddle-node bifurcation
, where the direction of the parameter
reverses as the curve is followed. The red curve in the figure above illustrates a turning point.
a mapping is repeatedly applied to an initial guess 
. If the method converges, and is consistent, then in the
limit the iteration approaches a solution of
.
Natural parameter continuation is a very simple adaptation of the iterative solver to a parametrized problem. The solution at
one value of
is used as the initial guess for the solution at 
. With 
sufficiently small the iteration applied to the initial
guess should converge.
One advantage of natural parameter continuation is that is uses the solution method for the problem as a black box. All that is required is that an initial solution can be given (some solvers used to always start at a fixed initial guess). There has been a lot of work in the area of large scale continuation on applying more sophisticated algorithms to black box solvers. (see e.g. LOCA).
However, natural parameter continuation fails at turning points, where the branch of solutions turns round. So for problems with turning points, a more sophisticated method such as pseudo-arclength continuation must be used (see below).
The first is
The second result is:
Please see the article on piecewise linear continuation
for details.
With these two operations this continuation algorithm is easy to state (although of course an efficient implementation requires a more sophisticated approach. See [B1]). An initial simplex is assumed to be given, from a reference simplicial decomposition of IR^n. The initial simplex must have at least one face which contains a zero of the unique linear interpolant on that face. The other faces of the simplex are then tested, and typically there will be one additional face with an interior zero. The initial simplex is then replaced by the simplex which lies across either face containing zero, and the process is repeated.
References: Allgower and Georg [B1] provides a crisp, clear description of the algotihm.
). The iterative solver is required to find a point at the given pseudo-arclength, which requires appending an additional
constraint (the pseudo-arclength constraint) to the n by n+1 Jacobian. It produces a square Jacobian, and if the stepsize is sufficiently small the modified Jacobian is full rank.
The algorithm is a predictor-corrector method. The prediction step finds the point (in IR^(n+1) ) which is a step
along the tangent vector at the current pointer. The corrector is usually Newton's method, or some variant, to solve the nonlinear system
where
is the tangent vector at 
.
The Jacobian of this system is the bordered matrix
in the algorithms described above is a real scalar. Most physical and design problems generally have many more than one parameter. Higher dimensional continuation refers to the case when 
is a k-vector.
The same terminology applies. A regular solution is a solution at which the Jacobian is full rank
. A singular solution is a solution at which the Jacobian is less than full rank.
A regular solution lies on a k-dimensional surface, which can be parameterized by a point in the tangent space (the null space of the Jacobian). This is again a straightforward application of the Implicit Function Theorem.
. The reason for such usage stems from the fact that various non-linear dynamical systems behave in a deterministic and predictable manner within a range of parameters which are included in the equations of the system. However, for a certain parameter value the system starts behaving chaotically and hence it become necessary to follow the parameter in order to be able to decipher the occurrences of when the system starts being non-predictable, and what exactly (theoretically) makes the system become unstable.
Analysis of parameter continuation can lead to more insights about stable/critical point bifurcations. Study of saddle-node, transcritical, pitch-fork, period doubling, Hopf, secondary Hopf (Neimark) bifurcations of stable solutions allows for a theoretical discussion of the circumstances and occurrences which arise at the critical points. Parameter continuation also gives a more dependable system to analyze a dynamical system as it is more stable than more interactive, time-stepped numerical solutions. Especially in cases where the dynamical system is prone to blow-up at certain parameter values (or combination of values for multiple parameters).
It is extremely insightful as to the presence of stable solutions (attracting or repelling) in the study of Nonlinear Partial Differential Equations where times stepping in the form of the Crank Nicolson algorithm is extremely time consuming as well as unstable in cases of nonlinear growth of the dependent variables in the system. The study of turbulence is another field where the Numerical Continuation techniques have been used to study the advent of turbulence
in a system starting at low Reynold's numbers. Also, a research using these techniques has provided the possibility of finding stable manifolds and bifurcations to invariant-tori in the case of the restricted three body problem in Newtonian gravity and have also given interesting and deep insights into the behaviour of systems such as the Lorenz equations.
as the problems of drawing contour maps (n=2), or isosurface
(n=3). The contour with value h is the set of all solution components of F-h=0
[B2] "Numerical Methods for Bifurcations of Dynamical Equilibria", Willy J. F. Govaerts, SIAM 2000.
[B3] "Lyapunov-Schmidt Methods in Nonlinear Analysis and Applications", Nikolay Sidorov, Boris Loginov, Aleksandr Sinitsyn, and Michail Falaleev, Kluwer Academic Publishers, 2002.
[B4] "Methods of Bifurcation Theory", Shui-Nee Chow and Jack K. Hale, Springer-Verlag 1982.
[B5] "Elements of Applied Bifurcation Theory", Yuri A. Kunetsov, Springer-Verlag Applied Mathematical Sciences 112, 1995.
[B6] "Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields", John Guckenheimer
and Philip Holmes
, Springer-Verlag Applied Mathematical Sciences 42, 1983.
[B7] "Elementary Stability and Bifurcation Theory", Gerard Iooss and Daniel D. Joseph, Springer-Verlag Undergraduate Texts in Mathematics, 1980.
[B8] "Singularity Theory and an Introduction to Catastrophe Theory", Yung-Chen Lu, Springer-Verlag, 1976.
[B9] "Global Bifurcations and Chaos, Analytic Methods", S. Wiggins, Springer-Verlag Applied Mathematical Sciences 73, 1988.
[B10] "Singularities and Groups in Bifurcation Theory, volume I", Martin Golubitsky and David G. Schaeffer, Springer-Verlag Applied Mathematical Sciences 51, 1985.
[B11] "Singularities and Groups in Bifurcation Theory, volume II", Martin Golubitsky, Ian Stewart and David G. Schaeffer, Springer-Verlag Applied Mathematical Sciences 69, 1988.
[B12] "Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems", Alexander Morgan, Prentice-Hall, Englewood Cliffs, N.J. 1987.
[B13] "Pathways to Solutions, Fixed Points and Equilibria", C. B. Garcia and W. I. Zangwill, Prentice-Hall, 1981.
[B14] "The Implicit Function Theorem: History, Theory and Applications", Steven G. Krantz and Harold R. Parks, Birkhauser, 2002.
[B15] "Nonlinear Functional Analysis", J. T. Schwartz, Gordon and Breach Science Publishers, Notes on Mathematics and its Applications, 1969.
[B16] "Topics in Nonlinear Functional Analysis", Louis Nirenberg (notes by Ralph A. Artino), AMS Courant Lecture Notes in Mathematics 6, 1974.
[B17] "Newton Methods for Nonlinear Problems -- Affine Invariance and Adaptive Algorithms", P. Deuflhard,
Series Computational Mathematics 35, Springer, 2006.
[A2] "Simplicial and Continuation Methods for Approximations, Fixed Points and Solutions to Systems of Equations", E. L. Allgower and K. Georg, SIAM Review, Volume 22, 28—85, 1980.
[A3] "An Algorithm for Piecewise-Linear Approximation of an Implicitly Defined Manifold", Eugene L. Allgower and Phillip H. Schmidt, SIAM Journal on Numerical Analysis, Volume 22, Number 2, 322—346, April 1985.
[A4] "Contour Tracing by Piecewise Linear Approximations", David P. Dobkin
, Silvio V. F. Levy, William P. Thurston
and Allan R. Wilks, ACM Transactions on Graphics, 9(4) 389-423, 1990.
[A5] "Numerical Solution of Bifurcation and Nonlinear Eigenvalue Problems", H. B. Keller, in "Applications of Bifurcation Theory", P. Rabinowitz ed., Academic Press, 1977.
[A6] "A Locally Parameterized Continuation Process", W.C. Rheinboldt and J.V. Burkardt, ACM Transactions on Mathematical Software, Volume 9, 236—246, 1983.
[A7] "Nonlinear Numerics" E. Doedel, International Journal of Bifurcation and Chaos
, 7(9):2127-2143, 1997.
[A8] "Nonlinear Computation", R. Seydel, International Journal of Bifurcation and Chaos
, 7(9):2105-2126, 1997.
[A9] "On a Moving Frame Algorithm and the Triangulation of Equilibirum Manifolds", W.C. Rheinboldt, In T. Kuper, R. Seydel, and H. Troger eds. "ISNM79: Bifurcation: Analysis, Algorithms, Applications", pages 256-267. Birkhauser, 1987.
[A10] "On the Computation of Multi-Dimensional Solution Manifolds of Parameterized Equations", W.C. Rheinboldt, Numerishe Mathematik, 53, 1988, pages 165-181.
[A11] "On the Simplicial Approximation of Implicitly Defined Two-Dimensional Manifolds", M. L. Brodzik and W.C. Rheinboldt, Computers and Mathematics with Applications, 28(9): 9-21, 1994.
[A12] "The Computation of Simplicial Approximations of Implicitly Defined p-Manifolds", M. L. Brodzik, Computers and Mathematics with Applications, 36(6):93-113, 1998.
[A13] "New Algorithm for Two-Dimensional Numerical Continuation", R. Melville and D. S. Mackey, Computers and Mathematics with Applications, 30(1):31-46, 1995.
[A14] "Multiple Parameter Continuation: Computing Implicitly Defined k-manifolds", M. E. Henderson, IJBC 12[3]:451-76, 2003.
[A15] "MANPACK: a set of algorithms for computations on implicitly defined manifolds", W. C. Rheinboldt, Comput. Math. Applic. 27 pages 15–9, 1996.
[A16] "CANDYS/QA - A Software System For Qualitative Analysis Of Nonlinear Dynamical Systems", Feudel, U. and W. Jansen, Int. J. Bifurcation and Chaos, vol. 2 no. 4, pp. 773–794, World Scientific, 1992.
The parameter
is usually a real scalarScalar (mathematics)
In linear algebra, real numbers are called scalars and relate to vectors in a vector space through the operation of scalar multiplication, in which a vector can be multiplied by a number to produce another vector....
, and the solution an n-vector. For a fixed parameter value
, maps Euclidean n-space into itself.Often the original mapping
is from a Banach spaceBanach space
In mathematics, Banach spaces is the name for complete normed vector spaces, one of the central objects of study in functional analysis. A complete normed vector space is a vector space V with a norm ||·|| such that every Cauchy sequence in V has a limit in V In mathematics, Banach spaces is the...
into itself, and the Euclidean n-space is a finite dimensional approximation to the Banach space.
A steady state
Steady state
A system in a steady state has numerous properties that are unchanging in time. This implies that for any property p of the system, the partial derivative with respect to time is zero:...
, or fixed point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
, of a parameterized family of flows
Flow (mathematics)
In mathematics, a flow formalizes the idea of the motion of particles in a fluid. Flows are ubiquitous in science, including engineering and physics. The notion of flow is basic to the study of ordinary differential equations. Informally, a flow may be viewed as a continuous motion of points over...
or maps
Map (mathematics)
In most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...
are of this form, and by discretizing
Discretization
In mathematics, discretization concerns the process of transferring continuous models and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical evaluation and implementation on digital computers...
trajectories of a flow or iterating a map, periodic orbits and heteroclinic orbit
Heteroclinic orbit
In mathematics, in the phase portrait of a dynamical system, a heteroclinic orbit is a path in phase space which joins two different equilibrium points...
s can also be posed as a solution of
.Other forms
In some nonlinear systems, parameters are explicit. In others they are implicit, and the system of nonlinear equations is writtenwhere
is an n-vector, and its image is an n-1 vector.This formulation, without an explicit parameter space is not usually suitable for the formulations in the following sections, because they refer to parameterized autonomous nonlinear dynamical systems of the form:
However, in an algebraic system there is no distinction between unknowns
and the parameters.Periodic motions
A periodic motion is a closed curve in phase space. That is, for some period.The textbook example of a periodic motion is the undamped pendulum
Pendulum
A pendulum is a weight suspended from a pivot so that it can swing freely. When a pendulum is displaced from its resting equilibrium position, it is subject to a restoring force due to gravity that will accelerate it back toward the equilibrium position...
.
If the phase space
Phase space
In mathematics and physics, a phase space, introduced by Willard Gibbs in 1901, is a space in which all possible states of a system are represented, with each possible state of the system corresponding to one unique point in the phase space...
is periodic in one or more coordinates, say
, with a vector, then there is asecond kind of periodic motions defined by
Here
is a diagonal matrixDiagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...
of integers that serves as an index of these periodic motions of the second kind.
The first step in writing an implicit system for a periodic motion is to move the period
from the boundary conditions to the ODEOrdinary differential equation
In mathematics, an ordinary differential equation is a relation that contains functions of only one independent variable, and one or more of their derivatives with respect to that variable....
:
The second step is to add an additional equation, a phase constraint, that can be thought of as determining the period. This is necessary because any solution of the above boundary value problem can be shifted in time by an arbitrary amount (time does not appear in the defining equations—the dynamical system is called autonomous).
There are several choices for the phase constraint. If
is a known periodic orbit at a parameter value near , then, Poincaré usedwhich states that
lies in a plane which is orthogonal to the tangent vector of the closed curve. This plane is called aPoincaré section.
For a general problem a better phase constraint is an integral constraint introduced by Eusebius Doedel, which chooses the phase so that the distance between the known and unknown orbits is minimized:
Homoclinic and heteroclinic motions
Solution component
A solution component of the nonlinear system is a set of points which satisfy and are connected to the initial solution by a path of solutions for which and
.This figure shows two solution components, one red and the other blue. Note that these two components may be connected outside the region of interest.
Numerical continuation
A numerical continuation is an algorithm which takes as input a system of parametrized nonlinear equations and an initial solution, , and produces a set of points on the solution component .Regular point
A regular point of is a point at which the JacobianJacobian
In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector- or scalar-valued function with respect to another vector. Suppose F : Rn → Rm is a function from Euclidean n-space to Euclidean m-space...
of
is full rank .Near a regular point the solution component is an isolated curve passing through the regular point (the implicit function theorem
Implicit function theorem
In multivariable calculus, the implicit function theorem is a tool which allows relations to be converted to functions. It does this by representing the relation as the graph of a function. There may not be a single function whose graph is the entire relation, but there may be such a function on...
). In the figure above the point
is a regular point.Singular point
A singular point of is a point at which the JacobianJacobian
In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector- or scalar-valued function with respect to another vector. Suppose F : Rn → Rm is a function from Euclidean n-space to Euclidean m-space...
of F is not full rank.
Near a singular point the solution component may not be an isolated curve passing through the regular point. The local structure is determined by higher derivatives of
. In the figure above the point where the two blue curves cross is a singular point.In general solution components
are branched curves. The branch points are singular points. Finding the solution curves leaving asingular point is called branch switching, and uses techniques from bifurcation theory
Bifurcation theory
Bifurcation theory is the mathematical study of changes in the qualitative or topological structure of a given family, such as the integral curves of a family of vector fields, and the solutions of a family of differential equations...
(singularity theory
Singularity theory
-The notion of singularity:In mathematics, singularity theory is the study of the failure of manifold structure. A loop of string can serve as an example of a one-dimensional manifold, if one neglects its width. What is meant by a singularity can be seen by dropping it on the floor...
, catastrophe theory
Catastrophe theory
In mathematics, catastrophe theory is a branch of bifurcation theory in the study of dynamical systems; it is also a particular special case of more general singularity theory in geometry....
).
For finite dimensional systems (as defined above) the Lyapunov-Schmidt decomposition may be used to produce two systems to which the Implicit Function Theorem applies. The Lyapunov-Schmidt decomposition uses the restriction of the system to the complement of the null space of the Jacobian and the range of the Jacobian.
If the columns of the matrix
are an orthonormal basis for the null space ofand the columns of the matrix
are an orthonormal basis for the left null space of , thenthe system
can be rewritten as
where
is in the complement of the null space of .In the first equation, which is parametrized by the null space of the Jacobian (
), the Jacobian with respect to is non-singular. So the implicit function theorem states that there is a mapping such that and . The second equation (with substituted) is called the bifurcation equation (though it may be a system of equations).The bifurcation equation has a Taylor expansion which lacks the constant and linear terms. By scaling the equations and the null space of the Jacobian of the original system a system can be found with non-singular Jacobian. The constant term in the Taylor series of the scaled bifurcation equation is called the algebraic bifurcation equation, and the implicit function theorem applied the bifurcation equations states that for each isolated solution of the algebraic bifurcation equation there is a branch of solutions of the original problem which passes through the singular point.
Another type of singular point is a turning point bifurcation, or saddle-node bifurcation
Saddle-node bifurcation
In the mathematical area of bifurcation theory a saddle-node bifurcation, tangential bifurcation or fold bifurcation is a local bifurcation in which two fixed points of a dynamical system collide and annihilate each other. The term 'saddle-node bifurcation' is most often used in reference to...
, where the direction of the parameter
reverses as the curve is followed. The red curve in the figure above illustrates a turning point.
Natural parameter continuation
Most methods of solution of nonlinear systems of equations are iterative methods. For a particular parameter value a mapping is repeatedly applied to an initial guess . If the method converges, and is consistent, then in thelimit the iteration approaches a solution of
.Natural parameter continuation is a very simple adaptation of the iterative solver to a parametrized problem. The solution at
one value of
is used as the initial guess for the solution at . With sufficiently small the iteration applied to the initialguess should converge.
One advantage of natural parameter continuation is that is uses the solution method for the problem as a black box. All that is required is that an initial solution can be given (some solvers used to always start at a fixed initial guess). There has been a lot of work in the area of large scale continuation on applying more sophisticated algorithms to black box solvers. (see e.g. LOCA).
However, natural parameter continuation fails at turning points, where the branch of solutions turns round. So for problems with turning points, a more sophisticated method such as pseudo-arclength continuation must be used (see below).
Simplicial or piecewise linear continuation
Simplicial Continuation, or Piecewise Linear Continuation (Allgower and Georg) is based on three basic results.The first is
| If F(x) maps IR^n into IR^(n-1), there is a unique linear interpolant on an (n-1)-dimensional simplex Simplex In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,... which agrees with the function values at the vertices of the simplex. |
The second result is:
| An (n-1)-dimensional simplex can be tested to determine if the unique linear interpolant takes on the value 0 inside the simplex. |
Please see the article on piecewise linear continuation
Piecewise linear continuation
- Simplicial Continuation :Simplicial Continuation, or Piecewise Linear Continuation is a one parameter continuation method which is well suited to small to medium embedding spaces...
for details.
With these two operations this continuation algorithm is easy to state (although of course an efficient implementation requires a more sophisticated approach. See [B1]). An initial simplex is assumed to be given, from a reference simplicial decomposition of IR^n. The initial simplex must have at least one face which contains a zero of the unique linear interpolant on that face. The other faces of the simplex are then tested, and typically there will be one additional face with an interior zero. The initial simplex is then replaced by the simplex which lies across either face containing zero, and the process is repeated.
References: Allgower and Georg [B1] provides a crisp, clear description of the algotihm.
Pseudo-arclength continuation
This method, which was proposed by H.B. Keller [A5] in the late 1970s, is based on the observation that the "ideal" parameterization of a curve is arclength. Pseudo-arclength is an approximation of the arclength in the tangent space of the curve. The resulting modified natural continuation method makes a step in pseudo-arclength (rather than). The iterative solver is required to find a point at the given pseudo-arclength, which requires appending an additionalconstraint (the pseudo-arclength constraint) to the n by n+1 Jacobian. It produces a square Jacobian, and if the stepsize is sufficiently small the modified Jacobian is full rank.
The algorithm is a predictor-corrector method. The prediction step finds the point (in IR^(n+1) ) which is a step
along the tangent vector at the current pointer. The corrector is usually Newton's method, or some variant, to solve the nonlinear systemwhere
is the tangent vector at .The Jacobian of this system is the bordered matrix
Gauss–Newton continuation
This method is a variant of pseudo-arclength continuation. Instead of using the tangent at the initial point in the arclength constraint, the tangent at the current solution is used. This is equivalent to using the pseudo-inverse of the Jacobian in Newton's method, and allows longer steps to be made. [B17]Continuation in more than one parameter
The parameter in the algorithms described above is a real scalar. Most physical and design problems generally have many more than one parameter. Higher dimensional continuation refers to the case when is a k-vector.The same terminology applies. A regular solution is a solution at which the Jacobian is full rank
. A singular solution is a solution at which the Jacobian is less than full rank.A regular solution lies on a k-dimensional surface, which can be parameterized by a point in the tangent space (the null space of the Jacobian). This is again a straightforward application of the Implicit Function Theorem.
Applications of numerical continuation techniques
Numerical continuation techniques have found a great degree of acceptance in the study of chaotic dynamical systems and various other systems which belong to the realm of catastrophe theoryCatastrophe theory
In mathematics, catastrophe theory is a branch of bifurcation theory in the study of dynamical systems; it is also a particular special case of more general singularity theory in geometry....
. The reason for such usage stems from the fact that various non-linear dynamical systems behave in a deterministic and predictable manner within a range of parameters which are included in the equations of the system. However, for a certain parameter value the system starts behaving chaotically and hence it become necessary to follow the parameter in order to be able to decipher the occurrences of when the system starts being non-predictable, and what exactly (theoretically) makes the system become unstable.
Analysis of parameter continuation can lead to more insights about stable/critical point bifurcations. Study of saddle-node, transcritical, pitch-fork, period doubling, Hopf, secondary Hopf (Neimark) bifurcations of stable solutions allows for a theoretical discussion of the circumstances and occurrences which arise at the critical points. Parameter continuation also gives a more dependable system to analyze a dynamical system as it is more stable than more interactive, time-stepped numerical solutions. Especially in cases where the dynamical system is prone to blow-up at certain parameter values (or combination of values for multiple parameters).
It is extremely insightful as to the presence of stable solutions (attracting or repelling) in the study of Nonlinear Partial Differential Equations where times stepping in the form of the Crank Nicolson algorithm is extremely time consuming as well as unstable in cases of nonlinear growth of the dependent variables in the system. The study of turbulence is another field where the Numerical Continuation techniques have been used to study the advent of turbulence
Turbulence
In fluid dynamics, turbulence or turbulent flow is a flow regime characterized by chaotic and stochastic property changes. This includes low momentum diffusion, high momentum convection, and rapid variation of pressure and velocity in space and time...
in a system starting at low Reynold's numbers. Also, a research using these techniques has provided the possibility of finding stable manifolds and bifurcations to invariant-tori in the case of the restricted three body problem in Newtonian gravity and have also given interesting and deep insights into the behaviour of systems such as the Lorenz equations.
Software
(Under Construction) See also The SIAM Activity Group on Dynamical Systems' list http://www.dynamicalsystems.org/sw/sw/- AUTO: Computation of the solutions of Two Point Boundary Value Problems (TPBVPs) with integral constraints. http://auto2000.sourceforge.net/ Available on SourceForge.
- HOMCONT: Computation of homoclinic and heteroclinic orbits. Included in AUTO
- MATCONT: Matlab toolbox for numerical continuation and bifurcation http://www.matcont.ugent.be/
- DDEBIFTOOL: Computation of solutions of Delay Differential Equations. A MATLAB package. Available from the K. U. Leuven Available from K. U. Leuven
- PyCont: A Python toolbox for numerical continuation and bifurcation. Native python algorithms for fixed point continuation, sophisticated interface to AUTO for other types of problem. Included as part of PyDSTool
- CANDYS/QA: Available from the Universität Potsdam [A16]
- MANPAK: Available from Netlib [A15]
- PDDE-CONT: http://seis.bris.ac.uk/~rs1909/pdde/
- multifario: http://multifario.sourceforge.net/
- LOCA: http://trilinos.sandia.gov/packages/nox/
- ENTWIFE: http://www.sercoassurance.com/entwife/
- DSTool
- GAIO
- OSCILL8: Oscill8 is a dynamical systems tool that allows a user to explore high dimensional parameter space of nonlinear ODEs using bifurcation analytic techniques. Available from SourceForge.
Examples
This problem, of finding the points which F maps into the origin appears in computer graphicsComputer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
as the problems of drawing contour maps (n=2), or isosurface
Isosurface
An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value within a volume of space; in other words, it is a level set of a continuous function whose domain is 3D-space.Isosurfaces are normally displayed using computer graphics, and are...
(n=3). The contour with value h is the set of all solution components of F-h=0
Books
[B1] "Introduction to Numerical Continuation Methods", Eugene L. Allgower and Kurt Georg, SIAM Classics in Applied Mathematics 45. 2003.[B2] "Numerical Methods for Bifurcations of Dynamical Equilibria", Willy J. F. Govaerts, SIAM 2000.
[B3] "Lyapunov-Schmidt Methods in Nonlinear Analysis and Applications", Nikolay Sidorov, Boris Loginov, Aleksandr Sinitsyn, and Michail Falaleev, Kluwer Academic Publishers, 2002.
[B4] "Methods of Bifurcation Theory", Shui-Nee Chow and Jack K. Hale, Springer-Verlag 1982.
[B5] "Elements of Applied Bifurcation Theory", Yuri A. Kunetsov, Springer-Verlag Applied Mathematical Sciences 112, 1995.
[B6] "Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields", John Guckenheimer
John Guckenheimer
John Guckenheimer joined the Department of Mathematics at Cornell University in 1985. He was previously at the University of California at Santa Cruz . He was a Guggenheim fellow in 1984, and was elected president of the Society for Industrial and Applied Mathematics in 1996. Guckenheimer received...
and Philip Holmes
Philip Holmes
Philip J. Holmes is the Eugene Higgins Professor of Mechanical and Aerospace Engineering at Princeton University. As a member of the Mechanical and Aerospace Engineering department, he formerly served as the interim chair until May 2007....
, Springer-Verlag Applied Mathematical Sciences 42, 1983.
[B7] "Elementary Stability and Bifurcation Theory", Gerard Iooss and Daniel D. Joseph, Springer-Verlag Undergraduate Texts in Mathematics, 1980.
[B8] "Singularity Theory and an Introduction to Catastrophe Theory", Yung-Chen Lu, Springer-Verlag, 1976.
[B9] "Global Bifurcations and Chaos, Analytic Methods", S. Wiggins, Springer-Verlag Applied Mathematical Sciences 73, 1988.
[B10] "Singularities and Groups in Bifurcation Theory, volume I", Martin Golubitsky and David G. Schaeffer, Springer-Verlag Applied Mathematical Sciences 51, 1985.
[B11] "Singularities and Groups in Bifurcation Theory, volume II", Martin Golubitsky, Ian Stewart and David G. Schaeffer, Springer-Verlag Applied Mathematical Sciences 69, 1988.
[B12] "Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems", Alexander Morgan, Prentice-Hall, Englewood Cliffs, N.J. 1987.
[B13] "Pathways to Solutions, Fixed Points and Equilibria", C. B. Garcia and W. I. Zangwill, Prentice-Hall, 1981.
[B14] "The Implicit Function Theorem: History, Theory and Applications", Steven G. Krantz and Harold R. Parks, Birkhauser, 2002.
[B15] "Nonlinear Functional Analysis", J. T. Schwartz, Gordon and Breach Science Publishers, Notes on Mathematics and its Applications, 1969.
[B16] "Topics in Nonlinear Functional Analysis", Louis Nirenberg (notes by Ralph A. Artino), AMS Courant Lecture Notes in Mathematics 6, 1974.
[B17] "Newton Methods for Nonlinear Problems -- Affine Invariance and Adaptive Algorithms", P. Deuflhard,
Series Computational Mathematics 35, Springer, 2006.
Journal articles
[A1] "An Algorithm for Piecewise Linear Approximation of Implicitly Defined Two-Dimensional Surfaces", Eugene L. Allgower and Stefan Gnutzmann, SIAM Journal on Numerical Analysis, Volume 24, Number 2, 452—469, 1987.[A2] "Simplicial and Continuation Methods for Approximations, Fixed Points and Solutions to Systems of Equations", E. L. Allgower and K. Georg, SIAM Review, Volume 22, 28—85, 1980.
[A3] "An Algorithm for Piecewise-Linear Approximation of an Implicitly Defined Manifold", Eugene L. Allgower and Phillip H. Schmidt, SIAM Journal on Numerical Analysis, Volume 22, Number 2, 322—346, April 1985.
[A4] "Contour Tracing by Piecewise Linear Approximations", David P. Dobkin
David P. Dobkin
David Paul Dobkin is the Dean of the Faculty and Phillip Y. Goldman '86 Professor of Computer Science at Princeton University.Dobkin was born February 29, 1948, in Pittsburgh, Pennsylvania. After receiving a B.S. from the Massachusetts Institute of Technology in 1970, he moved to Harvard University...
, Silvio V. F. Levy, William P. Thurston
William Thurston
William Paul Thurston is an American mathematician. He is a pioneer in the field of low-dimensional topology. In 1982, he was awarded the Fields Medal for his contributions to the study of 3-manifolds...
and Allan R. Wilks, ACM Transactions on Graphics, 9(4) 389-423, 1990.
[A5] "Numerical Solution of Bifurcation and Nonlinear Eigenvalue Problems", H. B. Keller, in "Applications of Bifurcation Theory", P. Rabinowitz ed., Academic Press, 1977.
[A6] "A Locally Parameterized Continuation Process", W.C. Rheinboldt and J.V. Burkardt, ACM Transactions on Mathematical Software, Volume 9, 236—246, 1983.
[A7] "Nonlinear Numerics" E. Doedel, International Journal of Bifurcation and Chaos
International Journal of Bifurcation and Chaos
International Journal of Bifurcation and Chaos is a journal that has been published by World Scientific since its founding in 1991. It covers chaos and nonlinear science in a diverse range of fields in Applied Sciences, such as astronomy and zoology, as well as Engineering, such as in aerospace...
, 7(9):2127-2143, 1997.
[A8] "Nonlinear Computation", R. Seydel, International Journal of Bifurcation and Chaos
International Journal of Bifurcation and Chaos
International Journal of Bifurcation and Chaos is a journal that has been published by World Scientific since its founding in 1991. It covers chaos and nonlinear science in a diverse range of fields in Applied Sciences, such as astronomy and zoology, as well as Engineering, such as in aerospace...
, 7(9):2105-2126, 1997.
[A9] "On a Moving Frame Algorithm and the Triangulation of Equilibirum Manifolds", W.C. Rheinboldt, In T. Kuper, R. Seydel, and H. Troger eds. "ISNM79: Bifurcation: Analysis, Algorithms, Applications", pages 256-267. Birkhauser, 1987.
[A10] "On the Computation of Multi-Dimensional Solution Manifolds of Parameterized Equations", W.C. Rheinboldt, Numerishe Mathematik, 53, 1988, pages 165-181.
[A11] "On the Simplicial Approximation of Implicitly Defined Two-Dimensional Manifolds", M. L. Brodzik and W.C. Rheinboldt, Computers and Mathematics with Applications, 28(9): 9-21, 1994.
[A12] "The Computation of Simplicial Approximations of Implicitly Defined p-Manifolds", M. L. Brodzik, Computers and Mathematics with Applications, 36(6):93-113, 1998.
[A13] "New Algorithm for Two-Dimensional Numerical Continuation", R. Melville and D. S. Mackey, Computers and Mathematics with Applications, 30(1):31-46, 1995.
[A14] "Multiple Parameter Continuation: Computing Implicitly Defined k-manifolds", M. E. Henderson, IJBC 12[3]:451-76, 2003.
[A15] "MANPACK: a set of algorithms for computations on implicitly defined manifolds", W. C. Rheinboldt, Comput. Math. Applic. 27 pages 15–9, 1996.
[A16] "CANDYS/QA - A Software System For Qualitative Analysis Of Nonlinear Dynamical Systems", Feudel, U. and W. Jansen, Int. J. Bifurcation and Chaos, vol. 2 no. 4, pp. 773–794, World Scientific, 1992.