ABSTRACT
APPROXIMATION WITH HERMITE-BIRKHOFF

INTERPOLATORY CONSTRAINTS AND
RELATED H-SET THEORY

BY
Donald M. Platte

we consider the question of existence,
characterization, uniqueness and error bounds
for the following approximating problem. Approxi-
mate in the uniform normaireal valued function
f E C(X), where X is a compact subset of a real
closed interval [a,b], from the family of
polynomials of degree n which satisfy Hermite-

Birkhoff interpolatory constraints.

In Chapter I we consider existence and
characterization. By adding the requirement that
certain incidence matrices be poised we get an
alternation theorem and a uniqueness theorem. Upper
bounds on the error of approximation are studied

in Chapter II. In Chapter III approximation in

Donald M. Platte

several variables with Lagrange interpolatory
constraints is considered. In particular an
"Inclusion Theorem" is presented which leads to
the study of minimal H—sets for Lagrange inter-

polatory constraints.

APPROXIMATION WITH HERMITE-BIRKHOFF
INTERPOLATORY CONSTRAINTS AND
RELATED H-SET THEORY

BY

n

(V?
Donald M? Platte

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

1972

TO MY WIFE
RITA

ii

ACKNOWLEDGEMENTS

My sincere appreciation goes to my major
Professor Gerald D. Taylor for his guidance. I
am especially indebted to him for his time, his

many suggestions, and his encouragement.

iii

CHAPTER

CHAPTER

CHAPTER

TABLE OF CONTENTS

INTRODUCTION . . . . . . . . . . . . . . .

I APPROXIMATION THEORY WITH INTERPOLATORY
CONSTRAINTS FOR FUNCTIONS OF ONE
VARIABIE O O O I O C C O O O O O O I O I 0

Section 1: Introduction and Existence . . .

Section 2: Results on Hermite-Birkhoff
Interpolation . . . . . . . . . .

Section 3: Characterization Theorem for a
Best Approximation . . . . . . .

Section 4: Uniqueness of Best Approximation.

II ERROR ESTIMATES FOR INTERPOLATORY
CONSTRAINTS C O O C C C O O O O O O O O 0

Section 1: Introduction . . . . . . . . . .
*
Section 2: Limit of En(f) Equals Zero . .
*
Section 3: Comparison of En(f) to En(f) .

III HFSET THEORY FOR APPROXIMATION WITH
INTERPOLATORY CONSTRAINTS . . . . . .

Section 1: Introduction . . . . . . . . . .

Section 2: Basic Definitions and Inclusion
meorem O O O O O O O O O O O O 0

Section 3: A Characterization Theorem for
H-SetS fOr K o o o o o o o o a

Section 4: Minimal H-Sets with Interpolatory
Constraints . . . . . . . . . . .

BI BLIOGRAPHY O O O O O O O o o o o o o o 0

iv

13
32

38
38
4o
47

61
61

62

65

82

105

Figure

Figure

Figure

Figure

Figure

1.1

3.1

3.2

LIST

OF FIGURES

31

68

69

69

84 and 85

INTRODUCTION

Paszkowski [20] and [21] established the
existence and uniqueness of a best approximation to
a prescribed f e C(X), X a compact subset of
[a,b]. from those elements of an n—dimensional Haar
subspace which interpolates f at the points
a :_x1 K...< xk g_b, k g_n. Deutsch [10] extended
the work of Paszkowski and showed a "complete
analogy" between Paszkowski's prdblem and the
classical Chebyshev prdblem of approximating a
continuous function by elements of an n—dimensional
Haar subspace of C(X). H.L. Loeb, D.G. Moursund,
L.L. Schumaker, and G.D. Taylor [16] studied the

prdblem of finding a best approximation to a function

in the set

C(X) = {f E C(X):f(xi) = ai0 and ai0 6 Reals

for i = 1.....k}

from the class

K = {p E M:p(3)(xi) = aij and aij e Reals for

lpooo'k' j: O,...,mi-1 and

k
Z) m. = m < n},
=1

where M is an extended Haar system of order max m.+l.
lgigk
The above problem is often referred to as "approximation

with Hermite interpolatory constraints."

In Chapter I we generalize the problem of
H.L. Loeb, D.G. Moursund, L.L. Schumaker and G.D.

Taylor by replacing K by

K = {p E Uh_1:p(3)(xi) = aij and aij 6 Reals for
(ioj) E I}.

where I is a set of m ordered pairs, m < n, and
Un-l denotes the polynomials of degree n-l. This
problem is referred to as "approximation with Hermite-
Birkhoff interpolatory constraints." We obtain
existence and the characterization of zero belonging
to the convex hull of an apprOpriate set. Using
results due to Ferguson [11] and others on the
existence and uniqueness of a solution of the Hermite-
Birkhoff prdblem.we are able to present an alternation

theorem, a uniqueness theorem, a strong uniqueness

theorem and continuity of the best approximation operator.

In Chapter II we study upper bounds on the
error of best approximation with Hermite-Birkhoff
constraints. Very little work has been done on error
bounds when constraints are present. Paszkowski

compared the error of approximation for his problem,

E;(f), to that of the classical Chebyshev error,

En(f). and obtained E;(f) g_AEn(f), where A is

a constant. we will show that the error of approxi—
mation for our prOblem, E;(f), does tend to zero

as n approaches infinity. Also for suitable f E SIX)
we have E;(f) _<_ AW, where A is a constant.

Lastly we show that there exists an f such that

*
lim sup En(f)/En(f) = m.
11-000

In Chapter III we investigate H—set theory
for approximation with Lagrange interpolatory constraints,
i.e., Paszkowski's problem. H-sets are important in
obtaining lower bounds of the error of approximation.
Collatz introduced the notion of H—sets in 1956 [7]
and has done considerable work in this area. G.D.
Taylor [26] studied minimal H-sets for the classical
Chebyshev approximation problem. In our work we Obtain
a characterization theorem for H-sets for approximation
with Lagrange constraints. We then investigate
minimal H-sets for this prOblem in a manner similar

to G.D. Taylor.

CHAPTER I

APPROXIMATION THEORY WITH INTERPOLATORY

CONSTRAINTS FOR FUNCTIONS OF ONE VARIABLE
Section 1: Introduction and Existence

Let X be a compact subset of some real

interval [a,b] and C(X) denote the usual Banach
algebra of all continuous real-valued functions
defined on X with the uniform norm

(i.e., Hf“ = max[|f(x)‘:x 6 X, f 6 C(X)}).

If K is a subset of C(X) and f E C(X) then define
* I
E (f) = inf{Hf-qH:q e K}.

we call 3p 6 K a best approximation to f e C(X) if

*
and only if E (f) = Hf-pH.

In this chapter we wish to consider the

