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

Electronic Transactions on Numerical Analysis

article

Fei Xue¹ 

[1] School of Mathematical and Statistical Sciences, Clemson University

关键词: fixed point iteration;    inexact Anderson acceleration;    non-contractive mapping;    one-step convergence;   

DOI  :  10.1553/etna_vol55s285

学科分类：数学（综合）

来源: Kent State University * Institute of Computational Mathematics

【 摘 要 】

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.

【 授权许可】

Unknown