ñòð. 1 |

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

g

c

d

e C. Brezinski

SummaryPlus | Full Text + Links | PDF (139 K)

On the history of multivariate polynomial interpolation, Pages 23-35

2. f

g

c

d

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

g

c

d

e M. Gasca and G. MÃ¼hlbach

Abstract | PDF (116 K)

The epsilon algorithm and related topics, Pages 51-80

4. f

g

c

d

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

c

d

e

f Herbert H. H. Homeier

Abstract | PDF (428 K)

Vector extrapolation methods. Applications and numerical comparison, Pages 149-165

6. f

g

c

d

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

f

c

d

g R. A. Lorentz

SummaryPlus | Full Text + Links | PDF (222 K)

Interpolation by Cauchyâ€“Vandermonde systems and applications, Pages 203-222

8. g

c

d

e

f G. MÃ¼hlbach

SummaryPlus | Full Text + Links | PDF (165 K)

The E-algorithm and the Fordâ€“Sidi algorithm, Pages 223-230

9. f

g

c

d

e Naoki Osada

SummaryPlus | Full Text + Links | PDF (76 K)

Diophantine approximations using PadÃ© approximations, Pages 231-250

10. f

g

c

d

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

e

c

d

f

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

g

c

d

e

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

g

c

d

e Thomas Strohmer

SummaryPlus | Full Text + Links | PDF (523 K)

Asymptotic expansions for multivariate polynomial approximation, Pages 317-328

14. f

g

c

d

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

g

c

d

e

theta algorithm, Pages 329-356

Ernst Joachim Weniger

SummaryPlus | Full Text + Links | PDF (189 K)

Index, Page 357

16. f

g

c

d

e Unknown

PDF (31 K)

Numerical Analysis 2000 Vol. II: Interpolation and extrapolation, Pages ix-xi

17. f

c

d

e

g C. Brezinski

SummaryPlus | Full Text + Links | PDF (34 K)

Journal of Computational and Applied Mathematics 122 (2000) ixâ€“xi

www.elsevier.nl/locate/cam

Preface

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

e

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.

Sauer.

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

convergence.

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 |