article

A survey of shadowing methods for numerical solutions of ordinary differential equations

Authors:

Kenneth R. JacksonAuthors Info & Claims

Applied Numerical Mathematics, Volume 53, Issue 2-4

Pages 299 - 321

Published: 01 May 2005 Publication History

Abstract

A shadow is an exact solution to a set of equations that remains close to a numerical solution for a long time. Shadowing can thus be used as a form of backward error analysis for numerical solutions to ordinary differential equations. This survey introduces the reader to shadowing with a detailed tour of shadowing algorithms and practical results obtained over the last 15 years.

References

[1]

Anosov, D.V., Geodesic flows and closed Riemannian manifolds with negative curvature. Proc. Steklov Inst. Math. v90. 1

[2]

Ascher, U.M., Mattheij, R.M.M. and Russell, R.D., Numerical Solution of Boundary Value Problems for Ordinary Differential Equations. 1988. Prentice-Hall Series in Computational Mathematics, 1988.Prentice-Hall, Englewood Cliffs, NJ.

[3]

Beyn, W.-J., On invariant closed curves for one-step methods. Numer. Math. v51. 103-122.

[4]

Bowen, R., ω-limit sets for axiom A diffeomorphisms. J. Differential Equations. v18. 333

[5]

Braun, M., Differential Equations and Their Applications. 1983. third ed. Springer, Berlin.

[6]

Channell, P.J. and Scovel, C., Symplectic integration of Hamiltonian systems. Nonlinearity. v3. 231-259.

[7]

Chow, S.N., Lin, X.B. and Palmer, K.J., A shadowing lemma for maps in infinite dimensions. In: Daffermos, C.M., Ladas, G., Papanicolaou, G. (Eds.), Differential Equations: Proceedings of the EQUADIFF Conference, Marcel Dekker, New York. pp. 127-136.

[8]

Chow, S.-N. and Palmer, K.J., On the numerical computation of orbits of dynamical systems: The one-dimensional case. Dynamics Differential Equations. v3. 361-380.

[9]

Chow, S.-N. and Palmer, K.J., On the numerical computation of orbits of dynamical systems: The higher dimensional case. J. Complexity. v8. 398-423.

[10]

Chow, S.-N. and Van Vleck, E.S., A shadowing lemma for random diffeomorphisms. Random Comput. Dynamics. v1 i2. 197-218.

[11]

Chow, S.N. and Van Vleck, E.S., Shadowing of lattice maps. In: Kloeden, P.E., Palmer, K.J. (Eds.), Chaotic Numerics, American Mathematical Society, Providence, RI. pp. 97-113.

[12]

Chow, S.-N. and Van Vleck, E.S., A shadowing lemma approach to global error analysis for initial value ODEs. SIAM J. Sci. Comput. v15 i4. 959-976.

[13]

Chow, S.N. and Van Vleck, E.S., Shadowing of lattice maps. In: Contemporary Mathematics, vol. 172. pp. 97-113.

[14]

In: Clarke, D.A., West, M.J. (Eds.), ASP Conference Series, vol. 123. Astronom. Soc. of the Pacific.

[15]

Coomes, B.A., Shadowing orbits of ordinary differential equations on invariant submanifolds. Trans. Amer. Math. Soc. v349 i1. 203-216.

[16]

Coomes, B.A., Koçak, H. and Palmer, K.J., Periodic shadowing. In: Kloeden, P., Palmer, K. (Eds.), Contemporary Mathematics, vol. 172. American Mathematical Society, Providence, RI. pp. 115-130.

[17]

Coomes, B.A., Koçak, H. and Palmer, K.J., Shadowing orbits of ordinary differential equations. J. Comput. Appl. Math. v52. 35-43.

[18]

Coomes, B.A., Koçak, H. and Palmer, K.J., Rigorous computational shadowing of orbits of ordinary differential equations. Numer. Math. v69. 401-421.

[19]

Coomes, B.A., Koçak, H. and Palmer, K.J., A shadowing theorem for ordinary differential equations. Z. Angew. Math. Phys. v46. 85-106.

[20]

Coomes, B.A., Koçak, H. and Palmer, K.J., Long periodic shadowing. Numer. Algorithms. v14. 55-78.

[21]

Corless, R.M., Continued fractions and chaos. Amer. Math. Monthly. v99 i3. 203-215.

[22]

Corless, R.M., Defect-controlled numerical methods and shadowing for chaotic differential equations. Physica D. v60. 323-334.

[23]

