Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Asymptotic analysis of a generalized Richardson extrapolation process on linear sequences

Author: Avram Sidi
Journal: Math. Comp. 79 (2010), 1681-1695
MSC (2000): Primary 40A05, 40A25, 41A60, 65B05, 65B10.
Published electronically: November 30, 2009
MathSciNet review: 2630007
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this work, we give a detailed convergence and stability analysis for the author’s generalized Richardson extrapolation process GREP$^{(m)}$ as this is being applied to linearly convergent or divergent infinite sequences $\{A_n\}$, where $A_n\sim A+\sum ^m_{k=1}\zeta _k^n\sum ^\infty _{i=0}\beta _{ki}n^{\gamma _k-i}$ as $n\to \infty$, $\zeta _k\neq 1$ being distinct. The quantity we would like to compute is $A$, whether it is the limit or antilimit of $\{A_n\}$. Such sequences arise, for example, as partial sums of power series and of Fourier series of functions that have algebraic and/or logarithmic branch singularities. Specifically, we define the GREP$^{(m)}$ approximation $A^{(m,j)}_n$ to $A$, with $n=(n_1,\ldots ,n_m)$ and $\alpha >0$, via the linear systems \center $A_l=A^{(m,j)}_n +\sum ^m_{k=1}\zeta _k^l\sum ^{n_k-1}_{i=0}\bar {\beta }_{ki}(\alpha +l)^{\gamma _k-i},\ \ j\leq l\leq j+\sum ^m_{k=1}n_k,$\endcenter where $\bar {\beta }_{ki}$ are additional unknowns. We study the convergence and stability properties of $A^{(m,j)}_n$ as $j\to \infty$. We show, in particular, that $A^{(m,j)}_n-A= \sum ^m_{k=1}O(\zeta _k^j j^{\gamma _k-2n_k})$ as $j\to \infty$. When compared with $A_j-A=\sum ^m_{k=1}O(\zeta _k^j j^{\gamma _k})$ as $j\to \infty$, this result shows that GREP$^{(m)}$ is a true convergence acceleration method for the sequences considered. In addition, we show that GREP$^{(m)}$ 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 GREP$^{(m)}$ with $m>1$.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 40A05, 40A25, 41A60, 65B05, 65B10.

Retrieve articles in all journals with MSC (2000): 40A05, 40A25, 41A60, 65B05, 65B10.

Additional Information

Avram Sidi
Affiliation: Computer Science Department, Technion, Israel Institute of Technology, Haifa 32000, Israel

Keywords: Acceleration of convergence, generalized Richardson extrapolation process, GREP$^{(m)}$, power series, Fourier series, asymptotic expansions.
Received by editor(s): April 30, 2009
Received by editor(s) in revised form: June 25, 2009
Published electronically: November 30, 2009
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.