In mathematics, Anderson acceleration, also called Anderson mixing, is a method for the acceleration of the convergence rate of fixed-point iterations.
Introduced by Donald G. Anderson,[1] this technique can be used to find the solution to fixed point equations
, consider the problem of finding a fixed point of
A classical approach to the problem is to employ a fixed-point iteration scheme;[2] that is, given an initial guess
However, the convergence of such a scheme is not guaranteed in general; moreover, the rate of convergence is usually linear, which can become too slow if the evaluation of the function
corresponds to the sequence of iterates from the previous paragraph).
Conventional stopping criteria can be used to end the iterations of the method.
[2] With respect to the standard fixed-point iteration, the method has been found to converge faster and be more robust, and in some cases avoid the divergence of the fixed-point sequence.
sum to one, we can make the first order approximation
is designed to bring a point closer to
sum to one, we can make the first order approximation
At each iteration of the algorithm, the constrained optimization problem
The problem can be recast in several equivalent formulations,[3] yielding different solution methods which may result in a more convenient implementation: For both choices, the optimization problem is in the form of an unconstrained linear least-squares problem, which can be solved by standard methods including QR decomposition[3] and singular value decomposition,[4] possibly including regularization techniques to deal with rank deficiencies and conditioning issues in the optimization problem.
Solving the least-squares problem by solving the normal equations is generally not advisable due to potential numerical instabilities and generally high computational cost.
) causes the method to break down, due to the singularity of the least-squares problem.
) results in bad conditioning of the least squares problem.
might be relevant in determining the conditioning of the least-squares problem, as discussed below.
is crucial to the convergence properties of the method; in principle,
is chosen to be too small, too little information is used and convergence may be undesirably slow.
affects the size of the optimization problem.
may worsen the conditioning of the least squares problem and the cost of its solution.
[3] In general, the particular problem to be solved determines the best choice of the
so as to maintain a small enough conditioning for the least-squares problem.
However, such method requires the evaluation of the exact derivative of
[4] Approximating the derivative by means of finite differences is a possible alternative, but it requires multiple evaluations of
Anderson acceleration requires only one evaluation of the function
On the other hand, the convergence of an Anderson-accelerated fixed point sequence is still linear in general.
[5] Several authors have pointed out similarities between the Anderson acceleration scheme and other methods for the solution of non-linear equations.
In particular: Moreover, several equivalent or nearly equivalent methods have been independently developed by other authors,[9][10][11][12][13] although most often in the context of some specific application of interest rather than as a general method for fixed point equations.
The following is an example implementation in MATLAB language of the Anderson acceleration scheme for finding the fixed-point of the function