CONVERGENCE ANALYSIS FOR ANDERSON ACCELERATION

Anderson(m) is a method for acceleration of fixed point iteration which stores m + 1 prior evaluations of the fixed point map and computes the new iteration as a linear combination of those evaluations. Anderson(0) is fixed point iteration. In this paper we show that Anderson(m) is locally r-linearly convergent if the fixed point map is a contraction and the coefficients in the linear combination remain bounded. Without assumptions on the coefficients, we prove q-linear convergence of Anderson(1) and, in the case of linear problems, Anderson(m). We observe that the optimization problem for the coefficients can be formulated and solved in nonstandard ways and report on numerical experiments which illustrate the ideas.