[114] R. Pennacchi, Le trasformazioni razionali di una successione, Calcolo 5 (1968) 37“50.

20 C. Brezinski / Journal of Computational and Applied Mathematics 122 (2000) 1“21

[115] R. Powell, S.M. Shah, Summability Theory and its Applications, Van Nostrand Reinhold, London, 1972.

[116] M. PrÃ vost, Acceleration property for the E-algorithm and an application to the summation of series, Adv. Comput.

e

Math. 2 (1994) 319“341.

[117] J.D. Pryce, Numerical Solution of Sturm“Liouville Problems, Clarendon Press, Oxford, 1993.

[118] B. Rhanizar, On extrapolation methods in optimization, Appl. Numer. Math. 25 (1997) 485“498.

[119] L.F. Richardson, The approximate arithmetical solution by ÿnite di erence of physical problems involving di erential

equations, with an application to the stress in a masonry dam, Philos. Trans. Roy. Soc. London, Ser. A 210 (1910)

307“357.

[120] L.F. Richardson, The deferred approach to the limit. I: Single lattice, Philos. Trans. Roy. Soc. London, Ser. A 226

(1927) 299“349.

[121] W. Romberg, Vereinfachte numerische Integration, Kgl. Norske Vid. Selsk. Forsk. 28 (1955) 30“36.

[122] H. Rutishauser, Ausdehnung des Rombergschen Prinzips, Numer. Math. 5 (1963) 48“54.

[123] H. Sadok, Quasilinear vector extrapolation methods, Linear Algebra Appl. 190 (1993) 71“85.

[124] A. Salam, Non-commutative extrapolation algorithms, Numer. Algorithms 7 (1994) 225“251.

[125] A. Salam, An algebraic approach to the vector -algorithm, Numer. Algorithms 11 (1996) 327“337.

[126] P.R. Graves-Morris, D.E. Roberts, A. Salam, The epsilon algorithm and related topics, J. Comput. Appl. Math. 122

(2000).

[127] J.R. Schmidt, On the numerical solution of linear simultaneous equations by an iterative method, Philos. Mag. 7

(1941) 369“383.

[128] C. Schneider, Vereinfachte Rekursionen zur Richardson-Extrapolation in Spezialfallen, Numer. Math. 24 (1975)

177“184.

[129] M.N. Senhadji, On condition numbers of some quasi-linear transformations, J. Comput. Appl. Math. 104 (1999)

1“19.

[130] D. Shanks, An analogy between transient and mathematical sequences and some nonlinear sequence-to-sequence

transforms suggested by it, Part I, Memorandum 9994, Naval Ordnance Laboratory, White Oak, July 1949.

[131] D. Shanks, Non linear transformations of divergent and slowly convergent sequences, J. Math. Phys. 34 (1955)

1“42.

[132] W.F. Sheppard, Some quadrature formulas, Proc. London Math. Soc. 32 (1900) 258“277.

[133] A. Sidi, Extrapolation vs. projection methods for linear systems of equations, J. Comput. Appl. Math. 22 (1988)

71“88.

[134] A. Sidi, On a generalization of the Richardson extrapolation process, Numer. Math. 57 (1990) 365“377.

[135] A. Sidi, Further results on convergence and stability of a generalization of the Richardson extrapolation process,

BIT 36 (1996) 143“157.

[136] A. Sidi, A complete convergence and stability theory for a generalized Richardson extrapolation process, SIAM J.

Numer. Anal. 34 (1997) 1761“1778.

[137] A. Sidi, D. Levin, Prediction properties of the t-transformation, SIAM J. Numer. Anal. 20 (1983) 589“598.

[138] E. Stiefel, Altes und neues uber numerische Quadratur, Z. Angew. Math. Mech. 41 (1961) 408“413.

[139] M. Toda, Waves in nonlinear lattice, Prog. Theor. Phys. Suppl. 45 (1970) 174“200.

[140] J. van Iseghem, Convergence of vectorial sequences, applications, Numer. Math. 68 (1994) 549“562.

[141] D. Vekemans, Algorithm for the E-prediction, J. Comput. Appl. Math. 85 (1997) 181“202.

[142] P. Verlinden, Acceleration of Gauss“Legendre quadrature for an integral with an endpoint singularity, J. Comput.

Appl. Math. 77 (1997) 277“287.

[143] G. Walz, The history of extrapolation methods in numerical analysis, Report No. 130, Universitat Mannheim,

Fakultat fur Mathematik und Informatik, 1991.

[144] G. Walz, Asymptotics and Extrapolation, Akademie, Berlin, 1996.

[145] E.J. Weniger, Nonlinear sequence transformations for the acceleration of convergence and the summation of

divergent series, Comput. Phys. Rep. 10 (1989) 189“371.

[146] J. Wimp, Sequence Transformations and their Applications, Academic Press, New York, 1981.

[147] P. Wynn, On a device for computing the em (Sn ) transformation, MTAC 10 (1956) 91“96.

