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

$ 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,$
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.