<<

. 6
( 83 .)



>>

initial-boundary value problems of the QD algorithm, Lett. Math. Phys. 34 (1995) 91“101.
[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

<<

. 6
( 83 .)



>>