APPROXleMATION 0F
VECTOR'VALUED FUNCTlflNS

Thesis for theDegrae of Ph. D.
MICHIGAN STATE UNIVERSTTY
LEE WARREN JOHNSON
1967

 

THE“

This is to certify that the

thesis entitled
Appromtion of Vector-valued Functions

presented by

Lee warren Johnson

has been accepted towards fulfillment
of the requirements for

DMflmi

Major professor

Date August 21 , 1967

0-169

 

LIBRARY

Michigan Sate
Umvenity

 

ABSTRACT

APPROXIMATION OF
VECTOR-VALUED FUNCTIONS

by Lee Warren Johnson

Let X be a compact space and let C(X) be the set of
all continuous functions on X to En. Let U be a closed
convex subset of En, with the origin in U. For feC(X),
define M(f) by: M(f)=inf{a\azo, f(x)éaU for all xex.}

If no multiple of U contains the range of f, write M(f)=ax

Let LF be.a linear subspace of C(x). If peLF, call
p an approximation to f if MKp-f)<a>. Call poéLF a best
approximation if pO is an approximation, and if
M(po-f)5M(p-f) for all p in LF.

Let M(p-f)=a<a). We say xeX is an extreme point of
p—f if [p-f](x) is in the boundary of aU. We examine some
of the properties of the extreme points of best approxima-
tions. We define several auxiliary notions, such as a
generalization of H—sets. Several characterizations of
best approximations are given in terms of these auxiliary
notions, and in terms of extreme points. Some applications
and examples are given, including new proofs of several
sell-known theorems, cast in the form of vector-valued
approximations.

We show, for example, how the following theorem of

Lee Warren Johnson

Moursund1 can be treated as a problem in approximation of
vector-valued functions.

Theorem: Let f(x) be twice differentiable on [a,b].
Among all polynomials anxn+---+a1x+ao, of degree n or less,
let p(x) be one that minimizes: maxEWp-ffl,lp'—f'fl}, where

Igl=su lg(x)\. If q(x) is another such polynomial, then
xe a,b

q'=p'o
We apply our results to this problem by setting:
a) F(x)=(f(x),f'(x))
b) LF=gf(x)\P(x)=(p(x),p'(x))9 P(x) of degree n or less}
0) U={(x,y)l -1sxs1, -1sys1}
d) X=[a,b]
Then: M(P-F)=max{flp-f“,IP'-f'WE.

1. Moursund, D. G. "Chebyshev Approximation of a Function
and its Derivatives" Mathematics 9; Computation,
18 (1964). 382-389.

APPROXIMATION OF
VECTORPVALUED FUNCTIONS

By

Lee Warren Johnson

A THESIS

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

DOCTOR OF PHILOSOPHY

Department of Mathematics

1967

”M

f“

< s
0.,V
1

IJ‘\
an

ACKNOWLEDGMENT

The writer wishes to express his appreciation to
Professor D. G. MOursund for his kind assistance and

guidance throughout the preparation of this thesis.

ii

INTRODUCTION

The classical problem of uniform approximation is
formulated as follows:

Let f(x) be a continuous real-valued function on
[0,1]. Among all polynomials p(x)=anxn+---+a1x+ao, of
degree n or less, find one that minimizes:

§2f0,1]|p(x)-f(x)|.

This problem, and many variants of it, have been
studied extensively. In the problem above, it is well
known that there is a solution, called a best uniform
approximation, and that the solution is unique. Further-
more, if p(x) is the best uniform approximation, then
p(x) can be characterized by the following theorem.

Thgorgm: p(x) is a best uniform approximation to
f(x) if and only if there are n+2 points 2:1 in [0,1],
xi<xi+1, such that p(xi)-f(xi)=(-1)i+1d, where
d=p(x1)-f(x1) and |p(x)-f(x) ISIdI for all x€[o,1].

This problem can be extended by considering finite
linear combinations a1g1(x)+---+angn(x) of continuous
"base" functions, rather than polynomials. The problem
can be further compounded by choosing the domain of f(x)
and gi(x) to be an arbitrary compact space, or perhaps a

compact subset of En.

iii

We have chosen to extend the problem in another
direction, by allowing f(x) and gi(x) to take on values
in.En; In Chapter II we have given some examples to show
that this is not a barren generalization.

In Chapter I, we treat the three fundamental ques-
tions of any theory of approximation. These are:
existence of a best approximation; uniqueness of a best
approximation; and the characterization of a best approxi-
mation. 0f the three, the latter is perhaps the most
important; if the characterization is strong enough, it
enables one to construct algorithms to find the best
approximation.

Notationally, we will write: [x|P(xI] for "the set
of all x such that P(x) holds", (xn) for a sequence, and
S(y,R) for the closed n-ball of radius R centered at yEEnu

iv

TABEE OF CONTENTS

CHAPTER I . . . . . . . . . .
CHAPTER II. . . . . . . .
BIBLIOGRAPHY. . . . . . . . .

CHAPTER I

APPROXIMATION OF VECTOR-VALUED FUNCTIONS

In this chapter we will consider the problem of ap—
proximating vector-valued functions. We will define what
is to be meant by an approximation and derive some perti-
nent results. Having deveIOped some of the necessary
theory, we will turn to some applications and examples.

In what follows we will always have:

a) X a compact space

b) C(X) the set of all functions continuous on X to

Euclidean n-space

c) LP a linear subspace of C(X).

Given f in C(X), we will be concerned mostly with
questions of characterization and uniqueness of best
approximations to f by functions in LF. It should be
noted that some of the following theorems are valid in a
more general setting where En is replaced by a real topo-
logical vector space, and LP by a convex subset of C(X).
In the interest of cohesiveness, we have dispensed with
some of this generality.

nginition: Let U be a closed convex set inEn with
a non-empty'interior, and let the origin be in U. For
f€C(X) we define M(f) by:

M(f)=inf[alaao, f(x)€aU for all x61].

1

If it happens that no multiple of U contains the range
of r, define M(f)=oo .

We observe the following about M(f):

a) If f(x)=o for all x in X, then M(f)=o

b) M(tf)=tM(f) for t real, tzo

c) M(f+g)sM(f)+M(g).

To prove the last observation we need the result:
(a+b)U=aU+bU when U convex and a,b are non-negative. To
prove this, note first that we clearly have (a+b)UCaU+bU.
If a=b=o, then (a+b)U=aU+bU. If one of a,b is non-zero,

let au1+bu2 be any element in aU+bU. Choose u3 by:

a b,. . .
u3:;:fiu1+g:fiu2, since U is convex, u3is in U. Then

(a+b)u3€(a+b)U; and since (a+b)u3=au1+bu2, we have shown
aU+bU;(a+b)U.

Now, to prove c), let M(f)=a and M(g)=b. We then
have f(X)CaU and g(X)C.bU. Consequently,
(f+g)(X)Cf(X)+g(X)CaU-I~bU. A8 (f+g)(X)C(a+b)U, we see that
M(f+g)sa+b=M(f)+M(g).

If the convex set U is absorbent (that is, for each
y€En some multiple of U contains y) and symmetric, then of
course the function M defines a norm on C(I). However, we
will not wish to restrict our considerations to just absor-
bent and symmetric sets U.

Definition: Let ream), pELF. Then 1) is called an

approximation to f (with respect to U) if MKp—f)<a>.

As usual, pOELF is a best approximation if M(po-f)SMKp-f)
for all p in LP.

By way of example consider the following problem:

