of the underlying ÿeld, counting multiplicities. This theorem has many interesting consequences

for bivariate interpolation problems, extensible to higher dimensions. For example, no unisolvent

2

interpolation problem in n can have more than n + 1 collinear points. Radon™s method in [32] is

a consequence of this type of observations, and some other more recent results of di erent authors

can also be deduced in a similar form, as we shall see later.

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

Another example of a result which shows the more general point of view taken in multivariate

interpolation at that time is due to Thacher Jr. and Milne [47] (see also [48]). Consider two uni-

1

variate interpolation problems in n’1 , with T1 ; T2 as respective sets of interpolation points, both of

cardinality n. Assume that T1 © T2 has cardinality n ’ 1, hence T = T1 ∪ T2 has cardinality n + 1. The

univariate Aitken“Neville interpolation formula combines the solutions of the two smaller problems

1

based on T1 and T2 to obtain the solution in n of the interpolation problem with T as the under-

lying set of interpolation points. The main idea is to ÿnd a partition of unity, in this case a ne

polynomials ˜1 ; ˜2 , i.e., ˜1 + ˜2 = 1, such that

˜1 (T2 \T1 ) = ˜2 (T1 \T2 ) = 0

and then combine the solutions p1 ; p2 with respect to T1 ; T2 , into the solution ˜1 p1 + ˜2 p2 with

respect to T . This method was developed in the 1930s independently by Aitken and Neville with

the goal to avoid the explicit use of divided di erences in the computation of univariate Lagrange

polynomial interpolants.

It was exactly this idea which Thatcher and Milne extended to the multivariate case in [47].

Let us sketch their approach in the bivariate case. For example, consider an interpolation problem

with 10 interpolation points, namely, the set T = {(i; j) : 06i + j63}, where i; j are nonnegative

2

integers, and the interpolation space 3 . The solution pT of this problem is obtained in [47] from

2

the solutions pTk ∈ 2 ; k = 1; 2; 3, of the 3 interpolation problems with respect to the six-point sets

Tk ‚ T , k = 1; 2; 3, where

T1 = {(i; j) : 06i + j62};

T2 = {(i; j) : (i; j) ∈ T; i ¿ 0};

T3 = {(i; j) : (i; j) ∈ T; j ¿ 0}:

Then,

p T = ˜1 p T 1 + ˜2 p T 2 + ˜3 p T 3 ;

where ˜k ; k = 1; 2; 3 are appropriate polynomials of degree 1. In fact, in this case these polynomials

are the barycentric coordinates relative to the simplex (0, 0), (3, 0), (0, 3) and thus a partition

of unity. In [47] the problem is studied in d variables and in that case d + 1 “small” problems,

with respective interpolation sets Tk ; k = 1; : : : ; d, with a simplicial structure (the analogue of the

triangular grid), are used to obtain the solution of the full problem with T = T1 © · · · © Td+1 as

interpolation points.

In 1970, Guenter and Roetman [19], among other observations, made a very interesting remark,

which connects to the Radon=BÃ zout context and deserves to be explained here. Let us consider a set

e

T of ( d ) points in R , where exactly ( m+d’1 ) of these points lie on a hyperplane H . Then T \H

m+d d

d’1

m’1+d m m

consists of ( d ) points. Let us denote by d; H the space of polynomials of d with the variables

m

restricted to H , which is isomorphic to d’1 . If the interpolation problems deÿned by the sets T \H

m’1 m

and T ©H are unisolvent in the spaces d and d; H , respectively, then the interpolation problem

m

deÿned by T is unisolvent in d . In other words, the idea is to decompose, whenever possible, a

problem of degree m and d variables into two simpler problems, one of degree m and d’1 variables

and the other one with degree m ’ 1 and d variables.

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

6. The ÿnite element approach

In 1943, Courant [11] suggested a ÿnite di erence method applicable to boundary value problems

arising from variational problems. It is considered one of the motivations of the ÿnite element

method, which emerged from the engineering literature along the 1950s. It is a variational method

of approximation which makes use of the Rayleigh“Ritz“Galerkin technique. The method became

very successful, with hundreds of technical papers published (see, e.g., the monograph [52]), even

before its mathematical basis was completely understood at the end of the 1960s.

Involved in the process of the ÿnite element method there are local polynomial interpolation

problems, generally for polynomials of low degree, thus, with only few interpolation data. The

global solution obtained by solving all the local interpolation problems is a piecewise polynomial of

a certain regularity, depending on the amount and type of interpolation data in the common boundary

