Verlag der Österreichischen Akademie der Wissenschaften

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 $\|w_k\|=\|g(x_k)-x_k\|$, 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.