Mathematics of Computation

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



Extrapolation methods and derivatives
of limits of sequences

Author: Avram Sidi
Journal: Math. Comp. 69 (2000), 305-323
MSC (1991): Primary 40A25, 41A60, 65B05, 65B10, 65D30
Published electronically: August 17, 1999
MathSciNet review: 1665967
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\{S_m\}$ be an infinite sequence whose limit or antilimit $S$ can be approximated very efficiently by applying a suitable extrapolation method E$_0$ to $\{S_m\}$. Assume that the $S_m$ and hence also $S$ are differentiable functions of some parameter $\xi$, $\frac{d}{d\xi}S$ being the limit or antilimit of $\{\frac{d}{d\xi}S_m\}$, and that we need to approximate $\frac{d}{d\xi}S$. A direct way of achieving this would be by applying again a suitable extrapolation method E$_1$ to the sequence $\{\frac{d}{d\xi}S_m\}$, 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 $\frac{d}{d\xi}S_m$ and $S_m$ have essentially different asymptotic behaviors as $m\rightarrow\infty$, the approximations to $\frac{d}{d\xi}S$ produced by this approach, despite the fact that they are good, do not converge as quickly as those obtained for $S$, and this is puzzling. In this paper we first give a rigorous mathematical explanation of this phenomenon for the cases in which E$_0$ is the Richardson extrapolation process and E$_1$ 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$_0$ to $\{S_m\}$ and then differentiating the resulting approximations to $S$, 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 $\frac{d}{d\xi}S$ has practically the same convergence properties as E$_0$ for $S$. 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.

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

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

Received by editor(s): March 26, 1998
Published electronically: August 17, 1999
Article copyright: © Copyright 1999 American Mathematical Society