Corless, R.M., Error backward. In: Contemporary Mathematics, vol. 172. pp. 31-62.

[24]

Corless, R.M., What good are numerical simulations of chaotic dynamical systems?. Comput. Math. Appl. v28 i10--12. 107-121.

[25]

Corless, R.M., Continued fractions and chaos. Amer. Math. Monthly. v99 i3. 203-215.

[26]

Corless, R.M. and Corliss, G.F., Rationale for guaranteed ODE defect control. In: Atanassova, L., Herzberger, J. (Eds.), Computer Arithmetic and Enclosure Methods, Elsevier, Amsterdam.

[27]

Dahlquist, G. and Björck, Å., Numerical Methods. 1974. Prentice-Hall Series in Automatic Computation, 1974.Prentice-Hall, Englewood Cliffs, NJ.

[28]

Dawson, S., Grebogi, C., Sauer, T. and Yorke, J.A., Obstructions to shadowing when a Lyapunov exponent fluctuates about zero. Phys. Rev. Lett. v73 i14. 1927-1930.

[29]

W.H. Enright, W.B. Hayes, Robust defect control for continuous rk-methods with high-order interpolants, submitted for publication

[30]

Farmer, J.D. and Sidorowich, J.J., Optimal shadowing and noise reduction. Physica D. v47. 373-392.

[31]

Fryska, S.T. and Zohdy, M.A., Computer dynamics and the shadowing of chaotic orbits. Phys. Lett. A. v166. 340-346.

[32]

Golub, G.H. and Van Loan, C.F., Matrix Computations. 1991. Johns Hopkins University Press, Baltimore, MD.

[33]

Gonzalez, O., Higham, D.J. and Stuart, A.M., On the qualitative properties of modified equations. IMA J. Numer. Anal. v19. 169-190.

[34]

Góra, P. and Boyarsky, A., Why computers like Lebesgue measure. Comput. Math. Appl. v16 i4. 321-329.

[35]

Grebogi, C., Hammel, S.M., Yorke, J.A. and Sauer, T., Shadowing of physical trajectories in chaotic dynamics: Containment and refinement. Phys. Rev. Lett. v65 i13. 1527-1530.

[36]

Hadeler, K.P., Shadowing orbits and Kantorovich's theorem. Numer. Math. v73. 65-73.

[37]

Hairer, E., Nørsett, S.P. and Wanner, G., Solving Ordinary Differential Equations. 1993. second ed. Springer, Berlin.

[38]

Hammel, S.M., Yorke, J.A. and Grebogi, C., Do numerical orbits of chaotic dynamical processes represent true orbits?. J. Complexity. v3. 136-145.

[39]

Hammel, S.M., Yorke, J.A. and Grebogi, C., Numerical orbits of chaotic dynamical processes represent true orbits. Bull. Amer. Math. Soc. v19. 465-470.

[40]

W. Hayes, Efficient shadowing of high dimensional chaotic systems with the large astrophysical n-body problem as an example, Master's Thesis, Dept. of Computer Science, University of Toronto, 1995

[41]

Hayes, W., Shadowing-based reliability decay in softened n-body simulations. Astrophys. J. Lett. v587. 59-62.

[42]

Hayes, W., Shadowing high-dimensional Hamiltonian systems: the gravitational n-body problem. Phys. Rev. Lett. v90 i5.

[43]

W. Hayes, K.R. Jackson, A fast shadowing algorithm for high dimensional ODE systems, 1996, unpublished

[44]

W.B. Hayes, Rigorous Shadowing of Numerical Solutions of Ordinary Differential Equations by Containment, Ph.D. Thesis, Department of Computer Science, University of Toronto, 2001, Available on the web as http://www.cs.toronto.edu/NA/reports.html#hayes-01-phd

[45]

Hayes, W.B. and Jackson, K.R., Rigorous shadowing of numerical solutions of ordinary differential equations by containment. SIAM J. Numer. Anal. v41 i5. 1948-1973.

[46]

Kahaner, D., Moler, C. and Nash, S., Numerical Methods and Software. 1989. Prentice-Hall Series in Computational Mathematics, 1989.Prentice-Hall, Englewood Cliffs, NJ.

[47]

Merritt, D., Elliptical galaxy dynamics. Publ. Astronom. Soc. Pacific. v111 i756. 129-168.

[48]

In: Merritt, D., Sellwood, J.A., Valluri, M. (Eds.), ASP Conference Series, vol. 182. Astronom. Soc. of the Pacific.

[49]