Let f(x) have a continuous derivative on [0,1].
Among all polynomials p(x) of degree n or less, find the
ones that minimize: max[“p-f", "p'—f'”], subject to
p(xl2f(x) for all x€[o,1]. Herele-f" is the uniform
norm, "p-ffl= sup Jp(x)-f(xfl .

x 0,1

We can place this problem in our context by defining
U=[(x,y)l ogxgl, ~1sygl]. Also, let F(x)=(f(x),f'(x)),

LF= P(x)|P(x)=(p(x),p'(x)), p(x) is a polynomial of degree:%
Then if X=[o,1], we have F maps X continuously into E2, and
LP is a linear subspace of C(X).

If M(P—F)=a, then for all xE[0,1], (P-F)(x)gaU. Hence,
(p(x)-f(x), p'(x)-f'(x))€aU for all xE[o,1], and no smaller
a will suffice to contain the range of P—F.

But (P—F)(x)§aU means that a2p(x)-f(x)zo, and that
azp'(x)-f'(x)2-a. Thus M(p-f)=a gives us that p(x)zf(x)
for all x€[o,1], and that a=max[}p-ffl,"p'-f1fl . Therefore,
finding P€LF that is a best approximation to F is equiva-
lent to solving the problem as originally posed.

Many problems in approximation of real-valued func-
tions, such as the one above, can be reformulated as pro—

blems in approximations of vector—valued functions. In

Chapter 2 we will examine some more problems of this type,

4

and we will attempt to apply results derived in this chap-
ter to them.

A standard result in the theory of uniform approxima-
tion of real-valued functions is that the set of best
approximations is convex when the set of approximating
functions is convex. We can readily obtain a similar
result.

Theorem 1: Let p and q be two best approximations to
f. If h=tp+(1-t)q, o<$<4, then h is also a best approxi-
mation to f.

‘22293: This follows immediately from the subadditi-
vity of M. Let MKp-f)=M(q-f)=a. Then as p is a best
approx imat ion , M( h-f )Za .

But, M(h—f)=M(tp+(1-t)q—f)StM(p-f)+(1-t)M(q-f)=a .
Therefore, MKh-f)=a, and consequently, h is a best approxi-
to f.

If p and f are real functions, and if p is an approxi—
mation to f, the extreme points of p—f are those points x
such that |p(x)-f(x)l=flp-f|. Best uniform approximations
can be characterized in terms of their extreme points. The
extreme points also play an important role in deciding
questions of uniqueness, and in the construction of algo-
rithms to find best approximations. We will define an
analog for vector-valued approximations.

In all that follows we will denote the topological
boundary of U by B(U). we note the following which are

obvious:

a) B(tU)=tB(U) for t real, positive

b) B(z+U)=z+B(U) for zEEn.

Definition: Let MKp-f)=a<a>. Then xdEX is an extreme
point of p-f if [p(xo)-f(xo)]EB(aU). We denote the set of
all extreme points of p-f by E(p,f).

To avoid trivial cases, we will always assume that B(U)
is not empty; that is, that U is not all of En. we will
also assume that M(p-f)>o, for the case M(p-f)=o is ideal,
and nothing of interest can be said.

Theorem 2: If p is an approximation to f, then.E(p,f)
is not empty.

2:92;: For yEEn let "y" be the usual Euclidean norm,
||y|1=fi§+...+y§. Let M(p-f)=a<oo. If E(p,i)=¢, then
(p-f)(XX:aU-B(aU)=V. Since I is compact, (p-f)(X) is come

 

pact. As V is open and (p-f)(X) is compact, the distance
between (p-f)(X) and the complement of V is positive; let
d>o be this distance.

Also, since (p-f)(x) is compact, there is b>o such
that||yflsb for all y in (p-f)(X). Let m be any element of
'(p-f)(X) and y any element of complement V. Then we have:

”(1%)m-y'l2llm-y"-éd.5"m”2“m-y"- .3ng Thus, the distance
between (1+&)Ep-f)(l)l and complement of V is positive.

Therefore, (lt§%4Ep-f)(X%QMCaU. Hence, (p-f)(XX:(§%EE)aU,

which means MKp-f)<a. This is contrary to our assumption,
so it must be that E(p,f)#'¢.

We will now examine some of the properties of the
extreme points of best approximations.

Theorem 3: ‘Let p and q be two best approximations to
f. Let h=tp+(1-t)q, where o<t<1. Then
E(h,f)gE(p,f)nE(q,r).

lggggg: Let M(p-f)=M(q-f)=a. By Theorem 1, M(h-f)=a,
since p and q are best approximations. Let x£E(h,f).

Then h(x)-f(x) is in B(aU). Thus
tp(x)+(1-t)q(x)—f(x)=t[p(x)-f(x)]+(1-t)[q(x)-f(x)] is in
B(aU). It is well known [1], that if y,z are in a convex
set W, and if y is in the interior of W, then the line
segment [y,z] is contained in the interior of W with the
possible exception of 2.

We note that h(x)-f(x) is in the interior of the line
segment joining p(x)-f(x) and q(x)-f(x), both of which are
in aU. In light of the above, we can have h(x)-f(x) in
B(aU) only if both p(x)-f(x) and q(x)-f(x) are in B(aU).
Thus, we have x£E(p,f) and xEE(q,f).

Definition: We call U strictly convex if for y,z
distinct, y€B(U), z€B(U) we have: ty+(1-t)z is not in
B(U) when o<t<1.

Theorem 5: Let p and q be two best approximations to
f. Let h=tp+(1-t)q, where o<t<fl. If U is strictly convex,

then x€E(h,f) if and only if x€E(p,f)nE(q,9) and p(x)=q(x).

7

Proof: If p(x)=q(x), and if x€E(p,fXTE(q,f), then
h(x)-f(x)=t[p(x)-f(X)]+(1-t)[q(x)-f(x)]=p(x)-f(x). Thus,
since p(x)-f(x) is in B(aU), so is h(x)-f(x). Hence,

x€E(h,f).

 

Conversely, suppose x€E(h,f). From Theorem 3, we
have that xEE(p,fXTE(q,f). If p(x) and q(x) are distinct,
then so are p(x)-f(x) and q(x)-f(x). Both p(x)-f(x) and
q(x)-f(x) are in B(aU). Since U is strictly convex, the
open line segment joining p(x)-f(x) and q(x)-f(x) would
then lie in the interior of U. But h(x)-f(x) lies on this
open segment, and we are supposing that h(x)-f(x) is in
B(aU). Hence, it must be that p(x)=q(x).

To avoid introducing too many symbols, we will also
use M in the following natural sense. For yeah, let
M(y)=inf[a| azo, yEaU] . M(y)=oo , if yfaU for all a>o. It
will be clear in the context of the problem whether we are
using M to measure (p-f)€C(I), or whether we are using M
in the sense of a Minkowski functional defined on a portion
of En.

In order to obtain our first characterization theorem,
we will need to restrict the convex set U by requiring that
the set [y€U|M(y)=‘fl be closed. In all that follows, we
will assume that U meets this condition.

By imposing this restriction on U, we are excluding
from consideration such convex sets as V: (x,y)|y2x2 . In

V, the set of 2 such that M(z)=1 is precisely the graph of

y=x2 with the origin removed. We do not, however, exclude

such sets as W: [(x,y)| osxs1, osysl] which have "flat sides".
In W, [}|M(z)=1 consists of the two line segments,
t(o,1)+(1-t)(1,1) and t(1,o)+(1-t)(1,1), where OSts1.
Finally, if the origin is an interior point of U, then
[yEUIMKy)=i] is easily seen to be closed. That this is

true is apparent from the fact that the Minkowski functional
is continuous onEn (in fact, uniformly continuous) when

the function is defined relative to a convex set containing
the origin as an interior point.

Lew: Let y,z be in En, and let a=M(y)<M(z)=-b<oo .
Then, as t ranges in [0,1], MKty+(1-t)z) ranges over all of
[a,b].

Igrgqg: Again, we denote the closed line segment join—
ing y and 2 by [y,z]. Choose t€(a,b), and let G=[y,z]]tU.
G is not empty since ‘(y)=a<t, and thus y€tU. Furthermore,
since G is a closed convex set contained in [y,z], G must
have the form [y,x].

Let M(x)=c. If c<t, we can choose s>o such that
sM(z)+(1-s)M(x)=sb+(1-s)c<t. If x1=sz+(1-s)x, then
x1€(x,z]. Also, M(x1)=M(sz+(l-s)x)SsM(z)+(1-s)M(x)<t.

But M(x1)<t would mean that x1EtU. This in turn gives
x6[y,x1);tU which contradicts our assumption that
[y,z]fltU=[y,x]. Consequently, it must be that M(x)=c2t.
As x€tU, we have MKx)S&. Thus, M(x)=t.