following problem. Suppose (x. k

1 i=1 C.X is a distinct

set of real numbers, called nodes, satisfying

a ( x1 < x2 <...< xk g_b and I is a set of m

—L

ordered pairs (i,j), where i and j are integers

with l g_i g_k and O < j g m-l. We assume m \ n

and X contains at least n-m+k+l points. Let Hh_1

denote the n-dimensional space of polynomials of

degree g_n-l and define
_ . (j) _ . -
(1.1.1) K — [p E Hn_l.p (xi) - aij for all, (1,3) 6 I},

where {aij:(i,j) 6 I} is a fixed set of real numbers.
The prOblem we wish to study is that of finding best

approximations to functions in the class

5(x) = {f e C(X):f(xi) = ai0 for all (1,0) 6 I}

from the set K.

Paszkowski [20] and [21] established the
existence and uniqueness of a best approximation to a
prescribed f 6 C(X) from those elements of an n-
dimensional Haar subspace which interpolates f at
the points a g_xl < x2 <...< xk g_b. That is, when
the above I is [(i,0):i = 1,2,...,k}. Deutsch [10]
extended the work of Paszkowski and showed a "complete
analogy" between Paszkowski's prdblem and the classical
Chebyshev problem of approximating a continuous
function by elements of an n-dimensional Haar sub—
space of C(X). H.L. Loeb, D.G. Moursund, L.L.
Schumaker and G.D. Taylor [16] studied the problem

of finding a best approximation to a function in C(X)

from the class

K = {p C M:p(3) (Xi) = aij for all (i'j) E I*}I

where

*
I = [(i'j) :for i = 1'2'ooo'k' j = O,l,...,mi-l

k

and Z m.=m]
. 1
i=1

and M is an extended Haar system of order max m.+l.
lgigk
A.L. Perrie [22] generalized the above paper by

replacing the class K by
R(f) -_- [§:(§)(j)(xi) -_- f‘j)(xi) for all (i.j) e 1*,
P E P and q 6 Q}:

where P and Q are finite dimensional subspaces of

cm'1(x).

Our work follows along the same lines as
H.L. Loeb, D.G. Moursund, L.L. Schumaker and G.D. Taylor
except we consider Hermite-Birkhoff constraints rather
than Hermite in an algebraic polynomial setting and
require certain incidence matrices to be poised.
This study includes the above mentioned paper as a
special case when the incidence matrices consist of

Hermite data only.

we end this section by stating an existence

theorem.

Theorem 1.1.1: If K of (1.1.1) is not
empty then there exists at least one polynomial p F K

which is a best approximation to a given f E CIX).

Proof: Since K—q. for any q G K, is a

 

finite dimensional subspace of Hn_1 a standard
compactness argument yields existence, see for example

Cheney [6. p.20]. C]

Section 2: Results on Hermite-Birkhoff Interpolation
In this section we wish to present some
definitions which will be used in the following
sections. we state here only those results on Hermite-
Birkhoff interpolation which will be needed later in

this thesis.

The Hermite-Birkhoff interpolation problem
can be stated as follows. Let there be given positive
integers k and m and let I be a set of m
ordered pairs (i,j), where i and j are integers
with l g_i g_k and O g_j g_m-1. Let x1....,xk
be distinct real numbers, called nodes, and for each
(i,j) G I let aij be a given real number. Then
does there exists a polynomial p(x) in class Qm—l
which satisfies, for each (i,j) 6 I. p(j)(xi) = aij
and if so is it unique?

Historically such interpolation problems were

first studied by G.D. Birkhoff [2] in 1906. Polya |23|

considered the interpolation problem for 2 nodes

in 1931. The current interest in these problems
starts with the work of I.J. Schoenberg [25].
Subsequently contributions have been made by Ferguson
[11], Atkinson and Sharma [1], Karlin and Karon [14]
and [15], 6.6. Lorentz [l7], and many others. The
tepics of these latter papers centers around the

uniqueness of the Hermite—Birkhoff polynomial.

I.J. Schoenberg [25] introduced the concept
of an m-incidence. A matrix B is called an m-

incidence matrix if

i=1,...,k 1if(i,j) GI
E = (eij) , where e13 =
j = O,1,...,m—l 0 otherwise
Note that Z: ei. = m and that E is a kxm matrix
(i.j)61 3

The Hermite-Birkhoff prdblem can now be restated as
follows: given an m—incidence matrix with k rows,
distinct nodes x1....,xk and a polynomial p(x) in
the class Um-l’ ‘which satisfies p(j)(xi) = O for
all eij = l, is p(x) identically zero? Whether

it is identically zero or not we say that p(x)

interpolates the matrix B at the nodes x1....,xk.

A sequence of consecutive 1's in row i,

l is called a block of data. A block

e00 =OOO=

l] eij+£=

of data beginning in column 0 constitutes Hermite data.
If only Hermite data is specified then the prdblem

is known as the Hermite prdblem. The question of
existence and uniqueness is answered positively for

the Hermite prdblem; see Wendroff [28, p.1-6].

Definition 1.2.1: Two m-incidence matrices
E and E are said to be equivalent, if they have
the same number of nonzero rows, and the nonzero rows

of E are a permutation of the nonzero rows of E.

Definition 1.2.2: Given an m-incidence matrix
B and distinct points x1....,xk, E is said to
be poised with respect to x1....,xk if the only
polynomial in nmel ‘which interpolates E at these
points is the zero polynomial. E is said to be
conditionally poised if there are distinct points
x1....,xk with respect to which E is poised. E is
poised (or unconditionally poised) if it is poised
with respect to all choices of distinct points
x1....,xk. If x1....,xk are real points with
x1 <...< xk then B is order poised if it is poised

with respect to these points.

Definition 1.2.3: Let E1 and E2 be m

and mZ-incidence matrices, respectively. If m = m

10

we define a class E1 9 E2 of m—incidence matrices

as follows: E 6 E1 e>E2 if the matrix El consisting

of the first ml columns of E and the matrix E2

consisting of the last m-m1 = m columns of E are

2

equivalent to E1 and E respectively.

2’

Definition 112.4: Given an m—incidence matrix
B, set

O,l.-.-.m-l.

5
II
II
'dbjw
(D
U
II

and

M = m. for q = O'lpooo'm-lo

Hence if p(x) interpolates E with zero
data, mj is the number of requirements on the j-th
derivative and Mg the number of requirements on the
polynomial up to and including its q-th derivative.
The numbers Md are called the Polya constants and
if Mq ;_q+l for q = O,...,m-l then B is said to

satisfy the Polya conditions.

Definition 1.2.5: Let E be a m—incidence
matrix and suppose that the left most one in a block
of ones in row i is eij = 1. Then this block is
supported if there exist indices il'iz'jl' and j2

such that 11 < i < 12, 31 < 3, 32 < j and

11

The following theorem is often called the
Decomposition Theorem. The proof may be found in

Ferguson [11] or Atkinson and Sharma [1].

 

Theorem 1.2.6: Let E1,E be m and

2 1
mZ-incidence matrices, respectively and let m = ml+m2.
If E 4 E1 QIEZ is poised with respect to the
given points x1....,xk, then E1 and E2 must

both.be poised with respect to the same points.
Conversely, if E1 and B2 are poised with respect

to x1....,xk, then every E 6 E1 GE>E2 is pOised

with respect to x1....,xk.

Theorem 1.2.7: (Ferguson [11] and independently,
Atkinson and Sharma [1]). A m-incidence matrix B
satisfying the Pdlya conditions is order poised

if each of its supported blocks is even.

Example 1.2.1: Let x1 < x2 < x3 a x4 be

given nodes and I = ((1,0),(2,l),(2,2),(3,0).(4,0)].

Then the 5-incidence matrix E is

 

 

[1 o o o o.1

o 1 1 o o
E:

1 o o o o

[1 o o o o].

12

Thus, m0 = 3, m1 = 1, m2 = 1, m3 = 0, m4 = 0 and

the Polya constants are Mb = 3, M1 = 4, M2 = 5,

M3 = 5, and M4 = 5. E satisfies the Polya

conditions and the only supported block is even,
hence E is order poised with respect to the nodes

and x .

x1' “2' X3' 4

Example 1.2.2: Let x1 < x < x be the

2 3
given nodes and E be the 9-incidence matrix

[’1 o o o 1 o o o o

 

E = O 1 1 O 1 1 1 O O
1 O O O 1 O O O 04 .
Let 1
r'l O O 0‘ f.l O O O O [
E1 = O 1 1 O and E2 = l l l O 0
1 O O 0‘ l O O O O ,

 

 

then E 6 E1 €>E2. E1 is order poised by theorem 1.2.7

and E2 is order poised since it contains only Hermite
data, thus theorem 1.2.6 implies E is order poised

with respect to x1, x2, and x It should be noted

3.
that this example shows that theorem 1.2.7 is not

necessary for the poiseness of an incidence matrix.

13

Section 3: Characterization Theorem for a Best
Approximation

For the remainder of this thesis, we shall
assume that the m-incidence matrix E satisfies the
Polya conditions and is poised with respect to the
given points a g_x1 < x2 <...< xk g_b. It follows
from definition 1.2.2 that E poised with respect
to the points {Xi}§=l implies the set K1 0f (1.1.1)

is not empty.

Lemma 1.3.1: For any p E K, K-p is an

n-m dimensional subspace of Hn-l'

Proof: That K-p is a subspace of “n—l

is easily checked. We show here that the dimension

of K-p is n-m.

Pick n-m points

}n-m

k
i=1 }

C X - [x i=1'

{Y1 i

Let E1 be the n—incidence matrix defined as follows:

i = l.2,ooo,k+(n“m)

E1 = (eij) j = O,1,...,n-l
where
’1 if (i.j) e I
eij = < 1 if i = k+1,...,k+(n-m)
and J = m-(k+l)+i
\.0 otherwise

 

l4

 

 

That is,
' 1
E O
E = 1
1 1 o
O
I O 1
By theorem 1.2.6 E1 is poised with respect to the
points
k n-m

thus there exist polynomials p1,...,pn_m such that
for each a

(m+i-l) _ . _ _
P: (Y1) - 611 for 1 _ l,2,...,n m

and
p£3)(xi) = O for all (i,j) e I.

These polynomials are linearly independent since

ni‘m
q(X) = a p (x)
£=l ‘ L

0

implies q(m+l-l)

(Yi) = O for i = l, o o o 'n-m' but
by construction

(m+i-l)

(I. .
J.

(y-) = 0

l

q(m+i-l)(yi) = p

i
(m+i-l)
i

and p (yi) = 1 implies ai = O for i = 1,...,n-m.

To see that these n—m polynomials span K-p, consider

q f K-P and let q(m+l-l)(yi) = bi for i = 1,...,n—m.

15

E1 poised with respect to the points
n-m k
[Y1 i=1 U {xi]i=1
n-m
implies q(x) is unique, but 23 bipi(x) satisfies
i=1
the same interpolation conditions, hence
n-m
q(x) = Z bipi.
i=1

Therefore p1,...,pn_m forms a basis for K-p.

That is, K-p is an n—m dimensional space. [3

Now we prove that a best approximation can be
characterized by zero belonging to the convex hull
of an appropriate set. This is a direct generalization
of a similar theorem that holds for the case of
Chebyshev approximation without constraints. In
order to prove the first characterization theorem we
must introduce some notation. For a fixed f 6 61X) and

for each p E K we define

Xp = [y e x:\f(y)-p(y)l = Hf-pH)-

If ¢1,...,¢fi_m represents a basis for K-p, p E K,

A
then for each y e X we shall write y to denote

the vector (¢i(y).¢é(y)....,¢h_m(y)) e Rn-m, where

Rd denotes Euclidean d-space. For any y e X let

A
0(y) = sgn(f(y)-p(y)) and H(0(y)y=y e x]

A _
denote the convex hull of the vectors 0(y)y e Rn m

fer y E X.

16

Theorem 1.3.2: Let f E C(X) and p e K.
Then p is a best approximation to f from K if

and only if

A
(o,...,o) e H[O(y)y:y e xp}.

Proof: (Necessity) Suppose p is a best

approximation to f from K and
A
(o,...,0) g H{o(y)y:y e xp}.

Then by the Theorem on Linear Inequalities [6, p.19]
we have the existence of a q E K-p such that
0(y)q(y) > O for every y 6 XP. Let pX = p+lq
and note that pk 6 K for all 1. Since Xp is

compact there exists a number

6 = min[0(y)q(y)=y 6 XP}

which is positive. Let

x1 = [y e x:0(y)q(y) > g} 0 [y E X=[f(y)-p(y)[

*
>§__.2LQ].
and X

Note that Xp CZX 1 is an open set since

1

it is the intersection of two Open sets. Let

X6 = X-Xl, then XO closed in the compact set X

implies Xb is compact. Therefore there exists a
( /

10 such that for all 0 x l ;.10 and y 6 X0 we

have [f(y)-px(y)[ < E*(f). NOW choose a 1 such

17

'k
that o < x g 10 and [|qu gE—éfl. Then if x 6 x1
*
and f(x) - p(x) > §_%£1. we have 0(x) > 0. Now

0(x) > O and o(x)q(x) > g implies q(x) > 0, thus

f(X) - p(X) - lq(x) g E*(f) - 1q(x) < E*(f)

and * *
f(x) - p(x) - lq(x) > E—éj-L - lq(x) > E302)-
- iéfl > -E*(f) .
If x G X1 and f(x) — p(x) < ~ §:é£l- we have
C(X) < O. 0(X) < O and O(x)q(x) > g implies

q(x) < 0. 'Ihus

* *
f(X) - p(x) " lq(x) < -' m- Xq(x) \‘ __ Lg).

and

* *
f(X) - p(x) - lq(x) 2- E (f) - lq(X) > -E (f).
Thus for all x 6 X we have

|f<x>-px<xn < E*(f).

‘

So px(x) C K is a better approximation to f,
which is a contradiction. Hence p a best approxi—
mation to f implies

A
(0.....0) e H[0(Y)y:y E xp].

(Sufficiency) Suppose p is not the best approximation
to f and that

A
(0,...,0) E H{O(y)y:y 6 Xp].

18

If p is not a best approximation to f from K then
there exists a q 6 K such that Hf-qH < Hf-pH. Thus

for all x E Xp we have

O(x)(f(x)-q(x)) < Hf—qH < Hf-pH = [f(x)-p(x)[

= o(x)(f(x)—p(x)).
Therefore O(x)(q(x)—p(X)) > O for all x e Xp, which

implies by the Theorem on Linear Inequalities that

A
(0.....0) f H{O(y)y=y F Xp].

Hence we have a contradiction; so

A
(0.....0) e H[O(y)y:y G xp}

implies p is a best approximation to f from K. D

Theorem 1.3.2 is true for any set K, where
the corresponding m—incidence matrix E is poised
with respect to the points x1....,xk. The poiseness

guarantees a basis for K.

One would like p a best approximation to f
from K to be equivalent to f—p having at least
n-m alternations, since this is the case for Chebyshev
approximation without constraints, see Cheney [6, pp.73—
75]. This is also true in F. Deutsch [10] and
H.L. Loeb, D.G. Moursund, L.L. Schumaker and G.D.
Taylor [16]. However, here the equivalence is not

true unless an additional condition is imposed on the

19

set K. In all the above studies the equivalence is
Obtained through contradiction, here it is possible

that all polynomials in K pass through some fixed

point (xo.yo), even though no constraint was

0' If x0 is also an extermal point
for f-p (i.e., lf(xO)-p(x0)[ = E*(f)) then no

specified at x

better approximation can be constructed. Also with
no further condition on K it is possible that f-p
alternates n-m times and p agrees with another
element q E K at n-m points distinct from
[Xi]:=l and yet q # p. Thus f-p alternating

n-m times and p E K not a best approximation to

f does not lead to a contradiction. An example

of the above problems and other difficulties is

given at the end of this section in Example 1.3.2 .

To obtain the new condition we must first
define a new incidence matrix E which is obtained
from E. Let r and s be non-negative integers

with O g_s g_r g n—m and let

S r
{‘11 i=1 U {”1 i=s+l

be a set of r distinct points in X, with

]r

[k
i=s+l

(“’1 C [Xi i=l'

Relabel the set

20

s k
[“1 i=1 U [Xi}i=1
as {t }k+s where t < t < < . Now define
1 i=1 1 2 "' tk+s
the (m+r)-incidence matrix B as follows:
N i: 1,...,k+S
(1.3.1) E = (di.)
3 j = O,...,m+r—l
where
r 1 'f t — e {x )k and
1 i ‘ XL i i=1
(2:1) 6 I-
. _ r
d = 1 if ti — x2 6 {wi i=1 and
13 j=min[j:(£,j) {I}.
. s . _
1 if ti 6 {ui}i=l and j — 0.
K0 otherwise.

 

Example 1.3.1:

and x1 ( 111 < X2 = w1

 

1 1
1 o

t‘= 1 1
1 o

. 1 0

Suppose

1 o o o o ]

O O l 1 O

O O O O O

( x3 < 112 then
0 O O O O O O W
O O O O O O O
O 1 1 O O O O
O O O O O O O
o o o o o o o J .

 

21

Remark 1.3.1: All the ones of E appear in
E and have the same column location. Furthermore,

if i1 and i are two row indices for E and if

2
if and i; are the row indices of E where the
ones of row i1 and 12 are found respectively,

then 11 > 12 implies 11 > 12.

We can now define the additional prOperty that

the set K must have to get an alternation theorem.

Definition 1.3.3: The set K possesses

 

property P if and only if the (m+r)-incidence matrix

E defined above is poised with respect to the points

k

U {u i=1'

{xi 1

Remark 1.3.2: If the m-incidence matrix

 

E = (eij

property P.

) has only Hermite data then set K has

This is true since the (m+r)-incidence matrix
E = (dij) has the property that dij’ = 1 implies
di' = l for j = O,l,...,j'. That is, E has only

3
Hermite data.

Remark 1.3.3: If the m—incidence matrix B
/
satisfies the Polya conditions and all blocks not
starting in the first column are supported even blocks

then K has property P.

22
Proof: First, the only blocks found in E
that do not start in column 1 are even blocks which
correspond to even blocks in E. The even blocks of
E are supported and remark 1.3.1 implies that the

even blocks of B have the same supports.

Secondly, we show E, satisfies the POlya
conditions. Let Mj, j = O,...,m+r-1 and Mj,
j = O,...,m-l denote the POlya constants of E
and B, respectively. Since all the ones of E
appear in E' with the same column location

Mj 21Mj 2,j+l for j = O,l,...,m-l. Now all the

additional ones of E, appear in the first column

or sometimes in a row of E, which correspond to a
row in E. These new ones replace the first zero
appearing in this row of E. In either case M;
equals all the ones of E. Hence M3 = m+r 2 j+1
for j = m,...,m+r-1. Thus the POlya conditions are
satisfied for E. Hence by theorem 1.2.7 E' is
poised with respect to the points and so set K

possesses property P. D

Remarks 1.3.2 and 1.3.3 show that there exist
sets K which have property P. The set K in

remark 1.3.2 corresponds to the set K defined in

23

the paper of H.L. Loeb, D.G. Moursund, L.L. Schumaker,

and G.D. Taylor [16].

For the alternation theorem we need to define

a special polynomial. Let i1....,i£, L g_k, be

k

. such that
i=1

the indices of those points {xi}

(in,O) E I for n = 1,...,1. Let

ui = max[j+l:ei O =...= ei j = l)
n n n

for n = 1,...,1. Now define the polynomial

z “i

H(x) = H (x-X. )
n=1 1n

n

It should be noted that the degree of H(x) is less
than or equal to m, also H(z) = 0 if and only

if z = x1 and (i,O) E I.

Fixing the polynomial H(x) defined above
we can now present an alternation theorem for any

set K possessing prOperty P.

Theorem 1.3.4: Let the set K have property

 

P and H be as defined above. Further assume

f G C(X) and p E K. Then p is a best approximation
to f from K if and only if there exist n—m+1
pOints, yl < y2 <...< Yn-m+l' Wlth yi E X - (x. G {XL

3
xj is a zero of H} for all i, such that

24

a) [f(yi)-p(yi)| = Hf-pH = E*(f)
b) sgn{[f(yi)-p(yi)] H(yi)}

= (-1)i+lsgn[[f(yl)-p(yl)]H(y1)}

for i = l'ooo'n‘m+lo

Proof: (Necessity) Suppose p is a best

 

approximation to f and there exist only r g n-m
points {Yi}i=l where conditions a) and b) hold.

We will show that this allows us to find a better
approximation to f from K which will be a
contradiction. For simplicity, set D(x) = f(x) — p(x)
in this proof.

1&0
that 50 = a, 5r = b and 51 = %(ni+gi) for

First we define r+1 points {g such

i

i = 1,...,r-l, where

*
n1 = inf[x e X:x > yi,[D(x)‘ = E (f) and
sgn[D(x)H(x)] = sgn[D(yi+l)H(yi+l)])
and
*
gi = sup[x 6 X:x \ yi+1,|D(x)[ = E (f) and
sgn[D(x)H(x)] = sgn[D(yi)H(yi)]}.
For i = 1,...,r-1 Ci < “1 since if there exists an
iO such that g. j> n. we could find two more points
11) 10
to add to the set {yi {£1 and still preserve conditions

a) and b) which would contradict our assumption that

25

there are exactly r such points. Furthermore, for
1 = 1"'°'r‘1 Y1 351 < “i Syn-1 5° 51 E(Yi'yi+1)

and also for i = 1,...,r y. E (§i_1.§i).

1

From the definitions of n1, Cl and 51
along with the hypothesis of the theorem we have,
for all x 6 X such that x g_§1, that D(x)sgn H(x)
is between E*(f)sgn[D(y1)H(yl)] and
E*<£)sgnrn(y2)H<Y2>] = <-1)E*<f)sgnl_n(y1)n<yl>1. with
equality possible only for E*(f)sgn[D(y1)H(y1)]. If
x F X and C1 g_x g_§1 then again from the definitions
and hypothesis we have D(x)sgn H(x) strflztly
between E*(f)sgn[D(yl)H(Yl)] and (-1)E*(f)sgn[D(y1)H(yl)]-
Thus for all x E X such that x E [€0.51] we have
D(x)sgn H(x) between E*(f)sgn[D(y1)H(y1)] and
-E*(f)sgn[D(yl)H(yl)] with equality possible only
for E*(f)sgn[D(y1)H(yl)]. By a similar argument, for
all x E X such that x e [§i_1,§i], i = 2,...,r,

i+l *

we have D(x)sgn H(x) between (-1) E (f)sgn[D(y1)H(Yl)]

' 'k
and (-l)lE (f)sgn[D(yl)H(y1)] 'with equality possible
.+ *
only for (-l)1 1E (f)sgn[D(yl)H(yl)].
D(x)sgn H(x) is a continuous function on X
since the only possible points of discontinuity are

points where H(x) = 0, but by construction of H(x),

H(x) = 0 implies x = xi and (i,0) 6 I and at

26

these points D(x) = 0. Therefore since [51-1'51] c X
is compact for i = 1,...,r there exist positive

real numbers 61 such that for all x 6 X n [gi-l'gi]

D(x)sgn H(x) is between (-1)i+1E*(f)sgn[D(y1)H(yl)]

and (—l)i[E*(f)—€i]sgn[D(y1)H(yl)]. NOw pick any
point

k r
z 6 X - ({xi]i=1 U {y.

}r-l
1 i=1

u {5 i=1)

i
and define the (m+r)—incidence matrix E as in equation
1.3.1 for the points

k r-l
}i=1 } U {2).

i=1

U [5

[X1 1
Since K has property P we have E poised with
respect to these points. Hence there exists a polynomial

S(x) E Um such that

+r-l

S(j)(xi) = o for all (i,j) e 1, s(gi) = o

for i = 1,...,r-l
and
r-l
(1.3.2) S(z) = sgn[H(z)- H (z-gi)].
i=1
Since set K has property P ‘we see that S(x) has
r-l
exactly the same zeros as H(x)- H (x-gi), thus
i=1
equation (1.3.2) implies
r—l

sgn s(x) = sgn[H(X)° H (X-§1)]
i=1

27

for all x 6 X. Let

E = min[€i:i = 1,...,r}

and define

q(x) = § <-1>r‘1(-sgn[D(yl)H(yl)]>-n§§§%n-.
we are assuming r g_n-m. Thus degree q(x) = degree S(x) §_

m-l+r-l+1 g_n-1, and so q(x) E Hn_1. For each

zeros]

x E X _ 1of H

q(x)sgn H(x) is between 0 and
c r-l r-l
§[(-1) <-1)sgn[n(y1)n<yl)] -sgni§1<x-§i)]
that is, for all
zeros
i = 1,...,r q(x) sgn H(x) is strictly between 0
and

§[(-l)r-l(-1)sgn[H(yl)D(y1)](-1)r-1+i+l]

G i+1.
= §[(-l)sgn[D(y1)H(y1n(-l) J-
We claim p-q e K is a better approximation
to f than p. Indeed, for all x E [§i_1.§i]
i = 1,...,r we have (f(x)-p(x)+q(x))sgn H(x) between

(-1)i+1E*(f)sgn[D(y1)H(y1)] + q(x)sgn H(x)

and

(-l)i[E*(f)-Ei]sgn[D(yl)H(y1)] + q(x)sgn H(x).

28

so from the properties Of q(x) we have
(f(x)-p(x)+q(x))sgn H(x) strictly between

i+l *

(-1) E (f)sgn[D(Y1)H(Yl)]

and

(-1)i[E*(f) - §]sgn[D(Yl)H(Yl)]

for all x 6 [§i_1,§i] i = 1,...,r. Thus for all

x 6 X
'k 'k
- E (f) < f(X) - (p(X)-q(x)) < E (f)

and this completes the proof of necessity.
(Sufficiency) Suppose p is not a best approximation
and conditions a) and b) hold. That is there exists

q E K such that Hq-fH < Hp-f“. Now we have

(p(X)-q(X))H(X) = (p(X)-f(X))H(X)-(q(X)—f(X))H(X).

Thus at the points yi i=1

sgn[(p(yi)-q(yi))H(yi)] sgn[(p(yi)-f(yi))H(yi)]-

Condition b) gives us

i+l

sgn[[p(yi)-f(yi)]H(yi)} (-l) sgnl[p(yl)-f(y1)JH(Yl)l

for i = l,...,n-m+1. Hence (p(x)-q(x))H(x) alternates
signs at least n-m times. Fix an i, i = 1,...,n-m+1.

Then there are two cases to consider: i) H(yi)H(Yi+1) 3 O

or 11) H(yi)H(yi+l) < o. If H(yi)H(Y ) > 0 then

1+1
the number of zeros of H(x) between (Yi'yi+l) is even,
but the zeros of H(x) between (Yi’yi+l) are elements

of the set

29

j j L}1=1' Xj 6 (Yi:Yi+1) and (3.0) e I}

and these zeros are also zeros of p-q. New

H(yi)H(yi+1) > O and

I(p(yi)-q(yi))H(yi)}-{(p(yi+1)-q(yi+1))H(yi+l)] K 0

implies p(x)-q(x) has an odd number of zeros in
the interval (Yi'yi+1)' We have accounted for an

even number of zeros. Thus p-q has a zero in
k

(Yioyi+1) — [xj j=1 or p-q has a zero of order one
or more at some
k
XL 6 (Yi'Y1+1) U {Xj]j=l°

Similarly, we obtain the same conclusion if

H(Yi)H(Yi+l) < O.

In either case p-q has n-m new zeros

[zi}g;T counting multiplicities. Let s be a non—

negative integer with O g_s g_n-m and let

n-m _ s .n—m
{21 i=1 ‘ {“1 1:1 U [W111=s+1 '
with
n—m k
{W1}1=s+1 C:{X1}1=1 '

~

Now we construct a n—incidence matrix B as in equation
1.3.1. Since the set K has prOperty P this matrix
is poised with respect to the points

3" {3

i=1 “'

[X 1 i=1

i

30

and since p(x) - q(x) interpolates E ‘with zero data
we have p(x) E q(x). This contradicts q(x) being
a better approximation, therefore conditions a) and

b) imply p(x) is a best approximation to f. U

The following example shows what can happen

if our set K does not have property P.

Example 1.32;: Let X = [-l,§] and

O and p’(0) = 0}-

K = {p(x) E H2=p(-1)
Let
. 2
0 1f X E [-1,§]
f(x) = 3(x- 2) if x G [§,l]
3 3
4 . 4
-3 (X- 3) If X E [ll§]1
then f 6 C[x]. As can be seen in figure 1.1 any

polynomial of the form ax2 - a, with [a] g.l, is

a best approximation to f from K.

The set K does not possess property P since
the 3-incidence matrix E defined for the points
[-l,0} U {l} is not poised. That is,

-~

’1 o o
1 o o;

31

 

-1 V

\V/

 

Figure 1.1

32

is not poised with respect to the points [-1,0,1).

The difficulty occurs at x=1 since all polynomials

in K must be zero at x=1. If we try to construct
S(x) as in the proof of theorem 1.3.4 we get

S(l) = O and since x=1 is an extreme point of f-p
we cannot construct a better approximation to f.
Theorem 143.4 would give -x2+l as a best approximation
to f since {0,1} would be the 2 required extreme
points. HOwever all the other best approximation can-
not be characterized by theorem 1.3.4 since they have
only one type of extreme point, i.e., if p is a best
approximation to f and p # -x2+1 then f(x)-p(x) = l

for all extreme points.

Section 4: uniqueness of Best Approximation and Continuity
of the Best Approximation Operator
The previous example shows that when prOperty
P is absent we may not have a unique best approximation.
In this section, as noted earlier, we continue to

assume that the set K has prOperty P.

Theorem 1.4.1: Let the set K have property P
and f G C(X). Then f(x) has a unique best approxi-

mation.

Proof: Let p and q be two distinct best

approximations to f from K, i.e.,

33

Hf-pH = Hf-qH = E*(f). Now Hf-QH = Hf-pH implies

C(X) (f(x)-p(x)) > C(X) (f(x)-q (x))

for all x 6 Xb, 'where 0(x) = sgn(f(x)-p(x)). Thus
o(x)(q(x)-p(x)) 2;O for all x 6 Xb. Let t be a

non-negative integer and z = [Z1 6 Xp:i = 1,...,t

and q(zi)-p(zi) = O). NOw t < n-m since t 2 n-m
implies an n-incidence matrix E may be constructed,
as in equation 1.3.1, which is poised with respect

to the points

n-m k
[z 1 U {xi}i=1

i i=1

and set K possessing property P ‘would then imply
that p E q.

Using the points

{2.}? u [x.}

k
1 i=1 i i

.=1
construct a (m+t)-incidence matrix E as in equation

~

1.3.1. Since E is poised with respect to the points

}k

t
[Z1]1=1 U {x i=1

i

there exists a polynomial h e K such that 0(zi)h(zi) = 1
O — - t C

for i — 1,...,t. Now Xb {zi}i=l is a compact set

and o(x)(q(x)-p(x)) positive and continuous implies

there exists a positive real number 6 such that

0(X)(Q(X)*P(X)) > 6 for every x 6 Xp-[zi]i=1'

34

Let

h x

S(X) = h(X) l

Nlm

Then

t
O for all x E {zi}i=l

(1.4.1) 0(X)(q(X)-p(X)+S(X)) >
}t

E
2 for all x 6 x -{z i=1°

p 1
Since S(x) e K, equation (1.4.1) and the Theorem on

Linear Inequalities implies that

A
(0.....0) é H(o(y)y:y e xp}.

This contradicts the assumption that p is a best
approximation to f from K (see theorem 1.3.2) and

completes the proof. C]

Next we wish to prove a strong uniqueness

theorem for this approximation prOblem.

Theorem 1.4;2: Let f 6 C(X). f A K, K have
property P, and suppose p 6 K is the best
approximation to f. Then there exists a constant

y = y(f) > 0 such that for all q 6 K
[If-q” _>_ [If-PH + YUP-qu-

Proof: By theorem 1.3.2 there exist points

 

y1,...,yt in X? such that the n-m tuple

35

(O,...,O) e H{O(yi) (¢1(Yi)"”'¢n-m(Y1))‘i = 1,...,t

and ¢j' j = l'ooo'n-m' is a baSiS for K-p}o
That is,
(1.4.2) =2 61106! W). (Y ) for j= 1.....n-m.
i= 1
t
where 6i > O for i = l,...,t and 2) 61 = 1. By
i=1

Caratheodory's Theorem we know t g_n-m+l, we now
show that t = n-m+l. Indeed, if t g_n-m, we may

pick additional points zl....,z contained in

n-m—t
X-(Xp U [xi}§=1) such that the matrix equation

 

P ‘ , 1 r T
(11071) - - - ¢1(Yt) 951(21) . . .:¢1(zn_m_t x1 0
d2 (Y1) ° ° ° ¢2 (Yt) ¢2 (21) o o .2¢ (Z H_m_ x2 0

Lgh-m(yl) ¢F‘m(yt) ¢h-m gh-m(zn-m-t) Xn-m] 0.1

h -

 

 

 

 

 

has the non-zero solution

[910(y1). 920(y2)..... 9t0(yt).0.....0]T

Thus there exist constants b1""'bn—m such that the

n-m
polynomial ¢= Z)‘b. 1¢i is non-zero and has the points
i=1
t n-m-t
‘Y1}1=1U‘21]1=1

as zeros. NOw we define, as in equation 1.3.1, an

n-incidence matrix E for the points

{x1}1=1 U {Y131=1 U [211;T-t °

36

Since ¢ interpolates E 'with zero data and since K
has property P ‘we see that ¢'5 0 on X, ‘which
gives us a contradiction, thus t = n-m+l.
NOW let h 6 K-p and “h“ = l. we have
n-m

h = Z] aj¢g, where aj are real constants not all
i=1

zero. From equation (1.4.2) we have
n-m

1:1 910(Yi)h(yi) = 0.

Since our set K has property P ‘we infer that at
least one of 0(yi)h(yi) is positive. Consequently
the expression max[o(yi)h(yi):i = 1,...,n-m] is

a positive continuous function on the set of h e K-p

with ”h“ = 1. Hence the number
y = min[max[0(yi)h(yi):i = 1,...,n-m}:
h E K-p and ”h” = 1]

is positive being the minimum of a positive continuous
function on the compact set {h e K—p:uh“ = 1]. Now
let q 6 K. Then h = p-q/flq—p" is of norm one and
contained in K-p. Thus there exists an index iO for

which 0(yi )h(yi )‘2 y. We then have
0 O

Ilf-qll 2 Curio) (f (yio) -q (1710))

____ C(yio) (f(yio)_p(yio)) + o (yio) (p (Yin) -q (1110))

2 "£13“ + Yup-q“

which completes the proof. [3

37

For each f 6 C(X) let «Hf be the unique
polynomial of best approximation to f from K. As
in the classical case we can show that T is a
continuous Operator, in fact T satisfies a Lipschitz

condition.

Theorem 1.4.3: Let K have property P,
then to each f E 61X) there corresponds a number

1 > 0 such that for all g E C(X)

H'rf- T<3 H _<_ X [If-9

 

 

Proof: See Cheney [6, pg.82]. D

 

CHAPTER II
ERROR ESTIMATES FOR
INTERPOLATORY CONSTRAINTS
Section 1: Introduction
The notation of this chapter is the same as
in Chapter I with the following exceptions. Here

X = [-1,1] and we define a set K.n for each n by

_ . (j) _ - -
Kn _ [p e un_1.p (xi) _ aij for all (1.3) e I].

The sets K.n need not possess prOperty P.
Corresponding to each K.n we define
* o
En(f) = inf ”f-pH.
PEKn
We shall denote the classical Chebyshev error by

En(f) = inf nf-pH.
r1

p6 n-l

Also, let Vi = max{j:(i.j) 6 I} and v = max{vi:

i = 1,...,k}.

*
In this chapter, we study the error En(f)
* .
and compare En(f) to En(f). To the best of our
knowledge S. Paszkowski [20], [21] and Mg‘Von Golitschek

[27] are the only ones that have done any work on this

38

39

prOblem. M. Von Golitschek only considered the case
of one node x1, and allowed non-consecutive constraints.

. * 1
One of his results was En(f) g_Aowf(fi), where A0

is a constant independent of f and n and wf is
the modulus of continuity of f. S. Paszkowski
considered the case where v. = O for i = 1,...,k,

l

i.e., the case of Lagrange interpolatory constraints.

His results were:

i) E;(f) g_A En(f) for all n and A a
fixed constant.

*
ii) For n large enough En(f) 3.2 En(f).

we will show that when at least one constraint is

placed on a derivative there does not exist a constant
'k

A independent of n such that En(f) g_A En(f) for

some f G C(X).

We shall first show that E;(f) does indeed
approach zero as n increases, but no upper estimate
is given. Secondly, we shall show that if
f E C(X) fl CV(X) is such that f(j)(xi) = aij for
all (i,j) E I then E;(f) S-En-V(f(V))’ If f
possesses an extension to an analytic function in
some domain of the complex plane which contains |-1,1]

and if f(J) (xi) = :1ij for all (i,j) c 1 then we

shall prove that E;(f) gQA n(f), ‘where A is a

4O

constant independent of n. Finally we shall show

that even if we require f to be analytic and

f(])(xi) = aij for all (i,j) e I there exists an
f such that
E; (f)
lim sup E_—TET=

*
Section 2: Limit of En(f) Equals Zero
00

Let K = L) Kh. Then the theorem we wish to
n=m

prove in this section is that K is dense in the set
C(X). This theorem will be proven by using the

following lemmas.

Lemma 2.2.1: If f 6 C(X) is such that for
each i = 1,...,k there exists a neighborhood Ni
of xi where f E CV+ 1(Ni)' then for each 6 > 0
there exists a polynomial p(x) such that f(j)(xi) =
p(j)(xi) for all (i,j) e I and furthermore

Hf-pH < €-

Proof: Let h(x) be the Hermite polynomial
k

of degree (12) Vi +k-1) such that h(j)(xi) = f(j)(xi)

=1
for i = l'ooo'k and j = 0,1....,\)io Define
k V'+1
H(x) = H (x-x.) l and let
- 1
i=1
(2.2.1) g(x) = f(x)-h(x)]

 

H(x) °

41

Then q(x) 6 C(X) since if x is not a point of

interpolation then H(x) # O and

ILLX) -h (X)
[I (x)

defines g as a continuous function at such an x.

NOw for x=xi we have f(j)(xi) = h(j)(xi) and

 

H(J)(xi) = O for j = O,l,...,vi, ‘whereas
(vi+1)
H (Xi) # 0- Therefore if we define g(xi) as
(vi+l) (vi+l)
f (xi) -h (xi)
9(Xi) = (v.+1)
i
11 (xi)

then by L'HOpital's rule

lim.g(x) = q(xi)
xaxi

and g is continuous at each Xi'

Now g(x) E C(X) implies by the weierstrass
Approximation Theorem [6, p.66] that given an e > 0
there exists an integer n and a polynomial pn(x)

of degree at most n such that
G
“s(x)-pub!) H _<_ m -
Thus from (2.2.1) we get

Ilf(X)-h(X)-pn(x) H(x) H _<_i_ c.

42

If we let p(x) = h(x) + pn(x)fl(x) then p(3)(xi) =
f(J)(xi) for i = 1,...,k and j = O,...,vi and

the proof is completed. B

In the following lemma we use the notation
Hflhmb] = max{ [f(x) \zx e [a.b]}.

where [a,b] c [~1,1] and f E C[a,b].

Lemma_§.2:g; Let I, be any non-empty subset
of [j:j = O,...,u}, where u is a fixed nonnegative
integer, and let aj be a real number for each
j E I. Assume f E C[a,b], let t be a fixed point
such that a g_t g_b and if 0 E I then a0 = f(t).
Define

G(f) = [q(x) E C[a,b]: there exists a neighborhood
N of t where g E Gui-1W): 9(a) = f(a),

900) = f(b) and 9”) (t) = aj for all

Then given an E > 0 there exists 9 E G(f) such

that “f"g||[a’b] < E.

Proof: (Case 1 a < t < h). f 6 C[a,b] implies

that given an 6 > 0 there exists a 6, with

O ( 6 K min[E§2-, §:£-, such that \f(a)-f(x)] \ g

and \f(b)-f(x)| < whenever \x-a] < 6 and

43

[x4b[ < 6, respectively. NOw we consider
f E C[a+6,b-6] and let q(x) be a polynomial of degree

11 such that

q(3)(t) = aj for all j e I.

Since the span A of <l,(x-t)u+1,(x-t)u+2,...> is an

algebra of continuous functions on [a+5,b-6] which
separates points and contains the constants we have
by the Stone-Weierstrass Theorem [6, p.191] that
there exists a polynomial

n u+i
r(x) = bO + Z} bi(x-t) G A

i=1
such that

“(f(X)“q(x))'r(X)H[a+5,b-5]< g .

\

If 0 c I then f(t)-q(t) = 0 implies [b0] < g thus

“f(x)-q(x)-r(x)+bOH[a+6'b_6] < g .

In either case we get a polynomial p(x) such that

(2.2.2) Hf-PH[a+5,b_5] < g

and p(3)(t) = aj for all j 6 I.

Now for all x F [a,a+5] consider the linear
function 1a(x), 'where

2a (x) = pla+6)6-f(al (x-a) + f(a) .

44

We have £a(a) = f(a), £a(a+6) = p(a+5) and

ux-au ,
IIf-za\|[a,a+5] _<_ [If-f(a) [b.5116] + 3a “Maw-f(a) |.

Now a g_x g_a+6 implies Hx-aH[a a+6]/6 S 1 and so

Hf-£.a“[a,a+6]s- Hf-f(a)u[a.a+£5] + [f(a+6)-f(a)[

+ [f(a+6)-p(a+6)[.

Now by construction of 5 and 6 along with equation

(2.2.2) we have

(2.2.3) Hf-L e.

aU[a,a+5] <

In a similar manner we construct a linear function

lb(x) for every x c [b-6.b] such that
f0?) = lbw). p(b-G) = Lb(b-6) and

(2.2.4) [|f-Lb[|[b_5'b] < 6.
Now we define q(x) e G(f) as follows:

f
£a(x) for all x F [a,a+5]

(2.2.5) q(x) = p(x) for all x E [a+6,b-6]

A

 

£b(x) for all x e [b-5,b].
K
It is clear from the construction and equations
(2.2.2-4) that g c G(f) and

Hf-glha'b] < e.

which completes this case.

45

(Case 2 a = t < b). Proceed as in case 1

except we replace g(x) as defined in (2.2.5) by

P(X) for all x 6 [a,b-5]
g(x) =
1b(X) for all x e [b-6,b].

we again have 9 G G(f) and
Hf-g ”[a,b] < E-

(Case 3 a < t = b). Proceed as in case 1

except we replace g(x) as defined in (2.2.5) by

La(x) for all x 6 [a,a+6]
9(X) = _
p(x) for all x E [a+6,b].

We again have 9 G G(f) and

[If-«111mm t 6.
This completes the proof. D

NOw we define numbers yi for i = O,l,...,k
as follows:

and
x1+1+x

yi =-——7f——- 1 = 1,...,k-l.

We also pick a 6 > 0 small enough such that the sets

Ni = [x G X:|xi-x| g_5} are disjoint for i = 1,...,k-

With this construction yi lies between Ni and

N for i = 1,...,k-l. With the above notation we

i+l

have the following lemma.

46

Lemma 2.2.3: For every f F C(X) and every
4 > 0 there exists f 6 C(X) such that;

(Vi-+1)

1) Pee (Ni) for i=1,...,k.

ii) f(j)(xi) = aij for all (i,j) E I.

111) Hf-fH < 6.

Proof: By lemma 2.2.2, there exist functions

91,...,gk such that for i = 1,...,k we have

1) 9i 4 C[Yi-l'yi]'

(Vi+1)

ii) 91 c C (Ni).

111) 91(Y1-1) f(yi_1) and gi(yi) = f(yi).

iv) géj)(xi) = aij for (i,j) c I.

v

V ]<E-

Uf-giU[Yi-1'yi

Now defining f = 91 for all x 6 [Yi-l'yi] for

i = 1,...,k we have our desired conclusion. D

we can now prove our theorem.

 

Theorem 2.2.4: R = L) K.n = c(x).
n=m
Proof: Let f 6 C(X) and C , 0 be given,
we will show that there exists a polynomial p e K such

that Hf-pH / 6. By lemma 2.2.3 there exists a function

f C C(X) such that:

47

_ (vi+l)
1) f c c (Ni) for 1 = 1,...,k.

ii) f(j)(xi) = aij for all (i,j) G I.

111) Hf—fH < 6/2.
lemma 2.2.1 implies the existence of a polynomial p 6 K

such that HE-PH < 6/2. So we have Hf—pH < 6 which

proves the theorem. E

It should be noted that another statement of

this theorem is: For any f 6 C(X),

*
lim E (f) = O.
ham n

*
Section 3: Comparison of En(f) to En(f)

*
We now prove two theorems which relate En(f)
to the error bound En(f). In the following theorems
we are assuming that f 6 C(X) is sufficiently

differentiable and that
f(j)(x ) = a for all (i j) e I
i ij ' °
Theorem 2.3.1: If f E C(V)(X) then there
exists a constant C independent of n such that

* / (V)
En(f) 1 c En_v(f ).

Proof: Let h(x) 6 Km and define g = f—h.

Now 9 C C(V) (X) and g(j)(xi) = O for all (i,j) 6 I.

48

Since 9 E C(V)(X) we have g(V) 6 C(X). hence by
the classical Chebyshev theory there exists a polynomial

such that p is the best Chebyshev
(v)

p c l.In-l-v

h(V)

approximation to 9 Since is a polynomial

of degree m-l-v g_n-l-v we have

(v) __ (v)
En_v(f ) — En_v(g )-

If there exists an i, l g_i g_m, such that

h(V)(xi) = f(V)(xi) then
[9(V)(Xi)-p(xi)[ = [p(xi)| ;_En_v(f(V)).

(v)

We now integrate 9 v times to get back

to g. That is, we define

and

pl(x) = $1 p(t)dt + 99"“ (x1)

for all x G X. Thus

“(IN-D131” 3 film”) (t) -p(t) [dt

(v)
gc En_v(f ),

1

where C1 is a constant independent of n. Notice

also that if for some 1, 1 < 1 < m, f(V”1)(x.) = h(V’1)(x.)
-— —- 1 1

then

[g(V-1)(xi)-p1(xi)\ = [pl(xi)[ g_c1 En_v(f(V)).

49

Continuing in this manner we get a polynomial

c
pV fln_1 such that
- (j)__ (j) (v)
(2.3.1) 1) Hg pV ”.3 Cv-jEn-v(f ) for
j = O,...,v, where CO = l and
Cv-j are constants independent of n.

(2.3.2) ii) [p£j)(xi)[ g-Cv-jEn—v(f(V)) for all

(i.j) 6 I.

Since the m-incidence matrix E defined for
the m ordered pairs (i,j) E I and the points [x }I=l

is poised with respect to the points (xi):=1 there

i
exist polynomials ¢ij e Um-l such that

(s) _
for (i,j) and (r,s) 6 I, where 6ir is the
Kronecker delta. 80 we define a polynomial ¢(x) of

degree m-l by

(2.3.3) (I = Z (-p(j) (x.))O. ..
(i,j)EI V 1 13

By construction the polynomial h+pv+¢' is in Kn

and thus using equations (2.3.1) and (2.3.3) we have

Hf-(h+pv+¢) n g [[f-(h+pv) n + Hon

(v) _ (j) .
< CVEn_V(f ) +(i§,.‘lj)€I‘ pv (xi)| [[Oijll)
(v) (j
< C E (f ) + m ¢.. -max P (x.) °m.

50

Hence, using equation (2.3.2) we see that there exists

a constant C independent of n such that
E*(f) / [[f-(h+p +91) M K c E (f(U))

which completes the proof. F

We now consider the case where for f e C(X)

and [pn E Hn:Hf—an = En(f) for n = 0,1,...) we
have
lim sup Hf-pnnl/n g_é with q > 1.

11-000
To see that the above prOperty is not vacous we
state the following theorem which may be found in

Meinardus [19, p.90-94].

Theorem 2.3.2: Let f be analytic in some

 

region containing [-l,l] and let 6d be the

supremum of all ellipses with foci -l and 1 such
that f is analytic in the interior of 6q (q equals
the sum of the half axesL Then 6g is called the

regularity ellipse for f. and we have

lim supEVEn(f) = g .

nam
Also if for q > 1 there exists a function f e C[-l,l]

such that

lim supW f;

nam

QIH

51

then f has an analytic extension f which has a

regularity ellipse 6g.

Theorem 2.3.3: Let f E C[-l,1] such that
f(J)(Xi) = aij for all (i,j) E I and let
[pn E Hn:Hf-an = En(f)' for n = O,...}. Furthermore,

assume

lim supivfi (f) < E with q > 1.
n —-q
nam
Then there exists a constant A independent of n

such that
*
En(f) _<_ AMEn (f) for all n l m.

Proof: If f 6 Hz for some 2 then for all
*
n]; L we have En(f) = En(f) = 0. Hence, there is
nothing to prove. Thus we may assume that f is

not a polynomial.

We wish to develOp an upper bound on the

difference f(a) - péj) for j = O,...,v. For any

integer L 'we have
”PM-DJ! 2:. Hpm-fll + Hf-pzn _\_' 2 E£(f).
Thus by Markoff's Inequality [6, p.91] we have

(2.3.4) upg’l-pij) n g 2(lr+l)2-£2-...-(L—j+2)2.EL(f)

j = l,...,v.

52

We now show that

converges uniformly to f(J) — pngj) on [-l,l] for

each fixed j. First, by using (2.3.4) we have

°° (j) (j) (j) ()
llgn(p,+1- P); )H _<_ 23n1l1>£+1~~pfzj H

_<_ 2 23 (141)2-

'(L—j+2)2-E£(f)
=n

_<_ 2 23 (1+1)23. Ez(f)'
£=n
Now applying the root test to this last series and

using our hypothesis we have

 

lim sup.¢/1+l)2jEL (f) < lim sup‘/E£(f)
L

1.400

- 1.

Thus by the Weierstrass Metest the series

'2‘ (p(j) _p(j))
‘=n L+1 L

converges uniformly on [-l,l]. Since the sequence
:Hf-an = En(f), n = 0,1,...) converges uniformly

to f on [-l,l] we know that

Z(p -p£)
L=n L+1

converges uniformly to f-pn on [-1,1]. Thus, using

a theorem from Fulks OD[12, p.370], we have

53

converges uniformly to f(J) - p33) on [-l,l]. So
from (2.3.4), for any integer n and for each fixed

integer l g,j 3 v

(j) (j) _ °° (j) (3')
(2.3.5) Hf --pn H— ”En pfil-p, H

g 2 Z (£+1)2-1.2°...°(L-j+2)2E£(f)
£=n

_<_ 2 «Enm -E (1+1)2j\/E‘L('f)'.
—n

Again, applying the root test to

00

Z (n+1)2j ,/Ez(f)

L=O

and using our hypothesis, we have

 

*WW

lim sup %;+1)2j \/E£(f) _<_ lim sup I“ {/Efif)

 

£4m law
3 fiim sup .‘z/E‘(f)
Lam
Jo?
Therefore
2 (1+1)23 \/E£(f)
2:0
converges. Let
c(.) = E (L+l)2j \/Ez(f).
3 L=O

where C(j) is a constant depending only on j and f.

 

Thus

for

Hit?

901}

54

Thus (2.3.5) implies that

”f(3)_pr£j) H g 2 C(j) F—n(f)

for each fixed n and j = 1,...,v. NOW let
. \/—Eo(f)
C1 = max({C(j):j = 1,...,v] U L——7E——}).
Then
(2.3.6) IIf(J)-prgj) 1| 3 2 c1./En(f)
for each fixed n and j = O,...,v, where Cl is

a constant depending only on v and f.

Since the m-incidence matrix E is poised
with respect to the points {Xi}:=l there exist

polynomials ¢ij 6 Hm_1, (1,3) 6 I, such that

(55):?) (XI) = 6ir éjs' (i,j) and (r,s) e I.

So if we define a polynomial

¢ = z: (f‘j’( .)-p‘j’ .))¢..
(i.j)€I X1 n (X1 13

we have ¢ + pn 6 Kn' Furthermore from equation (2.3.6)

() (')
uf—¢;pnn g.Hf-pnn +(1?3)21‘f J(xi>--pnJ (xi)! H¢in
<E(f) 2c./E f) 2?- ..

“’ n + 1 “( <1.j>e1u¢13”

 

g/En(f) (Jana) +(i2j)61 2 c1u¢ij||).

55

Finally, since ¢+pn EKn and E003) 2En(f)' if

we let

A= (f) + Z 2 c ¢..)
VB (1.3%: 1‘11,”

then A is a constant depending only on v and

*
En(f) g Hf-pn-¢H g AME—Ff .

which completes the proof. U

It should be noted that if equation (2.3.5)
of the above proof we factored out (En(f))e, with

O < E < 1, then equation (2.3.6) would be
(j)_ (j) G
Hf pn H g. 2 clmnwn .

where Cl now depends on v,f and E. With this

change the conclusion of the theorem would be
* E
En(f) g_A(En(f))

for any 0 < E < l, with A a constant depending
on v,€, and f only. This leads to the question of
whether there exists a constant A, depending on v

and f only, such that
*
En(f) _<_ A En(f)

for all f 6 C(X) with f(3)(xi) = aij for all (i,j) E I.

In the following theorem.we answer this question in the

negative.

56

Theorem 2.3.4: For each m, there exists a
function f E E]-l,1] such that
. E;(f)

Remarkyg.3.l: This proof consists of showing

 

that the proof of the analogous theorem in the case
monotone approximation, as presented by Lorentz and
Zeller [18], can be employed here. We will also

show that the function Lorentz and Zeller constructed
can be considered as analytic in some disk containing
[-1,l]. The only requirement that we make is that
one of the interpolation points is O and that the
polynomials in Kh agree with the constructed f for

the Vth derivative at 0, where Y may be one.

Proof: we need the lemma in Lorentz and

Zeller [18].

Lemma: For each y and each b > 0, there
exists a polynomial g with g(Y)(x) 2_O on ]-1,1]
and a polynomial P of degree 3y+4, with the

following prOperties:

1) M < 1. M < 1.
ii) g(Y)(O) = o, p‘Y)(0) < 0.

iii) ‘9”) (0)] > bug-PH > o.

