Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis

.We study the asymptotic convergence of AA( \(m\) ), i.e., Anderson acceleration (AA) with window size \(m\) for accelerating fixed-point methods \(xₖ₊₁=q(xₖ)\) , \(x_k ∈ R^n\) . Convergence acceleration by AA( \(m\) ) has been widely observed but is not well understood. We consider the case where the fixed-point iteration function \(q(x)\) is differentiable and the convergence of the fixed-point method itself is root-linear. We identify numerically several conspicuous properties of AA( \(m\) ) convergence: First, AA( \(m\) ) sequences \(\{x_k\}\) converge root-linearly, but the root-linear convergence factor depends strongly on the initial condition. Second, the AA( \(m\) ) acceleration coefficients \(β ⁽ᵏ⁾\) do not converge but oscillate as \(\{x_k\}\) converges to \(x*\) . To shed light on these observations, we write the AA( \(m\) ) iteration as an augmented fixed-point iteration \(zₖ₊₁ =Ψ (z_k)\) , \(z_k ∈ Rⁿ⁽ᵐ⁺¹⁾\) , and analyze the continuity and differentiability properties of \(Ψ (z)\) and \(β (z)\) . We find that the vector of acceleration coefficients \(β (z)\) is not continuous at the fixed point \(z*\) . However, we show that, despite the discontinuity of \(β (z)\) , the iteration function \(Ψ (z)\) is Lipschitz continuous and directionally differentiable at \(z*\) for AA(1), and we generalize this to AA( \(m\) ) with \(m> 1\) for most cases. Furthermore, we find that \(Ψ (z)\) is not differentiable at \(z*\) . We then discuss how these theoretical findings relate to the observed convergence behavior of AA( \(m\) ). The discontinuity of \(β (z)\) at \(z*\) allows \(β ⁽ᵏ⁾\) to oscillate as \(\{x_k\}\) converges to \(x*\) , and the nondifferentiability of \(Ψ (z)\) allows AA( \(m\) ) 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 \(xₖ₊₁=q(xₖ)\) and for various values of the window size \(m\) .