Minimum polynomial extrapolation

In mathematics, minimum polynomial extrapolation is a sequence transformation used for convergence acceleration.

While Aitken's method is the most famous, it often fails for vector sequences. An effective method for vector sequences is the minimum polynomial extrapolation. It is usually phrased in terms of the fixed point iteration:

x_{k + 1} = f(x_k).

Given iterates x₁,x₂,...,x_k in , one constructs the matrix U = (x₂ − x₁,x₃ − x₂,...,x_k − x_{k − 1}) whose columns are the k − 1 differences. Then, one computes the vector c = U ⁺ (x_{k + 1} − x_k) where U ⁺ denotes the Moore–Penrose pseudoinverse of U. The number 1 is then appended to the end of c, and the extrapolated limit is

where X = (x₂,x₃,...,x_{k + 1}) is the matrix whose columns are the k iterates starting at 2.

The following 4 line MATLAB code segment implements the MPE algorithm:

U=x(:,2:end-1)-x(:,1:end-2);
c=-pinv(U)*(x(:,end)-x(:,end-1));
c(end-1,1)=1;
s=(x(:,2:end)*c)/sum(c);

This mathematical analysis–related article is a stub. You can help Wikipedia by expanding it. v d e