57

NOw we construct a sequence of pairs fi'
Pi' i = 1,2,..., which correspond to increasingly
large bi' Each Pi is a polynomial of degree 3Y+4,

each fi' is an increasing polynomial of degree Ni'

and
(2.3.7) 1) ”fin < 1, “Pi“ < 1
(2.3.8) ii) fiY)(O) = o, piY)(o) < 0,
(2.3.9) iii) ‘P§Y)(O)‘ > bini-Piu > 0.

We can assume that 3Y+4 < N1 < N2 <... and take

bi = (2i+2)N§jl. The function f of the theorem is

defined as follows

C.f.(z)

f(Z) = 1 1

we

where C1 > 0 satisfies

 

C.

1 M1 = max[]fi(z)|:z is a complex number

V\
m
~

and ‘z‘ g_2], i = 1,2,...,

and

iEh+lCi g.Cann-PnH, n = 1,2,...,.

This can be done by defining the numbers Ci inductively
by means of the relation

1 . l
o, p o'—-——_ C ‘f _P |' }

 

 

 

. 1
m1n[§ Ci_1Hfi_1-P. 1

C.
1-

1

i=2'3'000'.

58

Now each

n
Fn(z) = 1E: Cifi(z)

is analytic for |z| g_2, and

 

n a) co
llf-Z c.f.u= 1123 can: 2: c- if.”
i=1 1 1 i=n+l 1 1 i=n+l 1‘ 1
m 1 . m 1
S E ”f.“ = Z: — I
i=n+l iZMi ' 1 i=n+l 12
n oc_> 1
implies Hf - 23 f.“ 4 O as n 4 m since 2) -§'4 0
i=1 1 i=n+1 i