between pieces. Some of the interest in multivariate polynomial interpolation along the 1960=1970s

was due to this method. Among the most interesting mathematical papers of that time in Finite

Elements, we can mention [53,5], see also the book [46] by Strang and Fix, but, in our opinion, the

most relevant papers and book from the point of view of multivariate polynomial interpolation are

due to Ciarlet et al., for example [7“9].

In 1972, Nicolaides [29,30] put the classical problem of interpolation on a simplicial grid of ( m+d )

d

points of Rd , regularly distributed, forming what he called a principal lattice, into the ÿnite element

context. He actually used barycentric coordinates for the Lagrange formula, and moreover gave

the corresponding error representations, see also [7]. However, much of this material can already

be found in [3]. In general, taking into account that these results appeared under di erent titles,

in a di erent context and in journals not accessible everywhere, it is not so surprising any more,

how often the basic facts on the interpolation problem with respect to the simplicial grid had been

rediscovered.

7. Hermite problems

The use of partial or directional derivatives as interpolation data in the multivariate case had not

received much attention prior to the ÿnite element method, where they were frequently used. It

seems natural to approach partial derivatives by coalescence, as in univariate Hermite interpolation

problems. However, things are unfortunately much more complicated in several variables. As it was

already pointed out by Salzer and Kimbro [39] in 1958, the Hermite interpolation problem based on

the values of a bivariate function f(x; y) at two distinct points (x1 ; y1 ); (x2 ; y2 ) and on the values of

2

the partial derivatives @f=@x; @f=@x at each of these two points is not solvable in the space 2 for

any choice of points, although the number of interpolation conditions coincides with the dimension

of the desired interpolation space. Some years later, Ahlin [1] circumvented some of these problems

by using a tensor product approach: k 2 derivatives @p+q f=@xp @yq with 06p; q6k ’ 1 are prescribed

at the n2 points of a Cartesian product. The interpolation space is the one spanned by x yÿ with

06 ; ÿ6nk ’ 1 and a formula for the solution is easily obtained.

We must mention that Salzer came back to bivariate interpolation problems with derivatives in [38]

studying hyperosculatory interpolation over Cartesian grids, that is, interpolation problems where

all partial derivatives of ÿrst and second order and the value of the function are known at the

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

interpolation points. Salzer gave some special conÿgurations of points which yield solvability of this

type of interpolation problem in an appropriate polynomial space and also provided the corresponding

remainder formulae.

Nowadays, Hermite and Hermite“Birkho interpolation problems have been studied much more

systematically, see [16,25] for references.

8. Other approaches

In 1966, Coatmelec [10] studied the approximation of functions of several variables by linear

operators, including interpolation operators. At the beginning of the paper, he only considered in-

terpolation operators based on values of point evaluations of the function, but later he also used

values of derivatives. In this framework he obtained some qualitative and quantitative results on the

approximation order of polynomial interpolation. At the end of [10], Coatmelec also includes some

examples in R2 of points which are distributed irregularly along lines: n + 1 of the points on a line

r0 , n of them on another line r1 , but not on r0 , and so on until 1 point is chosen on a line rn but

not on r0 ∪ · · · ∪ rn’1 . He then points out the unisolvence of the corresponding interpolation problem

2

in n which is, in fact, again a consequence of BÃ zout™s theorem as in [32].

e

In 1971, Glaeser [17] considers Lagrange interpolation in several variables from an abstract

algebraic=analytic point of view and acknowledges the inconvenience of working with particular

systems of interpolation points due to the possibility of the nonexistence of a solution, in contrast

to the univariate case. This is due to the nonexistence of polynomial spaces of dimension k ¿ 1 in

more than one variable such that the Lagrange interpolation problem has a unique solution for any

system of k interpolation points. In other words, there are no nontrivial Haar (or Chebychev) spaces

any more for two and more variables, cf. [12] or [24]. In [17], polynomial spaces with dimension

greater than the number of interpolation conditions are considered in order to overcome this problem.

Glaeser investigated these underdetermined systems which he introduced as interpolation schemes

in [17] and also studied the problem of how to particularize the a ne space of all solutions of a

given interpolation problem in order to obtain a unique solution. This selection process is done in

such a way that it controls the variation of the solution when two systems of interpolation points

are very “close” to each other, with the goal to obtain a continuous selection process.

Acknowledgements

1. We thank Carl de Boor for several references, in particular, for pointing out to us the paper [32]

