Derivative-free discrete gradient methods

Håkon Noren Myhr; Sølve Eidnes

doi:10.3934/jcd.2024004

Article Contents

2024, Volume 11, Issue 3: 256-273. Doi: 10.3934/jcd.2024004

This issue Previous Article Next Article Remarks on solitary waves in equations with nonlocal cubic terms

Derivative-free discrete gradient methods

Håkon Noren Myhr^1, , and
Sølve Eidnes^2,

1.
Department of Mathematical Sciences, Norwegian University of Science and Technology, Trondheim, Norway
2.
Department of Mathematics and Cybernetics, SINTEF Digital, 0373 Oslo, Norway

^*Corresponding author: Håkon Noren Myhr
^*Corresponding author: Håkon Noren Myhr

Received: August 2023

Revised: January 2024

Early access: January 29, 2024

Published online: January 29, 2024

The research was supported by the Research Council of Norway, through the projects DynNoise (No. 339389) and PhysML (No. 338779).

Abstract / Introduction Full Text(HTML) Figure(7) / Table(1) Related Papers Cited by

Abstract

Discrete gradient methods are a class of numerical integrators producing solutions with exact preservation of first integrals of ordinary differential equations. In this paper, we apply order theory combined with the symmetrized Itoh–Abe discrete gradient and finite differences to construct an integral-preserving fourth-order method that is derivative-free. The numerical scheme is implicit and a convergence result for Newton's iterations is provided, taking into account how the error due to the finite difference approximations affects the convergence rate. Numerical experiments verify the order and show that the derivative-free method is significantly faster than obtaining derivatives by automatic differentiation. Finally, an experiment using topographic data as the potential function of a Hamiltonian oscillator demonstrates how this method allows the simulation of discrete-time dynamics from a Hamiltonian that is a combination of data and analytical expressions.

Keywords:

Mathematics Subject Classification: Primary: 65L99; Secondary: 65L12.

Citation:

Full Text(HTML)

Figure 1. Numerical and theoretical convergence of $ S_{\tau} $, $ F_{\tau} $ and $ F'_{\tau} $ when the stepsize in time $ h $ decreases. Dotted lines represent the theoretical convergence rates (Lemma 3.1 and Theorem 4.1) and the solid lines the numerical results

Download: Full-size image PowerPoint slide

Figure 2. Error results for the double pendulum (left column) and the Lennard–Jones oscillator (right column). The top row shows the global error at end time, $ \|x_N - x(T)\|_2 $, plotted against the stepsize $ h $. The bottom row shows the $ L_2 $ error over time, $ \|x_n - x(t_n)\|_2 $, where the smallest stepsize was used. Dashed lines display the derivative-free (DF) methods. The gray dotted lines represent order $ h^1 $, $ h^2 $ and $ h^4 $ respectively

Download: Full-size image PowerPoint slide

Figure 3. Energy error for the double pendulum (left) and the Lennard–Jones oscillator (right) plotted over time where the smallest stepsize was used. Dashed lines represent the derivative-free (DF) methods

Download: Full-size image PowerPoint slide

Figure 4. Numbers of evaluations of $ H(x) $ for the double pendulum (left) and the Lennard–Jones oscillator (right) over multiple experiments with decreasing stepsize in time $ h $

Download: Full-size image PowerPoint slide

Figure 5. Work-precision diagrams where the $ L_2 $ (top row) and energy error (bottom row) is plotted against computational time for the double pendulum (left column) and the Lennard–Jones oscillator (right column) over multiple experiments with decreasing stepsize in time $ h $. Dashed lines display the derivative-free (DF) methods

Download: Full-size image PowerPoint slide

Figure 6. The total potential $ U(q) $ (upper left) and the trajectory of the topographic Hamiltonian $ q_n \approx q(t_n) $ in discrete time for $ t_n \leq t_N $ with $ t_N = 20, 200, 1000 $ from the upper to the lower right quadrant. $ \partial D(H_0) $ is the level set of the initial energy $ H(q_0, p_0) $. The color in the heatmap corresponds to the value of the total potential $ U(q) $

Download: Full-size image PowerPoint slide

Figure 7. Energy drift of the topographic Hamiltonian in discrete time

Download: Full-size image PowerPoint slide

Table 1. Numbers of evaluations of $ H(x) $ for the different derivative-free methods