[148] P. Wynn, On a procrustean technique for the numerical transformation of slowly convergent sequences and series,

Proc. Cambridge Philos. Soc. 52 (1956) 663“671.

[149] P. Wynn, Con uent forms of certain non-linear algorithms, Arch. Math. 11 (1960) 223“234.

C. Brezinski / Journal of Computational and Applied Mathematics 122 (2000) 1“21 21

[150] P. Wynn, Acceleration techniques for iterated vector and matrix problems, Math. Comput. 16 (1962) 301“322.

[151] P. Wynn, Singular rules for certain non-linear algorithms, BIT 3 (1963) 175“195.

[152] P. Wynn, Partial di erential equations associated with certain non-linear algorithms, ZAMP 15 (1964) 273“289.

[153] P. Wynn, Upon systems of recursions which obtain among the quotients of the PadÃ table, Numer. Math. 8 (1966)

e

264“269.

[154] P. Wynn, On the convergence and stability of the epsilon algorithm, SIAM J. Numer. Anal. 3 (1966) 91“122.

[155] M. Redivo Zaglia, Particular rules for the ‚-algorithm, Numer. Algorithms 3 (1992) 353“370.

Journal of Computational and Applied Mathematics 122 (2000) 23“35

www.elsevier.nl/locate/cam

On the history of multivariate polynomial interpolation

Mariano Gascaa; — , Thomas Sauerb

a

Department of Applied Mathematics, University of Zaragoza, 50009 Zaragoza, Spain

b

Institute of Mathematics, University Erlangen-Nurnberg, Bismarckstr. 1 1 , D-91054 Erlangen, Germany

2

Received 7 June 1999; received in revised form 8 October 1999

Abstract

Multivariate polynomial interpolation is a basic and fundamental subject in Approximation Theory and Numerical

Analysis, which has received and continues receiving not deep but constant attention. In this short survey, we review its

development in the ÿrst 75 years of this century, including a pioneering paper by Kronecker in the 19th century. c 2000

Elsevier Science B.V. All rights reserved.

1. Introduction

Interpolation, by polynomials or other functions, is a rather old method in applied mathemat-

ics. This is already indicated by the fact that, apparently, the word “interpolation” itself has been

introduced by J. Wallis as early as 1655 as it is claimed in [13]. Compared to this, polynomial

interpolation in several variables is a relatively new topic and probably only started in the second-half

of the last century with work in [6,22]. If one considers, for example, the Encyklopadie der Mathe-

matischen Wissenschaften [13] (Encyclopedia of Math. Sciences), originated by the Preu ische

Akademie der Wissenschaften (Prussian Academy of Sciences) to sum up the “state of art” of

mathematics at its time, then the part on interpolation, written by J. Bauschinger (Bd. I, Teil 2),

mentions only one type of multivariate interpolation, namely (tensor) products of sine and co-

sine functions in two variables, however, without being very speciÿc. The French counterpart, the

EncyclopÃ die de Sciences Mathematiques [14], also contains a section on interpolation (Tome I,

e

vol. 4), where Andoyer translated and extended Bauschinger™s exposition. Andoyer is even more

—

Corressponding author.

E-mail addresses: gasca@posta.unizar.es (M. Gasca), sauer@mi.uni-erlangen.de (T. Sauer).

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 3 - 8

24 M. Gasca, T. Sauer / Journal of Computational and Applied Mathematics 122 (2000) 23“35

explicit with his opinion on multivariate polynomial interpolation, by making the following statement

which we think that time has contradicted:

Il est manifeste que l™interpolation des fonctions de plusiers variables ne demande aucun principe

nouveau, car dans tout ce qui prÃ c‚ de le fait que la variable indÃ pendante etait unique n™a

ee e Ã

1

souvent jouÃ aucun rˆ le.

e o

Nevertheless, despite of Andoyer™s negative assessment, multivariate polynomial interpolation has

received not deep but constant attention from one part of the mathematical community and is to-

day a basic subject in Approximation Theory and Numerical Analysis with applications to many

mathematical problems. Of course, this ÿeld has deÿnitely been in uenced by the availability of

computational facilities, and this is one of the reasons that more papers have been published about

this subject in the last 25 years than in the preceding 75 ones.

To our knowledge, there is not any paper before the present one surveying the early papers and

books on multivariate polynomial interpolation. Our aim is a ÿrst, modest attempt to cover this

gap. We do not claim to be exhaustive and, in particular, recognize our limitations with respect

to the Russian literature. Moreover, it has to be mentioned that the early results on multivariate

interpolation usually appear in the context of many di erent subjects. For example, papers on cubature

formulas frequently have some part devoted to it. Another connection is Algebraic Geometry, since

the solvability of a multivariate interpolation problem relies on the fact that the interpolation points

do not lie on an algebraic surface of a certain type. So it is di cult to verify precisely if and

when a result appeared somewhere for the ÿrst time or if it had already appeared, probably even