with the result mentioned at the beginning of Section 4, related to Bezout™s theorem. We are also

grateful the help of Elena Ausejo, from the group of History of Sciences of the University of

Zaragoza, in the search of references.

2. M. Gasca has been partially supported by the Spanish Research Grant PB96 0730.

3. T. Sauer was supported by a DFG Heisenberg fellowship, Grant SA 627=6.

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

References

[1] A.C. Ahlin, A bivariate generalization of Hermite™s interpolation formula, Math. Comput. 18 (1964) 264“273.

[2] I.S. Berezin, N.P. Zhidkov, Computing Methods, Addison-Wesley, Reading, MA, 1965 (Russian version in 1959).

[3] O. Biermann, Uber naherungsweise Kubaturen, Monatshefte Math. Phys. 14 (1903) 211“225.

[4] O. Biermann, Vorlesungen uber Mathematische Naherungsmethoden, Vieweg, Braunschweig, 1905.

[5] G. Birkho , M.H. Schultz, R.S. Varga, Piecewise Hermite interpolation in one and two variables with applications

to partial di erential equations, Numer. Math. 11 (1968) 232“256.

[6] W. Borchardt, Uber eine Interpolationsformel fur eine Art symmetrischer Funktionen und deren Anwendung, Abh.

d. Preu . Akad. d. Wiss. (1860) 1“20.

[7] P.G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978.

P.G. Ciarlet, P.A. Raviart, General Lagrange and Hermite interpolation in Rn with applications to ÿnite element

[8]

methods, Arch. Rational Mech. Anal. 46 (1972) 178“199.

[9] P.G. Ciarlet, C. Wagschal, Multipoint Taylor formulas and applications to the ÿnite element method, Numer. Math.

17 (1971) 84“100.

[10] C. Coatmelec, Approximation et interpolation des fonctions di erentiables de plusieurs variables, Ann. Sci. Ecole

Norm. Sup. 83 (1966) 271“341.

[11] R. Courant, Variational methods for the solution of problems of equilibrium and vibrations, Bull. Amer. Math. Soc.

49 (1943) 1“23.

[12] P.J. Davis, Interpolation and Approximation, Blaisdell, Walthan, MA, 1963 (2nd Edition, Dover, New York, 1975).

[13] Encyklopadie der mathematischen Wissenschaften, Teubner, Leipzig, pp. 1900 “1904.

[14] EncyclopÃ die des Sciences Mathematiques, Gauthier-Villars, Paris, 1906.

e

[15] I.A. Ezrohi, General forms of the remainder terms of linear formulas in multidimensional approximate analysis I,

II Mat. Sb. 38 (1956) 389 “ 416 and 43 (1957) 9 “28 (in Russian).

[16] M. Gasca, T. Sauer, Multivariate polynomial interpolation, Adv. Comput. Math., 12 (2000) 377“410.

[17] G. Glaeser, L™interpolation des fonctions di erentiables de plusieurs variables, in: C.T.C. Wall (Ed.), Proceedings of

Liverpool Singularities Symposium II, Lectures Notes in Mathematics, Vol. 209, Springer, Berlin, 1971, pp. 1“29.

[18] H.H. Goldstine, A History of Numerical Analysis from the 16th Through the 19th Century, Springer, Berlin, 1977.

[19] R.B. Guenter, E.L. Roetman, Some observations on interpolation in higher dimensions, Math. Comput. 24 (1970)

517“521.

[20] E. Isaacson, H.B. Keller, Analysis of Numerical Methods, Wiley, New York, 1966.

[21] C.G.J. Jacobi, Theoremata nova algebraica circa systema duarum aequationum inter duas variabiles propositarum,

Crelle J. Reine Angew. Math. 14 (1835) 281“288.

[22] L. Kronecker, Uber einige Interpolationsformeln fur ganze Funktionen mehrerer Variabeln. Lecture at the academy

of sciences, December 21, 1865, in: H. Hensel (Ed.), L. Kroneckers Werke, Vol. I, Teubner, Stuttgart, 1895,

pp. 133“141. (reprinted by Chelsea, New York, 1968).

[23] K.S. Kunz, Numerical Analysis, McGraw-Hill, New York, 1957.

[24] G.G. Lorentz, Approximation of Funtions, Chelsea, New York, 1966.

[25] R. Lorentz, Multivariate Hermite interpolation by algebaic polynomials: a survey, J. Comput. Appl. Math. (2000)

this volume.

[26] S.E. Mikeladze, Numerical Methods of Mathematical Analysis, Translated from Russian, O ce of Tech. Services,

