Copyright Â© 2003 Elsevier B.V. All rights reserved
Volume 122, Issues 1-2, Pages 1-357 (1 October 2000)
Display Checked Docs | E-mail Articles | Export Citations
Convergence acceleration during the 20th century, Pages 1-21
e C. Brezinski
SummaryPlus | Full Text + Links | PDF (139 K)
On the history of multivariate polynomial interpolation, Pages 23-35
e Mariano Gasca and Thomas Sauer
SummaryPlus | Full Text + Links | PDF (109 K)
Elimination techniques: from extrapolation to totally positive matrices and CAGD, Pages 37-50
e M. Gasca and G. MÃ¼hlbach
Abstract | PDF (116 K)
The epsilon algorithm and related topics, Pages 51-80
e P. R. Graves-Morris, D. E. Roberts and A. Salam
SummaryPlus | Full Text + Links | PDF (256 K)
Scalar Levin-type sequence transformations, Pages 81-147
f Herbert H. H. Homeier
Abstract | PDF (428 K)
Vector extrapolation methods. Applications and numerical comparison, Pages 149-165
e K. Jbilou and H. Sadok
SummaryPlus | Full Text + Links | PDF (125 K)
Multivariate Hermite interpolation by algebraic polynomials: A survey, Pages 167-201
g R. A. Lorentz
SummaryPlus | Full Text + Links | PDF (222 K)
Interpolation by Cauchyâ€“Vandermonde systems and applications, Pages 203-222
f G. MÃ¼hlbach
SummaryPlus | Full Text + Links | PDF (165 K)
The E-algorithm and the Fordâ€“Sidi algorithm, Pages 223-230
e Naoki Osada
SummaryPlus | Full Text + Links | PDF (76 K)
Diophantine approximations using PadÃ© approximations, Pages 231-250
e M. PrÃ©vost
SummaryPlus | Full Text + Links | PDF (157 K)
The generalized Richardson extrapolation process GREP(1) and computation of derivatives of limits of sequences
with applications to the d(1)-transformation, Pages 251-273
SummaryPlus | Full Text + Links | PDF (185 K)
Matrix Hermiteâ€“PadÃ© problem and dynamical systems, Pages 275-295
Vladimir Sorokin and Jeannette Van Iseghem
SummaryPlus | Full Text + Links | PDF (156 K)
Numerical analysis of the non-uniform sampling problem, Pages 297-316
e Thomas Strohmer
SummaryPlus | Full Text + Links | PDF (523 K)
Asymptotic expansions for multivariate polynomial approximation, Pages 317-328
e Guido Walz
SummaryPlus | Full Text + Links | PDF (95 K)
2 process, of Wynn's epsilon algorithm, and of Brezinski's iterated
Prediction properties of Aitken's iterated
theta algorithm, Pages 329-356
Ernst Joachim Weniger
SummaryPlus | Full Text + Links | PDF (189 K)
Index, Page 357
PDF (31 K)
Numerical Analysis 2000 Vol. II: Interpolation and extrapolation, Pages ix-xi
g C. Brezinski
SummaryPlus | Full Text + Links | PDF (34 K)
Journal of Computational and Applied Mathematics 122 (2000) ixâ€“xi
Numerical Analysis 2000
Vol. II: Interpolation and extrapolation
Laboratoire dâ€™Analyse NumÃƒ rique et dâ€™Optimisation, UniversitÃƒ des Sciences et Technologies de Lille,
59655 Villeneuve dâ€™Ascq Cedex, France
This volume is dedicated to two closely related subjects: interpolation and extrapolation. The
papers can be divided into three categories: historical papers, survey papers and papers presenting
Interpolation is an old subject since, as noticed in the paper by M. Gasca and T. Sauer, the
term was coined by John Wallis in 1655. Interpolation was the Ã¿rst technique for obtaining an
approximation of a function. Polynomial interpolation was then used in quadrature methods and
methods for the numerical solution of ordinary di erential equations.
Obviously, some applications need interpolation by functions more complicated than polynomials.
The case of rational functions with prescribed poles is treated in the paper by G. Muhlbach. He
gives a survey of interpolation procedures using Cauchyâ€“Vandermonde systems. The well-known
formulae of Lagrange, Newton and Nevilleâ€“Aitken are generalized. The construction of rational
B-splines is discussed.
Trigonometric polynomials are used in the paper by T. Strohmer for the reconstruction of a signal
from non-uniformly spaced measurements. They lead to a well-posed problem that preserves some
important structural properties of the original inÃ¿nite dimensional problem.
More recently, interpolation in several variables was studied. It has applications in Ã¿nite di erences
and Ã¿nite elements for solving partial di erential equations. Following the pioneer works of P. de
Casteljau and P. BÃƒ zier, another very important domain where multivariate interpolation plays a
fundamental role is computer-aided geometric design (CAGD) for the approximation of surfaces.
The history of multivariate polynomial interpolation is related in the paper by M. Gasca and T.
The paper by R.A. Lorentz is devoted to the historical development of multivariate Hermite
interpolation by algebraic polynomials.
In his paper, G. Walz treats the approximation of multivariate functions by multivariate Bernstein
polynomials. An asymptotic expansion of these polynomials is given and then used for building, by
extrapolation, a new approximation method which converges much faster.
E-mail address: Claude.Brezinski@univ-lille1.fr (C. Brezinski).
0377-0427/00/$ - see front matter c 2000 Elsevier Science B.V. All rights reserved.
PII: S 0 3 7 7 - 0 4 2 7 ( 0 0 ) 0 0 3 5 2 - 6
x Preface / Journal of Computational and Applied Mathematics 122 (2000) ixâ€“xi
Extrapolation is based on interpolation. In fact, extrapolation consists of interpolation at a point
outside the interval containing the interpolation points. Usually, this point is either zero or inÃ¿nity.
Extrapolation is used in numerical analysis to improve the accuracy of a process depending of
a parameter or to accelerate the convergence of a sequence. The most well-known extrapolation
processes are certainly Rombergâ€™s method for improving the convergence of the trapezoidal rule for
the computation of a deÃ¿nite integral and Aitkenâ€™s 2 process which can be found in any textbook
of numerical analysis.
An historical account of the development of the subject during the 20th century is given in the
paper by C. Brezinski.
The theory of extrapolation methods lays on the solution of the system of linear equations corre-
sponding to the interpolation conditions. In their paper, M. Gasca and G. Muhlbach show, by using
elimination techniques, the connection between extrapolation, linear systems, totally positive matrices
There exist many extrapolation algorithms. From a Ã¿nite section Sn ; : : : ; Sn+k of the sequence (Sn ),
they built an improved approximation of its limit S. This approximation depends on n and k. When
at least one of these indexes goes to inÃ¿nity, a new sequence is obtained with, possibly, a faster
In his paper, H.H.H. Homeier studies scalar Levin-type acceleration methods. His approach is based
on the notion of remainder estimate which allows to use asymptotic information on the sequence to
built an e cient extrapolation process.
The most general extrapolation process known so far is the sequence transformation known under
the name of E-algorithm. It can be implemented by various recursive algorithms. In his paper,
N. Osada proved that the E-algorithm is mathematically equivalent to the Fordâ€“Sidi algorithm. A
slightly more economical algorithm is also proposed.
When S depends on a parameter t, some applications need the evaluation of the derivative of S
with respect to t. A generalization of Richardson extrapolation process for treating this problem is
considered in the paper by A. Sidi.
Instead of being used for estimating the limit S of a sequence from Sn ; : : : ; Sn+k , extrapolation
methods can also be used for predicting the next unknown terms Sn+k+1 ; Sn+k+2 ; : : :. The prediction
properties of some extrapolation algorithms are analyzed in the paper by E.J. Weniger.
Quite often in numerical analysis, sequences of vectors have to be accelerated. This is, in particular,
the case in iterative methods for the solution of systems of linear and nonlinear equations.
Vector acceleration methods are discussed in the paper by K. Jbilou and H. Sadok. Using projec-
tors, they derive a di erent interpretation of these methods and give some theoretical results. Then,
various algorithms are compared when used for the solution of large systems of equations coming
out from the discretization of partial di erential equations.
Another point of view is taken in the paper by P.R. Graves-Morris, D.E. Roberts and A. Salam.