In mathematics, minimum polynomial extrapolation is a

sequence transformation In mathematics, a sequence transformation is an operator acting on a given space of sequences (a sequence space). Sequence transformations include linear mappings such as convolution with another sequence, and resummation of a sequence and, more ...

used for

convergence acceleration In mathematics, series acceleration is one of a collection of sequence transformations for improving the rate of convergence of a series. Techniques for series acceleration are often applied in numerical analysis, where they are used to improve ...

of vector sequences, due to Cabay and Jackson. While

Aitken's method In numerical analysis, Aitken's delta-squared process or Aitken extrapolation is a series acceleration method, used for accelerating the rate of convergence of a sequence. It is named after Alexander Aitken, who introduced this method in 1926.Alex ...

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 In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. More specifically, given a function f defined on the real numbers with real values and given a point x_0 in the domain of f, the fixed-point iterat ...

: :

x_=f(x_k).

Given iterates

x_1, x_2, ..., x_k

\mathbb R^n

, one constructs the

n \times (k-1)

matrix

U=(x_2-x_1, x_3-x_2, ..., x_k-x_)

whose columns are the

k-1

differences. Then, one computes the vector

c=-U^+ (x_-x_k)

where

U^+

denotes the Moore–Penrose

pseudoinverse In mathematics, and in particular, algebra, a generalized inverse (or, g-inverse) of an element ''x'' is an element ''y'' that has some properties of an inverse element but not necessarily all of them. The purpose of constructing a generalized in ...

U

. The number 1 is then appended to the end of

c

, and the extrapolated limit is :

s=,

where

X=(x_2, x_3, ..., x_)

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);

References

Numerical analysis Articles with example MATLAB/Octave code {{mathanalysis-stub