mathematicsВестник российских университетов. МатематикаRussian Universities Reports. Mathematics2686-96672782-3342Тамбовский государственный университет имени Г.Р. Державина10.20310/2686-9667-2026-31-154-142-167mathematics-365Research ArticleНАУЧНЫЕ СТАТЬИORIGINAL ARTICLESУскорение сходимости кусочного метода Ньютона к особым решениям нелинейных уравненийAcceleration of convergence of the piecewise Newton method to singular solutions of nonlinear equationshttps://orcid.org/0000-0001-9851-0524ИзмаиловАлексей ФеридовичIzmailovAlexey F.

Измаилов Алексей Феридович, доктор физико-математических наук, профессор кафедры исследования операций    

119991, ГСП-2, г. Москва, Ленинские горы, 1

Alexey F. Izmailov, Doctor of Physical and Mathematical Sciences, Professor of the Operations Research Department    

1 Leninskiye Gory, Moscow 119991

izmaf@cs.msu.ruhttps://orcid.org/0009-0003-6425-0332ЯньЧжибайYanZhibai

Янь Чжибай, аспирант    

119991, ГСП-2, г. Москва, Ленинские горы, 1

Zhibai Yan, Post-Graduate Student    

1 Leninskiye Gory, Moscow 119991

yanzhibai@cs.msu.ruФГБОУ ВО «Московский государственный университет им. М. В. Ломоносова»РоссияLomonosov Moscow State UniversityRussian Federation20260607202631154142167Copyright © Измаилов А.Ф., Янь Ч., 20262026Измаилов А.Ф., Янь Ч.Izmailov A.F., Yan Z.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://mathematics.elpub.ru/jour/article/view/365

Статья посвящена способам ускорения сходимости вариантов метода Ньютона к особым решениям системы нелинейных уравнений. Для уравнений с гладкими отображениями литература, посвященная этим вопросам, весьма обширна. В частности, известно, что в естественных предположениях имеет место линейная сходимость базового метода Ньютона к особым решениям, с асимптотическим общим частным 1/2, из широких областей начальных точек. Используя специальный характер такой сходимости, ее можно в определенных смыслах ускорить за счет соответствующих модификаций базового метода Ньютона, а именно, процедур экстраполяции и оверрелаксации. Помимо обзора соответствующих теорий локальной сходимости, основные результаты работы состоят в распространении указанных алгоритмов и теорем об их локальной сходимости и скорости сходимости на кусочный метод Ньютона для уравнений с кусочно-гладким отображением. Важную роль при этом играют разработанные ранее конструкции, позволяющие охарактеризовать гладкие кусочные отображения, которые могут быть активными на итерациях методов. Статья также содержит результаты численного сравнения рассматриваемых способов ускорения кусочного метода Ньютона на кусочно-гладких переформулировках нелинейных комплементарных задач, включая некоторые иллюстративные примеры.

This paper is devoted to techniques intended for acceleration of convergence of the variants of the Newton method to singular solutions of systems of nonlinear equations. For equations with smooth mappings, there exists a rich literature on these issues. In particular, it is known that under natural assumptions, the rate of convergence of the basic Newton method to singular solutions is linear, with the asymptotic common ratio equal to 1/2, from wide domains of starting points. Making use of a special pattern of such convergence, it can be in some senses accelerated by introducing the corresponding modifications of the basic Newton method, namely, the extrapolation and overrelaxation procedures. Besides providing a survey of the related local convergence theories, the main results of the paper consist of extensions of the specified algorithms and their local convergence and rate-of-convergence theorems to the piecewise Newton method for equations with piecewise smooth mappings. The important role in this is played by previously developed constructions allowing to characterize smooth local selection mappings that can be active along the iterations of the method. The paper also contains the results of numerical comparison of the considered acceleration techniques for the piecewise Newton method for piecewise-smooth reformulations of nonlinear complementarity problems, including some illustrative examples.

