On theoretical upper limits for valid timesteps of implicit ODE methods

Kevin R. Green; George W. Patrick; Raymond J. Spiteri; Kevin R. Green; George W. Patrick; Raymond J. Spiteri

doi:10.3934/math.2019.6.1841

AIMS Mathematics

2019, Volume 4, Issue 6: 1841-1853. doi: 10.3934/math.2019.6.1841

Previous Article Next Article

Research article Special Issues

On theoretical upper limits for valid timesteps of implicit ODE methods

1.
Department of Computer Science, University of Saskatchewan, 110 Science Place, Saskatoon, SK, S7N 5C9, Canada
2.
Department of Mathematics and Statistics, University of Saskatchewan, 106 Wiggins Road, Saskatoon, SK, S7N 5E6, Canada

Received: 31 January 2020 Accepted: 07 February 2020 Published: 19 February 2020
MSC : 34A09

Implicit methods for the numerical solution of initial-value problems may admit multiple solutions at any given time step. Accordingly, their nonlinear solvers may converge to any of these solutions. Below a critical timestep, exactly one of the solutions (the consistent solution) occurs on a solution branch (the principal branch) that can be continuously and monotonically continued back to zero timestep. Standard step-size control can promote convergence to consistent solutions by adjusting the timestep to maintain an error estimate below a given tolerance. However, simulations for symplectic systems or large physical systems are often run with constant timesteps and are thus more susceptible to convergence to inconsistent solutions. Because simulations cannot be reliably continued from inconsistent solutions, the critical timestep is a theoretical upper bound for valid timesteps.
- implicit method,
- bifurcation,
- initial-value problem,
- double pendulum
Citation: Kevin R. Green, George W. Patrick, Raymond J. Spiteri. On theoretical upper limits for valid timesteps of implicit ODE methods[J]. AIMS Mathematics, 2019, 4(6): 1841-1853. doi: 10.3934/math.2019.6.1841

Related Papers:

Abstract

Implicit methods for the numerical solution of initial-value problems may admit multiple solutions at any given time step. Accordingly, their nonlinear solvers may converge to any of these solutions. Below a critical timestep, exactly one of the solutions (the consistent solution) occurs on a solution branch (the principal branch) that can be continuously and monotonically continued back to zero timestep. Standard step-size control can promote convergence to consistent solutions by adjusting the timestep to maintain an error estimate below a given tolerance. However, simulations for symplectic systems or large physical systems are often run with constant timesteps and are thus more susceptible to convergence to inconsistent solutions. Because simulations cannot be reliably continued from inconsistent solutions, the critical timestep is a theoretical upper bound for valid timesteps.

References