Method	Order	$ \overline \nabla H $	$ D_2^{\tau} \overline \nabla H $	$ S^{\tau} $	Total
IA	$ 1 $	$ 2n $	$ 2(n^2 + n) $	$ 0 $	$ 2n^2 +4n $
SIA	$ 2 $	$ 4n $	$ 4(n^2 + n) $	$ 0 $	$ 4n^2 + 8n $
SIA $ 4 $	$ 4 $	$ 4n $	$ 4(n^2 + n) $	$ 9n^2 -5n + 1 $	$ 13n^2 + 3n + 1 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Celledoni, R. I. McLachlan, D. I. McLaren, B. Owren, G. R. W. Quispel and W. M. Wright, Energy-preserving Runge-Kutta methods, ESAIM: Mathematical Modelling and Numerical Analysis, 43 (2009), 645-649. doi: 10.1051/m2an/2009020.
[2]	G. J. Cooper, Stability of Runge-Kutta methods for trajectory problems, IMA Journal of Numerical Analysis, 7 (1987), 1-13. doi: 10.1093/imanum/7.1.1.
[3]	J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Classics Appl. Math., 16, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. doi: 10.1137/1.9781611971200.
[4]	S. Eidnes, Order theory for discrete gradient methods, BIT Numerical Mathematics, 62 (2022), 1207-1255. doi: 10.1007/s10543-022-00909-z.
[5]	O. Gonzalez, Time integration and discrete Hamiltonian systems, Journal of Nonlinear Science, 6 (1996), 449-467. doi: 10.1007/BF02440162.
[6]	S. Greydanus, M. Dzamba and J. Yosinski, Hamiltonian neural networks, Advances in neural information processing systems, 32 (2019).
[7]	E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration, second ed., Springer Series in Computational Mathematics, vol. 31, Springer-Verlag, Berlin, 2006, Structure-preserving algorithms for ordinary differential equations.
[8]	E. Hairer, S. P. Nørsett and G. Wanner, Solving ordinary differential equations I nonstiff problems, second ed., Springer, Berlin, 2000.
[9]	A. Harten, P. D. Lax and B. Van Leer, On Upstream Differencing and Godunov-Type Schemes for Hyperbolic Conservation Laws, SIAM Review, 25 (1983), 35-61, Publisher: Society for Industrial and Applied Mathematics. doi: 10.1137/1025002.
[10]	T. Itoh and K. Abe, Hamiltonian-conserving discrete canonical equations based on variational difference quotients, Journal of Computational Physics, 76 (1988), 85-102. doi: 10.1016/0021-9991(88)90132-5.
[11]	J. K. Johnson, J. A. Zollweg and K. E. Gubbins, The Lennard-Jones equation of state revisited, Molecular Physics, 78 (1993), 591-618, Publisher: Taylor & Francis. doi: 10.1080/00268979300100411.
[12]	C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, Society for Industrial and Applied Mathematics, 1995. doi: 10.1137/1.9781611970944.
[13]	B. Leimkuhler and S. Reich, Simulating Hamiltonian Dynamics, Cambridge Monogr. Appl. Comput. Math., 14, Cambridge University Press, Cambridge, 2004.
[14]	G. McGregor and A. T. S. Wan,, Conservative hamiltonian monte carlo.
[15]	D. I. McLaren and G. R. W. Quispel, Integral-preserving integrators, J. Phys. A, 37 (2004), L489-L495. doi: 10.1088/0305-4470/37/39/L01.
[16]	R. I McLachlan, G. R. W. Quispel and N. Robidoux, Geometric integration using discrete gradients, Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 357 (1999), 1021-1045. doi: 10.1098/rsta.1999.0363.
[17]	Y. Miyatake, T. Sogabe and S.-L. Zhang, On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems, Journal of Computational and Applied Mathematics, 342 (2018), 58-69. doi: 10.1016/j.cam.2018.04.013.
[18]	P. H. Muir, Optimal discrete and continuous mono-implicit Runge-Kutta schemes for BVODEs, Advances in Computational Mathematics, 10 (1999), 135-167. doi: 10.1023/A:1018926631734.
[19]	R. M. Neal, MCMC using Hamiltonian dynamics, Handbook of Markov chain Monte Carlo, Chapman & amp; Hall/CRC Handb. Mod. Stat. Methods CRC Press, Boca Raton, FL, (2011), 113–162.
[20]	G. R. W. Quispel and D. I. McLaren, A new class of energy-preserving numerical integration methods, J. Phys. A, 41 (2008), 045206, 7pp. doi: 10.1088/1751-8113/41/4/045206.
[21]	L. F. Shampine, Conservation laws and the numerical solution of ODEs, Computers & Mathematics with Applications, 12 (1986), Part 2, 1287-1296.
[22]	H.-J. M. Shi, M. Q. Xuan, F. Oztoprak and J. Nocedal, On the numerical performance of derivative-free optimization methods based on finite-difference approximations, Optim. Methods Softw., 38 (2023), 289–311. doi: 10.1080/10556788.2022.2121832.
[23]	L. Uieda, D. Tian, W. J. Leong, W. Schlitzer, M. Grund, M. Jones, Y. Fröhlich, L. Toney, J. Yao, Y. Magen, T. Jing-Hui, K. Materna, A. Belem, T. Newton, A. Anant, M. Ziebarth, J. Quinn and P. Wessel, PyGMT: A Python interface for the Generic Mapping Tools, March 2023.
[24]	P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt and SciPy 1.0 Contributors, SciPy 1.0: Fundamental algorithms for scientific computing in Python, Nature Methods, 17 (2020), 261-272. doi: 10.1038/s41592-019-0686-2.
[25]	P. Wessel, J. F. Luis, L. Uieda, R. Scharroo, F. Wobbe, W. H. F. Smith and D. Tian, The generic mapping tools version 6, Geochemistry, Geophysics, Geosystems, 20 (2019), 5556-5564. doi: 10.1029/2019GC008515.