нелинейное уравнениекусочно-гладкое уравнениекусочный метод Ньютоналинейная сходимостьсверхлинейная сходимостьэкстраполяцияоверрелаксацияускорение Андерсонаnonlinear equationpiecewise smooth equationpiecewise Newton methodlinear convergencesuperlinear convergenceextrapolationoverrelaxationAnderson accelerationReferencesA. Griewank, “On solving nonlinear equations with simple singularities or nearly singular solutions”, SIAM Rev., 27 (1985), 537–563.A. Griewank, “On solving nonlinear equations with simple singularities or nearly singular solutions”, SIAM Rev., 27 (1985), 537–563.D. G. Anderson, “Iterative procedures for nonlinear integral equations”, J. Assoc. Comput. Mach., 12:4 (1965), 547–560.D. G. Anderson, “Iterative procedures for nonlinear integral equations”, J. Assoc. Comput. Mach., 12:4 (1965), 547–560.M. Dallas, S. Pollock, “Newton–Anderson at singular points”, Int. J. Numer. Anal. Mod., 20:5 (2023), 667–692.M. Dallas, S. Pollock, “Newton–Anderson at singular points”, Int. J. Numer. Anal. Mod., 20:5 (2023), 667–692.A. Fischer, A. F. Izmailov, M. Jelitte, “Newton-type methods near critical solutions of piecewise smooth nonlinear equations”, Comput. Optim. Appl., 80 (2021), 587–615.A. Fischer, A. F. Izmailov, M. Jelitte, “Newton-type methods near critical solutions of piecewise smooth nonlinear equations”, Comput. Optim. Appl., 80 (2021), 587–615.A. F. Izmailov, M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer, Cham, 2014.A. F. Izmailov, M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer, Cham, 2014.A. Griewank, “Starlike domains of convergence for Newton’s method at singularities”, Numer. Math., 35 (1980), 95–111.A. Griewank, “Starlike domains of convergence for Newton’s method at singularities”, Numer. Math., 35 (1980), 95–111.A. F. Izmailov, M. V. Solodov, “A general perturbed Newtonian framework and critical solutions of nonlinear equations”, Set-Valued Var. Anal., 33:1 (2025), art. no. 3.A. F. Izmailov, M. V. Solodov, “A general perturbed Newtonian framework and critical solutions of nonlinear equations”, Set-Valued Var. Anal., 33:1 (2025), art. no. 3.A. Fischer, A. F. Izmailov, M. V. Solodov, “Unit stepsize for the Newton method close to critical solutions”, Math. Program., 187 (2021), 697–721.A. Fischer, A. F. Izmailov, M. V. Solodov, “Unit stepsize for the Newton method close to critical solutions”, Math. Program., 187 (2021), 697–721.A. F. Izmailov, A. S. Kurennoy, M. V. Solodov, “Critical solutions of nonlinear equations: local attraction for Newton-type methods”, Math. Program., 167 (2018), 335–379.A. F. Izmailov, A. S. Kurennoy, M. V. Solodov, “Critical solutions of nonlinear equations: local attraction for Newton-type methods”, Math. Program., 167 (2018), 335–379.D. W. Decker, H. B. Keller, C. T. Kelley, “Convergence rates for Newton’s method at singular points”, SIAM J. Numer. Anal., 20 (1983), 296–314.D. W. Decker, H. B. Keller, C. T. Kelley, “Convergence rates for Newton’s method at singular points”, SIAM J. Numer. Anal., 20 (1983), 296–314.A. Griewank, Analysis and Modification of Newton’s Method at Singularities, PhD Thesis, Australian National University, Canberra, 1980.A. Griewank, Analysis and Modification of Newton’s Method at Singularities, PhD Thesis, Australian National University, Canberra, 1980.Дж. Ортега, В. Рейнболдт, Итерационные методы решения нелинейных систем уравнений co многими неизвестными, Мир, М., 1975; англ. ориг.J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, London, 1970.C. T. Kelley, R. Suresh, “A new acceleration method for Newton’s method at singular points”, SIAM J. Numer. Anal., 20 (1983), 1001–1009.C. T. Kelley, R. Suresh, “A new acceleration method for Newton’s method at singular points”, SIAM J. Numer. Anal., 20 (1983), 1001–1009.H.-D. Ebbinghaus, H. Hermes, F. Hirzebruch, M. Koecher, K. Mainzer, J. Neukirch, A. Prestel, R. Remmert, Numbers, Springer, New York, 1991.H.-D. Ebbinghaus, H. Hermes, F. Hirzebruch, M. Koecher, K. Mainzer, J. Neukirch, A. Prestel, R. Remmert, Numbers, Springer, New York, 1991.S. Pollock, L. G. Rebholtz, “Anderson acceleration for contractive and noncontractive operators”, IMA J. Numer. Anal., 41 (2021), 2841–2872.S. Pollock, L. G. Rebholtz, “Anderson acceleration for contractive and noncontractive operators”, IMA J. Numer. Anal., 41 (2021), 2841–2872.M. Dallas, S. Pollock, L. G. Rebholtz, “Analysis of an adaptive safeguarded Newton–Anderson algorithm of depth one with applications to fluid problems”, J. Adv. Comp. Sci. Eng., 2:3 (2024), 246–270.M. Dallas, S. Pollock, L. G. Rebholtz, “Analysis of an adaptive safeguarded Newton–Anderson algorithm of depth one with applications to fluid problems”, J. Adv. Comp. Sci. Eng., 2:3 (2024), 246–270.L. G. Rebholtz, M. Xiao, “The effect of Anderson acceleration on superlinear and sublinear convergence”, J. Adv. Comp. Sci. Eng., 96 (2023), art. no. 34.L. G. Rebholtz, M. Xiao, “The effect of Anderson acceleration on superlinear and sublinear convergence”, J. Adv. Comp. Sci. Eng., 96 (2023), art. no. 34.M. Dallas, “Anderson acceleration for perturbed Newton methods”, 2025 arXiv:2508.12513.M. Dallas, “Anderson acceleration for perturbed Newton methods”, 2025 arXiv:2508.12513.S. Pollock, “Fast convergence to higher multiplicity zeros”, 2019 arXiv:1911.10647.S. Pollock, “Fast convergence to higher multiplicity zeros”, 2019 arXiv:1911.10647.S. Pollock, H. Schwartz, “Benchmarking results for the Newton-Anderson method”, Res. Appl. Math., 8 (2020), art. no. 100095.S. Pollock, H. Schwartz, “Benchmarking results for the Newton-Anderson method”, Res. Appl. Math., 8 (2020), art. no. 100095.F. Facchinei, J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.F. Facchinei, J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.C. Oberlin, S. J. Wright, “An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems”, Math. Program., 117 (2009), 355–386.C. Oberlin, S. J. Wright, “An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems”, Math. Program., 117 (2009), 355–386.A. Izmailov, E. Uskov, Z. Yan, “Newton method vs. semismooth Newton method for singular solutions of nonlinear complementarity problems”, Adv. Syst. Sci. Appl., 23 (2023), 16–26.A. Izmailov, E. Uskov, Z. Yan, “Newton method vs. semismooth Newton method for singular solutions of nonlinear complementarity problems”, Adv. Syst. Sci. Appl., 23 (2023), 16–26.A. F. Izmailov, A. V. Arutyunov, “Stability of possibly nonisolated solutions of constrained equations with applications to complementarity and equilibrium problems”, Set-Valued Var. Anal., 26 (2018), 327–352.A. F. Izmailov, A. V. Arutyunov, “Stability of possibly nonisolated solutions of constrained equations with applications to complementarity and equilibrium problems”, Set-Valued Var. Anal., 26 (2018), 327–352.А. Н. Дарьина, А. Ф. Измаилов, “Об идентификации активных индексов в смешанных комплементарных задачах”, Вопросы моделирования и анализа в задачах принятия решений, ВЦ РАН, М., 2004, 72–87.A. N. Daryina, A. F. Izmailov, “On the identification of active indices in mixed complementary problems”, Modeling and analysis issues in decision making problems, Computing Center of the Russian Academy of Sciences, Moscow, 2004, 72–87 (In Russian).A. F. Izmailov, M. V. Solodov, “Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications”, Math. Program., 89 (2001), 413–435.A. F. Izmailov, M. V. Solodov, “Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications”, Math. Program., 89 (2001), 413–435.

The authors declare that there are no conflicts of interest present.