English version
ISSN 1817-2172, рег. Эл. № ФС77-39410, ВАК

Дифференциальные Уравнения
и
Процессы Управления

О журнале История Журнала Издатель Адреса Тематика Редакторский состав Рецензирование Для авторов Издательская этика Коллекция номеров English version

Применение модифицированного метода Рунге-Кутты к построению метода спуска для решения краевых задач

Автор(ы):

Герасим Владимирович Кривовичев

д. ф.-м. н., профессор кафедры моделирования электромеханических и компьютерных систем факультета Прикладной математики - процессов управления Санкт-Петербургского государственного университета (СПбГУ)

g.krivovichev@spbu.ru

Николай Васильевич Егоров

д.ф-м.н., профессор, заведующий кафедрой моделирования электромеханических и компьютерных систем факультета Прикладной математики - процессов управления Санкт-Петербургского государственного университета (СПбГУ)

n.v.egorov@spbu.ru

Аннотация:

Работа посвящена построению и анализу градиентного метода, основанного на модифицированном явном методе Рунге-Кутты второго порядка, построенном с использованием разложения Лагранжа --- Бюрмана. Предложен двухшаговый метод с инерцией, основанный на методе тяжелого шарика. Доказаны теоремы о сходимости для сильно выпуклой квадратичной и возмущенной квадратичной функции. Получены аналитические выражения для параметров метода, обеспечивающие оптимальную скорость сходимости. В случае квадратичной функции показано, что предложенный метод сходится быстрее, чем другие ускоренные методы. Представлены результаты применения метода к численному решению линейных и нелинейных краевых задач: задачи Дирихле для трехмерного уравнения Пуассона, задачи вариационного исчисления, задач для интегро-дифференциальных уравнений. Показано, что по сравнению с известными методами, предложенный метод позволяет получать численное решение с нужной точностью при разных разбиениях сетки за меньшее число итераций и время.

Ключевые слова

Ссылки:

  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. Альбер С. И., Альбер Я. И. Применение метода дифференциального спуска для решения нелинейных систем. Журнал вычислительной математики и математической физики, 1967; (68), № 1: 14-32
  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. Арушанян О. Б., Залеткин С. Ф. Приближенное решение задачи Коши для обыкновенных дифференциальных уравнений методом рядов Чебышeва. Вычислительные методы и программирование, 2016; (17), № 2: 121-131. \
  23. Ворожцов Е. В. Построение явных разностных схем для обыкновенных дифференциальных уравнений с помощью разложений Лагранжа - Бюрмана. Вычислительные методы и программирование, 2010; (11), № 2: 198-209
  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. Ворожцов Е. В. Применение разложений Лагранжа - Бюрмана для численного интегрирования уравнений невязкого газа. Вычислительные методы и программирование, 2011; (12), № 3: 348-361
  26. Ворожцов Е. В. Конструирование схем третьего порядка точности с помощью разложений Лагранжа - Бюрмана для численного интегрирование уравнений невязкого газа. Вычислительные методы и программирование, 2016; (17), № 1: 21-43
  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. Поляк Б. Т. О некоторых способах ускорения сходимости итерационных методов. Журнал вычислительной математики и математической физики, 1964; (4), № 5: 791-803
  29. Абрамовиц М., Стиган И. Справочник по специальным функциям. М. : Наука, 1979. 832 с
  30. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М. : Лаборатория знаний, 2020. 636 с
  31. Гантмахер Ф. Р. Теория матриц. М. : ФИЗМАТЛИТ, 2010. 560 с
  32. Поляк Б. Т. Введение в оптимизацию. М. : Наука, 1983. 384 с
  33. Нестеров Ю. Е. Введение в выпуклую оптимизацию. М. : МЦНМО, 2010. 280 с
  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. Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений. М. : Наука, 1978. 592 с
  36. Николаев Е. С. Методы решения сеточных уравнений. М. : Изд-во МГУ, 2023. 404 с
  37. Ортега Д., Пул У. Введение в численные методы решения дифференциальных уравнений. М. : Наука, 1986. 288 с
  38. Самарский А. А., Гулин А. В. Устойчивость разностных схем. М. : Наука, 1973. 415 с
  39. Эльсгольц Л. Э. Вариационное исчисление. М. : УРСС, 2023. 208 с
  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

Полный текст (pdf)