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

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

  • 1. M. Abramowitz and I.A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, Nat. Bur. Standards Appl. Math. Series, no. 55, U.S. Government Printing Office, Washington, D.C., 1964. MR 0167642 (29:4914)
  • 2. N. Bleistein and R.A. Handelsman, Asymptotic expansions of integrals, Holt, Rinehart and Winston, New York, 1975.
  • 3. P.J. Davis and P. Rabinowitz, Methods of numerical integration, second ed., Academic Press, New York, 1984. MR 760629 (86d:65004)
  • 4. W.F. Ford and A. Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer. Anal. 24 (1987), 1212-1232. MR 909075 (89a:65006)
  • 5. D. Levin and A. Sidi, Two new classes of nonlinear transformations for accelerating the convergence of infinite integrals and series, Appl. Math. Comp. 9 (1981), 175-215, Originally appeared as a Tel Aviv University preprint in 1975. MR 650681 (83d:65010)
  • 6. -, Extrapolation methods for infinite multiple series and integrals, J. Comput. Meth. Sci. Engrg. 1 (2001), 167-184.
  • 7. F.W.J. Olver, Asymptotics and special functions, Academic Press, New York, 1974. MR 0435697 (55:8655)
  • 8. D. Shanks, Nonlinear transformations of divergent and slowly convergent sequences, J. Math. and Phys. 34 (1955), 1-42. MR 0068901 (16:961e)
  • 9. A. Sidi, Some properties of a generalization of the Richardson extrapolation process, J. Inst. Math. Appl. 24 (1979), 327-346. MR 550478 (81a:65011)
  • 10. -, Analysis of convergence of the $ {T}$-transformation for power series, Math. Comp. 35 (1980), 833-850. MR 572860 (83d:41039)
  • 11. -, Extrapolation methods for oscillatory infinite integrals, J. Inst. Math. Appl. 26 (1980), 1-20. MR 594340 (81m:40002)
  • 12. -, The numerical evaluation of very oscillatory infinite integrals by extrapolation, Math. Comp. 38 (1982), 517-529. MR 645667 (83i:65023)
  • 13. -, A user-friendly extrapolation method for oscillatory infinite integrals, Math. Comp. 51 (1988), 249-266. MR 942153 (89e:65029)
  • 14. -, Acceleration of convergence of (generalized) Fourier series by the $ d$-transformation, Annals Numer. Math. 2 (1995), 381-406. MR 1343544 (96h:65005)
  • 15. -, Convergence analysis for a generalized Richardson extrapolation process with an application to the $ d^{(1)}$-transformation on convergent and divergent logarithmic sequences, Math. Comp. 64 (1995), 1627-1657. MR 1312099 (96a:65009)
  • 16. -, Further results on convergence and stability of a generalization of the Richardson extrapolation process, BIT Numerical Mathematics 36 (1996), 143-157. MR 1431580 (98f:65006)
  • 17. -, Computation of infinite integrals involving Bessel functions of arbitrary order by the $ \bar{D}$-transformation, J. Comp. Appl. Math. 78 (1997), 125-130. MR 1436784 (97k:65058)
  • 18. -, Further convergence and stability results for the generalized Richardson extrapolation process GREP$ ^{(1)}$ with an application to the $ D^{(1)}$-transformation for infinite integrals, J. Comp. Appl. Math. 112 (1999), 269-290. MR 1728465 (2000k:65045)
  • 19. -, Practical extrapolation methods: Theory and applications, Cambridge Monographs on Applied and Computational Mathematics, no. 10, Cambridge University Press, Cambridge, 2003. MR 1994507 (2004e:65005)
  • 20. A. Sidi and D. Levin, Rational approximations from the $ d$-transformation, IMA J. Numer. Anal. 2 (1982), 153-167. MR 668590 (83j:65012)
  • 21. J. Stoer and R. Bulirsch, Introduction to numerical analysis, third ed., Springer-Verlag, New York, 2002. MR 1923481 (2003d:65001)

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.

American Mathematical Society