Anderson acceleration for perturbed Newton methods

Matt Dallas

doi:10.3934/acse.2025024

Article Contents

December 2025, Volume 6, 57-75. Doi: 10.3934/acse.2025024

This volume Previous Article Octree-based adaptive mesh refinement and the shifted boundary method for efficient fluid dynamics simulations Next Article A parameter-driven physics-informed neural network framework for solving two-parameter singular perturbation problems involving boundary layers

Anderson acceleration for perturbed Newton methods

Matt Dallas^1, ,

1.
University of Dallas, USA

^*Corresponding author: Matt Dallas
^*Corresponding author: Matt Dallas

Received: August 2025

Revised: November 2025

Published online: November 28, 2025

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

Abstract

We present a convergence theory for Anderson acceleration (AA) applied to perturbed Newton methods (pNMs) for computing roots of nonlinear problems. Two important special cases are the classical Newton method and the Levenberg-Marquardt method. We prove that if a problem is 2-regular, then Anderson accelerated pNMs coupled with a safeguarding scheme, known as $ \gamma $-safeguarding, converge locally linearly in a starlike domain of convergence, but with an improved rate of convergence compared to standard perturbed Newton methods. Since Levenberg-Marquardt methods are a special case of pNMs, we obtain a novel acceleration and local convergence result for Anderson accelerated Levenberg-Marquardt. We further show that $ \gamma $-safeguarding can detect if the underlying perturbed Newton method is converging superlinearly, and respond by tuning the Anderson step down. We demonstrate the methods on several benchmark problems in the literature.

Keywords:

Mathematics Subject Classification: Primary: 65J15; Secondary: 65B99.

Citation:

FullText(HTML)

Figure 1. Channel flow domain and boundaries. The red vertical segment is $ \Gamma_{\text{in}} $, the blue is $ \Gamma_{\text{out}} $, and the remaining boundaries, in black, are $ \Gamma_{\text{wall}} $.

Download: Full-size image PowerPoint slide

Figure 2. Stable velocity solutions for different values of $ \mu $. The top and bottom figures are stable solutions when $ \mu = 0.9 $. When $ \mu = 1 $, the middle solution is stable.

Download: Full-size image PowerPoint slide

Figure 3. Residual history for channel flow problem with $ \mu = 0.98 $. Left: results for Newton and Newton–Anderson with algorithmic depths $ m = 1 $, 2, 5, and 10. Right: results for $ \gamma $-safeguarded Newton–Anderson applied asymptotically plotted with dash-dotted lines. We set $ r = 0 $ in Algorithm 4.

Download: Full-size image PowerPoint slide

Figure 4. Residual history for channel flow problem with $ \mu = 0.94 $. Left: results for Newton and Newton–Anderson with algorithmic depths $ m = 1 $, 2, 5, and 10. Right: results for $ \gamma $-safeguarded Newton–Anderson applied asymptotically plotted with dash-dotted lines. We set $ r = 0 $ in Algorithm 4.

Download: Full-size image PowerPoint slide

Figure 5. Left: Residual history for test function Beh1. Right: Residual history for test function Beh2. Dash-dotted lines correspond to AALM with $ \gamma $-safeguarding. Note that $ \gamma $AALM(1, 0.9) and $ \gamma $AALM(5, 0.9) coincide in each of these experiments.

Download: Full-size image PowerPoint slide

Figure 6. Residual history for test function Beh3. Dash-dotted lines correspond to $ \gamma $-safeguarded AALM. As in Figure 5, $ \gamma $AALM(1, 0.9) and $ \gamma $AALM(5, 0.9) coincide. $ \gamma $AALM(5, 0.9) is therefore omitted.

Download: Full-size image PowerPoint slide

Figure 7. Left: Residual history for test function Beh4 with the LM parameter $ \mu_k = 5 $ for all $ k\geq 0 $. Dash-dotted lines correspond to AALM with $ \gamma $-safeguarding. $ \gamma $AALM(5, 0.9) is omitted since it coincides with $ \gamma $AALM(1, 0.9). Right: Residual history for test function Beh4 with LM parameter $ \mu_k = \|f'(x_k)^Tf(x_k)\| $.