Merritt, D. and Valluri, M., Chaos and mixing in triaxial stellar systems. Astrophys. J. v471. 82-105.

[50]

N.S. Nedialkov, Computing Rigorous Bounds on the Solution of an Initial Value Problem for an Ordinary Differential Equation, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1999

[51]

Palmer, K.J., Exponential dichotomies, the shadowing lemma and transversal homoclinic points. In: Kirchgraber, U., Walther, H.O. (Eds.), Dynamics Reported, vol. 1, Wiley and Teubner.

[52]

Palmer, K.J., Shadowing in Dynamical Systems---Theory and Applications. 2000. Kluwer Academic, Dordrecht.

[53]

Palmer, K.J. and Stoffer, D., Rigorous verification of chaotic behaviour of maps using validated shadowing. Nonlinearity. v12. 1683-1698.

[54]

Pilyugin, S.Y., Shadowing in Dynamical Systems. 1999.

[55]

Quinlan, G.D. and Tremaine, S., Shadow orbits and the gravitational N-body problem. In: Sundelius, B. (Ed.), Dynamics of Disc Galaxies, Göteborg, Sweden. pp. 143-148.

[56]

Quinlan, G.D. and Tremaine, S., On the reliability of gravitational N-body integrations. Monthly Notices Roy. Astronom. Soc. v259. 505-518.

[57]

Sanz-Serna, J.M., Symplectic integrators for Hamiltonian problems: An overview. In: Iserles, A. (Ed.), Acta Numerica 1992, Cambridge University Press, Cambridge. pp. 243-286.

[58]

Sauer, T., Grebogi, C. and Yorke, J.A., How long do numerical chaotic solutions remain valid?. Phys. Rev. Lett. v79 i1. 59-62.

[59]

Sauer, T. and Yorke, J.A., Rigorous verification of trajectories for the computer simulation of dynamical systems. Nonlinearity. v4. 961-979.

[60]

Shadwick, B.A., Bowman, J.C. and Morrison, P.J., Exactly conservative integrators. SIAM J. Appl. Math. v59 i3. 1112-1133.

[61]

R. Skeel, The meaning of molecular dynamics, 1996, unpublished, e-mail: [email protected]

[62]

Skeel, R.D., Integration schemes for molecular dynamics and related applications. In: Ainsworth, M., Levesley, J., Marletta, M. (Eds.), The Graduate Student's Guide to Numerical Analysis, SSCM, Springer, Berlin. pp. 119-176.

[63]

Smale, S., Diffeomorphisms with many periodic points. In: Cairns, S. (Ed.), Differential and Combinatorial Topology, Princeton University Press, Princeton, NJ. pp. 63-80.

[64]

Smale, S., Differentiable dynamical systems. Bull. Amer. Math. Soc. v73. 747-817.

[65]

Struck, C., Galaxy splashes: The effects of collisions between gas-rich galaxy disks. In: Clarke, D.A., West, M.J. (Eds.), ASP Conference Series, vol. 123. Astronom. Soc. of the Pacific. pp. 225-230.

[66]

Van Vleck, E.S., Numerical shadowing near hyperbolic trajectories. SIAM J. Sci. Comput. v16 i5. 1172-1189.

Cited By

Orvieto ALucchi AWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Shadowing properties of optimization algorithmsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455424(12692-12703)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455424
Zhu YHayes W(2010)Algorithm 908ACM Transactions on Mathematical Software10.1145/1824801.182481537:3(1-13)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1824801.1824815

Index Terms

A survey of shadowing methods for numerical solutions of ordinary differential equations
1. General and reference
  1. Document types
    1. Surveys and overviews
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Ordinary differential equations
    2. Numerical analysis

Recommendations

The numerical solution of large systems of stiff IVPs for ODEs
Numerical methods for smooth solutions of ordinary differential equations
A numerical C¹-shadowing result for retarded functional differential equations

The aim of the present paper is to give a numerical C¹-shadowing between the exact solutions of a functional differential equation and its numerical approximations. The shadowing result is obtained by comparing exact solutions with numerical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Numerical Mathematics

Applied Numerical Mathematics Volume 53, Issue 2-4

May, 2005

444 pages

ISSN:0168-9274

Issue’s Table of Contents

Copyright © © 2004.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 May 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Orvieto ALucchi AWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Shadowing properties of optimization algorithmsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455424(12692-12703)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455424
Zhu YHayes W(2010)Algorithm 908ACM Transactions on Mathematical Software10.1145/1824801.182481537:3(1-13)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1824801.1824815

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents