Русская версия
ISSN 1817-2172, рег. Эл. № ФС77-39410, ВАК

Differential Equations and Control Processes
(Differencialnie Uravnenia i Protsesy Upravlenia)

About History Editorial Page Addresses Scope Editorial Staff Submission Review For Authors Publication Ethics Issues Русская версия

Application of the Modified Runge-Kutta Method to the Construction of the Descent Method for Solving Boundary Value Problems

Author(s):

Gerasim Vladimirovich Krivovichev

Doctor of Physical and Mathematical Sciences, Professor of Faculty of Applied Mathematics and Control Processes,
St. Petersburg State University (St. Petersburg State University)

g.krivovichev@spbu.ru

Nikolay Vasil'evich Egorov

Doctor of Physical and Mathematical Sciences, Professor of Faculty of Applied Mathematics and Control Processes,
St. Petersburg State University (St. Petersburg State University)

n.v.egorov@spbu.ru

Abstract:

The work is devoted to the construction and analysis of the gradient method based on a modified explicit second-order Runge--Kutta method, constructed using the Lagrange--Burmann expansion. A two-step method with inertia based on the heavy ball method is proposed. Convergence theorems are proven for strongly convex quadratic and perturbed quadratic functions. Analytical expressions for the optimal parameters of the method are obtained. For the quadratic function it is demonstrated, that the proposed method converges faster, than other well-known accelerated methods. The results of the application of the method to the numerical solution of linear and nonlinear boundary value problems (Dirichlet problem for a 3D Poisson equation, problems from the calculus of variations, problems for integro-differential equations) are presented. It is demonstrated that, in comparison with well-known methods, the proposed method allows one to obtain a numerical solution with the required accuracy for different grid resolutions in a smaller number of iterations and time.

Keywords

References:

  1. Ascher U. M., van den Doel K., Huang H., Svaiter B. F. Gradient descent and fast artificial time integration. ESAIM: M2AN, 2009; (43): 689-708
  2. Porta F., Cornelio A., Ruggiero V. Runge-Kutta-like scaling techniques for first-order methods in convex optimization. Applied Numerical Mathematics, 2017; (116): 256-272
  3. Eftekhari A., Vandereycken B., Vilmart G., Zygalakis K. C. Explicit stabilised gradient descent for faster strongly convex optimisation. BIT Numerical Mathematics, 2021; (61): 119-139
  4. Stillfjord T., Williamson M. SRKCD: A stabilized Runge-Kutta method for stochastic optimization. Journal of Computational and Applied Mathematics, 2023; (417): 114575
  5. Zhang J., Mokhtari A., Sra S., Jadbabaie A. Direct Runge-Kutta discretisation achieves acceleration. NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Montreal, 2018, pp. 3904-3913
  6. Zhang J., Sra S., Jadbabaie A. Acceleration in first order quasi-strongly convex optimization by ode discretization. 2019 IEEE 58th Conference on Decision and Control (CDC), Nice, 2019, pp. 1501-1506
  7. Shi B., Du S. S., Jordan M. I., Su W. J. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, 2022; (195): 79-148
  8. Luo H., Chen L. From differential equation solvers to accelerated first-order methods for convex optimization. Mathematical Programming, 2022; (195): 735-781
  9. Duruisseaux V., Leok M. Practical perspectives on symplectic accelerated optimization. Optimization Methods and Software, 2023; (38): 1230-1268
  10. Chen R., Li X. Implicit Runge-Kutta methods for accelerated unconstrained convex optimization. IEEE Access, 2020; (8): 28624-28634
  11. Areias P., Rabczuk T. An engineering interpretation of Nesterov’s convex minimization algorithm and time integration: application to optimal fiber orientation. Computational Mechanics, 2021; (68): 211-227
  12. Al’ber S., Al’ber Y. A method of differential descent for solving non-linear systems. USSR Computational Mathematics and Mathematical Physics, 1967; (7), no. 1: 15-40
  13. Abbott J. P., Brent R. P. Fast local convergence with single and multistep methods for nonlinear equations. The Journal of the Australian Mathematical Society. Series B. Applied Mathematics, 1977; (20): 173-199
  14. Brown A. A., Bartholomew-Biggs M. C. Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations. Journal of Optimization Theory and Applications, 1989; (62): 211-224
  15. Khiyabani F. M., Leong W. J. Quasi-Newton methods based on ordinary differential equation approach for unconstrained nonlinear optimization. Applied Mathematics and Computation, 2014; (233): 272-291
  16. Su W., Boyd S., Candes E. J. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 2016; (17), no. 53: 1-43
  17. Shi B., Du S. S., Su W., Jordan M. I. Acceleration via symplectic discretization of high-resolution differential equations. NIPS'19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, Vancouver, 2019, pp. 5744-5752
  18. Chan R. P. K., Tsai A. Y. J. On explicit two-derivative Runge-Kutta methods. Numerical Algorithms, 2010; (53): 171-194
  19. Turaci M. O., Ozis T. Derivation of three-derivative Runge-Kutta methods. Numerical Algorithms, 2016; (74): 247-265
  20. Qin X., Yu J., Yan C. Derivation of three-derivative two-step Runge-Kutta methods. Mathematics, 2024; (12): 711
  21. Dang Q. A., Hoang M. T. Positive and elementary stable explicit nonstandard Runge-Kutta methods for a class of autonomous dynamical systems. International Journal of Computer Mathematics, 2020; (97): 2036-2054
  22. Arushanyan O. B., Zaletkin S. F. Approximate solution of the Cauchy problem for ordinary differential equations by the method of Chebyshev series. Vychislitel’nye metody i programmirovanie, 2016; (17), № 2: 121-131. (In Russ. )
  23. Vorozhtsov E. V. Derivation of explicit difference schemes for ordinary differential equations with the aid of Lagrange-Burmann expansions. Vychislitel’nye metody i programmirovanie, 2010; (11), № 2: 198-209. (In Russ. )
  24. Vorozhtsov E. V. Derivation of explicit difference schemes for ordinary differential equations with the aid of Lagrange-Burmann expansions. Lecture Notes in Computer Science, 2010; (6244): 250-266
  25. Vorozhtsov E. V. Application of Lagrange-Burmann expansions for the numerical integration of the inviscid gas equations. Vychislitel’nye metody i programmirovanie, 2011; (12), № 3: 348-361. (In Russ. )
  26. Vorozhtsov E. V. Construction of third-order schemes using Lagrange-Burmann expansions for the numerical integration of inviscid gas equations. Vychislitel’nye metody i programmirovanie, 2016; (17), № 1: 21-43. (In Russ. )
  27. Jerez S. Non-standard Lagrange-Burman methods for the numerical integration of differential equations. Journal of Difference Equations and Applications, 2012; (18): 1899-1912
  28. Polyak B. T. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 1964; (4), no. 5: 1-17
  29. Abramowitz M., Stegun I. A. Handbook of Mathematical Functions. Martino Fine Books, 2014. 1060 p
  30. Bakhvalov N. S., Zhidkov N. P., Kobel’kov G. M. Chislennye metody [Numerical methods]. Moscow, Laboratoriia znanii Publ., 2020. 636 p
  31. Gantmacher F. F. Teoriya matrits[Theory of matrices]. Moscow, FIZMATLIT, 2010. 560 p
  32. Polyak B. T. Introduction to Optimization. Optimization Software Inc., 1987. 264 p
  33. Nesterov Y. E. Introductory Lectures on Convex Optimization: a Basic Course. Springer, 2004. 236 p
  34. Lessard L., Recht B., Packard A. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 2016; (26), 57-95
  35. Samarskii A. A., Nikolaev E. S. Metody resheniia setochnyh uravnenii [Methods of solution of grid equations]. Moscow, Nauka Publ., 1978. 595 p
  36. Nikolaev E. S. Metody resheniia setochnyh uravnenii [Methods of solution of grid equations]. Moscow, MSU Publ., 2023. 404 p
  37. Ortega M., Poole W. J. An Introduction to Numerical Methods for Differential Equations. Pitman Publishing Inc., 1981. 329 p
  38. Samarskii A. A., Gulin A. V. Ustoichivost’ raznostnyh shem [Stability of difference schemes]. Moscow, Nauka Publ., 1973. 415 p
  39. Elsholtz L. E. Variatsionnoe ischislenie[Calculus of Variations]. Moscow, URSS, 2023. 208 p
  40. Vasudeva M. A., Verwer J. Solving parabolic integro-differential equations by an explicit integration method. Journal of Computational and Applied Mathematics, 1992; (39): 121-132

Full text (pdf)