<<

. 41
( 83 .)



>>

For a special case, Jia and Sharma prove more

Theorem 4. Let A ‚ Nd . Let Aq ‚ A; q = 1; : : : ; m; V = A ; Vq = Aq ; q = 1; : : : ; m. Then Abel“
0
Goncharov interpolation (29) is regular for any node set Z if and only if A is the disjoint sum of
the Aq ; q = 1; : : : ; m.
d
This theorem implies Theorem 2. For example, for Hermite interpolation of type total degree, n =
d
A with A = {j | j ∈ N0 ; |j|6n} while the derivatives to be interpolated derive from the polynomial
spaces Vq = Aq with Aq = {j | j ∈ Nd ; |j|6kq }. The same holds for Hermite interpolation of type
0
coordinate degree. It also includes a similar theorem for multivariate Birkho interpolation.
In view of the these results, Jia and Sharma formulated the conjecture
R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 177


Conjecture 5. Let V and {Vq }m be scale-invariant subspaces of d
such that
q=1
m
Vq ‚ V:
q=1

Then Abel-Goncharov interpolation (29) is regular if and only if (30) holds.

3.3. A.e. regular Hermite interpolation of type total degree in R2

From the previous section, we have seen that multivariate Hermite interpolation can, except for
some very special cases, be at most regular for almost all choices of nodes. We denote this as
being regular a.e. Not too much is known about even a.e. regular Hermite interpolation of type total
degree. Gevorkian et al. [16] have proven

Theorem 6. Bivariate Hermite interpolation of type total degree (8) is regular a.e. if there are at
most 9 nodes with kq ¿1.
Sauer and Xu [38] have proven

Theorem 7. Multivariate Hermite interpolation of type total degree (8) in Rd with at most d + 1
nodes having kq ¿1 is regular a.e. if and only if
kq + kr ¡ n
for 16q; r6m; q = r.
The authors of Theorem 6 have also considered Hermite interpolation of type total degree from
the point of view of algebraic geometry. These results will be discussed in Section 6. A conjecture
due to them and Paskov [18,34], simultaneously does ÿt in here. Let us use the stenographic notation
N = {n; s1 ; : : : ; sm } to stand for Hermite interpolation of type total degree on m nodes interpolating
derivatives of order up to kq = sq ’ 1 at zq by bivariate polynomials of degree n. We are using
the standard notation of algebraic geometry here, working with orders of singularities sq . Also, we
will not be much concerned about the node set Z, since we are only interested in regularity a.e.
In addition, we allow an sq to be 0. This just means that there is no interpolation condition at that
node. We also do not demand that the condition (7) requiring that the number of degrees of freedom
in the interpolation space equals the number of functionals to be interpolated, holds.
With this freedom, we do not have interpolations n the strict sense of Equation 2 any more, so
let us just call them singularity schemes. We introduce addition among singularity schemes just by
vector addition. If N = {n; s1 ; : : : ; sm } and R = {r; t1 ; : : : ; tm }, then
N + R = {n + r; s1 + t1 ; : : : ; sm + t1 }: (31)
We can add singularity schemes of di erent lengths by introducing zeros in the shorter of them.
2
The relevance of this addition is that if Q1 ∈ n satisÿes the homogeneous interpolation conditions
2
of N and if Q2 ∈ r satisÿes the homogeneous interpolation conditions of R, where N and R
2
are of the same length and refer to the same nodes, then Q1 Q2 ∈ n+r satisÿes the homogeneous
interpolation conditions of N + R,
The conjecture is
178 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201


Conjecture 8. Let N correspond to a Hermite interpolation of type total degree (that is condition
(7) holds). Then N is singular if and only if there are schemes Ri = {ri ; ti; 1 ; : : : ; ti; m }; =1; : : : ; p
satisfying
m
ri + 2 ti; q + 2
¿ ; i = 1; : : : ; p;
2 2
q=1

such that
p
N= Mi :
i=1


The su ciency part of this theorem is easy to see. There are always nonzero polynomials Qi
satisfying the homogeneous interpolation conditions of Ri , i = 1; : : : ; p, since each of them can be
found by solving a linear system of homogeneous equations with less equations than unknowns.
p 2
By the above remark, i=1 Qi ∈ n is a nonzero polynomial satisfying the homogeneous conditions
for N.
We have already seen an example of this. It is our favorite singular Hermite interpolation: the
interpolation of ÿrst derivatives at two nodes in R2 by polynomials from 2 . In the notation used
2

here, this is the singularity scheme N = {2; 2; 2}. It can be decomposed as N = R + S, with
R = S = {1; 1; 1}. More singular Hermite interpolations constructed using this idea can be found in
[34; 28 Chapter 4].
There are essentially no other results for the a.e. regularity of general Hermite interpolation of
total degree. More is known for uniform Hermite interpolation of total degree. The results which
follow can be found in [38,28].
The simplest case of uniform Hermite interpolation is, of course, Lagrange interpolation in which
2
partial derivatives of order zero are interpolated at each node. The number of nodes in dim n for
some n and it is regular a.e.
The next case is when all partial derivatives up to ÿrst order are interpolated at each node.
Condition (7) is then
n+2 1+2
=m = 3m: (32)
2 2
This equation has a solution for n and m if and only if n = 1; 2 mod 3.

Theorem 9. For all n with n = 1; 2 mod 3; bivariate uniform Hermite interpolation of type total
degree interpolating partial derivatives of order up to one is regular a.e.; except for the two cases
with n = 2 (then m = 2) and n = 4 (then m = 5). The two exceptional cases are singular.

Note that our favorite singular Hermite interpolation is included. The smallest non-Taylor a.e.
regular case is for n = 5. The interpolation is then on 7 nodes.
The method of the proof of this and the following two theorems is to show that the Vandermonde
determinant does not vanish identically by showing that one of its partial derivatives is a nonzero
constant. The technique used to show this is the “coalescence” of nodes and, roughly speaking, tries
to reduce the number of nodes of the interpolation until a Taylor interpolation is obtained.
R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 179


If all partial derivatives up to second order are interpolated at each node, condition (7) becomes
n+2 2+2
=m = 6m: (33)
2 2
This equation has a solution for n and m if and only if n = 2; 7; 10; 11 mod 12.

Theorem 10. For all n with n = 2; 7; 10; 11 mod 12; bivariate uniform Hermite interpolation of type
total degree interpolating partial derivatives of order up to two is regular a.e.

The smallest non-Taylor a.e. regular case is for n = 7. The interpolation is then on 12 nodes.
For third derivatives, we must have n = 3; 14; 18; 19 mod 20.

Theorem 11. For all n with n=3; 14; 18; 19 mod 20; bivariate uniform Hermite interpolation of type
total degree interpolating partial derivatives of order up to three is regular a.e.

The smallest non-Taylor a.e. regular case is for n = 14. The interpolation is then also on 12 nodes.
For related results from algebraic geometry, see Section 6.

3.4. A.e. regular bivariate Hermite interpolation of type coordinate degree in R2

No theorems about the a.e. regularity of general Hermite interpolation of type coordinate degree
in Rd , as deÿned in (26), are known except for the relatively simple one given at the end of this
subsection. But there are a few things known of the uniform case. If we want to interpolate all
2
partial derivatives of order up to k1 in x and to k2 in y from (n1 ;n2 ) , then
(n1 + 1)(n2 + 1) = m(k1 + 1)(k2 + 1) (34)
must hold. The proofs of the the following theorems, all of which can be found in [28], are based
on the same techniques as for the theorems on a.e. regularity of uniform Hermite interpolation of
type total degree in the previous subsection.

Theorem 12. If (34) is satisÿed; and either k1 +1 divides n1 +1 or k2 +1 divides n2 +1; then bivariate
uniform Hermite interpolation of type coordinate degree interpolating all partial derivatives of
2
order up to k1 in x and to k2 in y from (n1 ;n2 ) is a.e. regular.

This is more general than tensor product interpolation, since there one would have that both k1 + 1
divides n1 + 1 and k2 + 1 divides n2 + 1. If n1 = n2 = n and k1 = k2 = k, which is a kind of (uniform)2
Hermite interpolation, then (34) forces k to divide n and we have

Corollary 13. Bivariate uniform Hermite interpolation of type coordinate degree interpolating all
2
partial derivatives of order up to k in x and in y from (n1 ;n2 ) is a.e. regular.

This corollary also holds in Rd , but theorems like Theorem 12 in Rd require much more restrictive
assumptions.
180 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201


As for uniform Hermite interpolation of type total degree, interpolations involving only lower
order derivatives can be taken care of completely.

Theorem 14. For all combinations; except two; of k1 ; k2 with 06k1 ; k2 62 and n1 ; n2 with
06k1 6n1 ; 06k2 6n2 satisfying (34); uniform bivariate Hermite interpolation of type coordinate
2
degree interpolating all partial derivatives of order up to k1 in x and to k2 in y from (n1 ;n2 ) is
2
a.e. regular. The two exceptional cases are k1 = 1 and k2 = 2 from (2; 3) and the corresponding
interpolation with x and y interchanged. These are singular.