[1]	S. Dharmaraja, Y. Wang, G. Strang, Optimal stability for trapezoidal-backward difference splitsteps, IMA J. Numer. Anal., 30 (2010), 141-148. doi: 10.1093/imanum/drp022
[2]	W. J. F. Govaerts, Numerical Methods for Bifurcations of Dynamical Equilibria, Society for Industrial and Applied Mathematics, 2000.
[3]	E. Hairer, C. Lubich, G. Wanner, Geometric numerical integration: Structure-preserving algorithms for ordinary differential equations, Springer-Verlag, 2006.
[4]	E. Hairer, S. P. Nørsett, G. Wanner, Solving ordinary differential equations I: Nonstiff problems., Springer-Verlag, 1993.
[5]	A. Stuart, A.R. Humphries, Dynamical Systems and Numerical Analysis, Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, 1998.
[6]	J. E. Marsden and M. West, Discrete Mechanics and Variational Integrators, Acta Numer., 10 (2001), 357-514. doi: 10.1017/S096249290100006X
[7]	G. W. Patrick, C. Cuell, Error analysis of variational integrators of unconstrained Lagrangian systems, Numer. Math., 113 (2009), 243-264. doi: 10.1007/s00211-009-0245-3
[8]	P. Deuflhard, B. Fiedler, P. Kunkel, Efficient Numerical Pathfollowing Beyond Critical Points, SIAM J. Numer. Anal., 24 (1987), 912-927. doi: 10.1137/0724059
[9]	U. M. Ascher, R. M. M. Mattheij, R. D. Russell, Numerical solution of boundary value problems for ordinary differential equations, Industrial and Applied Mathematics (SIAM), 1995.
[10]	C. B. Haselgrove, The Solution of Non-Linear Equations and of Differential Equations with TwoPoint Boundary Conditions, The Computer Journal, 4 (1961), 255-259. doi: 10.1093/comjnl/4.3.255
[11]	P. Deuflhard, Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms, Springer Publishing Company, 2011.
[12]	G. W. Patrick, C. Cuell, R. J. Spiteri, et al. On converting any one-step method to a variational integrator of the same order, ASME 2009 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 4 (2009), 341-349.
[13]	G. W. Patrick, Variational discretizations: discrete tangent bundles, local error analysis, and arbitrary order variational integrators, AIP Conference Proceedings, 1168 (2009), 1013-1016.
[14]	A. R. Humphries, Spurious solutions of numerical methods for initial value problems, IMA J. Numer. Anal., 13 (1993), 263-290. doi: 10.1093/imanum/13.2.263
[15]	A. Iserles, A. T. Peplow, A. M. Stuart, A unified approach to spurious solutions introduced by time discretisation. I: Basic theory, SIAM J. Numer. Anal., 28 (1991), 1723-1751. doi: 10.1137/0728086
[16]	R. Schreiber, H. B. Keller, Spurious solutions in driven cavity calculations, J. Comput. Phys., 49 (1983), 165-172. doi: 10.1016/0021-9991(83)90119-5
[17]	T. Murdoch, C. J. Budd, Convergent and spurious solutions of nonlinear elliptic equations, IMA J. Numer. Anal., 12 (1992), 365-386. doi: 10.1093/imanum/12.3.365
[18]	A. B. Stephens, G. R. Shubin, Multiple Solutions and Bifurcation of Finite Difference Approximations to Some Steady Problems of Fluid Dynamics, SIAM Journal on Scientific and Statistical Computing, 2 (1981), 404-415. doi: 10.1137/0902033
[19]	D. F. Griffiths, P. K. Sweby, H. C. Yee, On spurious asymptotic numerical solutions of explicit Runge-Kutta methods, IMA J. Numer. Anal., 12 (1992), 319-338. doi: 10.1093/imanum/12.3.319
[20]	E. Hairer, Variable time step integration with symplectic methods, Appl. Numer. Math., 25 (1997), 219-227. doi: 10.1016/S0168-9274(97)00061-5
[21]	S. Blanes, C. J. Budd, Adaptive Geometric Integrators for Hamiltonian Problems with Approximate Scale Invariance, SIAM Journal on Scientific Computing, 26 (2005), 1089-1113. doi: 10.1137/S1064827502416630
[22]	E. Hairer, G. Söderlind, Explicit, time reversible, adaptive step size control, SIAM J. Sci. Comput., 26 (2005), 1838-1851.
[23]	B. Leimkuhler, S. Reich, Simulating Hamiltonian Dynamics, Cambridge University Press, 2004.
[24]	M. Schatzman, Numerical analysis: A mathematical introduction, Clarendon Press, Oxford, 2002.
[25]	A. Iserles, A first course in the numerical analysis of differential equations, Cambridge University Press, Cambridge, 2009.
[26]	J. Guchenheimer and P. Holmes, Nonlinear oscillations, dynamical systems, and bifurcation of vector fields, Springer-Verlag, 1983.
[27]	Y. A. Kuznetsov, Elements of applied bifurcation theory, Springer-Verlag, 2004.
[28]	U. Kirchgraber, Multistep methods are essentially one-step methods, Numerische Mathematik, 48 (1986), 85-90. doi: 10.1007/BF01389443
[29]	J. C. Phillips, R. Braun, W. Wang, et al. Scalable molecular dynamics with NAMD, J. Comput. Chem., 26 (2005), 1781-1802. doi: 10.1002/jcc.20289
[30]	C. D. Cantwell, D. Moxey, A. Comerford, et al. Nektar plus plus: An open-source spectral/hp element framework, Comput. Phys. Commun., 192 (2015), 205-219. doi: 10.1016/j.cpc.2015.02.008
[31]	J. Pitt-Francis, M. O. Bernabeu, J. Cooper, et al. Chaste: using agile programming techniques to develop computational biology software, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366 (1878), 3111-3136.
[32]	J. Juno, A. Hakim, J. TenBarge, et al. Discontinuous Galerkin algorithms for fully kinetic plasmas, J. Comput. Phys., 353 (2018), 110-147. doi: 10.1016/j.jcp.2017.10.009
[33]	S. Reich, Backward error analysis for numerical integrators, SIAM J. Numer. Anal., 36 (1999), 1549-1570. doi: 10.1137/S0036142997329797

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)