9

Theorem 5: Let b>o,'- (yn)ch. IfJ-—(~yn)—> yo, then
(m<yn>)_. Moo).

PM: Since bU is closed, and since the sequence
(yn) is contained in bU, we have yOEbU. Suppose M(yo)=a.
Let e>o be given, and suppose a-ezo. If yn is such that
M(yo)ZM(y'n)+e, we have a—e2M(yn). Hence, yn€(a-e)U.

(a—e)U is closed, and yo¢(a-e)Y; so we can have but finite-
ly many yn such that M(yo)2M(yn)+e. If (a-e)<o, then
M(yn)+e>M(yo) for all n. Thus, in any case, for all but
finitely many yn, we have M(yo)<M(yn)+e.

Suppose M(yo)+esM(yn). Then on the line segment
[yo,yn], we can choose zn such that M(zn)=M(yo)+e=a+e. We
know we can make this choice of zn by the intermediate-value
property of M, proven in the lemma.

If there were infinitely many yn such that
M(yo)+eSM(yn), then the zn chosen would form a sequence
(Zn)' This sequence (zn) would of necessity converge to
yo. By our restriction on U, [z|M(z)=a+e] is a closed set.
We have. chosen the zn so that M( zn)=a+e. If (zn)-9 yo, it
would mean that yo is in the set z|M( z)=a+e . However,
M(yo)=a, and this then means there cannot be infinitely many
yn such that M(yo)+esM(yn). Hence, for all but finitely
many yn, we have M(yo)+e2M(yn). Therefore, we have shown
that (M(yn))—) ll(yo).

99%: Let ll(p—f)=a<oo . Then there is x€E(p,f)
such that M(p(x)-f( x))=a.

1O

Igrggf: Mtp-f)=a means for every n, (p-f)(X) is not
contained in (aq%)U. So we can choose xfiEX such that
M(p(xn)-f(g1))Za-%. As I is compact, we may assume
(xn)_sxo. p-f continuous means (p(xn)-f(xn))—9 P(xO)-f(xo).
Then by Theorem 5 we have M(p(xo)-f(xo))=a.

If p(xo)-f(xo) were not in B(aUL we could extend the
line segment joining o and p(xO)-f(xo) slightly, and the
extended segment would still be in aU. Formally, there
would exist t>o such that (1+t)[p(xo)-f(xo)]€aU. Then we
would have p(xo)-f(xo) in.T§fU ; that is to say,
M(p(xo)-f(xo))<a.

This establishes the corollary.

Theorem 6: p is a best approximation to f if and only
if among all approximations to f, p is best on E(p,f).

,Prgqf: By p is best on.E(p,f) we mean, as usual, that
given any approximation q, M(qef)2MKp-f) when the domain of
q-f and p-f is restricted to E(p,f)CX. To denote this, we
will write M'(q-f)=d, which will mean M(q-f)=d when the
domain of q-f is restricted to E(p,f). That is,
[q(x)-f(x)]€dU for all xEE(p,f) and no smaller multiple of
U will suffice.

Let M(p-f)=a. Suppose p is a best approximation on
E(p,f). Then M'(p-f)=a (by the corollary above). If q is
any other approximation, we have M'(q-f)2am Clearly,
M(q-f)2M'(q-f). Since M'(p-f)=M(p-f), we may assert
M(q-f)ZM(p-f). Hence, p best on E(p,f) means p is a best

approximation.

11

Conversely, suppose p a best approximation,MKp-f)=a.
If p is not best on.E(p,f), then there is an approximation
q such that M'(p-ffi>M'(q—f). Let M(q—f)=b, and
M'(q-f)=a-c, c>o.

Let x£E(p,f) and t€(o,1). Then, as M(q(x)-f(x))Sa~c,
M(tq(x)+(1-t)p(x)-f(x))StM(q(x)-f(x))+(1-t)M(p(x)-f(x))S

t(a~c)+(1-t)a<a.
If x¢E(p,f), then M(p(x)-f(x))<a. Consequently,
M(tq(x)+(1-t)p(x)-f(x))Stb+(1-t)M(p(x)-f(x)). As
M(p(x)-f(x))<a, we can choose t€(o,1) so small that
tb+(1-t)M(p(x)-f(x))<a. By the above, we see that for
each xEX, there is t€(o,1) such that
M(tq(x)+(1—t)p(x)-f(x))<a.

Suppose we cannot choose a fixed t in (0,1) that will
work for all x61. Then for tn=%, we have anX such that
M(tnq(xn)+(1-tn)p(xn)-f(xn))2an Since I is compact, we may
assume (xn)—> x0, x061.

We show first that xd¢E(p,f). If xdEE(p,f), then
(M(q(xn)-f(xn)))—+ M(q(xo)-f(xo)). But, since
M(q(xo);f(xo))sarc, we may choose N so that for nzN,.
M(q(xn)-f(xn))Sa-%. This would give:

M(tnq(xn)+(1-tn)p(xn)-f(xn) )Stn(a-§)+(1-tn)a=a-.§i. This

is contrary to our assumption that

M(tnq(xn)+(1-tn)p(xn)-f(xn) )2a.

12

On the other hand, we see that:
aSM(tnq(xn)+(1-tn)p(xn)-f(xn))stnb +(1-tn)M(p(xn)—f(xn)).
As n—> oo , (1-tn)M(p(xn)-f(xn)) goes to M(p(xo)-f(xo)).
This would mean M(p(xo)-f(xo))=a, or that xHEE(p,f). But
this cannot be, as shown above. So we are led finally to:
there must be some t€(o,1) such that M(tq(x)+(1-t)p(x)-f(x»<a
for all x61. This would say that M(tq+(1-t)p-f)<a in con— A
tradiction to p being a best approximation. To avoid this
contradiction, we must have that p is a best approximation
on E(p,f).

We turn our attention now to the convex set U. It is
well known that for UCEn, if x€B(U), there is a hyperplane
Hx through x such that U lies on one side of Ex. Associated
with this hyperplane Hx is a linear functional Lx such that
either:

a) Lx(z)=1 for all zEHx,

b) Lx(z)=o for all zEHx, and if uEU, then Lx(u)So.

and if uEU, then Lx(u)S1, or

If the origin is an interior point of U, then b) never
happens. Let Q be the set of all such "normalized" linear
functionalslgcthat are associated with supporting hyper-
planes Hx of U.

We now define something which we will call an H—set,
following the terminology of Collatz [2].

Mil-92: A set [xi]§X, together with a correspond-
set of functionals [Ll]: Q, is called an H—set for LF if
there is no function q in LF such that Lj(q(xj))>o for all

xjeH

. l i ll Ill-ll
l“ ll ll I'll-l1 )‘llllll'll‘l‘ll'

13

As an example, let U be the closed unit disc in E2.
Let LF=|:(p(x),P'(X))| p(x) a polynomial, degree p(x)$1], and
X=[O,1].

H-—-)

 

/

47
%%

 

 

I

23 3

 

 

 

 

figure 1.

In the above figure:

H1 a supporting hyperplane of U through (0,1)
H2 a supporting hyperplane of U through (o,-1)
H3 a supporting hyperplane of U through (1,0)

H4 a supporting hyperplane of U through (-1,o)

14

The corresponding linear functionals in Q are: L1(x,y)=y,
L2(X,y)=-y, L3(x,y)=x, and L4(x,y)=-x.

Since LF is the set of all functions P(x):[o,1]-e.32
where P(x) has the form (ax+b,a), we may pick out H-sets
with no difficulty.