This theorem includes cases Theorem 12 does not cover. For example, interpolating partial deriva-
2
tives of ÿrst order in x and second order in y at each of eight nodes from (8; 3) is regular a.e. But
Theorem 12 does not apply since neither 2 divides 9 nor does 3 divide 4.
We conclude this subsection with a theorem on non-uniform interpolation.

Theorem 15. A bivariate Hermite interpolation of type coordinate degree interpolating all partial
2
derivatives of order up to kq; 1 in x and to kq; 2 in y at zq ; q = 1; : : : ; m from (n1 ;n2 ) is a.e. regular
if the rectangle (0; n1 + 1) — (n2 + 1) is the disjoint union of the translates of the rectangles
(0; kq; 1 + 1) — (kq; 2 + 1) q = 1; : : : ; m.

This theorem does not hold in Rd for d¿3.



3.5. Singular Hermite interpolations in Rd

The general trend of the results of this subsection will be that a Hermite interpolation in Rd will
be singular if the number of nodes is small, typically m6d + 1. Of course, Taylor interpolations are
excepted. Also Lagrange interpolation by linear polynomials (m = d + 1) is excluded. The theorems
can all be found in [28,38].

Theorem 16. Hermite interpolation of type total degree in Rd ; d¿2; is singular if the number of
nodes satisÿes 26m6d + 1 except for the case of Lagrange interpolation which is a.e. regular.

Implicitly, condition (7) is assumed to be satisÿed.
The theorem includes our favorite singular Hermite interpolation. It is proved showing that the
interpolation restricted to a certain hyperplane is not solvable.
One application of this theorem is a negative result related to the construction of ÿnite elements.
The statement is that there is no ÿnite element interpolating all derivatives up to a given order (which
may depend on the vertex) at each of the vertices of a tetrahedron in Rd , d¿2, which interpolates
d
from a complete space, say n . The existence of such an element would have been desirable as it
would have combined the highest degree approximation, n + 1, and global continuity available for a
given amount of computational e ort.
For interpolation of type coordinate degree, we have
R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 181


Theorem 17. Bivariate uniform Hermite interpolation of type coordinate degree interpolating all
2
partial derivatives of order k1 in x and to k2 in y at either two or three nodes from (n1 ;n2 ) is
singular unless either p1 + 1 divides n1 + 1 or p2 + 1 divides n2 + 1.

The exceptional cases are regular by Theorem 12.
Singular uniform Hermite interpolation schemes on more than d + 1 nodes in Rd are hard to ÿnd.
Here are some for uniform Hermite interpolation of type total degree due to Sauer and Xu [38].

Theorem 18. Uniform Hermite interpolation of type total degree interpolating all partial deriva-
tives of order up to k at each of m nodes in Rd by polynomials from n is singular if
d

(n + 1) · · · (n + d)
m¡ :
((n ’ 1)=2 + 1) · · · ((n ’ 1)=2 + d)

In R2 , the smallest example is covered by this theorem is the interpolation of all partial derivatives
of up to ÿrst order at each of 5 nodes by quartic polynomials.

3.6. Conclusions

We have seen that Hermite interpolation of either total or coordinate degree type is regular if
m = 1, is singular if there are not too many nodes and, for uniform Hermite interpolation of type
coordinate degree, there are no other exceptions if we are interpolating derivatives of order up to
one, two or three. Really general theorems for a.e. regularity of interpolations with arbitrarily high
derivatives are not known. The same holds for the results obtained by the methods of algebraic
geometry, as we will see in Section 6.
In this section, we have assiduously ignored one of the essential components of interpolation.
Most of the theorems of this section concerned a.e. regularity. To use these interpolations, one must
ÿnd concrete node sets for which the interpolations are regular. Only for Lagrange interpolation are
any systematic results are known. Otherwise, nothing is known. For this reason, special constructions
of interpolations which include the node sets, such as those in Sections 5 and 6, are of importance,
d
even if the interpolation spaces are not complete spaces n .


4. Alternatives to classical multivariate Hermite interpolation

4.1. Lifting schemes

Our extension of univariate to “classical” multivariate Hermite interpolation, namely to multivariate
Hermite interpolation of type total degree, has one glaring defect. It is not regular for any choice of
nodes. It is in fact possible to get rid of this unfavorable property, but alas, at a price. The method
to be introduced here, called “lifting”, yields a multivariate interpolation which is formulated exactly
as in the univariate case. In our context, it was introduced by Goodman [19] motivated by the ÿrst
special cases, those of Kergin [25], Hakopian [21] and of Cavaretta et al. [5]. For a more complete
survey, see the book [1] of Bojanov, Hakopian and Sahakian, or the thesis of Waldron [43] and the
references therein.

<<

. 41
( 83 .)



>>