in an implicit way, in a di erent context. We remark that another paper in this volume [25] deals,

complementarily, with recent results in the subject, see also [16].

d

Along the present paper we denote by k the space of d-variate polynomials of total degree not

greater than k.

2. Kronecker, Jacobi and multivariate interpolation

Bivariate interpolation by the tensor product of univariate interpolation functions, that is when

the variables are treated separately, is the classical approach to multivariate interpolation. However,

when the set of interpolation points is not a Cartesian product grid, it is impossible to use that idea.

Today, given any set of interpolation points, there exist many methods 2 to construct an adequate

polynomial space which guarantees unisolvence of the interpolation problem. Surprisingly, this idea

of constructing an appropriate interpolation space was already pursued by Kronecker [22] in a

widely unknown paper from 1865, which seems to be the ÿrst treatment of multivariate polynomial

interpolation with respect to fairly arbitrary point conÿgurations. Besides the mathematical elegance

of this approach, we think it is worthwhile to devote some detailed attention to this paper and to

resolve its main ideas in today™s terminology, in particular, as it uses the “modern” approach of

connecting polynomial interpolation to the theory of polynomial ideals.

1

It is clear that the interpolation of functions of several variables does not demand any new principles because in the

above exposition the fact that the variable was unique has not played frequently any role.

2

See [16,25] for exposition and references.

M. Gasca, T. Sauer / Journal of Computational and Applied Mathematics 122 (2000) 23“35 25

Kronecker™s method to construct an interpolating polynomial assumes that the disjoint nodes

z1 ; : : : ; zN ∈ Cd are given in implicit form, i.e., they are (all) the common simple zeros of d poly-

nomials f ; : : : ; f ∈ C[z] = C[ 1 ; : : : ; d ]. Note that the nonlinear system of equations

1 d

f( 1; : : : ; d) = 0; j = 1; : : : ; d; (1)

j

is a square one, that is, the number of equations and the number of variables coincide. We are

interested in the ÿnite variety V of solutions of (1) which is given as

V :={z1 ; : : : ; zN } = {z ∈ Cd : f (z) = · · · = f (z) = 0}: (2)

1 d

The primary decomposition according to the variety V allows us to write the ideal I(V )={p : p(z)=

0; z ∈ V } as

N

I(V ) = ’ k; 1 ; : : : ; d ’ ;

1 k; d

k=1

where zk = ( k; 1 ; : : : ; k; d ). In other words, since f ∈ I(V ), k = 1; : : : ; d, any of the polynomials

k

f ; : : : ; f can be written, for k = 1; : : : ; N , as

1 d

d

k

f= gi; j (·)( i ’ k; i ); (3)

j

i=1

k

where gi; j are appropriate polynomials. Now consider the d — d square matrices of polynomials

k

Gk = [gi; j : i; j = 1; : : : ; d]; k = 1; : : : ; N

and note that, due to (3), and the assumption that f (zk ) = 0; j = 1; : : : ; d; k = 1; : : : ; N , we have

j

® ®

f (Zj ) ( ’ k; 1 )

1 j; 1

0 = ° . » = Gk (zj ) ° .

.

. »; k = 1; : : : ; N: (4)

. .

f (zj ) ( ’ k; d )

d j; d

Since the interpolation nodes are assumed to be disjoint, this means that for all j = k the matrix

Gk (zj ) is singular, hence the determinant of Gk (zj ) has to be zero. Moreover, the assumption that

z1 ; : : : ; zN are simple zeros guarantees that det Gk (zk ) = 0. Then, Kronecker™s interpolant takes, for

any f : Cd ’ C, the form

N

det Gk (·)

Kf = f(zj ) : (5)

det Gk (zk )

j=1

Hence,

det Gk (·)

P = span : k = 1; : : : ; N

det Gk (zk )

is an interpolation space for the interpolation nodes z1 ; : : : ; zN . Note that this method does not give

only one interpolation polynomial but in general several di erent interpolation spaces, depending on

how the representation in (3) is chosen. In any way, note that for each polynomial f ∈ C[z] the

di erence

N

det Gk (z)

f’ f(zj )

det Gk (zk )

j=1

26 M. Gasca, T. Sauer / Journal of Computational and Applied Mathematics 122 (2000) 23“35

belongs to the ideal f ; : : : ; f , hence there exist polynomials q1 ; : : : ; qd such that

1 d

N d

det Gk (z)

f’ f(zj ) = qj f : (6)

j

det Gk (zk )

j=1 j=1

k

Moreover, as Kronecker points out, the “magic” polynomials gi; j can be chosen such that their leading

k

homogeneous terms, say Gi; j , coincide with the leading homogeneous terms of (1=deg f )@f =@ i . If

j j

we denote by F the leading homogeneous term of f , j = 1; : : : ; d, then this means that

j j

1 @F j

k

Gi; j = ; i; j = 1; : : : ; d; k = 1; : : : ; N: (7)

deg F @ i

j