For example, 0,1 is an H-set if we correspond o
with L1, and 1 with L2. If Q6LF, then Q(o)=(b,a) and
0(1)=(a+b,o). L1(Q(o))=a, L2(Q(1))=-a, and hence we
cannot have L1(Q(o))>o and L2(Q(1))>o. A less trivial
H-set is given by the correspondence: 0 éénL3,‘%16) L1,
and 1 ée»L4. If there were PELF, such that L3(P(o))>o,
L1(PC%))>0, and L4(P(1))>o, we would have for
P(X)=(p(1),p'(x)) that p(o)>o, p'(-12)>o, and p(1)<o. But
p(x) is linear so there can be no such P6LF. Finally,
the correspondence 0 (,.L3,-%.¢, L2, and 1 €§.L4 is not an
H—set for LP, because the function QGLF, given by
Q(x)=(-x+%,-1), does satisfy L3(Q(o))>o, L2(QC%)X>0 and
L4(Q(1)X>o.

The following theorem is a natural extension of an
important result in the theory of uniform approximation
of real-valued functions. It gives some information about
a lower bound for M(p-f), where p is a best approximation
to f.

Theorem :2: Let [xJQL [LJCQ be an H-set for LF, and
let pELF be a best approximatidn to f, M(p-f)=a. If q€LF,
and if L3(q(xj)-f(xj)k>o for all 13€[%t]’ then for some
xk€ [xi] , we have Lk(q(xk)-f(xk))5a.

15

Proof: We first note that if yeaU, then gy6U. There-

 

fore, for all Li€Q we have Li(%y)s1. Thus, y€aU means
Li(y)Sa for all LiéQ.

Having noted the above, we now suppose the conclusion

3
Lj(q(xj)-f(xj)k>a. M(p-f)=a implies Lj(p(xj)-f(xj))$a.by

of the theorem false. Then, for all x-€[xi , we have

the observation above. This gives us
Lj(p(xj)-f(xj))-Lj(p(xj)-f(xj)X>o. Using the linearity of

J
contradicts our assumption that [II], [Li is an H-set.

L., we obtain Lj(q(xj)-p(xj))>o for all x [x4]. But this

To obtain our next characterization theorem, we will
ask that the convex set U have the following property:
through each y€B(U) there is one and only one supporting
hyperplane (essentially, that B(U) have no corners). If
p(x) is an approximation to f€C(X), then there is a natural
correspondence between x1€E(p,f) and some LiEQ. If
M(p-f)=a, then xi€E(p,f) means that %[p(xi)-f(xi)]€B(U).
Through %[p(xi)-f(xi)], there is a unique supporting
hyperplane, say Hi, with an associated linear functional
IfifiQ. The correspondence xi«¢a L1 is the one to which we
refer in c) and d) of Theorem 8.

Theorem 8: Suppose U is compact, the origin is not
in B(U), and that through each point of B(U) passes one
and only one supporting hyperplane of U. Then, the

following are equivalent:

16

a) p is a best approximation to f

b) p is a best approximation to f on E(p,f)

c) E(p,f) is an H-set

d) For each qGLF, there is xj€E(p,f) such that

Lj(q(xj)-f(xj))2M(p-f).

.Erggf: Before beginning the proof, we will make
several observations and establish two rather obvious
lemmas. First, we observe that for each.y€En, there is
a>o such that by€U for azbzo. This is clear since the
origin is in the interior of U. We should also note that
that [yeUIM(y).-.1] is precisely B(U) when the origin is in
the interior of U. Consequently, [y€U|M(y)=1] is closed.

Law 1: u€U if and only if Li(u)$1 for all L160.

2322:: By construction of Q, if uEU, then Li(u)$1
for all LfEQ.

Suppose Li(y)Sfl for all LfEQ. As remarked, there is
a>o, such that by€U for all b such that oSbSa. Choose the
largest such a, say a'. Then a'yEU, but (a'+t)y¢U for all
t>o. Clearly, there is such a largest value a', for U is
compact, and hence, cannot contain a half-line emanating
from the origin and going through y.

By our choice of a', we have that a'y€B(U). Let
LiEQ be the functional associated with the hyperplane
through a'y. Then Li(a'y)=1, or a'Li(y)=1. But Li(y)SJ,
so that ahs1. Since byEU for all b such that OSbSa', and

since tSa', we have y€U.

17

Every linear functional onEn may be represented as an
inner-product. Thus, if L is a functional, there is a fixed

vector kEEn such that L(x)=(k,x). As usual,

 

(k,x)=k1x1+'°'+knlql. We may define “L" by IILI=\/k$+'°'+k§.

Then with the Euclidean norm on En, we have that:
|L<x>l = I<k.x>lsll LIIII xll=llkllllx
Lemma 2: There is T>o such that I LillfiT for all LiEQ.

 

 

2329:: This follows immediately, since the origin is
an interior point of U. Choose r>o such that an n-ball
centered at the origin, with radius r, is contained in the
interior of U. Denote this sphere by S(o,r). Let 263(0);
and let LEQ be the functional associated with the unique
supporting hyperplane through 2. Then L( z)=1, and if uéU,
L(u)51. Suppose L is given by L(y)=(k,y). The vector
[fifik is in S(o,rX:U; consequently, Lqfiak)s1. Thus,
(k,u-fik)=r||h||s1; or u k||$_;.. Choosing T=% will establish the
lemma.

LeTma 3: Let x€B(U), H the unique supporting hyper-
plane of U through x, and let LEQ be the linear functional
associated with H. Suppose yEEn, and L(y)<o. Then, there
is a>o such that the open segment (x,x+ay) is contained in
U-B(U) .

2122;: Let L(y)=—b, b>o; and, suppose the‘assertion
is false. Then, for all n, x+%y is not in U-B(U). L(x)=1,

so L(xf%y)=L(x)h%L(y)=flqg. As xf%y is not in U-B(U),

18

lemma 1 gives us that there is LHEQ, such that Ln(x+%y)21.
Hence, we have Ln(x+%y)-L(x+%y)2-g.
Since x€U, we may assert Ln(x)=1—dn, dn2o. Using

Ln(x+%y)—L(x+%y)2%, we obtain:

Ln<x>+ph<y>-L<x>-%L<y>=(1-en>+%xh<y>-<1.§>z-g. Thus, we
have éLh(y)2dn. Suppose there is d>o such that dfizd, for
all n sufficiently large. Then, we would have
Ln(y)2ndfi2nd, for large n. But, by lemma 2,
ILh(y)F;"Lh“"yWSKTn
large n. Thus, we may assume that (dn)—> 0. Because
Ih(x)=1-dn, (Ln(x))-> 1=L(x)-

As before, for every m there is kfiEEn such that

 

; so, we cannot have I»n(y)2nd for

Lm(z)=(km,z), for all zEEn. By lemma 2, there is K>o such
thatllkmwSK. By passing to subsequences, if necessary, we
may assume that the sequence (Lm) converges to a linear
functional L'. As noted above, L'(x)=1. Furthermore,
since LnEQ, Ln(u)S1 for all uEU. Thus, H'=|:z|L'(z)=1] is
a supporting hyperplane of U, through x€B(U). By the
supposed uniqueness of supporting hyperplanes, it must be
that H'=H (H the support plane determined by L). Then,
as [2 IL(x)=1]=[z|L'(z)=1], it must be that L=L'.

To gain our contradiction, we need only recall that
Ln(y)2ndn20, and hence L'(y)20. But, we had supposed that
L(y)=rb<n. Hence, for some N, if nzN, x+%y is in U-B(U).

Therefore, there is a>o such that (x,x+ayX:U-B(U).

19

Now we are in a position to prove Theorem 8.

a)=§b): we already have this from Theorem 6.

b)=ec): let p be a best approximation to f on.E(p,f),
with M(p—f)=a. If E(p,f) were not an H-set, then there
would be q'ELF such that Li(q'(xi))>o, for all x1€E(p,f).
Let q=—q'; then Li(q(xi))<o for all xi€E(p,f).

Since p(xi)-f(xi) is in B(aU), we may apply Lemma 3.
Thus, there is af>o suCh that p(xi)+bq(xi)-f(xi) is in
aU-B(aU), for all b€(o,ai). Thus, we have
M(p(xi)+bq(xi)-f(xi))<a when b€(o,ai). Suppose there is no
fixed a. that will work for all xi€E(p,f). That is, there

3
is no ao>o such that for b€(o,aj), all xiEE(p,f),

J
p(xi)+bq(xi)—f(xi) in aU-B(aU).

This being the case, for each n there is xߤE(p,f),
such that p(xn)+%q(xn)-f(xn) is not in aU-B(aU). It is
evident that E(p,f) is closed, and hence compact, since
E(p,fXZX compact. We may assume (Inl-e-xo, xaEE(p,f)-
Applying Lemma 3 to x0, we have: there exists N such that
for b in (o,fi), p(xo)+bq(xo)-f(xo) is in aU-B(aU). In
particular, p(xo)+£Nq(xo)ef(xo) is in aU-B(aU). Hence,
M(p(xo)4?3Nq(xo)-f(xo))<a.

By the way the xn were chosen, p(xn)+%q(xn)—f(xn) is

not in aU-B(aU). Then, since aU-B(aU) is convex,

p(xn)+bq(xn)-f(xn) cannot be in aU-B(aU) when 1:2,}. For

n>_2N, H321}? Thus, p(xn)+£Nq(xn)-f(xn) is not in aU-B(aU)
when n22N. However, p(xo)+i%q(xo)-f(xo) is in aU-B(aU)9

20

and aU-B(aU) is an open set. Furthermore, since (In)—> x0,
we must have for infinitely many 1, that p(xi)h£Nq(xi)-f(xi)
is in aU-B(aU). This is a contradiction; therefore, there
is some ao>o, such that b€(o,ao) implies p(x)+bq(x)—f(x) is
in aU—b(aU).

The image of E(p,f) under (p+bqef) is compact, and is
contained in aU-B(au). Since aU—B(aU) is Open, we can show,
as in Theorem 2, that M'(p+bq:f)<a. But this cannot be,
since p is a best approximation on E(p,f). Thus, it must be
that E(p,f) is an H-set.

c)=>d): suppose there were q€LF such that
Li(q(xi)-f(xi))<a, for all Xf5E(p,f). Recall that if
xi€E(p,f), then Li(p(xi)-f(xi))=a. This existence of qELF,
as postulated above, would lead us to:
Li(p(xi)—f(xi))-Li(q(xi)-f(xi))>o. This would mean
Li(p(xi)-q(xi))>o, for all x1€E(p,f), contrary to c).

