Acceleration of convergence of general linear sequences by the Shanks transformation

作者：Sidi Avram^*

来源：Numerische Mathematik, 2011, 119(4): 725-764.

DOI：10.1007/s00211-011-0398-8

The Shanks transformation is a powerful nonlinear extrapolation method that is used to accelerate the convergence of slowly converging, and even diverging, sequences {A (n) }. It generates a two-dimensional array of approximations A(n)((j)) to the limit or anti-limit of {A(n)} defined as solutions of the linear systems
At = A(n)((j)) + (n)Sigma(k=1) (beta) over bar (k) (Delta A(l+k-1)), j <= l <= j + n,
where (beta) over bar (k) are additinal unknowns. In this work, we study the convergence and stability properties of A(n)((j)), as j -> infinity with n fixed, derived from general linear sequences {A(n)}, where A(n) similar to A + Sigma(m)(k=1) zeta(n)(k) Sigma(infinity)(i=0) beta(ki)n(gamma k-i) as n -> infinity, where zeta (k) not equal 1 are distinct and |zeta(1)| = ... = |zeta (m) | = theta, and gamma (k) not equal 0, 1, 2, . . .. Here A is the limit or the anti-limit of {A (n) }. Such sequences arise, for example, as partial sums of Fourier series of functions that have finite jump discontinuities and/or algebraic branch singularities. We show that definitive results are obtained with those values of n for which the integer programming problems
max(s1,...,sm) Sigma(m)(k=1) [(R(gamma k))s(k) - s(k) (s(k) - 1)]
subject to s1 >= 0, ..., s(m) >= 0 and (m)Sigma(k=1) s(k) = n,
have unique (integer) solutions for s (1), . . . , s(m) . A special case of our convergence result concerns the situation in which R(gamma 1) = ... R gamma(m) = alpha and n = m nu with nu = 1, 2, . . . , for which the integer programming problems above have unique solutions, and it reads An(j) - A = O(theta j j alpha-2v) as j -> infinity, , this result shows that the Shanks transformation is a true convergence acceleration method for the sequences considered. In addition, we show that it is stable for the case being studied, and we also quantify its stability properties. The results of this work are the first ones pertaining to the Shanks transformation on general linear sequences with m > 1.

• 出版日期2011-12