Download: Full-size image PowerPoint slide

Table 1. Results for Anderson accelerated Newton and inexact Newton applied to the Chandrasekhar H-equation for $ \bar{\omega} = 1 $.

Algorithm	Iterations	$ \\|f(x_k)\\| $	Algorithm	Iterations	$ \\|f(x_k)\\| $
Newt	16	4.45e-09	inNewt	16	9.21e-09
AANewt(1) $ \gamma $AANewt(1, 0.9)	6 12	2.24e-11 2.01e-09	AAinNewt(1) $ \gamma $AAinNewt(1, 0.9)	8 13	1.14e-09 3.12e-09
AANewt(5) $ \gamma $AANewt(5, 0.9)	7 12	8.04-09 2.01-e09	AAinNewt(5) $ \gamma $AAinNewt(5, 0.9)	14 13	2.47e-09 3.17e-09
AANewt(10) $ \gamma $AANewt(10, 0.9)	7 12	8.01e-09 2.01e-09	AAinNewt(10) $ \gamma $AAinNewt(10, 0.9)	20 12	3.40e-09 3.17e-09
AANewt(50) $ \gamma $AANewt(50, 0.9)	7 12	8.01e-09 2.01e-09	AAinNewt(50) $ \gamma $AAinNewt(50, 0.9)	61 13	4.35e-09 3.17e-09

| Show Table

DownLoad: CSV

Table 2. Results for Anderson accelerated Levenberg-Marquardt and inexact Levenberg-Marquardt applied to the Chandrasekhar H-equation for $ \bar{\omega} = 1 $.

Algorithm	Iterations	$ \\|f(x_k)\\| $	Algorithm	Iterations	$ \\|f(x_k)\\| $
LM	16	5.58e-09	inLM	17	4.28e-09
AALM(1) $ \gamma $AALM(1, 0.9)	6 12	1.72e-09 2.20e-09	AAinLM(1) $ \gamma $AAinLM(1, 0.9)	9 12	4.93e-09 8.46e-09
AALM(5) $ \gamma $AALM(5, 0.9)	10 12	4.81e-09 2.20e-09	AAinLM(5) $ \gamma $AAinLM(5, 0.9)	24 12	2.63e-09 8.5e-09
AALM(10) $ \gamma $AALM(10, 0.9)	13 12	3.70e-09 2.20e-09	AinLM(10) $ \gamma $AAinLM(10, 0.9)	51 12	3.5e-09 8.47e-09
AALM(50) $ \gamma $AALM(50, 0.9)	45 12	2.81e-09 2.89e-09	AAinLM(50) $ \gamma $AAinLM(50, 0.9)	F 12	- 8.47e-09

| Show Table

DownLoad: CSV

Table 3. Results for Anderson accelerated Newton and Anderson accelerated Levenberg-Marquardt applied to the Chandrasekhar H-equation for $ \bar{\omega} = 0.8 $.