as n 4 m. Therefore Fn(z) converges uniformly to
f(z) in ‘2] g 2 so that f(z) is analytic inside

‘2] g_2. Let

n-l
(2.3.10) ¢h = 1:1 Cifi + cnpn.

Then ¢h is a polynomial of degree Nn~l' Therefore
EN +1(Fn)‘S,HFn-¢h” = Cann-PnH, n = 2,3,--°.
n-l
On the other hand, let Q be any polynomial of degree
- . (Y) _
Nn-l 1n KNn-1+l’ 30 Q (0) — 0. By (2.3.8) and

(2.3.10)

(11(1)!) (0) = cup; Y’ (o)

is negative and hence by Markhoff's Inequality

59

(2.3.11) |¢éY)(o)| = \¢gY)(o)-Q(Y)(o)| g_Ni:1H¢h-QH

|/\

Ni:1(HFn'QH + HFn-¢5H)

ni31<nFn-ou + ennfn-Pnn).

Using equation (2.3.9), (2.3.8) and (2.3.10), respectively,

we have

(2.3.12) (2n+2)Nfi31 Cann—Pnu bncnufn‘PnH

/\

Cn]P£Y)(O)]

n-l
|_Zlcifi( Y) (o)+cnPr(lY) (o) |
1:

ME” (0) \.

