Nonlinear equations are ubiquitous in the sciences, a famous example being the Navier-Stokes equations in fluid mechanics. To compute a numerical solution for a given nonlinear equation, one often employs an iterative scheme such as Newton’s method. To apply Newton’s method to a nonlinear system of equations \(f: \mathbb{R}^n \to \mathbb{R}^n\), one selects an initial iterate \(x_0 \in \mathbb{R}^n\), and for \(k \ge 0\), solves \(f’(x_k)w_{k+1} = -f(x_k)\)  and sets \(x_{k+1} = x_k + w_{k+1}\). 

If \(f(x^*)=0\), \(f’(x)\) is Lipschitz continuous, and \(f’(x^*)\) is invertible, then the Newton-Kantorovich theorem says that Newton’s method converges quadratically in a neighborhood of \(x^*\). When \(f’(x^*)\) is singular, however, Newton’s method is much slower, exhibiting linear convergence in a star-shaped region about \(x^*\). Problems for which \(f’(x^*)\) is singular are known as singular problems and \(x^*\) is called a singular point. Such problems arise frequently in parameter-dependent problems since any bifurcation point is necessarily a singular point. 

The recent works [1] and [2] with Sara Pollock (University of Florida) and Leo Rebholz (Clemson University) analyze Anderson accelerated Newton’s method, denoted NA, applied to singular problems. In [1], we prove that NA is accelerated relative to standard Newton, and prove local convergence of NA with \(\gamma\)-safeguarding, a computationally inexpensive safeguarding scheme. 

In [2] we develop an adaptive version of \(\gamma\)-safeguarding that automatically detects if the problem is nonsingular, and responds by “turning off” Anderson asymptotically. The result is a flexible algorithm with a tunable parameter that performs well for singular and nonsingular problems and can recover convergence from both standard Newton and NA with the right parameter choice. This is demonstrated in the right-most plot in Figure 1. 

This work was presented and developed at ICERM during the Summer 2023 Acceleration and Extrapolation Methods workshop and Spring 2024 Numerical PDEs semester program. 

References 

[1] Matt Dallas and Sara Pollock. Newton-Anderson at singular points. Int. J. Numer. Anal. and Mod., 20(5):667–692, 2023. 

[2] Matt Dallas, Sara Pollock, and Leo Rebholz. Analysis of an adaptive safeguarded Newton-Anderson algorithm with applications to fluid problems. Submitted, 2024. URL: https://doi.org/10.48550/arXiv.2402.09295.