Misplaced Pages

Minimum polynomial extrapolation

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In mathematics, minimum polynomial extrapolation is a sequence transformation used for convergence acceleration of vector sequences, due to Cabay and Jackson.

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 ) . {\displaystyle x_{k+1}=f(x_{k}).}

Given iterates x 1 , x 2 , . . . , x k {\displaystyle x_{1},x_{2},...,x_{k}} in R n {\displaystyle \mathbb {R} ^{n}} , one constructs the n × ( k − 1 ) {\displaystyle n\times (k-1)} matrix U = ( x 2 − x 1 , x 3 − x 2 , . . . , x k − x k − 1 ) {\displaystyle U=(x_{2}-x_{1},x_{3}-x_{2},...,x_{k}-x_{k-1})} whose columns are the k − 1 {\displaystyle k-1} differences. Then, one computes the vector c = − U + ( x k + 1 − x k ) {\displaystyle c=-U^{+}(x_{k+1}-x_{k})} where U + {\displaystyle U^{+}} denotes the Moore–Penrose pseudoinverse of U {\displaystyle U} . The number 1 is then appended to the end of c {\displaystyle c} , and the extrapolated limit is

s = X c ∑ i = 1 k c i , {\displaystyle s={Xc \over \sum _{i=1}^{k}c_{i}},}

where X = ( x 2 , x 3 , . . . , x k + 1 ) {\displaystyle X=(x_{2},x_{3},...,x_{k+1})} is the matrix whose columns are the k {\displaystyle 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

  1. Cabay, S.; Jackson, L.W. (1976), "A polynomial extrapolation method for finding limits and antilimits of vector sequences", SIAM Journal on Numerical Analysis, 13 (5): 734–752, Bibcode:1976SJNA...13..734C, doi:10.1137/0713060


Stub icon

This mathematical analysis–related article is a stub. You can help Misplaced Pages by expanding it.

Categories: