q=1

while

«

2

e(2) ’ 2zq = 0:

2

q=1

Nodes for which the minimum in (63) is attained are said to be in general position. This is not

quite the usual deÿnition, but is equivalent. Be aware of the fact that we have already used “general

position” with another meaning.

So, the concept of special systems is wider than that of singular Hermite interpolations of type

total degree. A special system which happens to be an interpolation, i.e., for which (62) holds, is a

singular interpolation scheme.

It has been a problem of long standing in algebraic geometry to determine, or to characterize all

special systems. They have come up with the following conjecture in R2 .

Conjecture 35. Let (n; s1 ; : : : ; sm ) be a special system in R2 and P a solution of it for some node set

in general position. Then there is a (nonzero) polynomial Q such that Q2 divides P. The polynomial

Q is a solution of a system (r; t1 ; : : : ; tm ) with the same nodes and with

m

2

r’ sq = ’1: (64)

q=1

Hirschowitz [22,23] has veriÿed this conjecture for some special cases

Theorem 36. Let n; d¿2. The linear system (n; 2; : : : ; 2) with m nodes in Rd is special exactly in

the following cases:

(a) for n = 2: if and only if 26m6d;

(b) for n¿3: if and only if (d; n:m) is one of (2; 4; 5); (3; 4; 9); (4; 3; 7) or (4; 4; 14).

R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 197

We have already seen some of these. Theorem 16, formulated in the terminology of this section,

states that interpolations (n; s1 ; : : : ; sm ) in Rd are special if 26m6d + 1. One must exercise care

when comparing the two results, since the above theorem also includes non-interpolation schemes.

For example, the systems described in a) are interpolating if and only if m = 1 + d=2, i.e., only for

spaces of even dimension. In those cases, they are, indeed, covered by Theorem 16.

Of the special schemes in (b), (2; 4; 5); (4; 3; 7) and (4; 4; 14) are interpolations. The scheme

(3; 4; 9) has 36 interpolation conditions, while the dimension of the interpolation space is 35. The

singularity of (2; 4; 5) and (4; 4; 14) follow from Theorem 18.

There are many other results in the literature. For example, Hirschowitz [22], treats the case

(n; 3; : : : ; 3) exhaustively.

Let us now return to the condition n2 ’ q sq = ’1 of Conjecture 35. It derives from the calculus

2

on schemes we used in Section 3.3: addition is

(n1 ; s1; 1 ; : : : ; s1; m ) + (n2 ; s2; 1 ; : : : ; s2; m ) = (n1 + n2 ; s1; 1 + s2; 1 ; : : : ; s1; m + s2; m )

and an “inner product” is

m

(n1 ; s1; 1 ; : : : ; s1; m ); (n2 ; s2; 1 ; : : : ; s2; m ) = n1 n2 ’ s1; q s2; q :

q=1

Thus if we set N = (n; s1 ; : : : ; sm ), then

m

2 2

n’ sq = N; N :

q=1

Many facts about interpolation schemes can be expressed in terms of this calculus. For example, if

N1 and N2 are special then so is N1 + N2 . In fact, if Pi are polynomials satisfying Ni ; i = 1; 2,

then, as we have seen before, P1 · P2 satisÿes N1 + N2 . Or, Bezout™s theorem (in R2 ) can be

expressed in the following way: If Pi are polynomials satisfying Ni ; i = 1; 2 which are relatively

prime, then

N1 ; N2 ¿0:

Here the schemes are not assumed to be special.

We can also reformulate Hirschowitzs™ conjecture

Conjecture 37. Let N be a special interpolation scheme in R2 . Then there is another scheme R

satisfying condition (64) such that

N; R = ’2:

More details about this calculus can be found in Miranda [31].

It is interesting to note, that Gevorkian Hakopian and Sahakian have a series of papers of

singular Hermite interpolations, some of which we have already referred to, in which they use

exactly this calculus, but with a slightly di erent notation. They have also formulated a conjecture

about singular interpolations which is based on schemes which have fewer interpolation conditions

than the dimension of the space being interpolated from. They say that (n; s1 ; : : : ; s1 ) belongs to the

198 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201

less condition class (LC), if (in R2 )

m

n+2 sq + 2

¿ :

2 2

q=1

As we have seen, the importance of these “less” schemes is that there always exists a polynomial

satisfying the homogeneous conditions, i.e., L(2) (’ m sq zq ) has dimension at least one for each

n q=1

node set.

Their conjecture, reformulated in terms of special schemes, is

Conjecture 38. Let N be an interpolation scheme in R2 . Then N is special if and only if there

are schemes Mi ; i = 1; : : : ; r belonging to LC; such that

r

N= Mi :

i+1

This conjecture is not true in R3 : N = (4; 3; 3; 1; : : : ; 1) with 15 1™s is a singular interpolation

scheme in R3 which is not decomposable into “less” schemes.

No one seems to have integrated the results from these two sources.

6.3. Lagrange interpolation spaces of minimal dimension

In this subsection, we stay with Lagrange interpolation but allow interpolating spaces consisting of

arbitrary functions. What we want to do is to ÿx the number of nodes and then ÿnd one interpolation

space, such that Lagrange interpolation on that number of nodes is always solvable, no matter where

the nodes are located. If the number of nodes is equal to the dimension of a complete space of

polynomials (in Rd for d¿2), then it is clear that we cannot choose that space itself. But perhaps

there is another possibly non-polynomial space of the same dimension that does the trick. If not,

then we allow the dimension of the space from which we will interpolate to increase until we have

found one that works. The theorem of Severi (Theorem 19) tells us that if we want to do Lagrange

interpolation on m nodes in Rd , then we can do it with m’1 . Its dimension is

d

m’1+d

d:

If we allow noncomplete spaces of polynomials, then one can get away with smaller dimension. In

[28], it is shown that it can be done with a space of dimension roughly m ln m in R2 . Vassiliev [42]

has considered these questions in a more general context.

Let M be a topological space, V a ÿnite dimensional subspace of C(M ) (not necessarily polyno-

mial). V is called m-interpolating (over M ) if the Lagrange interpolation problem: ÿnd P ∈ V such

that

f(zq ) = cq ; q = 1; : : : ; m (65)

is solvable for any choice of nodes zq from M and values cq . Before, in the context of Severis™

theorem, we called the problem “solvable” in this case. Here dimV = m is not assumed and, in

R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 199

general, not possible. Now we want to ÿnd the space of lowest possible dimension, and deÿne

I (V; m) = min dimV;

Z

where the minimum is taken over all spaces which are m-interpolating and over all node sets Z of

size m.

1

For example, I (R; m) = m ’ 1 and a space of minimal dimension is m’1 . A ÿrst interesting result

by Vassiliev is

Theorem 39.

2m ’ b(m)6I (R2 ; m)62m ’ 1;

where b(m) is the number of ones in the binary representation of m.

It immediately follows that, for example, that I (R2 ; 2n ) = 2 · 2n ’ 1, since b(2n ) = 1. For m = 3;

b(m) = 2 and the lower bound is the true value. A space of minimal dimension is V =span{1; x; y; x2 +

y2 }. V is 3-interpolating. In fact, V = span{1; R z t ; T z t | 16t6m ’ 1}, where z = x + iy, provides

the upper bound in the theorem. The lower bound is the di cult one to prove.

If M = S 1 is the unit circle in R2 , then I (M; m) = m if m is odd and I (M; m) = m + 1 if m is even,

for we can take the space of trigonometric polynomials of degree [m=2] in both cases.

Theorem 40. For any d-dimensional manifold M; we have

I (M; m)6m(d + 1):

In the case of the unit circle, the theorem predicts 2m instead of the correct answer 2[m=2] + 1.

I suppose this theory has more conjectures than proven theorems, so, appropriately, we close with

another conjecture of Vassiliev

Conjecture 41. If d is a power of 2; then

I (Rd ; m)¿m + (d ’ 1)(m ’ b(m)):

References

[1] B.D. Bojanov, H.A. Hakopian, A.A. Sahakian, Spline Functions and Multivariate Interpolations, Kluwer Academic

Publishers, Dordrecht, 1993.

[2] L. Bos, On certain conÿgurations of points in R n which are unisolvent for polynomial interpolation, J. Approx.

Theory 64 (1991) 271“280.

[3] B. Buchberger, Ein algorithmisches Kriterium fur die Losbarkeit eines algebraischen Gleichungssystems, Aeq. Math.

4 (1970) 373“383.

[4] J.R. Busch, Osculatory interpolation in R n , SIAM J. Numer. Anal. 22 (1985) 107“113.

[5] A.L. Cavaretta, C.A. Micchelli, A. Sharma, Multivariate interpolation and the Radon transform, Part I, Math. Z. 174

(1980), 263“269; Part II, in: R.A. DeVore, K. Scherer (Eds.), Quantitative Approximation, Academic Press, New

York, 1980, pp. 49 “ 62.

[6] C.K. Chung, T.H. Yao, On lattices admitting unique Lagrange interpolations, SIAM J. Numer. Anal. 14 (1977)

735“741.

200 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201

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

[8] C. de Boor, A. Ron, The least solution for the polynomial interpolation problem, Math. Zeit. 210 (1992) 347“378.

[9] C. de Boor, A. Ron, Computational aspects of polynomial interpolation in several variables, Math. Comp. 58 (1992)

705“727.

[10] F.-J. Delvos, W. Schempp, Boolian Methods in Interpolation and Approximation, Longman Scientiÿc & Technical,

Harlow, 1989.

[11] M. Gasca, J.I. Maeztu, On Lagrange and Hermite interpolation in R n , Numer. Math. 39 (1982) 1“14.

[12] M. Gasca, G. Muhlbach, Multivariate polynomial interpolation under projectivities, Part I: Lagrange and Newton

interpolation formulas, Numer. Algebra 1 (1991) 375“400.

[13] M. Gasca, G. Muhlbach, Multivariate polynomial interpolation under projectivities, Part II: Neville“Aitken formulas,

Numer. Algor. 2 (1992) 255“278.

[14] M. Gasca, G. Muhlbach, Multivariate polynomial interpolation under projectivities III, Remainder formulas, Numer.

Algor. 8 (1994) 103“109.

[15] M. Gasca, T. Sauer, Multivariate polynomial interpolation, Adv. Comp. Math., to appear.

[16] H. Gevorkian, H. Hakopian, A. Sahakian, On the bivariate Hermite interpolation, Mat. Zametki 48 (1990) 137“139

(in Russian).

[17] H. Gevorkian, H. Hakopian, A. Sahakian, J. Approx. Theory 80 (1995) 50“75.

[18] H. Gevorkian, H. Hakopian, A. Sahakian, Bivariate Hermite interpolation and numerical curves, J. Approx. Theory

85 (1996) 297“317.

[19] T.N.T. Goodman, Interpolation in minimal semi-norm, and multivariate B-splines, J. Approx. Theory 37 (1983)

212“223.

[20] W. Grobner, Algebraische Geometrie I, II, Bibliographisches Institut Mannheim, Mannheim, 1968, 1970.

[21] H.A. Hakopian, Les di erences divisÃ es de plusieurs variables et les interpolations multidimensionnelles de types

Ã e

Lagrangien et Hermitien, C. R. Acad. Sci. Paris 292 (1981) 453“456.

[22] A. Hirschowitz, La mÃ thode d™Horace pour l™interpolation a plusieurs variables, Man. Math. 50 (1985) 337“388.

e Ã

[23] A. Hirschowitz, Une conjecture pour la cohomologie des diviseurs sur les surfaces rationelles gÃ nÃ riques, J. Reine

ee

Angew. Math. 397 (1989) 208“213.

[24] R.-Q. Jia, A. Sharma, Solvability of some multivariate interpolation problems, J. Reine Angew. Math. 421 (1991)

73“81.

[25] P. Kergin, A natural interpolation of C K functions, J. Approx. Theory 29 (1980) 29“278.

[26] S.L. Lee, G.M. Phillips, Construction of lattices for Lagrange interpolation in projective spaces, Constructive Approx.

7 (1991) 283“297.

[27] G.G. Lorentz, K. Jetter, S.D. Riemenschneider, Birkho Interpolation, Addison-Wesley, Reading, MA, 1983.

[28] R.A. Lorentz, Multivariate Birkho Interpolation, Springer, Heidelberg, 1992.

[29] C. Micchelli, A constructive approach to Kergin interpolation in Rk : multivariate B-splines and Lagrange

interpolation, Rocky Mountain J. Math. 10 (1979) 485 “ 497.

[30] C.A. Micchelli, P. Milman, A formula for Kergin interpolation in Rk , J. Approx. Theory 29 (1980) 294“296.

[31] N. Miranda, Linear systems of plane curves, Notices AMS 46 (1999) 192“202.

[32] H.M. Moller, Linear abhangige Punktfunktionale bei zweidimensionalen Interpolations- und Approximations-

problemen, Math. Zeit. 173 (1980) 35“49.

[33] H.M. Moller, Grobner bases and numerical analysis, in: B. Buchberger, F. Winkler (Eds.), Groebner Bases and

Applications, Cambridge University Press, Cambridge, 1998, pp. 159“179.

[34] S.H. Paskov, Singularity of bivariate interpolation, J. Approx. Theory 75 (1992) 50“67.

[35] T. Sauer, Polynomial interpolation of minimal degree, Numer. Math. 78 (1997) 59“85.

[36] T. Sauer, Grobner bases, H-bases and interpolation, Trans. AMS, to appear.

[37] T. Sauer, Y. Xu, On multivariate Lagrange interpolation, Comp. Math. 64 (1995) 1147“1170.

[38] T. Sauer, Y. Xu, On multivariate Hermite interpolation, Adv. Comp. Math. 4 (1995) 207“259.

[39] T. Sauer, Y. Xu, Regular points for Lagrange interpolation on the unit disc, Numer. Algorithm 12 (1996) 287“296.

[40] L. Schumaker, Fitting surfaces to scattered data, in: G.G. Lorentz, C.K. Chui, L.L. Schumaker (Eds.), Approximation

Theory 2, Academic Press, Boston, 1976.

[41] F. Severi, E. Lo er, Vorlesungen uber Algebraische Geometrie, Teubner, Berlin, 1921.

R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 201

[42] V.A. Vassiliev, Complements of discriminants of smooth maps: topology and applications, Transl. Math. Mon. 98

(1992) 209 “210; translated from Funkt. Analiz i Ego Pril. 26 (1992) 72“74.

[43] S. Waldron, Lp error bounds for multivariate polynomial interpolation schemes, Ph. D. Thesis, Department of

Mathematics, University of Wisconsin, 1995.

[44] S. Waldron, Mean value interpolation for points in general position, Technical Report, Dept. of Math., Univ of

Auckland, 1999.

[45] Y. Xu, Polynomial interpolation in several variables, cubature formulae, and ideals, Adv. Comp. Math., to appear.

Journal of Computational and Applied Mathematics 122 (2000) 203“222

www.elsevier.nl/locate/cam

Interpolation by Cauchy“Vandermonde systems and

applications

G. Muhlbach

Institut fur Angewandte Mathematik, Universitat Hannover, Postfach 6009, 30060 Hannover, Germany

Received 30 April 1999; received in revised form 22 September 1999

Abstract

Cauchy“Vandermonde systems consist of rational functions with prescribed poles. They are complex ECT-systems

allowing Hermite interpolation for any dimension of the basic space. A survey of interpolation procedures using CV-systems

is given, some equipped with short new proofs, which generalize the well-known formulas of Lagrange, Neville“Aitken

and Newton for interpolation by algebraic polynomials. The arithmetical complexitiy is O(N 2 ) for N Hermite data. Also,

inversion formulas for the Cauchy“Vandermonde matrix are surveyed. Moreover, a new algorithm solving the system of N

linear Cauchy“Vandermonde equations for multiple nodes and multiple poles recursively is given which does not require