Numerical Analysis Seminar
Date: March 8, 2019
Time: 12:45PM - 1:45PM
Location: BLOC 628
Speaker: Sara Pollock, University of Florida
Title: Anderson acceleration improves the convergence rate in linearly converging fixed point methods
Abstract: The extrapolation method known as Anderson acceleration has been used for decades to speed up nonlinear solvers in many applications, however a mathematical justification of the improved convergence rate has remained elusive. Here, we provide theory to establish the improved convergence rate. The key ideas of the analysis 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 this method of acceleration improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step.