Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis
Hans De Sterck, Yunhui He · SIAM Journal on Matrix Analysis and Applications · 2022
Abstract. We study the asymptotic convergence of AA([Formula: see text]), i.e., Anderson acceleration (AA) with window size [Formula: see text] for accelerating fixed-point methods [Formula: see text], [Formula: see text]. Convergence acceleration by AA([Formula: see text]) has been widely observed but is not well understood. We consider the case where the fixed-point iteration function [Formula: see text] is differentiable and the convergence of the fixed-point method itself is root-linear. We identify numerically several conspicuous properties of AA([Formula: see text]) convergence: First, AA([Formula: see text]) sequences [Formula: see text] converge root-linearly, but the root-linear convergence factor depends strongly on the initial condition. Second, the AA([Formula: see text]) acceleration coefficients [Formula: see text] do not converge but oscillate as [Formula: see text] converges to [Formula: see text]. To shed light on these observations, we write the AA([Formula: see text]) iteration as an augmented fixed-point iteration [Formula: see text], [Formula: see text], and analyze the continuity and differentiability properties of [Formula: see text] and [Formula: see text]. We find that the vector of acceleration coefficients [Formula: see text] is not continuous at the fixed point [Formula: see text]. However, we show that, despite the discontinuity of [Formula: see text], the iteration function [Formula: see text] is Lipschitz continuous and directionally differentiable at [Formula: see text] for AA(1), and we generalize this to AA([Formula: see text]) with [Formula: see text] for most cases. Furthermore, we find that [Formula: see text] is not differentiable at [Formula: see text]. We then discuss how these theoretical findings relate to the observed convergence behavior of AA([Formula: see text]). The discontinuity of [Formula: see text] at [Formula: see text] allows [Formula: see text] to oscillate as [Formula: see text] converges to [Formula: see text], and the nondifferentiability of [Formula: see text] allows AA([Formula: see text]) sequences to converge with root-linear convergence factors that strongly depend on the initial condition. Additional numerical results illustrate our findings for several linear and nonlinear fixed-point iterations [Formula: see text] and for various values of the window size [Formula: see text].