Putting (2.3.11) and (2.3.12) together, we have

(2.3.13) (2n+1)CnN::1an-Pnn S_N§:1HFn-QH.

Since Q 6 KNn-1+l we have from (2.3.13)

*

EN

n = 2,3,°°°.

n-l+l(Fn) 2_(2n+1)Cann-PnH,

*
Now we are ready to compare EN +1(f) and
n-1

EN +1(f). From the definitions of the Ci' i = 1,2,...,
n-1

and from (2.3.7) we have

(2.3.14) E) C.Hf. g. E) c. g_c If -P .
i=n+1 1 1“ i=n+l 1 “I n “H

60

Therefore, using (2.3.14) and (2.3.10),
E (f) < E) c.f. - ¢
Nn_1+l "" “i=1 1 1 n”
on n
S..Z> CiniH + H.23Cifi"¢hu
1:

1=n+l

g 2 CIJIfn-IP1n H-

 

 

With Q the best approximation to f (from KN +1
n—1
and equation (2.3.13) we have
3* m-ni Cf on
Nn—l+l i=1 i i
In H \ °°
2|ZC.f.-Q - [23 C.f.]
i=1 1 1 i=n+1 1 1‘
.2 (2n+l)cnufn‘PnH — HiEh+lCifiH.
So from equation (2.3.14)
*
EN +1(f) 22ncnllfn-Pnl].
n-l
Thus
*
EN +1(f) 2nC Hf -P H
n—l . n n n
11m sup 2 11m sup 2 C Hf -P “-= m.
11400 EN +1(f) n-ooo n n n

C]

CHAPTER III
H-SET THEORY FOR APPROXIMATION WITH
INTERPOLATORY CONSTRAINTS
Section 1: Introduction
In this chapter we study H—set theory as
it pertains to approximation with interpolatory

constraints.

Definition 3.1.1: M = M1 U M2 is an H-set
for a class K of continuous real (or complex)
valued functions if and only if there exists no pair

4 . .
a1, a2 - K satisfying al-az > 0 on M1 and

al-az < O on M2. M is said to be a minimal H-
. c .

set prOVided N1 M1 and N2 c M2 ‘Wlth at least

one containment proper and N = N1 U N2 is not

an H-set for K.

H-sets are also called extremal signatures
by many authors. H-sets are important in approximation
theory due to the existence of an "Inclusion Theorem,"
i.e., H-sets are important in finding lower bounds

for the error of best approximation. Collatz I7]

61

62

was the first to consider H-sets and their relation

to an "Inclusion Theorem." H-sets have been studied
by many authors. See for example Brosowski [3], [4],
[5], Collatz [7], [8], [9], L. Johnson [13], Rivilin

and Shapiro [24] and Taylor [26].

The goal of this chapter is threefold. First, to
show that the Inclusion Theorem holds for approximation
with interpolatory constraints. Secondly, to give a
characterization theorem for the H-sets of this
prOblem. Finally, to classify and enumerate all possible
minimal H-sets for the problem of best approximation
to a continuous function by a linear polynomial which

interpolates at a fixed number of nodes.

Section 2: Basic Definitions and Inclusion Theorem

 

Let X be a compact subset of d-dimensional
Euclidean space which contains at least n+1 points.
Let V be an n—dimensional subspace of C(X) spanned

by the functions ¢1,...,¢n, ‘where ¢l ? 1.

Let T = {ti:i = 1,...,m] be a set of m \ n

points (nodes) in X, where we will allow the possibility

that T is empty. Given f 6 C(X) - V we define

63

