User:Mhender/Sandbox
From Wikipedia, the free encyclopedia
Contents |
[edit] Numerical Continuation
Numerical Continuation is a method of computing approximate solutions of a system of parameterized nonlinear equations,
| F(u,λ)=0. |
The parameter λ is usually a real scalar, and the solution an n-vector.
| For a fixed parameter value λ, F(*,λ) maps Euclidean n-space into itself. |
Often the original mapping F 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 orbits can also be posed as a solution of F=0.
[edit] Other forms of the problem:
In some nonlinear systems, parameters are explicit. In others they are implicit, and the system of nonlinear equations is written
| F(u)=0 |
where u is an n-vector, and it's image F(u) is an n-1 vector.
[edit] Definitions:
| A Solution component Γ_(u0,λ0) of the nonlinear system F is a set of points (u,λ) which satisfy F(u,λ)=0 and are connected to the initial solution (u0,λ0) by a path of solutions (u(s),λ(s)) for which (u(0),λ(0))=(u0,λ0), (u(1),λ(1))=(u,λ), and F(u(s),λ(s))=0. |
This figure show two solution components, one red and the other blue. Note that these two components may be connected outside the region of interest.
| A Numerical Continuation takes as input a system of parameterized nonlinear equations and an initial solution (u0,λ0), F(u0,λ0)=0, and produces the solution component Γ_(u0,λ0). |
| A Regular Point of F is a point (u,λ) at which the Jacobian of F is full rank (n). |
Near a regular point the solution component is an isolated curve passing through the regular point (The Implicit Function). In the figure above the point (u0,λ0) is a regular point.
| A Singular Point of F is a point (u,λ) 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 F. 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 branch switching, and uses techniques from bifurcation theory (singularity theory, catastrophe theory).
[edit] Particular Algorithms
[edit] Natural Parameter Continuation
Most methods of solution of nonlinear systems of equations are iterative methods. For a particular parameter value λ0 a mapping is repeatedly applied to an initial guess u0. If the method converges, and is consistant, then in the limit the iteration approaches a solution of F(u,λ0)=0.
Natural parameter continuation is a very simple adaptation of the iterative solver to the parameterized 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 iterative method for 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).
[edit] Simplicial Continuation
[edit] Pseudo-arclength Continuation
[edit] Examples
This problem, of finding the points which F maps into the origin appears in computer graphics 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
[edit] Higher Dimensional Continuation
The parameter λ is usually a real scalar, but it may be a k-vector. For k>1 a continuation method is called a multiparameter continuation method, or a higher dimensional continuation method.
[edit] References
[edit] Books
"Introduction to Numerical Continuation Methods", Eugene L. Allgower and Kurt Georg, SIAM Classics in Applied Mathematics 45. 2003.
"Numerical Methods for Bifurcations of Dynamical Equilibria", Willy J. F. Govaerts, SIAM 2000.
"Lyapunov-Schmidt Methods in Nonlinear Analysis and Applications", Nikolay Sidorov, Boris Loginov, Aleksandr Sinitsyn, and Michail Falaleev, Kluwer Academic Publishers, 2002.
"Methods of Bifurcation Theory", Shui-Nee Chow and Jack K. Hale, Springer-Verlag 1982.
"Elements of Applied Bifurcation Theory", Yuri A. Kunetsov, Springer-Verlag Applied Mathematical Sciences 112, 1995.
"Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields", John Guckenheimer and Philip Holmes, Springer-Verlag Applied Mathematical Sciences 42, 1983.
"Elementary Stability and Bifurcation Theory", Gerard Iooss and Daniel D. Joseph, Springer-Verlag Undergraduate Texts in Mathematics, 1980.
"Singularity Theory and an Introduction to Catastrophe Theory", Yung-Chen Lu, Springer-Verlag, 1976.
"Global Bifurcations and Chaos, Analytic Methods", S. Wiggins, Springer-Verlag Applied Mathematical Sciences 73, 1988.
"Singularities and Groups in Bifurcation Theory, volume I", Martin Golubitsky and David G. Schaeffer, Springer-Verlag Applied Mathematical Sciences 51, 1985.
"Singularities and Groups in Bifurcation Theory, volume II", Martin Golubitsky, Ian Stewart and David G. Schaeffer, Springer-Verlag Applied Mathematical Sciences 69, 1988.
"Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems", Alexander Morgan, Prentice-Hall, Englewood Cliffs, N.J. 1987.
"Pathways to Solutions, Fixed Points and Equilibria", C. B. Garcia and W. I. Zangwill, Prentice-Hall, 1981.
"The Implicit Function Theorem: History, Theory and Applications", Steven G. Krantz and Harold R. Parks, Birkhauser, 2002.
"Nonlinear Functional Analysis", J. T. Schwartz, Gordon and Breach Science Publishers, Notes on Mathematics and its Applications, 1969.
"Topics in Nonlinear Functional Analysis", Louis Nirenberg (notes by Ralph A. Artino), AMS Courant Lecture Notes in Mathematics 6, 1974.
[edit] Journal Articles
"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.
"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.
"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.
"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.
"Numerical Solution of Bifurcation and Nonlinear Eigenvalue Problems", H. B. Keller, in "Applications of Bifurcation Theory", P. Rabinowitz ed., Academic Press, 1977.
"A Locally Parameterized Continuation Process", W.C. Rheinboldt and J.V. Burkardt, ACM Transactions on Mathematical Software, Volume 9, 236--246, 1983.
"Nonlinear Numerics" E. Doedel, International Journal of Bifurcation and Chaos, 7(9):2127-2143, 1997.
"Nonlinear Computation", R. Seydel, International Journal of Bifurcation and Chaos, 7(9):2105-2126, 1997.
"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.
"On the Computation of Multi-Dimensional Solution Manifolds of Parameterized Eqautions", W.C. Rheinboldt, Numerishe Mathematik, 53, 1988, pages 165-181.
"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.
"The Computation of Simplicial Approximations of Implicitly Defined p-Manifolds", M. L. Brodzik, Computers and Mathematics with Applications, 36(6):93-113, 1998.
"New Algorithm for Two-Dimensional Numerical Continuation", R. Melville and D. S. Mackey, Computers and Mathematics with Applications, 30(1):31-46, 1995.
"Multiple Parameter Continuation: Computing Implicitly Defined k-manifolds", M. E. Henderson, IJBC 12[3]:451-76, 2003.