d)=%a): this follows immediately. If qELF, and if
Lj(q(xj)-f(xj))zaq then M(q(xj)-f(xj))2ae Since
M(q-f)ZM(q(xj)-f(xj)), M(q—-f)2a=M(p-f). Hence, p is a best
approximation to f.

In the following group of theorems, we will consider
some of the implications of non-uniqueness of best approxi-
mations. we can prove these theorems under weaker hypo-
theses than those that were needed for Theorem 8. That is,
we need not require U to be compact, nor do we need unique
supporting hyperplanes at each point of B(U). Specifically,

we shall require that U be closed, convex, and have an

21

interior point. Further, let [y€U|M(y)=1] be a closed set.

Theorem 9: Let U be as above. If p and q are best
approximations to f, then.E(p,fMTE(q,f)# C.

2299:: Let h(x) be any convex combination of p(x)
and q(x). By Theorem 1, h(x) is a best approximation to
f(x). By Theorem 2, E(h,f)¥ C. From Theorem 3,
E(h,f¥;E(p,fXIE(q,f), so the conclusion follows.

Theorem 10: If p and q are both best approximations
to f, then p and q are best approximations on.E(p,fXWE(q,f).

gpggg: Since E(p,fMTE(q,f)# C, the result is not
meaningless. Let M(p-f)=M(q-f)=a. Suppose there is hELF,
such that M(h(x)-f(x))Sb<a for all x€E(p,fX]E(q,f). Then,
for t€(o,1), M(th(x)+(1-t)q(x)-f(x))<a, whenthE(p,fXTE(q,f).
As in previous arguments, we suppose there is no t6(o,1)
that will work for all of’E(p,f). This gives us a sequence
(XnKE(P,f), such that M(%h(xn)+(1-%)q(xn)-f(xn)) z a.

We can suppose that (xn)_9.xo, xdEE(p,f). Also, since
M(%h(xn)+(15%)q(xn)-f(xn)) goes to M(q(xO)-f(xo)) as n—> an
we see that xdEE(q,f).

Since M(h(x)-f(x))Sb<a for xEE(p,fX]E(q,f), we have
M(h(xO)-f(xo))$b. Then, for n large enough, M(h(xn)-f(xn))<a.
Clearly, M(q(xn)-f(xn))Sa for all n. Using the subadditive
property of M, we have for n large enough:
M(1n-11(xn)+(1-%)q(xn)-f(xn))<;—la+(1-%)a=a. This is contrary ,

to our assumption about the points xn. Thus, there must be
t€(o,1) such that M(th(x)+(1-t)q(x)-f(x))<a, for all
x€E(p,f). But, by Theorem 6, p is a best approximation if

22

and only if p is a best approximation on.E(p,f). Hence,
we cannot have tE(o,1) such that M(th(x)+(1-t)q(x)-f(x))<a,
for all xEE(p,f).

Thus, p must be a best approximation on.E(p,fMTE(q,f).
The same argument will work for q; so the conclusion of
Theorem 10 follows.

Theorem 11: Let p and q both be best approximations
to f. Let h=tp+(1-t)q, o<t<fl. Suppose M(p-f)=M(q-f)=a.

If xEE(h,f), then p(x)-f(x) and q(x)-f(x) are on a common
support plane of aU.

‘nggf: By Theorem 3, E(h,f);E(p,fOOE(qu). Hence, if
xEE(h,f), then p(x)-f(x) and q(x)-f(x) are both in B(aU).
If p(x)-f(x)=q(x)-f(x), we are finished.

Suppose then, that p(x)-f(x)¢ q(x)-f(x). Let L be
the line segment joining p(x)-f(x) and q(x)-f(x). Then
h(x)-f(x)xis in the interior of L. Let H be a support plane
of aU, through h(x)-f(x). We would like to show that H
contains L, and hence, contains p(x)-f(x) and q(x)-f(x).

There are only two possibilities: either LflH=L, or
Iffi:h(x)-f(x). The latter cannot happen, for it would mean
p(x)—f(x) and q(x)-f(x) are on different sides of H. As H
is a support plane of aU, p(x)-f(x) and q(x)-f(x) must be
on the same side of H. Hence, IOH=L, which proves Theorem
11.

Corollary: Suppose LF has the property: given any ks1
points xfEX and ks1 points ffEEn, there is hELF such that
h(xi)=fi, i=1,"'k—1.

23

Let p and q be best approximations to f,
M(p—f)=M(q-f)=a. Then, there are at least k points x in
E(p,fMWE(q,f) such that p(x)-f(x) and q(x)-f(x) lie on the
same support plane of aU.

[22293: Let h be any convex combination of p and q.
Then h is a best approximation on E(h,f). From the inter-
polatory property of LF, it follows that E(h,f) has at
least k points. The corollary follows then, from Theorem 11.

We now prove a theorem that will guarantee the exis-
tence of a best approximation in most of the problems we
consider. The result will be easy to obtain, for we will
ask that the set LF of approximating functions be a finite
dimensional subspace of C(X). Also let X be a metric space.

Theorem 12: Let LF be a finite dimensional subspace
of C(X), and let U be compact. For each f€C(X), if f has
an approximation, then f has a best approximation.

2:29;: For yEEn, let "y" be the Euclidean norm. For
f€C(X), let Hffl=22§“f(le Under this norm, C(X) is a Banach

space. Furthermore, "fHSA if and only if f(X¥;S(o,A).

Let a=inf M(p-f) , a<no. For each n, we can choose pfiELF
pELF

such that M(pn-f)$a+%. For all n, (pn-f)(X¥;(a+1)U. Thus,
pn(XEEa+1)U-+f(1fl.

As U and f(x) are compact, we can choose K>o, such that
[(a+1)U+f(X)};S(o,K). Hence, "pnflSK for all n.

Since LF is finite dimensional, a sphere of radius K

in LF is compact. We may assume then, that (pn)-9»po, pdELF.

24

Under the norm of C(X), (pn)—9»po means (pn(x))—9ipo(x)
for each xEX. This will allow us to show that pO is an
approximation, and the M(pO-f)=a.

Let xEX, since [pn(x)-f(x)]€(a+1)U; and since U is
closed, it must be that [po(x)-f(xina+1)U. By Theorem 5,
we can assert M(pn(x)-f(x)) goes to M(po(x)-f(x)) as
n—a oo . Since M(pn-f)$a-%, M(po-f)Sa. Hence,
M(po-f)sm(q-f) for all q€LF.

Theorems 9, 10, 11, and the corollary to Theorem 11,
find their greatest application in resolving questions of
uniqueness of best approximations. Theorems 6 and 8 are
theorems that characterize a best approximation, and are
typically most useful when X is a finite point set.
Theorem 7 finds its utility in measuring how close a given

approximation is to a best approximation on an H-set.

CHAPTER II

APPLICATIONS

In this chapter, we will apply some of the results
of Chapter I to several specific problems. As a first
application, consider the problem below:

(A) Let f(x) have a continuous k-th derivative on
[0,1]. Among all polynomials p(x)=anxn+°°'+a1x+ao, of
degree n or less, find the one that minimizes:

max J[p(x)—f(x)]2+[pv(x)-r-(1012+-o-+[p(k>(x)-r<k>(x)]2‘.
x€[o,1]

 

This problem can be restated as:

(B) Let F(x)=(f(x),f'(x),°'°f‘k’(x)), and let X=[o,1].
Let U be the closed unit sphere in'Ek+1. Let
LF=[P(X)|P(X)=(p(x),p'(x),'-°,p00(x)), p(x) a polynomial,

degree p(X)Sn].

Find PELF that is a best approximation to F.

Clearly, problem (A) and problem (B) are equivalent
problems.

Theorem: Problem (B) has one and only one solution.

2322;; Since U is compact, and since LP is a finite
dimensional subspace of C(X), Theorem 12 will guarantee at
least one solution.

Suppose there were two solutions, say P and Q, to (B).

By Theorem 1, H=iP+iQ is also a best approximation to F.

25

26

Since U is strictly convex, we may apply Theorem 4.
That is, if x'€E(H,F), then P(x')=Q(x')-

We will suppose for the present that nZk. Using the
generalized Vandermonde matrix, it is easy to show that we

k+1

xi in [0,1]. Here, [r] means "the greatest integer in r."

can find SELF such that S(xi)=F(xi), for any [91;] points

Recalling Theorem 5, H is a best approximation to P

if and only if H is a best approximation 0n E(H,F). In

light of the above, E(H,F) must have at least ii: +1
points, for we can fit [%$% points exactly. Hence,
P(X)=Q(x) 0n [ii] +1 points. Consider

P(X)-Q(x)=(p(x)-q(x),p'(x)-q'(x),-“,(k)(X)-q ‘k’un. If
P(x')=Q(x'), then x' is a zero of multiplicity k+1 0f p-q.

We note: (k+1)[%$-‘1'-]2n-k+1. Counting multiplicity,
P‘q has (k+1)([%${]+fl zeroes. But,

(k+1) [fifl]+1)2(n-k+1)+(k+1)=n+2. Hence, counting multi-
plicity, p-q has at least n+2 zeroes. As p,q have degree n,
it must be that qu; and thus PEQ.

If n<k, then ‘%$% =0. However, by Theorem 2, E(H,F)#¢,
so let xfl€E(H,F). Then, as above, P(x')-Q(x')=0. Since
k>n, x' is a zero of p—q, of multiplicity at least n+1. So
again, PEQ. This establishes the uniqueness claimed in the
theorem.

Using Theorem 8, we can characterize the best approxi-

mation in (B) as follows:

27

Theorem: P is a best approximation to F if and only
if the system, (P(xi)-F(xi),Q(xi))>0 xi€E(P,F), is inconsis-
tent for all Q€LF.

‘nggi: For’yEEn, let My” be the Euclidean norm. For
kEEn, let H= [zl(k,z)=l|kI2 . If zES(0,|lkIl), then
[(k,z)k§HkHHzlSHkH2. Thus H is a hyperplane through k,
such that S(0,HkH) is on one side of H. The linear func-
tional, associated with H, is given by L(z)=(k,z).

In problem (B), U is the unit n-ball in En, U=S(0,1).
In particular, if [P(xi)-F(xi)]€B(aU), then "P(xi)-F(xi)“=a.
In view of the above remarks, we may associate a linear
functional Li with xi, where L1 is given by:
Li(z)=%(P(xi)-F(xi),z). Then, Hi=[zlLi(z)={] is a hyper-
plane through-%[P(xi)-F(xi)], with U on one side of Hi'
Here, of course, %[P(xi)-F(xi)]€B(U). Suppose now
M(P-F)=a.

Since U obviously satisfies the conditions of Theorem 8,
P is a best approximation to F if and only if E(P,F) is an
H—set. We have shown above how to correspond a linear func—
tional Li to xiEE(P,F). Given QELF, Li(Q(xi))=
%(?(xi)-F(xi),o(xi)). Hence, E(P,F) is an H-set if and only
if the system -;-(P(xi)-F(xi),Q(xi))>0, xiEE(P,F), is incon-
sistent for all QELF. Since a>0, the theorem is proved.

The theorem which follows is given by Meinardus and
Schwedt [3]. It is the basic inclusion theorem in the
theory of uniform approximation of complex functions. Al-

though the theorem is not difficult to prove, the proof

28

usually given sheds little light on the theorem. After
some preliminary remarks, we will'see that this result
follows immediately from Theorem 7.
Let C(X) be the set of continuous (complex) functions
on X. For f€C(X), define ||f||=51€1plf(x)| . Let LFCC(X), and
x

suppose a=inf Hp-f”.
pELF

Theorem: Let pOEIJQ and e=pO—f. Let V be a fixed
subset of X with the properties:

a) |e(x)k>o for all x€X

b) There is no q€LF such that Re(§q)>0 for all xev.

Then: inf Ie(x)lS aSflell .
x€V

.EEQQI: It is clear that asflefl. We now note the
obvious: we may regard f as being given by
f(x)=f1(x)+if2(x)=(f1(x),f2(x)), where f1 and f2 are real
functions. Choose U as the unit disc in.E2, then
“fH=M(f)=M((f1,f2)).

Let e=po-f=w1+iw2, and for qELF, let q=v1+iv2.

If Re[;?;3q(x)]>o, then
Re[(w1(x)-iw2(x))(v1(x)+iv2(x))]>o. This is the same as
w1(x)v1(x)+w2(x)v2(x)>0, 0r (w1(x),w2(x)(v1(x),v2(x))>0.
Thus, by requiring that there be no qELF such that
ReEETE]Q(x)]>0 for all xEV, it must be that
(w1(x),w2(x))(v1(x),v2(x))>0 cannot hold for all xev,
(v1,v2)€LF.

29

For XfEV, define Li to be the linear functional given

- . - 1
by the inner product. Li(z)]3T§;W(e(xi)’Z)° Then,

x‘
[hlLi(z)=T] is a support plane of U, through|3%;i%€B(U).
e i

Furthermore, by the remarks above, Li(q(xi))>o for all xfev,
does not hold for any qELF. Consequently, V is an H-set.

As Li(e(xi))=|e(xi)l, and as le(xi)|>o by a), we have from
Theorem 7 that inf Li(e(xi)) Sa. Thus, inf le(xi)|Sa.

By letting C(X) be the set of real-EEIXed continuous
functions on X, and by setting U=[-1,1], the results of
Chapunrl can be made to apply to the usual problems of uni-
form approximation. In this case, B(U) consists of the
two real numbers 1 and -1. The linear functionals corres-
ponding to B(U) are merely L(x)=x and L'(x)=-x. Hence, if
TEX is an H-set, we can write V as V=PUN, where V has the
property: there is no qELF such that q(x)>o for x€P and
q(x)<0 for x€N.

What follows is a new proof of a theorem proven by
Collatz [4].

Theorem: Let f(x,y) be a real function defined on WCEZ.
Let W be compact, and strictly convex. Further, suppose
f(x,y) has continuous first partials in the interior of W.
Then, f(x,y) has one and only one best uniform approximation
of the form bx+cy+d.

“3329;: That there is at least one best approximation

is certain by Theorem 12. Let p(x,y)=bx+cy+d be one such

30

best approximation, and suppose M(p-f)=a.

We first obtain a lower bound on the number of points
in E(p,f). We will prove that E(p,f) has at least three
points. Theorem 8 is applicable to this problem, so we know
that E(p,f) must be an H-set. Suppose z1 and 22 are given,
21 and 22 in it. we will exhibit q€LF such that q(z1)>0
and q(22)<0.

Let "y“ be the Euclidean norm, for y6E2. Consider

first the case Hzfll¥"22|. To begin; suppose that

 

Hz1flg>flz1flflzzfl+e, e>o. Let z1=(x1,y1) and zz=(x2,y2).

Choose q(x,y)€LF by: q(x,y)=x1x+y1y-flz1"2+e. Then,

q(z1)="z1"2-"z1“2+e=e>o, and

(1(22)=(z1 , 22)—|Iz1|| 2+e SK z1 , z2)l - ||z1||2+esllz1|||| 22"" "21" 2-I-e<o .
To handle the case “z2"2>flz1““22“+e, reverse the roles

of z1and 22. This will give qELF such that q(zzh>0, and

q(z1)<o. Choosing h=—q gives us h(z1)>o, and h(z2)<b.
Suppose flz1fl=flzzfl. If 21 and z2 are linearly indepen-

dent, we can choose q LP by solving:

x1 y1 m 1
: . Then q(x,y)=mx+ny has the desired
x2 y2 n 1

pr0perty. Finally, if "z1"="22“, and z1, 22 are not line-
arly independent, then z1=—z2. Choosing q€LF by:
q(X,y)=x1x+y1y, gives us q(z1)>o and q(22)<0. From these
observations, if E(p,f) is to be an H-set, it must be that

E(p,f) contains at least three points.

We now suppose there are two best approximations to f,

31

say p and q. By Theorem 1, any convex combination h, of
p and q is also a best approximation. From the above rem?
arks, E(h,f) contains at least three points. Since U=[—1,1]
is strictly convex, Theorem 4 tells us that p(zi)=q(zi) for
for all zi€E(h,f). Thus, if p(x,y)=bx+cy+r, and if
q(x,y)=mx+ny+s; then for zi€E(h,f), zi=(xi,yi), we have
bxi+cyi+r=mxi+nyi+s. Hence, (b-m)xi+(c-n)yi+(r-s)=o, for
all (xi,yi)€E(h,f). This is sufficient to guarantee that
all the 25§E(h,f) are collinear in.E2. By hypothesis, W
is strictly convex. Since the extreme points of h—f are
collinear, and since there are at least three such extreme
points, it must be that for some zk§E(h,f), 2k is in the
interior of W. As zk§E(p,fdflE(q,f), again by Theorem 4, it
must be that |p(zk)-f(zk)|=|q(zk)-f(zk)l=a.

Since p-f and q—f take their maximum at zk, and since
2k is in the interior of W, it must be that all partials
of p-f and q—f vanish at Zk' p(x,y)-f(x,y)=bx+cy+r-f(x,y),
and q(x,y)-f(x,y)=mx+ny+s-f(x,y). Thus, we have:
m=fx(zk)=b, and n=fy(zk)=c. As p(zk)=q(zk), we must also
have r=s. Thus, p(z)=q(z) for all z, proving uniqueness.

The above theorem is rather remarkable in that a sime
ilar theorem cannot be proved for quadratic polynomials.
Rivlin and Shapiro showed [5], that given any plans region
w, there is an 000 function on w which admits infinitely

many best approximations. They also extended Collatz's

result to C1 functions defined 0n.En.

32

The theorem below was proven by Moursund [6]. In the
following, “f” is the uniform norm.
Theorem: Let f(x) be twice differentiable on [0,1].

Among all polynomials a xn+'--+a1x+ao, of degree n or less,

n
let p(x) be one that minimizes: max[fip-ffl,up'-f'm]. If
q(x) is another such polynomial,1hen q'=p'.

12129:: We reformulate the problem as follows:
let LF=[P(xN P(x)=(p(x),p‘(x)), degree p(x)$n], and let
F(x)=(f(x),f'(x)). Define U= (x,y)| -1sxs1, -1Sys1 . If
PGLF is such that M(P—F)=aSM(Q-F) for all QELF, then clearly
p(x) is a polynomial that minimizes: max[Np-ffl,flp'-f'n].

We note that Theorem 12 guarantees at least one best
approximation. As in previous problems, we first get a
lower bound on the number of extreme points that a best
approximation must have. For this, we again turn to the
generalized Vandermonde matrix. Given any [nflpoints xi in
[0,1], we can find p(x) of degree n or less, such that
p(xi)=f(xi) and p'(xi)=f'(xi). Thus, if P(x) is a best
approximation, we see by Theorem 6 that E(P,F) contains at
least Q51 +1 points.

We first prove the theorem in the special case where
+1

n is even and.E(P,F) contains exactly [éEf]+1 points. The

picture below will be helpful:

 

 

 

 

 

. p'-f' ,
s
1 E
______-_---_ e e e: l__ ' __________ H1
//” v/’
3U;::::>/'w”
//
p—f
.. —- ---- --—. c 4 . ---- ----—--H2
3 2
H4 H3

 

figure 2.

The heavy dots in B(aU) represent the images of extreme
points under the mapping PLF. The lines H1, H2, H3 and H4
are support planes of aU.

If P(xi)-F(xi) is in B(aU), it must be that either
|p(xi)-f(xi)|=a, or Ip'(xi)-f'(xi)|=a. If xi#o, xi#1, then
[p(xi)-f(xi)l=a means p'(xi)-f(xi)=0, for |p(x)-f(x)k§a
when x€[0,1]. Similarly, if Ip'(xi)-f'(xi)l=a, and if

xiio, xi¥1, then p"(xi)-f"(xi)=o. From these observations,

34

we have that only 0 and 1 can be mapped into the corners
of aU, and that all other extreme points are either zeroes
of p'-f', or of p"-f".

To consider the special case where n is even and
E(P,F) has exactly %31;]+1 points, let E(P,F)=[x1,x2,..,xk]

2
and k==|EI-1-;-l +1.

We observe first thatlp'(xi)-f'(xi]=a, for
i=1,2,°°°,k. If this were not the case, suppose, for ins-
tance, thatlp'(x1)-f'(x1)L<a. Choose q(x)=anxn+---+a1x+aO
by the following:

—1 x1 x? - - - x? [a0 f(x,)
1 x2 x3 - - - x3 31 f(x2)
O 1 2x2 ° nxrzl-1 a2 f'(x2)
1 xk xi . xi an_1 f(xk)

-0 1 2xk - - - nxfifilan d Lf'(xk)

 

 

 

 

 

 

Then, q(xi)-f(xi)=o, i=1,2,---,k. Also, q'(xi)-f'(xi)=o,
for i=2,3,-°-,k. Suppose Iq'(x1)-f'(x1)l=b; if
hf(x1)-f°(x1)[<a, then we can choose t>o such that

tb+(1-t)Ip'(x1)—f'(x1)l<a. Furthermore,

th'(xi)-f“(xi)1+(1-t)Ip'(xi)-f'(xi)|=o+(l-t)|p'(xi)-f'(xi)L<a

for i=2,3,...,k. Similarly,
t 'q(xi)—f(xi)l +(1-t)| p(xi)—f(xi)|$(1-t)a<a.

35

If we choose Q=(tq+(1—t)p,tq'+(1-t)p'), then Q would be
a better approximation than P on E(P,F). Hence, in our spe-
cial case, P a best approximation means that Ip'(xi)-f'(xifl=a
for i=l,2,---,k.

If P is the only best approximation, the theorem is
proven for our special case. Suppose then, that Q=(q,q')
is another best approximation. Let C be any convex come
bination of P and Q. Then G is also a best approximation.
Since E(C,F)§E(P,F){1E(Q,F), it must be that E(C,F) has no
more than [Egé]+1 points. But if C is to be a best approx-
imation, E(C,F) must have at least [25;]+1 points. Hence
E(C,F) has exactly [%§l]+1 points. Thus, we have,
E(C,F):E(P,F)=[x1,x2,---,xk], k=[E§1]+1.

By our previous remarks, it must be that
|c°(xi)—f'(xi)l=a, i=1,2,---,k. Since M(P-F)=M(Q-F)=a,
we know lq'(xi)-f'(xi)k§a. If q'(xi)-f'(xi) #'p'(xi)-f'(xi)
for some i, we would have Ic'(xi)-f'(xi)L:a. Hence, it
must be that q'(xi)=p'(xi) for i=1,2,---,k. As we noted
before, except for xi=o and xi=1, we have p"(xi)-f"(xi)=o.
Similarly, q"(xi)-f"(xi)=o, so p"(xi)=q"(xi) when xifio,
xi¥1. Thus, p'(x)-q'(x) has, counting multiplicity, at

2
and q' are polynomials of degree less than n-1, we have

least k+k-2 zeroes. But k-1=[é11]=%,so 2(k-1)=n. As p'

p°=q'o
Having disposed with this troublesome special case, we

can quickly prove the theorem by appealing to Theorem 11.

36

Again, if P is the only best approximation, we are fin-
ished. Suppose Q is another best approximation. By the
corollary to Theorem 11, we have E51 +1 points xi in
E(P,FXTE(Q,F) such that P(xi)-F(xi) and Q(xi)-F(xi) lie
on the same support plane of aU.

From Figure 2, it is evident that this means, for each
xi, either p(xi)-f(xi)=q(xi)-f(xi) or p'(xi)-f'(xi)=
soup-ma).

Let y1,y2,---,yS be those points xi such that
P(Xi)-f(xi)=q(xi)-f(xi), and also assume yi<yi+1‘ Let
Z1,Zz,---,Zt be the remaining points xi. Thus:

a) p(yi)=q(yi); and p'(yi)=q'(yi) When yiiomir-‘h

b) p'(zi)=q°(zi); and p"(zi)=q"(zi) when zi¥o,zi¥1.
Furthermore, s+t2[E§#]+1.

Define j=2 if both 0 and 1 are among the yi; define
k=2 if both are among the Zi' Define j=1 (3:0), if
one (neither) of 0,1 are among the yi. Define k=1 (k=o),
if one (neither) of 0,1 are among the zi. Then we have,
0Sj+kS2. This definition will aid in counting the zeroes
of p”(x)-q'(x), for p(x)-q(x) has s-j double zeroes, and
p'(x)-q'(x) has t-k double zeroes.

We can count the zeroes of p'(x)—q'(x) as follows:

a) s-j, these are the double zeroes of p(x)-q(x)

b) t, these are the t zeroes 21 0f p'(x)-q'(x)

c) t—k, these are the double zeroes of p'(x)—q'(x)

d) s—1

To justify d), we will show that there is a zero of

37

p'(x)-q'(x), of odd multiplicity, in (yi,yi+1). For if
not, p'(x)—q'(x) does not change sign in (yi,yi+1); thus

p(x)-q(x) would be monotone in (yi,y ). But, as noted

1+1
above, p(yi)-q(yi)=o=p(yi+1)—q(yi+1). Thus, there must be
a zero of odd multiplicity in (yi,yi+1). Since in b) and

c) we have counted only t-k double zeroes of p'-q', we must

).

add another zero for each of the 3-1 intervals (yi,yi+1

In particular, if z3 is the only zero of p'-q' in
(yi,yi+1), it must be that 23 is a zero of at least mult-
iplicity three, of p'-q'.

Adding a), b), c) and d), we have that p'-q' has at

least 28+2t-j-k—1 zeroes. As j+k52, p'-q' has at least

2s+2t~3=2(s-1)+2t-1 zeroes. we recall that s+t219§#]+1,
or (s-1)+t2[£;—1]. If n is odd, 2(8-1)+2t22 [25-1]=n+1. Thus,

for n odd, 2(s-1)+2t-12n; hence p'-q' has at least n zeroes.
But p'-q' is a polynomial of degree n-1 or less, so it
must be that p'=q'. we have disposed of the possibility:
n even, s+t=[agé]+1, in our special case. Thus, for n even,
we need only consider s+t2[25¥]+2. Arguing as above, we
get that p'-q' has at least n+1 zeroes; or that p'=q'.
Hence, the theorem is proved.

The remainder of this chapter will be devoted to some
general observations, and some more examples that may be
treated as vector-valued approximation problems.

As we have already noted, the uniform approximation
of real-valued functions may be cast in our terms by choos-

ing U=[-1,1].

38

If we choose U=[0,1], a best approximation is a best
one-sided approximation. That is, if M(p-f)§M(q—f) for all
qeLF, then flp-fflfiflq-ffl for all q€LF such that q(xfi2f(x),
for each x€X.

If we wished to weight positive errors twice as heavily
as negative errors, we could choose U=[-2,1]. In applying
the results of Chapter I, the convex set [-2,1] is no dif-
ferent from the convex set [-1,1]. Thus, if f is contin-
uous and real on [0,1], it is easy to derive some results
that are similar to those for uniform approximation of
continuous functions. In particular, if f is continuous,
there is one and only one best polynomial approximation of
degree n or less. This can be shown using Theorem 12 and
the corollary to Theorem 11. An alternating sign charac-
terization of the best approximation follows quickly from
Theorem 8. Thus, if M(p-f)=a, p the best polynomial app-
roximation of degree n or less, then there are at least
n+2 points xi in E(p,f) such that:

a) p(xi)-f(xi):a =>rp(xi+1)-f(xi+1)=-2a

b) p(xi)-f(xi)=-2a =>1p(xi+1)-f(xi+1)=a

In uniform approximation, positive weight functions
w(x) are sometimes introduced. Such a problem would take

the form: find p€Lr that minimizes mean w(x)|p(x)-f(x)| .
X

We can handle such problems by letting:

LF1=[w(x)p(x)lp(x)€IF], and.f1(x)=w(x)f(x). Then LF1 is a

linear subspace of C(X), since LP is.

39

Some other problems that can be reformulated as prob-
lems in vector-valued approximation are given below. We
let f(x) be a continuous real function on [0,1], LF a lin-
ear subspace of C[0,1].

a) find pELF, such that among all functions in LF

that are monotone increasing on [0,1], p is a best

uniform approximation.

b) let x1,x2,...,xk in [0,1], b1,b2,...,bk be posi-

tive. Find the best uniform approximation to f among

functions q(x) in LF such that |q(xi)'f(xi)[sbi:
i=1,2,---,k.

c) let b>o. Find the best uniform approximation to f

among functions q(x) in LF such that lq"(x)1Sb, for

all x€X.
d) let g and f be continuous on [0,1]. Find p€LF that
minimizes: max Ip(x)-f(x)|+|p(x)-g(x)l .

x€[o,1]

The results of Chapter I can be brought to bear on
such problems by suitably choosing the convex set U.

BIBLIOGRAPHY

Eggleston H.G. Conv xit . Cambridge: Cambridge
University PEess, 1958.

Garabedian, H.L. (ed.) A oximation of Functions.
Amsterdam: Elsevier Pablishing'56., 1965.

Meinardus, G., and D. Schwedt. "Nicht-lineare

Approximation" Archiv for tional Mechanics
and Apelysis, 17 (1964), 297-32 .

Collatz, L. "Approximation von Funktionen bei einer
und bei mehreren unabhangigen Veranderlichen"

Zeitschrift ffir An t Mathematik und
Mechanik, 36 (195 , 19 -211.
Rivlin T.J., and H.S. Shapiro. "Some Uniqueness
Problems in Approximation Theory" Comm 'c tions
eg Pure egg.Applied Mathematics, 13 (1980) 35-47.
Moursund, D.G. "Chebyshev Approximation of a Function

and its Derivatives” Mathemeties e; Computation,
18 (1964), 382-389.

40