Extrapolation methods and derivatives of limits of sequences
Author:
Avram Sidi
Journal:
Math. Comp. 69 (2000), 305323
MSC (1991):
Primary 40A25, 41A60, 65B05, 65B10, 65D30
Published electronically:
August 17, 1999
MathSciNet review:
1665967
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be an infinite sequence whose limit or antilimit can be approximated very efficiently by applying a suitable extrapolation method E to . Assume that the and hence also are differentiable functions of some parameter , being the limit or antilimit of , and that we need to approximate . A direct way of achieving this would be by applying again a suitable extrapolation method E to the sequence , and this approach has often been used efficiently in various problems of practical importance. Unfortunately, as has been observed at least in some important cases, when and have essentially different asymptotic behaviors as , the approximations to produced by this approach, despite the fact that they are good, do not converge as quickly as those obtained for , and this is puzzling. In this paper we first give a rigorous mathematical explanation of this phenomenon for the cases in which E is the Richardson extrapolation process and E is a generalization of it, thus showing that the phenomenon has very little to do with numerics. Following that, we propose a procedure that amounts to first applying the extrapolation method E to and then differentiating the resulting approximations to , and we provide a thorough convergence and stability analysis in conjunction with the Richardson extrapolation process. It follows from this analysis that the new procedure for has practically the same convergence properties as E for . We show that a very efficient way of implementing the new procedure is by actually differentiating the recursion relations satisfied by the extrapolation method used, and we derive the necessary algorithm for the Richardson extrapolation process. We demonstrate the effectiveness of the new approach with numerical examples that also support the theory. We discuss the application of this approach to numerical integration in the presence of endpoint singularities. We also discuss briefly its application in conjunction with other extrapolation methods.
 [BRS]
