Volume 55, pp. 285-309, 2022.

One-step convergence of inexact Anderson acceleration for contractive and non-contractive mappings

Fei Xue

Abstract

We give a one-step convergence analysis of inexact Anderson acceleration for the fixed point iteration $x_{k+1}=g(x_k)$ with a potentially non-contractive mapping $g$, where $g(x_k)$ is evaluated approximately and the minimization of the nonlinear residual norms is performed in the vector 2-norm by the linear least-squares method. If $g$ is non-contractive, then the original fixed point iteration does not converge, but a recent analysis by S. Pollock and L. Rebholz [IMA J. Numer. Anal., 41 (2021), pp. 2841–2872] shows that Anderson acceleration may still converge provided that the minimization at each step has a sufficient gain. In this paper, we show that inexact Anderson acceleration exhibits essentially the same convergence behavior as the exact algorithm if each $g(x_k)$ is evaluated with an error proportional to the nonlinear residual norm $\Vert w_k\Vert =\Vert g(x_k)-x_k\Vert$, regardless of whether $g$ is contractive or not. This means that the existing relationship between exact and inexact Anderson acceleration can be generalized in a unified framework for both contractive and non-contractive mappings. Numerical experiments show that the inexact algorithm can converge as rapidly as the exact counterpart while it can lower the computational cost.

Full Text (PDF) [701 KB], BibTeX , DOI: 10.1553/etna_vol55s285

Key words

fixed point iteration, inexact Anderson acceleration, non-contractive mapping, one-step convergence

AMS subject classifications

65N22, 65H10, 65F50

Links to the cited ETNA articles

[29]	Vol. 6 (1997), pp. 271-290 T. Washio and C. W. Oosterlee: Krylov subspace acceleration for nonlinear multigrid schemes