n
K = [ X? a.¢.:a., i = 1,...,n, are real and
. i i 1
i=1
n
a. . t. = f t. , ' = 1,...,m .
121 1(211(3) ( J) J 1
We require K to be nonempty. If y e K then K-y

is a finite dimensional subspace of V.

we now present the Inclusion Theorem which
gives a lower bound for the deviation E;(f). The
proof of this theorem is essentially the same as the
proof in Meinardus [19, p.13], we present it here

only for completeness.

Theorem 3.2.1: Let hO be a fixed function
in K and suppose a subset D CTX, D n T = ¢, is
prescribed with the prOperty that f(x) - h0(x) # O

for all x E D. If there exist no function h e K

such that

(3.2.1) (f(x)-hO(X))(h(x)-ho(x)) > O for all x E D
then

(3.2.2) E;(f).2 inf[[f(x)-h0(x)[:x e D]

Proof: If inf{[f(x)—ho(x)|:x G D] = 0 then
there is nothing to prove. Hence we may assume
inf[[f(x)-ho(x)|:x G D} > 0. Now if (3.2.2) is not

valid, i.e., if

64

E;(f) < inf[[f(x)-ho(x)[:x c D],
then there exists an hl 6 K such that
E;(f) g Hf-hlu < inf[[f(x)-ho(x)[:x e D},
from.which it follows that
(3.2.3) [f(x)-hl(x)[ < [f(x)-h0(x)[ for all x G. D.
Thus we have
(f(x)—ho(x))(hl(x)-h0(x)) = (f(x)-hem)2
- (f(X)-hO(X))(f(x)-hl(X))
for all x C D. That is
(f(x)-ho(x))(h1(x)'ho(x)).2 [f(x)-ho(xn[[f(x)-ho(x)[
- [f(x)—h1(X)[}
for all x F D. Therefore (3.2.3) gives us
(f(x)—h0(x)) (hl(x)—ho(x)) > O for all x c D,

but this contradicts (3.2.1), which completes the proof.

To see how H-sets are connected to finding

*
lower bounds for En(f) consider the following theorem.

Theorem 3.2.2: (L. Collatz [9, p.45]) Let
M = M1 U M2 be an H-set for K and suppose for
hO C K that (f(x)-ho(x)) > O for x F M1 and
(f(x)-h0(x)) < O for x G M2. Then

E;(f)‘2 inf[[f(x)-h0(x)[:x e m].

65

Proof: Let hl be any element of K- Then
M an H-set implies that it is not possible for
(h1(x)-ho(x)) > O for all x 6 M1 and (h1(x)-ho(x)) < O
for all x 6 M2. Thus, using the hypothesis, it is

not possible for
(f(x)-h0(x))(hl(x)-ho(x)) > 0 for all x E M.

Now if we let M equal the set D of the Inclusion

Theorem we have the conclusion

* a
En(f)-2 inf[[f(x)-h0(x)[:x G M}. D

Section 3: A Characterization Theorem for H-Sets for K

 

First we show that the determination of H—sets
for K is equivalent to the determination of H-sets

for the homogeneous interpolation problem.

Theorem 3.3.1: Let

 

Ko

n n
[12: ai¢i:1§] ai¢i(tj) = O for all tj 6 T}.

Then M = M1 U M2 is an H-set for K if and only if

M is an H-set for K

Proof: Let M be an H-set for K and suppose

M is not an H-set for KO. We will show that this

leads to a contradiction. If M is not an H-set for

K0 then there exists an he'KO such that h(x) > O

66

for all x C M and h(x) < O for all x 6 M2. Let

1

h be an arbitrary element from K and consider the

1
elements h1 and h2 = hl-h of K. We have

(h1(x)—h2(x)) > O for all x C M and (h1(x)—h2(x» < O

l
for all x C M2. But this contradicts the fact that

M is an H—set for K. Thus M an H-set for K

implies M is also an H—set for KO.

Now suppose M is an H-set for KO but not

for K. we will again obtain a contradiction. M
not an H-set for K implies there exist h1 and

h2 C K such that (hl(x)-h2(x)) > O for x C M1

and (h1(x)-h2(x)) < O for x 6 M2. But h1 - h2

is an element of K0 and thus we have our contradiction.

Therefore M an H-set for KO implies M is an

H—set for K. D

Due to theorem 3.3.1 we will only consider

the problem of finding H-sets for K Before we

0.
can characterize the H-sets for Kb we need some

definitions.

Definition 3.3.2: Let S be a point set in
n

 

X. Then J(S) shall denote the image of S in R

with respect to the mapping

J(s) = (¢1(S).¢2(s),...,¢n(s)) for each s C S.

67

Definition 3.3.3: Let M and

. . _ n
T = [t.:i = 1,...,m < n} be two pOint sets in R .

u = Span[0, tZ-tl' o o o ' tm-tl}

which will also be denoted as <t2-tl,...,tm-tl>

and

CW(M,T) = {Q e Rn:Q-t1==A+u(R-t1), where
A C u, R C H(M) and u is a positive

real number].

If m=O (i.e., T=¢) then CW(M,T) = H(M)
which is the case studied by Taylor [26] and

Brosowski [3].

Remark 3.3.1: If M = [Rl,...,Rk} then

CW(M,T) may also be defined as

k

[Q C Rn:Q-t1 = A + Z: a.(R.-tl), where A E m
i=1 1 1

and ”i 2_O, i = 1,...,k, with at least one

nonzero.].
Remark 3.3.2: Since a is a linear subspace
of Rn, CW(M,T) may also be defined as

{Q 6 anq-tl = u(A+R-t1), where A e u, R e H(M)

and u. is a positive real number}.

68

Example 3.3.1: Let M: {(1.1).(1,0)} and
T = {(0,0)}. Then CW(M,T) is the wedge between the
rays from (0,0) through (1,1) and from (0,0)
through (1,0). It includes the rays except the

point (0,0). See Figure 3.1.

Example 3.3.2: M = ((1.0,0), (0,1,0), (0,0,1)}
and T = [(0,0,0)}. Then CW(M,T) is the first octant

including boundary except (0,0,0). See Figure 3.2.

 

 

 

Figure 3.1

69

 

Figure 3.2

 

 

 

Figure 3.3

70

Example 3.3.3: M = [(0,1,0)(l,l,0)} and
'r = {(0,0,0). (o,o,1)}. Then CW(M,T) is all the
points between the two half planes determined by
[(0,l,0)} U T and [(l,l,0)] U T respectively.
CW(M,T) includes the half planes except for the line
determined by (0,0,0) and (0,0,1), i.e., the

z-axis. See Figure 3.3.

Theorem 3.3.2: CW(M,T) is a convex set.

 

Proof: Let Q and P 6 CW(M,T) where

‘3
r1.

H
II

A+u(R-tl)
and

= B+l(S-t1)

with A,B 6 fl, R,S C H(M) and u > O, X > 0. Let

0 < a < 1. Then
q(Q-tl) + (l-a)(P-t1) = oA + (l—a)B

an R Q—an S—t

+ (am-(1%!) 1») {guru-(17) au-I-(l-a) l

l}°
Since R and S 6 H(M) ‘we have

(l-a) 1
OLLH-(l-a) 1

(11.1

aLH-(l-Q.) A S

R+

in H(M). Thus au+(l-a)1 > 0 implies aQ+(l-a)P C CW(M,T),

which proves that CW(M,T) is convex. C1

71

Theorem 3.3.3: If M is compact and

H(M) n (u + [tl}) = o then

CW (M, T)

CW(M,T) U (m + {t1}).

Proof: First we show CW(M,T) U (m + {tl)) c CW(M,T).
Let A C U + [t1}. Choose a fixed positive point
R C H(M) and consider the sequence {R1}:=1 C'CW(M,T)

defined as follows:

R.-t =A-t

1
1 1 + i(R-tl)'

1

Using the translation invariance of Euclidean distance,

we have
d(A R ) = d(A A + 1(R—t ))
' i ' i l
= d(0 l(R-t ))
’i l
1
= I d(O,R-t1).
Thus
lim d(A,Ri) = d(0,R-tl) - lim % = o,
i-ooo 1400

which implies A E CW(M,T). Therefore
CW(M,T) U(m + [tl})CZCW(M,T).
Next we show that CW(M,T) U(m + [t1}) is

closed. Let {Ri}:=l be a sequence of points in

CW(M,T) U(u + It1}) such that

(3.3.1) lim Ri = R,
i-ooo

72

we must show that R e CW(M,T) U(u + [tl}). Now

R1 6 CW(M,T) U(u + [t1}) implies

where Ai E M. Si 6 H(M) and Hi > O for i = 1,2,'°°

The first thing we show is that the sequence

[ui}:=1 is bounded above. Suppose not, then there exists
a subsequence [Hi }, with ik 4 m as k a m, such
k
that
(3.3.3) lim “1 = m.
kqm k

So if for each ik equation (3.3.2) is divided by
La we have
R
1 Ai
“i (Rik—t1) = ”i + (Sik—t
k k

 

 

(3.3.4) 1).

Because of (3.3.1) there exists an integer N SUCh that

d(Rik,R) 5 l

for all ik z_N. Thus

3 1 + d(R—t 0)

10
for all ik z'N. Hence using equations (3.3.3) and

(3.3.5) in equation (3.3.4) we have

73

l

 

l

 

 

. l '— u. i l
k-m 1k k-m Jk k
A.
1k
= lim d(— , 3. -t1) 2 o.
kam Ui 1k
k
or
A.
1k
U. l l
kam 1 k
k
Thus the distance between H(M) and M + [t1] is zero.

But since H(M) is compact and u + [t1] is closed

this implies H(M) n(u + [tl})#'¢. This contradicts

our hypothesis. Therefore the sequence {Hi}:=l is

bounded above.

Now we consider equation (3.3.2) again.
The sequence {Si}:=l is contained in the compact

set H(M) and hence has an accumulation point S.

:=1 is bounded above and below.

The sequence {mi}

Hence it also has an accumulation point L5 with

0': u / +m. Thus there exists an indexing ik' with
ik 4 m as k 4 m, such that

R. -t = A. +u. (S. -t ),

1k 1 ik ik 1k 1
lim R. = R
1 I

kam k

lim “i = u,

k4m k
and

lim S1 = S.

kem k

74

But this implies the sequence [Ai } converges to
k
A 6 fl, since fl is closed. Thus we have

R-t1 = A+Ll(S-t1) .

where A E m, S C H(M) and u a non-negative real
number. That is R e; CW(M,T) U(m + {t1}) and this

shows that CW(M,T) U(91 + [tl}) is closed.

Now we have CW(M,T) U (21+[t1]) c CW(M,T),
CW(M,T) CCW(M,T) U (flH—[tlD and CW(M,T) U (n+{tl])

closed, thus CW(M,T)

CW(M,T) U (u+{t1}). (:3

Now we present the characterization theorem
for H-sets when interpolatory constraints are placed

on the approximating class.

Theorem 3.3.4: Define

 

m
u = [Q g Rn:Q = 23 xi(.a(ti)-.p(tl)), where
i=2

Xi is real for i = 2,...,m].

If M = M1 U M2 is a finite set with M1 0 M2 = ¢

and M n T = ¢ then M is an H-set for KO if and

only if at least one of the following holds:

1) (91+J(t1)) n H(J(Ml)) 7! 9!.
ii) (m+J(tl)) n H(MMZH 7’ 91-
iii) cw(.a(Ml)..a(T)) n CW(J(M2).J(T)) :1 (5.

75

Proof: (Sufficiency) First we show that if i)
holds then M is an H-set. Suppose i) holds and

n
there exists a polynomial Z) ai¢i 6 K0 such that

i=1
n
(3.3.6) 1E1 ai¢i(Q) / o for Q 6 M1
and
n
(3.3.7) iii ai¢i(Q) < 0 for Q 6 M2.

That is, M is not an H-set.

Let Q be any point in X such that

‘

3(0) C (91+J(t1)) n H(J(Ml)). In what follows we will
n

show that Z‘ ai¢i(Q) > O. This will be our desired

i=1 n n

contradiction since 23ai¢i€ KO implies 23
i=1

a.x. = 0
i=1

11

for all points of u + J(tl).

J(Q) E H(J(M1)) implies by the Caratheodry
Theorem that there exist at most n+1 points
012020 0 - 0 an+1 1n M1; With J(Qi) E J(Ml) for

i = l,...,n+1, such that

n+1
— n+1
where li > O for all i and .Ei xi = 1. This
implies that 1
n+1

(3.3.8) ¢j(o) = .1 xi¢j(Qi). j = 1.....n.
1:

76

n+1
Now (3.3.6) and the fact that 11.2 0 and 2) 11:1
i=1
imply

n+1 n
1E1 11(j21 aj¢j(Qi)) > o .

But this is equivalent to
n n+1

and by (3.3.8) this becomes

n
jEl aj¢j (Q) /‘ O.

n
Thus we have :7 aj¢j positive at Q which is a
3:1

contradiction as JKQ) 6 ”3+ J(t1). Thus condition

1) implies M = M1 U M2 is an H-set.

The proof that condition ii) implies M is

an H-set is similar to the above proof.

Now we shall show that condition iii) implies

M is an H-set. Suppose iii) holds and M is not
n

an H-set, then there exists a polynomial Z: ai¢i 6 KO
i=1
such that
n
(3.3.9) 2: a.¢. (Q) >0 for Q 6 M1
i=1 1 1
and
n
(3.3.10) 1E: ai¢i(Q) < o for Q G M2.

77

n
By the previous argument.we have Z) aiyi > 0 for all
i=1

points (Yl'°"'yn) C.H(J(M1)). we now show

n
1E1 aiyi 2 0 for all pOints (yl....,yn) C CW(J(M1),JCT)).

Let Q 3 (Y1' . ..,yn) be in CW(J(M1),J(T) ). Then by

definition
Q-J(tl) = A + H(R-J(tl)),

where A 6 m, u is a positive real number and
R C H(J(Ml) ) . Hence we have
. = A.+ R.- . t + . t
yJ 3 u(3¢3(1)) (53(1)
for j = l,...,n, where A = (Al"°"An) and
R = (Rl'°"'Rn)° Therefore
n

.A. + . R.- . t
a3 3 j=l aju( J ¢J( l))

n
(3.3.11) 2‘ a.y. _
j=1 33 j

n
a.A. + U 2 a.R.

n

7

=1

n

+ a. . t

:31 j¢3( 1)

n

Z

:1 J 3 3:1 3 J

n n
U 3231 aj¢j (t1) + 3'51 aj¢j (t1).

n
Now since Z3 a.¢. C K (3.3.11) becomes
j=1 3 J O

78

n
Now R e H(J(M1)) implies Z ajRj > 0. Thus 11 > o

3:1
n
implies Z} a.y. > 0 for all points (y ,...,y ) e
j=l j j l n
CW(J(M1) . J(T) ) .
n
By a similar argument 2} ajyj < 0 for all
3:1

points (y1,...,yn) €CW(J(M2),J(T)). Thus
CW(J(M1).J(T)) r) CW(J(M2). J(T)) = 91 which
contradicts condition iii). Hence the assumption
that M is not an H-set is false, i.e., M is an

H-Set o

This concludes the sufficiency of the proof.
(Necessity) Assume M is an H-set and conditions
i), ii) and iii) do not hold. Using theorem 3.3.3

we have

 

(3.3.12) CW(J(MIT.J(T)) = CW(J(M1).J(T)) U (91+.a(t1)).

Thus by using the negations of iii) and ii) we get

from equation (3.3.12) that

 

(3.3.13) CW(J(M1).J(T)) r) H(J(M2)) = (6-

 

Since CW(J(M1),J(T)) is closed and H(J(M2)) is

compact, (3.3.13) implies there exists a hyperplane

n
23 aixi = a which strictly separates the two sets.
i=1

79

Thus without loss of generality, we may assume

 

n
1:31 ixi > a for (x1,...,xn) 6 CW(J(M1),J(T))

and

n
i2: aixi < a for (X1""'Xn) E H(J(M2)).

We now show that there exists a hyperplane

 

which separates CW(J(M1) .J(T)) from H(J(M2)) and
such that the points of fl'+ J(t1) lie on the

hyperplane. First suppose
J(t1) = (¢1(t1).....¢n(tl)) e 9.8-J(t1)

satisfies

MI!

1 ai¢i(tl) = ['3 > (I

i
and that there exists an integer j between 2 and m

such that

n
i=1 ai¢i (tj) = Y ¢ Bo Y 2 0..
New for all 1 the points 1(J(tj)-J(tl)) + J(tl)

are in T + J(t1) and we have

N]:

ai1)‘(¢i(tj)—¢i (1:1)) + (211(5)) = NH» +13.

i 1
Thus by an appropriate choice of l we can get

1(YLB) + B / a which would contradict the fact that

 

n

.23 aixi >u for all points in CW(J(M1),J(T)).

i=1 n

Therefore aixi = B for all points in u'+ J(t1).

i=1

80

n
Now we show that Z) aixi 2.8 for all points
i=1

in CW(J(M1) ,J(T)). Suppose there exists a point

Q = (01. ---.Qn) e CW(J(M1),J(T)) such that

n
K = '
a . 1E: aiQi Y < D.

Now Q C. CW(J(M1).J(T)) implies

(3.3.14) Q-J(tl) = A + 1(R-J(tl)).

Where A = (A1. ooo'An) 6 ”p R = (RllO-ooRn) 6 H(J(M1))I

and l is positive. Recalling the definition of u
n

we see that Z‘ aiAi = 0. Thus (3.3.14) implies that
i=1

n

n
(3.3.15) 1:1 aiQi

MD

+

n

1

Now we consider the points 011 where
Qu - J(t1) = A + uMR-JN’CIH.

with A and R the same as in the definition of 0
above. By the definition of CW(J(M1),JKT)) we have
Q11 C CW(J(M1),JCT)) for any positive U. Furthermore,
since a < Y < B there exists a positive u? such

*
that u (v-B) < a < 8. Thus using (3.3.15) and the
'k 'k

*
point Q11: (Qf’,...,Qg ) we have

81

n £f n * n
.2 aIQi “ .2 aiAi + 11 1.2 ai(Ri'¢i(ti))
i=1 i=1 i=1
n 'k
. t = -' 1 6 .
+ iE1 ai¢1( l) u (Y H) + L \ G
n
But this contradicts the fact that Z) aixi > a for
i=1

all points of CW(J(M1).J(T)) . Therefore we have

n
(3.3.16) 2. aixi _>_f3, (x1.....xn) 6CW(J(M1).J(T)).

i=1

n

(3.3.17) i=1 aixi < (3, (x1....,xn) 6 H(J(M2))
and

n
(3.3.18) 151 aixi ,B' (X1....,Xn) E II + J(tl).

Using the definition of CW(J(M2).J(T)) (3.3.17)

may be replaced by

n
(3.3.19) a.x. < 6. (xl,...,xn) 6 CW(J(M2),J(T)).

. i 1
i=1

Using the negations of i) and iii) and an

argument similar to the above argument we get a
n
hyperplane bixi = e such that

i=1

n
(3.3.20) i§1 bixi > 8. (X1,...,xn) C CW(J(M1),J(T))
n
(3.3.21)

1 bixi _<_ e, (x1....,xn) 6 CW(J(M2).J(T))

l

and

90 (Xlo-o-oxn) 6 i! + cut-1).

n
(3.3.22) b.x.
1:1 1 i

82

n
Adding the hyperplane Z: aixi = H to the hyperplane
n 1:1 n
2) b.x. = 6 ‘we get a hyperplane Z] c.x. = 9+8
. i i . i 1
i=1 i=1
where ci = ai+bi' i = l,...,n. Using (3.3.16)

with (3.3.20), (3.3.19) with (3.3.21), and (3.3.18)

with (3.3.22) we have

n
(3.3.23) 23 c.x.
i=1 1 1

> 6+6. (x1.....xn) e cw(J(Ml).-0(T)).

n
(3.3.24) 131 Cixi < 6+6. (x1.....xn) 6 CW(J(M2).J(T)).

and

n
= t
(3.3.25) i=1 cixi 9+8, (x1....,xn) C M + J( 1).

Hence, recalling that ¢i E l and using
(3.3.23). (3.3.24) and (3.3.25) we have a polynomial
p = (cl-B-B)¢1 + c2¢é +...+ cnfih such that p(x) > 0
on H(Ml), p(x) < 0 on H(M2) and p(x) = O on T.
Thus p C K0 and separates M1 from M: but this
contradicts the fact that M = M1 U M2 is an H-set
of K0. Thus M an H-set for K.O implies at least

one of the three conditions. This concludes the

proof. 0

Section 4: Minimal H-Sets With Interpolatory Constraints

 

In this section V = <l,x1,...,xn> and
n . .
T = [ti C R :i = l,...,m<n+l}. It is assumed that

the vectors ti-tl, i = 2,...,m are linearly independent

83

and hence span a m-l dimensional hyperplane. Here

n n
l
= , , g = , .t.. =
KO [311:2 alx1 x0 1, a:L C R and a0 +i§1 al 31 0.

where tj = (tj1,...,tjn), j = l,...,m}.

Thus K0 is a linear subspace of V and its dimension

is n-m+l. Let h(n,m) denote the number of minimal

H-sets for the space K When T=¢ (i.e., m=0)

0'
G.D. Taylor [26] established the following theorem.

 

Theorem 3.4.1: In Rn there are precisely
h(n) = h(n,0) minimal H-sets where
2 .
k. + 2k. , if n = 2k
h(n) =
k2 + 3k + 1, if n = 2k+l.

The theorem we wish to establish is the following.

Theorem 3.4.17: In Rn there are precisely

h(n,m) minimal H-sets (Card M1 3 Card M2) ‘where

_ h(n-l) + l + n for m=l
h(n,m) =
h(n-m) + 3 + (n-m) if m ;_2,

with h(n-m) as defined in theorem 3.4.1.

The following figure is a list of minimal H—
sets of K0 for dimensions 1,2 and 3. The sets can
be shown to be minimal H-sets by use of the characterization

theorem 3.3.4 and the definition of minimal H-sets.

84

 

 

 

 

I||¢.[ v.[ x - , X)
W x “we
0 7/
x m J)
0
o
x x )
o o
moan m>onm
«nu won one mpmmum Mom
m n A~.mvm.A>.x.Hv u > e u AH.~V u m.A>.x.Hv u >
J .0 x 0
.Nz mo pawom m mmuocmo 0
.HS mo ucfiom m mmuocwo 0 r
_ .uawom \ (:Iillww )0. N
.coflumaomumucfl cm mmuocmo x
r

 

\

m u 345.619 u >
musflom coflumaomnmucH m mucflom :oflumaomumucw N psfiom GOAUMHOQHTUCA H

Figure 3.4

85

Figure 3.4 (cont‘d)

mucfiom coflu
(waomuwpcfl mo mcmHm on“

Ca we a: mo ucflom H

 

mmommm mam: mnemommo

Cw mum as no mucwom m

 

 

woman mam: TEMm

m£u ca mum N: can as

 
   

mmcmamllfiox\»0

mam: wwwmcfi 11.

 

 

moan m>onm

may mm; 620 mumnum Hom
m u 8.me

AN.m.x.av u >

  

souomzmuumu
Townes

 

moan m>onm
ms“ was Tao mummtm Mom

e u 3.8m
AN.>.x.H/ u >

86

From the characterization theorem for H-sets
for KO we see that there are essentially 2 types

of H-sets to be considered. They are:

i) Type 1: (m+tl) n H(Ml) ¥ 0 or
(mtl) r) H(Mz) :4 (2.

ii) Type 2: CW(M1.T) n CW(M2.T) 7! (5

and not type 1.

It should be noted here that we may ignore the action
of the identity function. Thus J(y1,...,yn) may be
considered as (Y1....,yn). Hence CW(J(M1),J(T)) =
CW(M1,T) and CW(M1,T) c: Rn. The type 1 minimal
H—sets are easy to count and will be counted later.
We will now prove that the number of type 2 minimal
H-sets equals h(n-m)+l. That is the type 2 minimal
H-sets equal in count one more than the number of

minimal H-sets G.D. Taylor Obtained for Rn-m.

For the present we will consider only type 2
minimal H-sets. The first theorem, we prove is a

Caratheodry type theorem.

Theorem 3.4.2: Let CW(M,T) ERn and

 

H(M) fl (fl+t1) = ¢. Then every point Q C CW(M,T)
is expressible as a linear combination of elements

of T plus a positive linear combination of less

87

than or equal to n-m+l elements of M. Here

m = Card T and m g_n.

Proof: If Q C CW(M,T) then by remark 3.3.1
k
(3.4.1) Q--t1 = A +23 xi(Ri-—tl).
i=1
i = 1,...,k, at least one is nonzero, and Ri C M
for i = l,...,k. Let us assume k is the minimal
number of elements of M that are needed to

represent Q-t1 as in (3.4.1). Thus in (3.4.1)

xi ) 0 for all i.

Now if k > n-m+1, i.e., k+m-l > n then

the vectors tz-tl' o o o ' tm-tl' Rl-tl' o o o ' Rk-tl are

linearly dependent. That is there exist scalars,

oi, i = 2,...,m and Bi, i = 1,...,k, such that
m k

(3.4.2) .23 oi(ti-tl) +23 Bimi-tl) = 0.
i=2 i=1

Since the vectors ti-tl. i = 2,...,m are assumed
independent and since H(M) n (u+tl) = ¢ at least
two of the 81's are not zero. Thus, using

(3.4.2), (3.4.1) can be written as

k
Q-tl = 130.) +i§i(xi+mi) (Ri-tl).
m
where B(x) = Z) l a.(t.-t1) + A and A is any
i=2 1 1

 

88

real number. Now choosing A correctly, we can

do the following:

1) Keep xi+xBi 2_0 for all i. (Recall

Xi > 0 for all i).

ii) For at least one i, say i0.

1. + is. = o.
lo 10

Thus for this 1 we have

R

i=1
lav-’1O
That is Q-tl C CW(M-[Ri [,T) which contradicts
O
the minimality of k. Therefore k g_m—n+l. C]

We now give a series of lemmas which lead

to our theorem.

Lemma 3.4.3: In R“, M = M1 U M.2 a minimal

 

H-set of type 2 implies:

i) Both M1 and M2 are finite sets

of g_n+l-m elements.

11) If M1 = [R1,...,Rk} and M2 = [81,...,S£}
then the vectors R2-R1,...,Rk-R1 are
linearly independent. i.e., H(Ml) is

a kel simplex. Likewise for M2.

 

89

Proof: Part i) follows immediately from the
definition of minimality for a type 2 H—set and

theorem 3.4.2.

For Part ii) we suppose M1 U M2 is a minimal
H—set of type 2 and that the vectors RZ-Rl,...,Rk-Rl
are linearly dependent, i.e., the vectors span a
space of dimension at most k-2. Let

Q C CW(M1,T) fl CW(M2,T).'rhis implies that
(3.4.3) Q-t1 = A + u(R-t1).

where A C m, R C H(Ml) and u is a positive real
number. New conSider R-R1 C H(Ml) - 1R1} = H(Ml-[R1}).
Since M1 - [R1] = [O,RZ-Rl,...,Rk-R1] 18 contained

in a space of dimension k—2 we have by the

Caratheodory Theorem

k
i=1
l¢10
k
where Y. 2.0: Z) Y. = l and l < i < k. That is
1 i=1 i —- 0'—
i¢lo
E: k k
R = Y.(R.-R ) + Z) Y.R = Z) Y.R..
i=1 i i 1 i=1 1 1 i=1 i 1.
15110 171iO i#io

Thus R 6 H(Ml-{Ri 1). Thus from (3.4.3) we have
0

Q-tl = A + ”(R-t1):

90

where R C H(Ml-{R. ]), i.e.,
10

Q 6 CW(Ml-[RiO),T)f1CW(M2,T).
But this implies that M1 U M2 is not a minimal
H-set of type 2 which is a contradiction. There-
fore vectors Rz-Rl....,Rk-Rl are linearly

independent and our proof is complete. U

Due to lemma 3.4.3 we will from now on

let M1 = [Rl,...,Rk} and M2 = (51,...,s£].

Lemma 3.4.4: Let M1 = [R1,...,Rk] and
{(Rl-tl).--o.(Rk-t1).
(tz-tl),...,(tm—t1)] and v = [(sl-tl),...,(s£-t1),

M2 = [31,...,s£}. If both U

(t2-tl),...,(tm-t1)} are independent then

M = M1 U M2 is not an H—set of type 1.

Proof: If M is an H—set of type 1 then
either (”+t1) F)H(Ml) #’¢ or (fl+t1) nZH(M2) # Q.

Without loss of generality we assume (u+t1) n.H(M1) ¢ ¢.

This implies there exist scalars xi, i = 1,...,k,
k k
such that Z} l.R. C u+t and Z) A. = 1. Thus
.=1 i i 1 .=1 1
k i i
Z} 11(Ri-t1) C 2L But this contradicts the assumption
i=1

that. U is linearly independent. Therefore M is
xuat a minimal H—set of type 1 which completes our

proof. U

91

Lemma 3.4.5: If M = M1 U M2 a minimal
H-set of type 2 then U = [Rl-tl,...,Rk-t1,
tZ-tl' o o o 'tm-tl] and V = [Sl-tl' o o o 1 S L-tl'
t2-t1,...,tm-tl] both consist of linearly independent

elements.

Egggf; Suppose U is a linearly dependent
set. We will show that this implies that M is not
a minimal H—set of type 2. Now U linearly
dependent implies there exist scalars ei, i = 2,...,m,

and Yi, i = 1,...,k, not all zero such that
k

(3.4.4) _EJ ei(ti-t1) + .23 Yi(Ri-t1) = 0.
i=2 i=1
Since the set [tj-t1:j = 2,...,m} is assumed
linearly independent and the set [tj-tl:j = 2,...,m] U
{Ri-tl], for any i, is linearly independent (due
to the fact that M is a minimal H—set of type 2)

we must have at least two Yi's which are nonzero

in (3.4.4).

NOW M a type 2 minimal H-set implies

there exists Q C CW(M1,T) n CW(M2,T) such that

k
(3.4.5) Q-t1 = A + 1:; ai(Ri-tl).

Vfliere A E u. oi > O, i = 1,...,k, and Ri C M.

i = 1,...,k. Due to (3.4.4) equation (3.4.5) may be

92

written as

k
(3.4.6) Q-t1 = 3(1) + iEi(ai+lYi)(Ri-tl)

m
for any choice of 1. where B(A) = A + Zilei(ti-t1).
i=2

So, as we did in theorem 3.4.2, we choose a l(# 0)

such that:

i) at least one oi + AYi = 0, say

ai + lYi = 0.
0 0

ii) All oi + lYiI2_0. (Recall oi > 0

for all i).
Thus we have

k
Q-tl = 3(1) + 1E; (ai+lYi)(Ri-tl)-
iac’i0

But this implies Q 6 CW(Ml-[Ri l). That is M
0

was not a minimal H—set of type 2 which is our

desired contradiction.

The proof that V is linearly independent

is analogous . E]

New using lemmas 3.4.5 and 3.4.4 we present

the following theorem.

93

Theorem 3.4.6: M = M1 U M.2 is a minimal

H-set of type 2 if and only if

i) cw(M1.T) n CW(M2.T) :1 ¢

11) The SGtS U = [Rlntlpooo'Rk-tl'
tz-tl'ooo'tm-tl} and

V = {Sl-tl'...'SL-tl't2-tl'...'tm-tl}

are linearly independent.

iii) For each Q 6 CW(M1.T) n CW(M2.T)

Q-t1 has the unique form

k
,
A+ ZIo.(R.-t ) where A 6 fl and o. > 0, i = 1,...,k.
i=1 i i l i
Q“tl=< )1
13+ ZB-(S.-t1) where B 6 9.! and B- > o, i = l,...,L.
i=1 1 1 l

 

K

Proof: (Necessity) Part i) follows from the

 

definition of a type 2-minima1 H-set. Part ii)
follows from lemma 3.4.5. For Part iii), the fact
that oi > O, i = 1,...,k and 61 > O, i = l,...,L
follows from the definition of a type 2 minimal
H—set, the remainder of the uniqueness follows from
part ii).

(Sufficiency) Part i) and part ii) along with lemma
3.4.4 implies that M is an H—set of type 2. Part

iii) insures that this H-set is minimal. [3

94

Lemma 3.4.7: If M.= M.l U M2 is a minimal

H-set of type 2 then Q,R C CW(M1.T) n CW(M2,T) implies

<Q-t10t2-t1' o o o ' tm-tl> = <R-t1, tz-tl' o o o ' tm-tl>o
Proof: Suppose Q,R C CW(M1,T)(WCW(M2,T).
Then
k
Q-t1 = A + Z- oi(Ri-t1)
i=1

'where A C u and oi > 0, i = 1,...,k. Also

k
R-t = A + .23 aimi—tl)

1 i=1

where A' C m and a; > 0, i = 1,...,k. Thus for

any choice of l

k
(3.4.7) 1(R-t1)+Q-t1 = A + AA +151 (oi+).ai) (Ri-tl) .

Now we choose A such that:

i) At least one of the oi+ko{'s is zero.

ii) oi+loi 2_0, i = 1,...,k.

We must have ai+Nai== 0 for all i, since otherwise

the existence of at least one i, say i where

0'
oi +loi’ ¥ 0 implies
O O
1(R+t1) + Q 6 CW(Ml-[Rio},T) n CW(M2,T),
‘which contradicts minimality of M. But because of

(3.407), ai+mi = O, i = l'ooo'k' implies

95

R-tl E <Q-t1, tz-tl' o o o ' tm-tl>'

which completes the proof. D

Lemma 3.4.8: Let U and V be as defined
in theorem 3.4.6, U = span U and V = span V. If
M = M1 U M2 is a minimal H—set of type 2 then

U D V is an m-dimensional space.

Proof: Since M is a minimal H-set of

type 2 there exists Q C CW(M .T) n CW(M2.T) such

that
. k
A + Z) o.(R.-t ), where A C u and
. i i 1
i=1
Oi /O’ 1:1'ooo'ko
Q-t1 = a z
1 B + Z) 8.(S.-t ), where B C M and
. i i 1
i=1
6' >00 i=l'ooo'zo

1
Thus Q-t1 is in U n V and is linearly independent
from the vectors ti-tl. i = 2,...,m. Hence

= ( _ _ ... _ \ . _ . .
W (Q t1,t2 t1, ,tm tl/ is an m dimenSional

subspace contained in U D V.

Now let R C U n V, i.e.,

k

A' + Z} af(R.-t ) ‘where A’ C u and
. i i 1
i=1

of C R' for i = 1,...,k.

i
L
B' + Z) Bf(S.-tl) where B’ C u and
i=1 1 1

a; s R’ for i = 1,...,t.

96

Thus for any choice of A

k
A+AA + iE)1(ai+).ai)(Ri-tl)
Q+lR-tl =

L
B+lB + _23(Bi+1Ui)(Si-t1).
i=1
Recalling that oi > 0, i = 1,...,k and Bi > 0,
i = l,...,n, ‘we can choose a A ¢ 0 such that

oi+kai 2 0, i = l,...,k and Bi+lfii > 0, i = 1,...,k.

For this choice of l the point
Q+AR E CW(MlpT) fl CW(M2,T).

Thus, using lemma 3.4.7 we have Q+XR-tl C W. Hence

U n U = W’ and is an m—dimensional space. D

By lemma 3.4.3 we know that M and M2 are

1
both finite sets if M = M1 U M2 is a minimal H-set
of type 2. The next lemma puts a further restriction

on the cardinality of M1 and M2.

Lemma 3.4.9: If M = M1 U M2 is a minimal
H—set of type 2 then m+k+L-2 _<_n, where

and L = Card M .

k = Card M1 2

Proof: If U is a subspace of Rn let

 

dim U denote the dimension of U. Now if U and
‘V are 2 subspaces of Rn then dim U U V =

<flim U + dim V - dim U n V. So, if‘we let U and V
lee as defined in theorem 3.4.6 and let U = span U

Eand U = span V then using theorem 3.4.6 and

97

lemma 3.4.8 we have

dim U U U = (k+m-l) + (me-l)-m = k+£+m-2 g_n,

which completes the proof. D

Lemma 3.4.10: If there exist j minimal

 

H—sets of type 2 in Rn-1 then there exist

 

_.]

. . . . n
j +-[n—m/2] + 1 minimal H-sets in R , where

denotes greatest integer.

Proof: We begin by noting that any minimal
H—set in Rn-1 is also a minimal H-set in Rn.
This following immediately from theorem 3.4.6. Thus
any addition minimal H-set of type 2 must be such
that no n-l dimensional hyperplane of Rn contains
the union of CW(M1.T) and CW(M2,T), i.e., no
hyperplane of dimensions n-l contains U U U since
in this case we would have already counted the
configuration while counting the minimal H-sets
in Rn-l. Using lemma 3.4.9 we see that we need
only consider those cases where m+k+L-2 = n, k 2_£'; 1.
But here a straight forward enumeration shows that

we can have at most [n-m/2] + 1 additional

minimal H—sets of type 2.

To see that each of these possibilities

does represent a minimal H—set of type 2 it is

98

only necessary to construct sets M1 = [R1,...,Rk}

. n
that parts i), ii) and iii) of theorem 3.4.6 are
satisfied. To do this, let e1 denote the point
with all coordinates zero except the ith coordinate

which is l and e0 denote the origin. Let

T = [eo,e1,...,em-l} be the fixed set of interpolation
points, M1 = [em,...,em+k-1] and
M2 : [em+£-l+...+en-L+l_en-£+2'em+£~2+en-£+2_en—£+3’

m+L-3 n—L+3 n-L+4 m+l n-l n m n
e +e -e e +e 1 .

'00.,

If n=1 then M2 = [em+...+en}. It is easily seen
that U = (T-{eo}) U (Ml-{e0]) and
V = (T-[e0}) U (Mz-[eo}) are linearly independent
sets. Thus part ii) of theorem 3.4.6 is satisfied.
Any vector in U = span U has the form

1

(a1,...,am_l,o1,...,ok,0,...,0), where ai, oj C R

for i = l,...,m-l and j = 1,...,k. Any vector

in V = span V has the form

(bl'°"'bm-1'Bz"'"BZ'Bl'Bl'""Bl'§2-Bl'63-BZ"°"
62-51-11
'where the last Bl is in the n-b+l coordinate and
Bi'bj C R1' for i = l,...,L and j = l,...,m-l.

From the hypothesis we know that m+k-l = n-b+l.

99

Thus CW(M1,T) n CW(M2,T) is not empty. Also,

U n U = <el,e2,...,em-1,em+em+l+...+em+k-1>o Hence
the representation of a vector in CW(M1,T) n CW(M2,T)
is unique. Therefore parts i) and iii) of theorem

3.4.6 are satisfied and thus M = M1 U M2 is a

minimal H-set of type 2. W

Theorem 3.4.11: In Rn there are precisely

 

h(n-m)+l minimal H-sets of type 2 (Card M1 < Card M2),

where

[r2+2r if n—m=2r20

h(n—m) = 2
r + 3r + 1 if n-m = 2r+l > 0.

2522;; (By induction on n-m, recall m is fixed).
If m=n then by lemma 3.4.9 M = M1 U M2 is a
minimal H—set of type 2 if and only if M1 and M2
each contains a single point. That is for m=n we
get one minimal H-set of type 2. Now if n-m=l
then using lemma 3.4.10 the number of minimal H-sets
of type 2 is l + [%] + l = 2. So using lemma 3.4.10
and proceeding by induction we have

n-m / r2 + 2r if n-m = 2r 2_0

h(n—m) = Z:[%]+l = 2
j=1 r + 3r + 1 if n-m

2r+l > 0.

Thus the number of minimal H-sets of type 2 is

h(n-m)+l and our proof is complete. D

100

This concludes the case of the minimal H-set
of type 2, we will now count the minimal H-sets
of type 1. If M = M1 U M2 is a minimal H—set
of type 1 then either H(Ml) n (fl+tl) # ¢' or
H(Mz) fl (m+tl) #’¢Z We will assume without loss

of generality that H(Ml) fl (”+tl) # ¢.

Lemma 3.4.12: If M is a minimal H—set
of type 1 then H(Ml) is a k-l simplex, i.e.,
1f M1 = {R1,...,Rk} then the vectors Rz-Rl,...,Rk-Rl

are linearly independent.

Proof: M a minimal H-set of type 1 implies

there exists Q C H(Ml) fl (u+tl). Thus

k k
Q = Z) a.R., where 7? o. = l and a. 2_0 for all i.
i=1 1 1 i=1 1 1

Therefore

Q‘Rl = .
1

W

is a point in H([Ri-Rlzi = l,...,k}). If
[RZ-R1,...,Rk-R1} is a linearly dependent set then
by the Caratheodory Theorem every element in
H([Ri-R1:i = l,...,k}) can be written as a linear
combination of k-l elements of [Ri-R1:i==l,...,k].

That is, there exists an integer i such that

O

101

k k
Q-R1 =.Z} Bi(Ri—Rl), where .23 31:1 and 81 2,0
- 1:1 1:].

15110 1:110

for all i.

Thus Q C H(Ml—[Rio}), i.e., M = M1 U M2 18 not

minimal which is a contradiction. [3

Lemma 3.4.13: M is a minimal H-set of type
if and only if H(Ml) is a k-l simplex and
H(Ml) fl (m+tl) consist of a single point interior

to H(Ml).

Proof: (Necessity) Lemma 3.4.12 implies M

is a k—l simplex.

Next, suppose there exists Q C H(Ml) fl (”+t1)
such that Q is in a face of H(M1)J’Then clearly

M is not a minimal H-set of type 1.

If H(Ml) fl (m+tl) contains two distinct
points Q and R in the interior of H(Ml) then the
points 1Q + (l-A)R are in H(Ml) fl (fl+tl) for
0 g_l g_l. Now if we let 1 increase beyond 1
there exists a 10 such that AOQ + (l-x0)R is on a
face of H(Ml) and then we may apply the previous
argument to conclude M is not a minimal H-set.
(Sufficiency) Since H(M1)fl (u+t1) #’¢' we have from

the definition that M is an H-set of type 1. The

102

minimality follows from the fact that if we remove

a point R from M then H(Ml-[R]) no longer

1

intersects fl+tl. G

Corollary 3.4.14: M a minimal H-set of

 

type 1 implies m+k—2 g.n, where m = Card T

and k = Card Ml°

proof: Let M1 = [Rl,...,Rk}. Then by
lemma 3.4.13 dim(<R2-R1,...,Rk-Rl> fl (m+t1)) = 0.

Thus dim(<R2-R1,...,Rk-Rl> U (”+t1)) = k-l+m—l < n. D

Lemma 3.4.15: If there are j minimal H-sets

 

of type 1 in Rn_1, n'Z 1, then there are j+l

minimal H-sets of type 1 in Rn.

Proof: First, it is clear from lemma 3.4.13

that every minimal H-set of type 1 in Rn.1 is

also a minimal H—set of type 1 in Rn. Thus
any additional H-set of type 1 in Rn must be such

that the vectors tz-tl' o o o O tm-tl'RZ-Rll o o o ' Rk-Rl

span Rn, i.e., m+k-2 = n. So this allows the

possibility of one additional H-set of type 1.

To see that such a configuration is possible

we write Rn = Rm-1 @ Rk-l and construct a k-l

Rk-l

simplex in with barycenter at the origin

103

of k_l. Then by embedding in the obvious manner

we shall have our desired configuration. C

Theorem 3.4.16: The number of minimal H-sets

 

of type 1 in Rn, denoted by g(n,m), equals the

following:

n if m = l
g (norm) 2
(n—m)+2 if m'2 2.
Proof: (Case 1, m=l). For m=n=l we only

have the configuration of a line determined by two
points with the interpolation point interior to the
line segment determined by the two points as a

minimal H-set. Now using lemma 3.4.15, we have by

induction g(n,l) = n.

(Case II, m 2 2). The proof here is by
induction on n-m. For n = m 2_2 the dimension
of m is m—lIE l and therefore we get 2 minimal

H—sets of type 1. They are:

1) M1 consist of a single point contained

in m+tl.

ii) M1 consist of 2 points such that

H(Ml) n (m+tl) is a single point.

104

This is all that is possible since corollary 3.4.14
implies m+k-2 g_n and in this case m=n. Hence

Card M = k 3.2.

1
Now we proceed by induction on n-m using
lemma 3.4.15 and we have g(n,m) = 2+(n-m). D
Now using theorems 3.4.11 and 3.4.16 we
have our desired results.

Theorem 3.4.17: In Rn there are precisely

 

h(n,m) minimal H—sets (Card M1 3 Card M2), where

J’h(n-l) + l + n for m = l

h(n,m) =
]‘h(n—m) + 3 + (n-m) for m

[M
N

BIBLIOGRAPHY

BIBLIOGRAPHY

K. Atkinson and A. Sharma, A Partial Characterization
of Poised Hermite-Birkhoff Interpolation
Problems, Siam J. Numer. Anal. 6 (1969), pp.230-
236.

G.D. Birkhoff, General Mean Value and Remainder
Theorems With Applications to Mechanical
Differentiation and Integration, Trans. Am.
Math. Soc. 7 (1906). pp.107-136.

B. Brosowski, Uber Extremalsignaturen Linearer
Polynome in n Veranderlichen, Numer. Math. 7
(1965). PP. 396- 405.

, Uber Tschebyscheffsche Approximation

 

durch Asymptotisch Konvex Funktionfamlien,
Computing,l (1966), pp.214-223.

Uber Tschebyscheffsche Approximation

 

mit Linearen Nebenbedingungen, Math. Z. 88
(1965). pp.105-128.

E.W. Cheney, Introduction to Approximation Theory,
McGraw—Hill, Inc., New York, 1966.

L. Collatz, Approximation von Funktionen bei Einer
und bei Mehreren Unabhangigen Veranderlichen,
Z. Angew. Math. Mech. 36 (1956). PP 198- 211.

, The Determination of H-sets for the

 

Inclusion Theorem in Nonlinear Tschebyscheff
Approximation, Approximation Theory, Proc.
Sympos., Lancaster, 1969, pp.l79-l89. Academic
Press, London, 1970.

, Inclusion Theorems for the Minimal
Distance Rational Tschebyscheff Approximation
with Several Variables, in H.L. Garabedian,
Approximation of Functions, pp.43-56. Elsevier,
1965.

 

105

10.

ll.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

106

F. Deutsch, Uniform Approximation with Interpolatory
Constraints, J. Math. Anal. Appl. 24 (1968),
pp062-790

D. Ferguson, The Question of Uniqueness for G.D.
Birkhoff Interpolation Problems, J. Approx.
Theory 2 (1969), pp.l-28.

W. Fulks, Advanced Calculus, John Wiley and Sons,
Inc., New York, 1964.

 

L. Johnson, Minimal H—sets and Unicity of Best
Approximations, (to appear).

S. Karlin and J. Karon, On Hermite—Birkhoff
Interpolation, J. Approx. Theory, (to appear).

, Poised and Non-Poised Hermite—Birkhoff
Interpolation, (to appear).

 

H.L. Loeb, D.G. Moursund, L.L. Schumaker, G.D. Taylor,
Uniform Generalized Weight Function Polynomial
Approximation with Interpolation, Siam J.

Numer. Anal. 6 (1969), pp.284-293.

G.G. Lorentz, Birkhoff Interpolation and the
Problem of Free—Matrices, (to appear).

G.G. Lorentz and K.L. Zeller, Degree of Approximation
by Monotone Polynomials II, J. Approx. Theory 2
(1969). PP.265-269.

G. Meinardus, Approximation of Functions: Theory
and Numerical Methods, Springer-Verlag, New
York, 1967, (Translated by L.L. Schumaker).

 

 

S. Paszkowski, On Approximation with nodes, Razprawy,
Pat. 14 (1957), 63 pp.

S. Paszkowski, On the Weierstrass Approximation
Theorem, Colloq. Math. 4 (1956—57), pp.206-210.

A.L. Perrie, Uniform Rational Approximation with
Osculatory Interpolation, J. Comp. and
Systemsciences 4 (1970), pp.509-522.

23.

24.

25.

26.

27.

28.

107

G. Polya, Bermerkungen zur Interpolation und zu
Naherungstheorie der Balkenbregung, Z. Angew.
Math. Mech. 11 (1931), pp.445—449.

T.J. Rivlin and H.S. Shapiro, A Unified Approach
to Certain Problems of Approximation and
Minimization, J. Siam 9 (1960). ppo670-699.

I.J. Schoenberg, 0n Hermite-Birkhoff Interpolation,
J. Math. Anal. Appl., 16 (1966). PP.538-543.

G.D. Taylor, On Minimal H—sets, J. Approx. Theory
5 (1972). PP.113—ll7.

M. Von Golitschek, Generalization of the Jackson
Approximation Theorems in the Sense of
C.H. Mfintz, Bull. Amer. Math. Soc. 75 (1969),
pp. 524-528.

B. Wendroff, Theoretical Numerical Analysis,
Academic Press, New York and London, 1966.

 

728

mmmMM
RI1
8"
U1
v.11
T'l."4
S”
R"
E”
VI
"0

3175

1293

llT][[l[Hlll[l[