A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)

Abstract

This paper provides theoretical justification that Anderson acceleration (AA) improves the convergence rate of contractive fixed-point iterations in the vicinity of a fixed-point. AA has been used for decades to speed up nonlinear solvers in many applications. However, a rigorous mathematical justification of the improved convergence rate has remained lacking. The key ideas of the analysis presented here are relating the difference of consecutive iterates to residuals based on performing the inner-optimization in a Hilbert space setting, and explicitly defining the gain in the optimization stage to be the ratio of improvement over a step of the unaccelerated fixed-point iteration. The main result shown here is that AA improves the convergence rate of a fixed-point iteration to first order by a factor of the gain at each step. While the acceleration reduces the contribution from the first-order terms in the residual expansion, additional superlinear terms arise. In agreement with the theory, numerical tests are given which illustrate improved linear convergence rates, but for quadratically converging fixed-point iterations the rate is slowed. Our tests further illustrate how AA can perform similarly to damping in enlarging the domain of convergence.