. 1
( 83 .)


Journal of Computational and Applied Mathematics
Copyright © 2003 Elsevier B.V. All rights reserved

Volume 122, Issues 1-2, Pages 1-357 (1 October 2000)

View: Citations
Display Checked Docs | E-mail Articles | Export Citations

Convergence acceleration during the 20th century, Pages 1-21
1. f
e C. Brezinski
SummaryPlus | Full Text + Links | PDF (139 K)

On the history of multivariate polynomial interpolation, Pages 23-35
2. f
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
3. f
e M. Gasca and G. Mühlbach
Abstract | PDF (116 K)

The epsilon algorithm and related topics, Pages 51-80
4. f
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
5. g
f Herbert H. H. Homeier
Abstract | PDF (428 K)

Vector extrapolation methods. Applications and numerical comparison, Pages 149-165
6. f
e K. Jbilou and H. Sadok
SummaryPlus | Full Text + Links | PDF (125 K)

Multivariate Hermite interpolation by algebraic polynomials: A survey, Pages 167-201
7. e
g R. A. Lorentz
SummaryPlus | Full Text + Links | PDF (222 K)

Interpolation by Cauchy“Vandermonde systems and applications, Pages 203-222
8. g
f G. Mühlbach
SummaryPlus | Full Text + Links | PDF (165 K)

The E-algorithm and the Ford“Sidi algorithm, Pages 223-230
9. f
e Naoki Osada
SummaryPlus | Full Text + Links | PDF (76 K)

Diophantine approximations using Pad© approximations, Pages 231-250
10. f
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
11. g
with applications to the d(1)-transformation, Pages 251-273
Avram Sidi
SummaryPlus | Full Text + Links | PDF (185 K)
Matrix Hermite“Pad© problem and dynamical systems, Pages 275-295
12. f
Vladimir Sorokin and Jeannette Van Iseghem
SummaryPlus | Full Text + Links | PDF (156 K)

Numerical analysis of the non-uniform sampling problem, Pages 297-316
13. f
e Thomas Strohmer
SummaryPlus | Full Text + Links | PDF (523 K)

Asymptotic expansions for multivariate polynomial approximation, Pages 317-328
14. f
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
15. f
theta algorithm, Pages 329-356
Ernst Joachim Weniger
SummaryPlus | Full Text + Links | PDF (189 K)

Index, Page 357
16. f
e Unknown
PDF (31 K)

Numerical Analysis 2000 Vol. II: Interpolation and extrapolation, Pages ix-xi
17. f
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
C. Brezinski
Laboratoire d™Analyse Numà rique et d™Optimisation, Università des Sciences et Technologies de Lille,
e e
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
new developments.
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
and CAGD.
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.

. 1
( 83 .)