Department of Commerce, Washington DC, pp. 521“531.

[27] S. Narumi, Some formulas in the theory of interpolation of many independent variables, Tohoku Math. J. 18 (1920)

309“321.

[28] L. Neder, Interpolationsformeln fur Funktionene mehrerer Argumente, Skandinavisk Aktuarietidskrift (1926) 59.

[29] R.A. Nicolaides, On a class of ÿnite elements generated by Lagrange interpolation, SIAM J. Numer. Anal. 9 (1972)

435“445.

[30] R.A. Nicolaides, On a class of ÿnite elements generated by Lagrange interpolation II, SIAM J. Numer. Anal.

10 (1973) 182“189.

[31] K. Pearson, On the construction of tables and on interpolation, Vol. 2, Cambridge University Press, Cambridge,

1920.

[32] J. Radon, Zur mechanischen Kubatur, Monatshefte Math. Physik 52 (1948) 286“300.

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

[33] H.E. Salzer, Note on interpolation for a function of several variables, Bull. AMS 51 (1945) 279“280.

[34] H.E. Salzer, Table of coe cients for interpolting in functions of two variables, J. Math. Phys. 26 (1948) 294“305.

[35] H.E. Salzer, Note on multivariate interpolation for unequally spaced arguments with an application to double

summation, J. SIAM 5 (1957) 254“262.

[36] H.E. Salzer, Some new divided di erence algorithms for two variables, in: R.E. Langer (Ed.), On Numerical

Approximation, University of Wisconsin Press, Madison, 1959, pp. 61“98.

[37] H.E. Salzer, Divided di erences for functions of two variables for irregularly spaced arguments, Numer. Math.

6 (1964) 68“77.

[38] H.E. Salzer, Formulas for bivariate hyperosculatory interpolation, Math. Comput. 25 (1971) 119“133.

[39] H.E. Salzer, G.M. Kimbro, Tables for Bivariate Osculatory Interpolation over a Cartesian Grid, Convair Astronautics,

1958.

[40] A. Sard, Remainders: functions of several variables, Acta Math. 84 (1951) 319“346.

[41] A. Sard, Remainders as integrals of partial derivatives, Proc. Amer. Math. Soc. 3 (1952) 732“741.

[42] T. Sauer, Yuan Xu, On multivariate Lagrange interpolation, Math. Comput. 64 (1995) 1147“1170.

[43] T. Sauer, Yuan Xu, A case study in multivariate Lagrange interpolation, in: S.P. Singh (Ed.), Approximation Theory,

Wavelets and Applications, Kluwer Academic Publishers, Dordrecht, 1995, pp. 443“452.

[44] D.D. Stancu, The remainder of certain linear approximation formulas in two variables, J. SIAM Numer. Anal.

1 (1964) 137“163.

[45] I.F. Ste ensen, Interpolation, Chelsea, New York, 1927 (2nd Edition, 1950).

[46] G. Strang, G.J. Fix, An Analysis of the Finite Element Method, Prentice-Hall, Englewood Cli s, NJ, 1973.

[47] H.C. Thacher Jr., W.E. Milne, Interpolation in several variables, J. SIAM 8 (1960) 33“42.

[48] H.C. Thacher Jr., Derivation of interpolation formulas in several independent variables, Ann. N.Y. Acad. Sci.

86 (1960) 758“775.

[49] T.N. Thiele, Interpolationsrechnung, Teubner, Leipzig, 1909.

[50] R.S. Walker, Algebraic Curves, Springer, Berlin, 1978.

[51] E.T. Whittaker, G. Robinson, Calculus of Observations, 4th Edition, Blackie and Sons, London, 1944.

[52] O.C. Zienkiewicz, The Finite Element Method in Structural and Continuum Mechanics, McGraw-Hill, London, 1967.

[53] M. Zlamal, On the ÿnite element method, Numer. Math. 12 (1968) 394“409.

Journal of Computational and Applied Mathematics 122 (2000) 37“50

www.elsevier.nl/locate/cam

Elimination techniques: from extrapolation to totally positive

matrices and CAGD

M. Gasca — , G. Muhlbach

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

Received 20 May 1999; received in revised form 22 September 1999

Abstract

In this survey, we will show some connections between several mathematical problems such as extrapolation, linear

systems, totally positive matrices and computer-aided geometric design, with elimination techniques as the common tool

to deal with all of them. c 2000 Elsevier Science B.V. All rights reserved.