F.
L. Bauer, H.
Rutishauser, and E.
Stiefel, New aspects in numerical quadrature, Proc. Sympos.
Appl. Math., Vol. XV, Amer. Math. Soc., Providence, R.I., 1963,
pp. 199–218. MR 0174177
(30 #4384)
 [B1]
Claude
Brezinski, Accélération de suites à
convergence logarithmique, C. R. Acad. Sci. Paris Sér. AB
273 (1971), A727–A730 (French). MR 0305544
(46 #4674)
 [B2]
C.
Brezinski, A general extrapolation algorithm, Numer. Math.
35 (1980), no. 2, 175–187. MR 585245
(81j:65015), http://dx.doi.org/10.1007/BF01396314
 [BS]
Roland
Bulirsch and Josef
Stoer, Fehlerabschätzungen und Extrapolation mit rationalen
Funktionen bei Verfahren vom RichardsonTypus, Numer. Math.
6 (1964), 413–427. MR 0176589
(31 #861)
 [DR]
Philip
J. Davis and Philip
Rabinowitz, Methods of numerical integration, 2nd ed.,
Computer Science and Applied Mathematics, Academic Press, Inc., Orlando,
FL, 1984. MR
760629 (86d:65004)
 [FS]
William
F. Ford and Avram
Sidi, An algorithm for a generalization of the Richardson
extrapolation process, SIAM J. Numer. Anal. 24
(1987), no. 5, 1212–1232. MR 909075
(89a:65006), http://dx.doi.org/10.1137/0724080
 [H]
T.
Hȧvie, Generalized Neville type extrapolation schemes,
BIT 19 (1979), no. 2, 204–213. MR 537780
(80f:65005), http://dx.doi.org/10.1007/BF01930850
 [L]
J.
N. Lyness, An error functional expansion for
𝑁dimensional quadrature with an integrand function singular at a
point, Math. Comp. 30
(1976), no. 133, 1–23. MR 0408211
(53 #11976), http://dx.doi.org/10.1090/S00255718197604082110
 [LM]
J.
N. Lyness and G.
Monegato, Quadrature error functional expansions
for the simplex when the integrand function has singularities at
vertices, Math. Comp. 34
(1980), no. 149, 213–225. MR 551299
(80m:65017), http://dx.doi.org/10.1090/S00255718198005512998
 [LN]
J.
N. Lyness and B.
W. Ninham, Numerical quadrature and asymptotic
expansions, Math. Comp. 21 (1967), 162–178. MR 0225488
(37 #1081), http://dx.doi.org/10.1090/S0025571819670225488X
 [N1]
Israel
Navot, An extension of the EulerMaclaurin summation formula to
functions with a branch singularity, J. Math. and Phys.
40 (1961), 271–276. MR 0140876
(25 #4290)
 [N2]
I. Navot, A further extension of the EulerMaclaurin summation formula, J. Math. and Phys., 41 (1962), pp. 305323.
 [Sc]
Claus
Schneider, Vereinfachte Rekursionen zur RichardsonExtrapolation in
Spezialfällen, Numer. Math. 24 (1975),
no. 2, 177–184 (German, with English summary). MR 0378342
(51 #14510)
 [Sh]
Peter
Naur, The energy production in convective cores in stars,
Danske Vid. Selsk. Mat.Fys. Medd. 29 (1954), no. 5,
14. MR
0068899 (16,961c)
 [Si1]
Avram
Sidi, EulerMaclaurin expansions for integrals over triangles and
squares of functions having algebraic/logarithmic singularities along an
edge, J. Approx. Theory 39 (1983), no. 1,
39–53. MR
713360 (84j:65026), http://dx.doi.org/10.1016/00219045(83)900679
 [Si2]
Avram
Sidi, Generalizations of Richardson extrapolation with applications
to numerical integration, Numerical integration, III (Oberwolfach,
1987) Internat. Schriftenreihe Numer. Math., vol. 85,
Birkhäuser, Basel, 1988, pp. 237–250. MR 1021539
(90k:65076)
 [Si3]
Avram
Sidi, A complete convergence and stability theory for a generalized
Richardson extrapolation process, SIAM J. Numer. Anal.
34 (1997), no. 5, 1761–1778. MR 1472195
(98g:65012), http://dx.doi.org/10.1137/S0036142994278589
 [W]
P.
Wynn, On a device for computing the
𝑒_{𝑚}(𝑆_{𝑛}) tranformation, Math. Tables Aids Comput. 10 (1956), 91–96. MR 0084056
(18,801e), http://dx.doi.org/10.1090/S00255718195600840566
 [BRS]
 F.L. Bauer, H. Rutishauser, and E. Stiefel, New aspects in numerical quadrature, in Experimental Arithmetic, High Speed Computing, and Mathematics, Proc. Sympos. Appl. Math., vol. 15, AMS, Providence, Rhode Island, 1963, pp.199218. MR 30:4384
 [B1]
 C. Brezinski, Accélération de suites à convergence logarithmique, C.R. Acad. Sci. Paris, 273 (1971), pp. A727A730. MR 46:4674
 [B2]
 C. Brezinski, A general extrapolation algorithm, Numer. Math., 35 (1980), pp. 305323. MR 81j:65015
 [BS]
 R. Bulirsch and J. Stoer, Fehlerabschätzungen und Extrapolation mit rationalen Funktionen bei Verfahren vom RichardsonTypus, Numer. Math., 6 (1964), pp. 305323. MR 31:861
 [DR]
 P.J. Davis and P. Rabinowitz, Methods of Numerical Integration, 2nd edition, Academic Press, New York, 1984. MR 86d:65004
 [FS]
 W.F. Ford and A. Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer. Anal., 24 (1987), pp. 305323. MR 89a:65006
 [H]
 T. Håvie, Generalized Neville type extrapolation schemes, BIT, 19 (1979), pp. 305323. MR 80f:65005
 [L]
 J.N. Lyness, An error functional expansion for dimensional quadrature with an integrand function singular at a point, Math. Comp., 30 (1976), pp. 305323. MR 53:11976
 [LM]
 J.N. Lyness and G. Monegato, Quadrature error functional expansions for the simplex when the integrand function has singularities at vertices, Math. Comp., 34 (1980), pp. 305323. MR 80m:65017
 [LN]
 J.N. Lyness and B.W. Ninham, Numerical quadrature and asymptotic expansions, Math. Comp., 21 (1967), pp. 305323. MR 37:1081
 [N1]
 I. Navot, An extension of the EulerMaclaurin summation formula to functions with a branch singularity, J. Math. and Phys., 40 (1961), pp. 305323. MR 25:4290
 [N2]
 I. Navot, A further extension of the EulerMaclaurin summation formula, J. Math. and Phys., 41 (1962), pp. 305323.
 [Sc]
 C. Schneider, Vereinfachte Rekursionen zur RichardsonExtrapolation in Spezialfällen, Numer. Math., 24 (1975), pp. 305323. MR 51:14510
 [Sh]
 D. Shanks, Nonlinear transformations of divergent and slowly convergent sequences, J. Math. and Phys., 34 (1955), pp. 305323. MR 16:961c
 [Si1]
 A. Sidi, EulerMaclaurin expansions for integrals over triangles and squares of functions having algebraic/logarithmic singularities along an edge, J. Approx. Th., 39 (1983), pp. 305323. MR 84j:65026
 [Si2]
 A. Sidi, Generalizations of Richardson extrapolation with applications to numerical integration, in Numerical Integration III, ISNM Vol. 85, H. Brass and G. Hämmerlin, eds., Birkhäuser, Basel, Switzerland, 1988, pp. 237250. MR 90k:65076
 [Si3]
 A. Sidi, A complete convergence and stability theory for a generalized Richardson extrapolation process, SIAM J. Numer. Anal., 34 (1997), pp. 305323. MR 98g:65012
 [W]
 P. Wynn, On a device for computing the transformation, Math. Comp., 10 (1956), pp. 305323. MR 18:801e
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
40A25,
41A60,
65B05,
65B10,
65D30
Retrieve articles in all journals
with MSC (1991):
40A25,
41A60,
65B05,
65B10,
65D30
Additional Information
Avram Sidi
Affiliation:
Computer Science Department, Technion—Israel Institute of Technology, Haifa 32000, Israel
Email:
asidi@cs.technion.ac.il
DOI:
http://dx.doi.org/10.1090/S0025571899011692
PII:
S 00255718(99)011692
Received by editor(s):
March 26, 1998
Published electronically:
August 17, 1999
Article copyright:
© Copyright 1999
American Mathematical Society
