A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
复制标题
DOI：
10.1137/19m1245384
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Claire Evans;Sara N. Pollock;L. Rebholz;Mengying Xiao
中科院分区：
文献类型：
--
作者：
Claire Evans;Sara N. Pollock;L. Rebholz;Mengying Xiao
本文首次证明了安德森加速（AA）提高了一般不动点迭代的收敛速度。几十年来，AA一直被用于加速许多应用中的非线性求解器，但是仍然缺乏改进收敛速度的严格数学证明。这里提出的分析的关键思想是在Hilbert空间设置中执行内部优化的基础上，将连续迭代的差异与残差相关联，并将优化阶段的增益明确定义为非加速定点迭代的一步改进的比率。我们证明的主要结果是，AA提高了收敛速度的不动点迭代到一阶的增益的一个因素，在每一步。除了提高收敛速度，我们的研究结果表明，AA增加了收敛半径。最后，我们的估计表明，虽然线性收敛速度提高，额外的二次项出现在估计，这表明为什么AA通常不会提高收敛二次收敛不动点迭代。给出了几个数值试验的结果，说明了理论。
This paper provides the first proof that Anderson acceleration (AA) improves the convergence rate of general fixed point iterations. 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 we prove is that AA improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step. In addition to improving the convergence rate, our results indicate that AA increases the radius of convergence. Lastly, our estimate shows that while the linear convergence rate is improved, additional quadratic terms arise in the estimate, which shows why AA does not typically improve convergence in quadratically converging fixed point iterations. Results of several numerical tests are given which illustrate the theory.