Ускорение сходимости кусочного метода Ньютона к особым решениям нелинейных уравнений

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

1. A. Griewank, “On solving nonlinear equations with simple singularities or nearly singular solutions”, SIAM Rev., 27 (1985), 537–563.

2. D. G. Anderson, “Iterative procedures for nonlinear integral equations”, J. Assoc. Comput. Mach., 12:4 (1965), 547–560.

3. M. Dallas, S. Pollock, “Newton–Anderson at singular points”, Int. J. Numer. Anal. Mod., 20:5 (2023), 667–692.

4. 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.

5. 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.

6. A. Griewank, “Starlike domains of convergence for Newton’s method at singularities”, Numer. Math., 35 (1980), 95–111.

7. 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.

8. A. Fischer, A. F. Izmailov, M. V. Solodov, “Unit stepsize for the Newton method close to critical solutions”, Math. Program., 187 (2021), 697–721.

9. 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.

10. 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.

11. A. Griewank, Analysis and Modification of Newton’s Method at Singularities, PhD Thesis, Australian National University, Canberra, 1980.

12. Дж. Ортега, В. Рейнболдт, Итерационные методы решения нелинейных систем уравнений co многими неизвестными, Мир, М., 1975; англ. ориг.

13. C. T. Kelley, R. Suresh, “A new acceleration method for Newton’s method at singular points”, SIAM J. Numer. Anal., 20 (1983), 1001–1009.

14. H.-D. Ebbinghaus, H. Hermes, F. Hirzebruch, M. Koecher, K. Mainzer, J. Neukirch, A. Prestel, R. Remmert, Numbers, Springer, New York, 1991.

15. S. Pollock, L. G. Rebholtz, “Anderson acceleration for contractive and noncontractive operators”, IMA J. Numer. Anal., 41 (2021), 2841–2872.

16. 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.

17. 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.

18. M. Dallas, “Anderson acceleration for perturbed Newton methods”, 2025 arXiv:2508.12513.

19. S. Pollock, “Fast convergence to higher multiplicity zeros”, 2019 arXiv:1911.10647.

20. S. Pollock, H. Schwartz, “Benchmarking results for the Newton-Anderson method”, Res. Appl. Math., 8 (2020), art. no. 100095.

21. F. Facchinei, J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.

22. C. Oberlin, S. J. Wright, “An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems”, Math. Program., 117 (2009), 355–386.

23. 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.

24. 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.

25. А. Н. Дарьина, А. Ф. Измаилов, “Об идентификации активных индексов в смешанных комплементарных задачах”, Вопросы моделирования и анализа в задачах принятия решений, ВЦ РАН, М., 2004, 72–87.

26. A. F. Izmailov, M. V. Solodov, “Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications”, Math. Program., 89 (2001), 413–435.