Algorithm	Iterations	$ \\|f(x_k)\\| $	Algorithm	Iterations	$ \\|f(x_k)\\| $
Newt	4	3.8e-14	LM	4	4.18e-14
AANewt(1) $ \gamma $AANewt(1, 0.9)	5 4	1.34e-11 2.63e-14	AALM(1) $ \gamma $AALM(1, 0.9)	5 4	2.12e-11 2.60e-14
AANewt(5) $ \gamma $AANewt(5, 0.9)	8 4	2.0e-11 2.62e-14	AALM(5) $ \gamma $AALM(5, 0.9)	8 4	8.5e-14 2.60e-14
AANewt(10) $ \gamma $AANewt(10, 0.9)	13 4	8.83e-13 2.62e-14	AALM(10) $ \gamma $AALM(10, 0.9)	13 4	4.55e-14 2.60e-14
AANewt(50) $ \gamma $AANewt(50, 0.9)	26 4	5.92e-09 2.62e-14	AALM(50) $ \gamma $AALM(50, 0.9)	26 4	2.03e-09 2.60e-14

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. An, X. Jia and H. Walker, Anderson acceleration and application to the three-temperature energy equations, J. Comput. Phys., 347 (2017), 1-19. doi: 10.1016/j.jcp.2017.06.031.
[2]	D. Anderson, Iterative procedures for nonlinear integral equations, J. Assoc. Comput. Mach., 12 (1965), 547-560. doi: 10.1145/321296.321305.
[3]	R. Awada, J. Carrayrou and C. Rosier, Anderson acceleration. convergence analysis and applications to equilibrium chemistry, Appl. Numer. Math., 208 (2025), 60-75. doi: 10.1016/j.apnum.2024.01.022.
[4]	R. Behling, D. Goncalves and S. Santos, Local convergence analysis of the Levenberg–Marquardt framework for nonzero-residue nonlinear least-squares problems under an error bound condition, J. Optim. Appl., 183 (2019), 1099-1122. doi: 10.1007/s10957-019-01586-9.
[5]	S. Chandrasekhar, Radiative Transfer, Engineering special collection, Dover Publications, 1960.
[6]	M. Dallas and S. Pollock, Newton-Anderson at singular points, Int. J. Numer. Anal. and Mod., 20 (2023), 667-692. doi: 10.4208/ijnam2023-1029.
[7]	M. Dallas, S. Pollock and L. G. Rebholz, Analysis of an adaptive safeguarded Newton-Anderson algorithm of depth one with applications to fluid problems, Advances in Computational Science and Engineering, 2 (2024), 246-270. doi: 10.3934/acse.2024013.
[8]	D. Decker, H. Keller and C. T. Kelley, Convergence rates for Newton's method at singular points, SIAM J. Numer. Anal., 20 (1983), 296-314. doi: 10.1137/0720020.
[9]	D. Decker and C. T. Kelley, Expanded convergence domains for Newton's method at nearly singular roots, SIAM J. Sci. Stat. Comput., 6 (1985).
[10]	P. Deuflhard, Newton Methods for Nonlinear Problems, Springer Series in Computational Mathematics, Springer, 2005.
[11]	S. Eisenstat and H. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17 (1996), 16-32.
[12]	C. Evans, S. Pollock, L. Rebholz and M. Xiao, A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically), SIAM J. Numer. Anal., 58 (2020), 788-810. doi: 10.1137/19M1245384.
[13]	V. Eyert, A comparative study on methods for convergence acceleration of iterative vector sequences, J. Comput. Phys., 124 (1996), 271-285. doi: 10.1006/jcph.1996.0059.
[14]	H. Fang and Y. Saad, Two classes of multisecant methods for nonlinear acceleration, Numer. Linear Algebra Appl., 16 (2008), 197-221. doi: 10.1002/nla.617.
[15]	A. Fischer, A. Izmailov and M. Solodov, Accelerating convergence of the globalized Newton method to critical solutions of nonlinear equations, Comput. Optim. Appl., 78 (2021), 273-286. doi: 10.1007/s10589-020-00230-x.
[16]	A. Fischer, A. F. Izmailov and M. V. Solodov, Unit stepsize for the Newton method close to critical solutions, Math. Program., 187 (2021), 697-721. doi: 10.1007/s10107-020-01496-z.
[17]	A. Fischer, A. F. Izmailov and M. V. Solodov, The Levenberg–Marquardt method: An overview of modern convergence theories and more, Comp. Optim. Appl., 89 (2024), 33-67. doi: 10.1007/s10589-024-00589-1.
[18]	A. Griewank, Starlike domains of convergence for Newton's method at singularities, Numer. Math., 35 (1980), 95-111. doi: 10.1007/BF01396373.
[19]	A. Griewank, On solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Review, 27 (1985), 537-563. doi: 10.1137/1027141.
[20]	A. Izmailov, A. Kurennoy and M. Solodov, Critical solutions of nonlinear equations: Local attraction for Newton-type methods, Math. Progam., 167 (2018), 355-379. doi: 10.1007/s10107-017-1128-5.
[21]	A. Izmailov, A. Kurennoy and M. Solodov, Critical solutions of nonlinear equations: Stability issues, Math. Progam., 168 (2018), 475-507. doi: 10.1007/s10107-016-1047-x.
[22]	A. Izmailov and M. Solodov, A general perturbed Newtonian framework and critical solutions of nonlinear equations, Set-Valued and Variational Analysis, 33 (2025), 27 pp. doi: 10.1007/s11228-025-00739-5.
[23]	C. Kanzow, N. Yamashita and M. Fukushima, Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math, 172 (2004), 375-397. doi: 10.1016/j.cam.2004.02.013.
[24]	C. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995.
[25]	C. Kelley, Numerical methods for nonlinear equations, Acta Numer., 27 (2018), 207-287. doi: 10.1017/S0962492917000113.
[26]	P. Lott, H. Walker, C. Woodward and U. Yang, An accelerated Picard method for nonlinear systems related to variably saturated flow, Adv. Water Resour., 38 (2012), 92-101. doi: 10.1016/j.advwatres.2011.12.013.
[27]	S. A. Nazzer, M. Jazar and C. Rosier, Convergence acceleration of iterative sequences for equilibrium chemistry computations, Comp. Geosci., 25 (2021), 1509-1538. doi: 10.1007/s10596-021-10054-1.
[28]	M. Pasini, J. Yin, V. Reshniak, and M. Stoyanov, Anderson acceleration for distributed training of deep learning models, SoutheastCon 2022, (2022), 289-295. doi: 10.1109/SoutheastCon48659.2022.9763953.
[29]	Y. Peng, B. Deng, J. Zhang, F. Geng, W. Qin and L. Liu, Anderson acceleration for geometry optimization and physics simulation, ACM Trans. Graph., 37 (2018), 1-14. doi: 10.1145/3197517.3201290.
[30]	F. Pich, Reduced Order Models for Parametric Bifurcation Problems in Nonlinear PDEs, PhD thesis, 2020.
[31]	S. Pollock, A regularized Newton-like method for nonlinear pde, Numer. Funct. Anal. and Optim., 36 (2015), 1493-1511. doi: 10.1080/01630563.2015.1069328.
[32]	S. Pollock and L. Rebholz, Anderson acceleration for contractive and noncontractive operators, IMA J. Numer. Anal., 41 (2021), 2841-2872.
[33]	S. Pollock and L. Rebholz, Filtering for Anderson acceleration, SIAM J. Sci. Comput., 45 (2023), A1571-A1590. doi: 10.1137/22M1536741.
[34]	S. Pollock and L. Rebholz, Anderson Acceleration for Numerical PDEs, SIAM, 2025. doi: 10.1137/1.9781611978490.
[35]	S. Pollock, L. Rebholz and M. Xiao, Anderson-accelerated convergence of Picard iterations for incompressible Navier-Stokes equations, SIAM J. Numer. Anal., 57 (2019), 615-637. doi: 10.1137/18M1206151.
[36]	S. Pollock and H. Schwartz, Benchmarking results for the Newton–Anderson method, Results Appl. Math., 8 (2020), 100095, 11 pp.
[37]	L. Rebholz and M. Xiao, The effect of Anderson acceleration on superlinear and sublinear convergence, J. Sci. Comput., 96 (2023), 23 pp. doi: 10.1007/s10915-023-02262-x.
[38]	R. Thompson, K. Rasmussen and T. Lookman, Improved convergence in block copolymer self-consistent field theory by Anderson mixing, J. Chem. Phys., 120 (2004), 31-34. doi: 10.1063/1.1629673.
[39]	A. Toth and C. Kelley, Convergence analysis for Anderson acceleration, SIAM J. Numer. Anal., 53 (2015), 805-819. doi: 10.1137/130919398.
[40]	H. Walker and P. Ni, Anderson acceleration for fixed-point iterations, SIAM J. Numer. Anal., 49 (2011), 1715-1735. doi: 10.1137/10078356X.
[41]	D. Wang, Y. He, and H. D. Sterck, On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM, J. Sci. Comput., 88 (2021), 38, 35 pp. doi: 10.1007/s10915-021-01548-2.
[42]	Y. Yang, Anderson acceleration for seismic inversion, Geophysics, 86 (2021).