Anderson acceleration

Anderson acceleration, also called Anderson mixing, is a numerical method for speeding up the convergence of fixed-point iterations, the repeated application of a function to its own output in search of a value x that satisfies f(x) = x. Plain fixed-point iteration is not guaranteed to converge and, when it does, usually converges only linearly, which becomes slow and costly when each evaluation of the function is expensive. The method was introduced by Donald G. Anderson. At each step it keeps the last few iterates and residuals and picks the combination of them whose residual is smallest, which comes down to solving a small linear least-squares problem. Compared with the standard iteration it has been found to converge faster and more robustly, and in some cases to avoid divergence of the sequence. It needs only one evaluation of the function per iteration and no derivative, unlike Newton's method, although its convergence remains linear in general. The memory depth and an optional mixing parameter set the balance between speed and conditioning, and the method has been related to quasi-Newton and multisecant methods and, for linear problems, to GMRES.