Anderson Acceleration as a Krylov Method with Application to Convergence Analysis

Anderson acceleration (AA) is widely used for accelerating the convergence of nonlinear fixed-point methods, but little is known about how to quantify the asymptotic convergence acceleration provided by AA. As a roadway towards gaining more understanding of convergence acceleration by AA, we study AA(m), i.e., Anderson acceleration with finite window size m, applied to the case of linear fixed-point iterations. We write AA(m) as a Krylov method with polynomial residual update formulas, and derive \((m+2)\) $(m+2)$ -term recurrence relations for the AA(m) polynomials. We derive several results based on these polynomial residual update formulas, including orthogonality relations, acceleration coefficient bounds, nonlinear recursions, and residual convergence bounds. We apply these results to study AA(1) residual convergence patterns and the influence of the initial guess on the asymptotic convergence factor.