View of On best one-sided approximation with interpolatory families

180 ^{SIN HITOTUMATU B}

Ilere we start from

k

:2, since (l - ^2-Ð : ll2 is too

sma11

to

recover later by other prod.ucts. Hence the convergence region is ¡estricted

in

I zt

I ^{S B} - þt: ^{B' *0.568...,} (15) 0.57... :

e- B/

<

_l

tl <

ea'

: L.76...

For ^other

values

of

ú, we make scaling

t :2^

^.

y

(m being integer), and. set

22:

^{77¡ .}

log"2 in

(14) instead

of 0.

Here

we

cannot

take

112 <

Sy S I ^or 1 3y

^5_2,

^{bttt we must}

^choose

^the

^mantissa

y in

(16)

³¹⁴

=y =312 or tlJt:t

But this restriction is not

serious

in the

actraT programming.

=JÌ.

Finally

remark

that this

algorithm

is not

suitable

for the

computation of 1og

I

when

the

argument

I is

quite cl,ose

to l. In

such

a

case

we

should replace

the function by

^1og (1

* ^r)

^computed.

^by the Taylor

series

log

(l *s) :5 - ^"' 2t s ^{+ "'} - ^....

^'

or by other

approximation formulas, Added.

in

Proof ^:

After I

^køue

finisked to þreþør ent I

^the

þøþers [3], t4l

^ønd.

l5l ^&re c

^d.

u rn

^sed,

here. Tlt'e øuthor woul,d.

lihe to d,i ons eir in ø

seþørøte þaþer.

REFERENCÉS

[1 ] ^W alther, J. 5., A unified, algorithm for elementary Junotions, Spring Joint ^Com- puter Confetence 379-385, 1971.

[2] Hitotumatu S., Cowþlex øri.thmetiothroøgh CORDIC, R.I.M.S. Preprint 138 (1973) ;

will appeat in l{odai Math. Sem. Report.

[3] ^{M e g g i t} t, J. 8., Psewd,o-diui,sion ønd, þseud,o-multi,þlicalion þlocesses, IBM J. ^Res.

Dev. G, 210-226, (19621.

[ ] Specker, W. I{., A ^class of algoritkrnus for \t x, ^exp ø, sin x, cos Í, t{t x ^and ct{t x, IEEÐ Trans. Þ.C. ^11r, 85-86, (1965).

l5l Koyùf,.ãgi, S., W atanabe, I(. ancl IIagiwâta, H., Aþþroxi'mation of ele-

' mentary functions by micro-þrogramming (in Japanes), Ptoc. 14th Annual Meeting of the Inlormation Processing Society of Japan, l7l-172, ^(1573).

Received 1. IlL 1974.

Reseørch Institute Jor M athetnatical Sciences

I{ltoto Uniuersil,jt, Kyoto, _Jaþart

REVUE D'ANALYSE NUMÉRIQUE

ET DE LA TIIÉORIE DE L'APPROXIMATION,

Tome

3,

No

2,

1924,

pp. tBl-Z0B

CN BEST ONE-SIDED APPROXIMATION WITH INTERPOLATORY FAMILIES*

by

II]JA, LAZARDVIC (Beogracl)

0.

Introduction

I,etX beasetformedwithn f ^{l pointsof the real axis}

^{andf :}

X

_{-> R}

be the restriction, at X, of a polynomial of

degree

ø. Evidently,

there are polynomials

P

^anð,

_Q of

degree

n,

sttc\t

that-

(0.1) P(x) > 0,

_Q@)

z

⁰

forxeX,and,

(0.2) .f:P-QonX.

Professor

r.

^popovrcru has proposed the following

problem: to

study

the

existence

and the

uniqueness

ãf a pair (P*,Q\-of

polynomials oi d.egree

S ø which is minimal,

i.e.,

(0.3) P>P*>0,QZQ*20 onX

for every pair

_{(P, Q)}

which

verifies (0.2)

; if the

problem has

a

solution,

let

this-

minimal pair be

determined.

Further, let a similar

^{problem be}

solved.

in the

case when

X

contains

n + ²

^points.

+ Communicatecl at the Colloque on Functional Bquations, I.açi lgTB

182 ILIJA LAZAREVIC

From

(0.1), (0,2)

and

(0.3) we have

(P* = 0¡e* -f : ^{?* >}

⁰⁾

- ^{(P* > gAP* >Í) *P*}

^>

)

max

{o,f} : _{f *}

(?* l0A/+ Q*: ^Px ì

⁰⁾

₌ ^{(0* > 0A?* >} -Í)*8*

^Z

>

max

{0, - Í} : (- f)*' If

(0.4) p(o)

: max lo(ø)

^I

,ex

for

every @

e c[x], ^then

^we

^{want to}

^find. the poly[ornials

P*, ?* ^with

properties

(0.5)

^p(P*

- f*) :

_p-9,Í+

min

p(P

- ^Í*)

BEST ONE-SIDED APPROXIMATION 183

The norm

1 ^{is the}

^{measufe of}

^the

^closeness

^{of the}

approximation.

For

a

fixed

^elemènt

/ ^from

^C

[X]

^{we denote}

(r.2) ^CB: _{s = CtXl lYx = X,

_e@)

=Í(x)}.

Let

^X(

C

^C

txl ^{be a}

subspace (closed), ^and

c1P -1

/.\cl?-ld=clflt

o,p-CsÀK:19 eI(,lYx =X,

^S@)

_=l@)),

The

purpose

is to

^stucly

the

elements

g* from 7tr

such

that

(1.3)

þ(Í - ^8*) :

min

þ(f -

^g)'

e=x(a 2 .)

and.

and (0.6) where

, s{,*: _{{þ =} enlYx ₌ X, _þþc) Zf*(*)}, ef,-rt*: {þ = e,,lYx ₌ X, _þ(x) ¿ (-/)*(ø)}'

Therefore, one observe

that the

above problem

is a

specimen

of the

best nofm.

our aim in ^this

^paper

is a

stud.Y

e

for

instance

[B-10]),

^{which seems}

to

be practicaly.

statement

of tho problem;

exístenee

of a

best approximation

I,et xl¡e

a compact set of the real axis and

c[x]

^be

_{the ireal}

^normed

linear space

of all fuïctionS/: X + R

which are contintiotls on

X,

normed

by

means of

(1.1) þU): ^ma5 lf@)lf ^eclx).

p(?*

- (-/)*) : ^min

^p(Q

- (-/)*),

ç'g('-f l¡

ne-sid.ed.

hom

I(.

approxi-

X). The following theorems

^deals

with

approximation from below

; ^n

^anäTogous

^result

holds.for_approxila-

tion

frã^m above.

In our

case

þ(f - g):-y*. U@)--g(x)), but in

^order

to put in

evidence

the similarity with the

uncolstrained.

ulifo.lm.approxj-

-n[iã"- we shall frequently

^usé

th" notation

introduced

in

(1.1).

rt will

be supposed

that

d: Eff;I("; X): inf þ(Í -

^g)

^>

^0.

,

&. ^JUB

In the

following

*" r""d

statement ^(see

for

instance

[4], Th.

^{1.4.1.) :}

TrIEORDM

l.l. Let w

be

a yeal,

l'inear ^sþace

ahich is

_þrouid'ed,

u¿tninlnorm

_ll.ll,7C

CW øsubsþøc ^:W +

R.

ø

continuows.functio' nøl'.

For

^a.

fixed

^{el,ement 8o}

e I(

l,et

s': _{{8 =} w

lq(s)

<'qkò. cw.

If

Q'i.s ø giaen

s ønd'

^ectiuel'y

_!(l;.)

^one.

den"otes

thi cone ^ts re

^{cone of} .ad'kerent.

d,epl,ø,canents,

the ^s iús ^um

^re\øtiu

^of

^set

QÀxC ^øt

^{the þo}

K(Q ;

sò n ^/((s

^{; so)}

^{O KII(';}

^gof

:

@'

If

these cones øre ^co'ybaetc tken the a.boae cond'ition i,s l,ihewise necessøry

m'inirnumon.Q)1(. f {or

ⁱ

It ^{is worth}

mentioning

that the

characterization theorêms

for

^o'ie-

sid"J-"ppró"itàtøu*uy ^{Ë" proved directly by}

^means

^{of the}

^{cones of}

BEST ONE-SIDED APPROXIMAT1ON 185

784 ^{ILIJA LAZAREVIC 4 5}

admissible d.eplacements as

well as of the

adherent cones.

Other

proofs

may

be perfoimed.

by

using

the fact that the

^one-sided approximation is a particular case of some problems of uniform approximation with constraints (sêe

for

instance

c.

D. TAVr{on

[12]). In

the second. of

this

^paper- we ^gene-

ialize the

one-sided approximátion

in the following manner:

^{instead of} an

interval

_la,

bf

^{one cõnsiders an}

^arbitrary

compact set and

the

Cheby- shev space

on

_lø,

ó] is

substituted

by an interpolatory set of

functions

which

are defined

on this

set.

Firstly we get two results

regarding

the

existence

problem in

the case when

X

^contains

only a finite

number

of points

as

well as 7l is

^a

finite

dimensional subspace.

We note that in this

case any

f

^:

X-+

R

is

continuous

on X. It is well known that the proof of the

existence of

a best approximation

essentía1y depend

on the fact that a

continuous

function on a

compact

set

attains

its

extreme values.

THEoREM

1.2. Let X: _{xt, ...,

frn,}, x¿

e R

a.nd

KCCIXI

Jor

^euery

f

^:

^X

^-+

R

there

erists øt

leøst one elent'ent

g* : g*(f

;

Proof.

^'We consider the sets

M¿: _{{g =} ctxl _l0

=Í(x¿) - ^{g(x,) 3 c},} i : l, ...,ry

where ¿ is arbitrary sufficiently large positive

constant.

The

^sets _Q

: : À ^{M¿ and} Q(11(

^are

^compact CIX]

respectively

in K, and d,:

inf _þ(f -g). The functional I

^defined.

^by

c=Q n'l(,

ç(g)

: _þU - ù: ^{max lÍ@')} -

^s(%t)

^{I g = clxl'}

where ^Ð

is an arbitrary

positive number.

Taking into

account

that

MÀI%+ø, inf þ(Í-Ð: ^inf þU-8):d',

ß. ^M

nr(s

^c=x(p

we

^see

that it is

enough

to

seek

the minimum of

_ç(g)

: þU-,Ð

^on

M ^

^fC-.

^{The set M} ^ ^{1(, is}

^compact

in ^X(,

^because

it is

closed. and

toånA"ä in

7(. The

"onti"úity of _þ7Í - ^{g) with}

^respect

^{to g,}

^implies

^that

there is at least

one element

g* _{= M}

'

r('B such

that þ(f - ^8*) :

_c.

min

_M

_{nltp þ(Í} -

⁸⁾

:

_c'Xtp

min þ(Í - ^ù'

One observes

that

the above theorems follow from a more general situation.

Namely, if _Ç ^is a

^{closed. subset}

^from CIX]

^such

with f ^e

^C

eïery lXl ^admits sïbset ^at {g least one =

^C

lxl S I þU

element

- ^{g) S p},} of

best ap^P 'of

"l"menis from _Q.

In

particular, this

is true if _Ç

^is

a finite

dimensional space ^7e.

i

Then

^x).

being continuous cn ClXl, attaiirs its minimum at least on a ^point

gx =

^Q

()

7(,, anð. we have ç(sx)

: _{þ(f -}

8x)

:

,#T* ^þU - ^Ð

^--

_,y;i ^þU -Ð. J

THEoRÐM 1.3.

IÍ _{X C} R is a

comþact and,

K is

ø

finite

d'imensionatr subsþace

of CIX),

then

foieuery Í ^{e ClXl}

there exists øt l,east one elemen'i

S*J; X; X) oÍ

^best one-sid.ed' øþþroxirna.tion.

Proof. I.et X(: sqaî{gr, ..', g,}, where ^gt, .. _', (,, is ^any

^basis,

g¿

e

C

[X] ^for i - l, '..,n.

^{Iuet Co be}

^the

^set

Ca:

_{E

₌ ClXl lyx = X,

_e@)

=

Í(r)}.

Further the

set

'V :

CB

fl ^{7l is}

^{convex and. closed}

in

^71.

The

functional

1

^definecl

^by

^(1.1),

is-òontinuous on

7f.

Now, let us

consider

M : _{{8 =} c[x] _lþU -s) ^<

^d

⁺

^Ð],

2.

Characterization

(i)

^{General ease}

is a

modification

of the

characteri-

iï:"::"f#ii-".#il?"f J"ffiilit

] ^{is arbitrary}

subspace (closed

with

respect

to

norm þ).

For a fixed g ^e I(a

we denote

E*(Ð : _{x ^e x _lÍ@) -

^eþ6)

: _þ(f -

^s)},

C-(s) : _ix ^e X lÍ\x) -

^g(x1

: 0j,

and

A(e):E*(ùUC-(s), l if xeE*(g),

-

¹

if

^{%e C_(s).}

i:r ffi

ot(x)

:

is known that

even

in

ord.er

to

clevälop

a theory of

best approximation

it is

necessaty

to

assume

that the approximating set has at least

one

element which verifies

^go@)

<Í(%) for a7I x ^e X. This fact

we sha1l

frequently

symbo1lically denote

with

^gs

( _/.

THEoRÞM 2.1.

IÍ

there exists øn ^el,ernent go

eK

ulticlt' uerifies

go1Í,

th,en

a

necessq.r)l and' sufficient condition

uhick

must be aerified'

by g* ₌

_?(

suck that

g*

be øn elernent

of

best one-síded' øþþrox'i,møtion from

f,

^nørnel'y

g*:

_&+(f

_{i\lc; X¡,} is thøt

I'h,ere d'oes

not

exists

g ë l(

such that

(2.1)

^{o(r) g(x)}

)

⁰

for ^øtl x e A(¡,à,

where 6

:

õs*.

Proof.

The functional q:C[X]+R

^defined

by

^q(S)

:þU-Ð

is continuous ancl convex. Therefore

the

sets

Q

: _{{s =} clxll _þU - ^{d < þU- s*)}}

186 ILlJA LAZAREVIC

C": _{{g =} ClXllYx ₌ x, _Í(x) -

^e@)

^>

^0},

afe convex. Since go

= Ci

on" nas

i f) ^{X + Ø. Inthis}

way the conditions

of tlre

Theorem

1.1 are

fu1fi1led.

Thus g*(/;7{,; X)

verifies

(2.2)

^K(Q ; e*)

I ^{K(C"; s*) O IdlI(; g*)} :

_ø .

But it ^{is known}

^(see

^for

^instacne

tal or

t2l),

(2.g) K(Q; s*):

^{g

^{€ ctxl}

^I

\x ^{e E*(s*),}

e@)'sign (/(ø)

- s*(#))>0},

(2.4) K(Cu;g*) : _{{s = Ctxl lVø =} C-(g*),

g(x)

<0},

(2.s) ^{KlT(; g*l} : \t.

^:

In

our case sign

(f(*) - ^e*@)): f

^{1 for all}

^{x e}

^{E+(g*) and} (2.2) reduces to

{e = clx)lYx ₌

^E*.(s*),

s@)> o}O _{{g =} ClxllYx ₌ ^C-(s*),

s@)<0)nYc:Ø,

which

proves

our

assertion.

f]

(ii)

The.dase

with finitc

dimensional subspace

F'irstly

we note

that in this

case the. set ,4(g*) which

is

defined

in

(Ð, contained.

only

finited. much

of points.

T,et

X be;a

comPact.of

real

line which

contain at

least

n

distinct,

points

as

well as I(ÇC[X] be a

^sub-

space of dimension

n.We

may write 7(

:

sqan

{gr, ..'., g,}

^where

8t, "

^{., g,}

is a

basis

of xL 8¡ e Clxl' i = l'.':"n' ^{Then we}

^may

oroblem

to

the same

topic in'n''

This is motivated by taking

ih; üt;;;biuttivoque

ðorrespondence between ^7t:

and R":

g

: f

^engt,

^e î('-' a':

^(o¿r, ' '

',

^æ,)

e

R" _' h:1

lfherefore

to the set C,

corresponde

the

^set

6 '7 BEST ONE-SIDED APPROXIMATION 187

transpose our

into

account

{2.6)

VB:

^æ

e R" lYx ^e x, )

"ugi@)

sf(x)

' _É-1

ì I

and.

Further ^we

^define

the

continuous application

ø: x s ^{R" by}

ø(r) :

(gr(*),

..., g*(x)),

^%

= X,

and

put

ø(A(Ð)

:

_{ø(x)

_lYx ' ^t(ù}'

'The

following

charact eÅzatiott' theorem

is

valid _'

\fl:l'

which satisfies

l(ù :0 _for

^øl,l'

_{g =} x9' ;j

^,

Proof

.

We sha1l show

that : (g* =

^g:*(Í

t )l*

^(ø)

+

^(å)

+

^(c

oi"*'áiîr,Ëäääî.rl-¡rrtiv ¿., )

^denote

tt"""ó"iåï pr"ä""t p"rt"i, in "õiäi,ri R". T ^{he set To}

^{show .\o) defined}

_=.(u ⁱⁿ

mav 6e written in the

form

:

Vp

:

_{æ

₌ R'l\ ^{x e} X,

^(æ,

^ø(x))

=

f(x))

ssw?ne

^{øn el'ernent go}

^e

^{1(' suck thøt}

4.

_,s

;;:|;io _'L ,T',!""ui.* "/,,#:",Í'!ii:{,

'n : _8*'(

^xL;

x):

(a)

Tltere ^d,oes

not

exist

g €

span {gr,

...,

^gn} such

that

o(x)g(x)

>

⁰

Jor

^øll'

x ₌ A(g*)'

e

conuex hul':, or the set

of

^n-tuþtes

(b)

The zero n-aector

0¡, is in

^th

{o(x)(g,(x),

^{. . .,}

s"þ)) lYx =

^,4(g*)}.

(")

^. '

., x,, in

A(g*),

ry _=.T I ^l'

^{ønd' þositiue}

'nurnbers

contiäuousl fünctionøl' t'

e ClXlf'

^del'ined'

on CIX "

^tYþe

('.:, ',';:'4:å

o@a)v¡r(x')'

r =ctxt

).

), (2

In

1et .6)

and our problem

_reduces

to the finding of a ^point (* ^€ R, for

which q(ø*)

: min

_9(a)

qeV

where

ç(q)

: _þ(r -å.,*)

By

using

the

formulae

(2.8)-(2.5),

we

find

K(Q; Sù : {g = ClXllyx _{= E*(s*),}

g(#)

> 0}:

:

_{oc

e _R" lYx = E-(g*\,

^(q.,

ø(x\) > 0}:

^:

:

_{o{

e R"lV* = a(E*(g*)), (", g) >

^0}.

K(C";8*) : _{{g = CLX|lvx =}

_{C_(g*), g(ø)}

_< 0}:

: _{ø e R _{IV* =} C_(g*), (*, - ^{ø(x)) >}

^O}

: : _{{a e} R" lVp ^e - a(c_(g*)), (*, p) >

^o},

KlTt; E*f : R.

By

means

of the

Theorem 2.1, we conclude

with the fact

that,

the

systern

of linear

inequalities

in

R"

(0,,

P) ) o _{Vg =}

^a(E*(e*))

in unknown ø, is

inconsistent,

i.e., there isn't any solution.

since

this

systern

^^;:"o;,fll;'Í ^:' ,.,'il''. ⁼

c-(s*)Ì'

(2.7) _{(a, 9) >} 0, with _{p = {g}} :{o(x)ø(x)lyr -

^A(g*)}.

lh" i:!

^{p_ì

^t:

^compact

ⁱⁿ

^R,,.

^It

^{is known (see}

^for

^instance

il,

^p.

rr'e

lnconsrstent

property of system (2.7) is

equivalent

ïiti

(2.8) _{o¡r e co}

_({p})

which,is

equivalent

with _{(þ), 1ne} chqim will be

completed

by

(b)

+

(c).

rn

order

to

show this

it

is sufficiently

to showihat

(2.é)

BEST ONE_SIDED APPROXIMATION

189

valent with

(c). On account of Caratheodory Theorem, there

exist at

most

?t,

+ | ^points

Pr, ^{. .}

., p-

anð,

positive

coefficients

p,

such

that

ñ (2.e)

with

m

pt

e

{c(x¡) ø(x) ^|

x, =

^A(g*)},

Dp,:l,Pn>0, 1<m'3nll.

11

x, e _a(E*(g*))

_{we have}

p¡9¿

:

p¿ø(x¿)

:

o(x¿) p¡a(r¿),

as well

as

if

xn

= -

^ø(C

-(g*)),

^{we have}

p¿þ¡: -

^p¿a(x¿)

:

6(xi) p,eþçi).

Thus,

from

(2.9), we have

M

oÃ,

: _D

pogn

i:r

0or

: _D

ø@a) pna(x,)

: D

pno(xo)@r(xn), .

n:t

¿:r ^,

g,(x)),

which is

equivalent

with

lBB ILIJA LAZAREVIC

I

B

(2.10)

m

Ð'(*,)

^p¿gp(x¿)

:0,

h.

: l, ...,

/t,.

By_multiplying_every

:

1, . . .,

n,

and

by

adding _{_eguation} these

in

equalities, (2.10)

-with we

arbitra,ry numbers obtain uo,

h:

ti"@,) r'[å ^{noso@)]: o,} x¡ =

^A(s*),

that

is

t(Ð :i"@)

_¿:t pis@)

: o, _Vs:

_k=l

f

^noro.

ⁿ

We note that,

E*(g*) * ^ø.Indeer

^{, 1et us assume contrary.} The inequa-

lity 1 S m

impTíes C_(g*)

* Ø, i.e., we must

have ,4(g*)

:

C_(gx) ãnd 191)

that

showing

ß

equl-

n 11t

o :

i:l

_D

o(x,) pog@o)

: - D

¿ :t ^p¡g(x¿)

BEST ONE-SIDED APPROXIMATION 191

ILIJA LAZAREVIC 10 11

190

(3.1)

for every x¡ = A(ß*). In ^other

^words,

^{for the element} E:

^g

-go ^e

^ììt]

holds

1n Itl

f,

^e,(s

- so)@,):ÐP"(Í(*') -

^eo(ø'))

^>

^o'

(because

g*(x,):f(x,) f.ot all x, e A(g*D,which

^asserte

that there is

arr

èlement

in' ^,L

^such

^that

UÐ

:0.

'^"*^il-";;ection *itn trr"'inicity

^{we note}

^{that the}

conditions

which

^rn'e

best

^aPp

aph we s

the

best rpolatory

S.

3.

Approximation

with intcrpolatory

^sets

Let I(CCIX) ^{be an}

interpolat-ory subspace

on X-.of

^{dimension ø}

i."., li i, fiieur" i"i"ipoiátoty rät of ihe ord"r n, on X.

_þee

.[B]),

^and

i','ôf*l--" n ii " noti-r"to linear

continuous

functional

^defined

bv

he notes

that in

case

when X : la,å1, the

prewronski

^^ '(f;:

f;)

\ht...'*nJ

in this'case

^(3.2)

flicients

_"(t, ^{. . ., ^(,}

'"""#1äiì"å"Ë,f

The followirg

^{theórem deals}

with r-nicity

^solution

of best

^one-sided

"pp';;ì;;ti;;. ä;-i;;;f- ^{ol tni'}

^the

^{orcm mav be}

^performe

^{d bv}

^using

similar arguments wit'h

i¡ose frcm

^the unconstrained case (see

for

instance

ta, p.

e6l),

Let u

^{st one}

that

^that

a. *U: Ze

^t

aþþ exist

^{LS nec}

tiìãt ^to

^be

we

^note

^that in interpolatory

^case,

iÎ the functional

^which

is

consi- d,ered-rin

ih.or.- i.l. ttt' r;

ortogána1

on x(, i'e', t(g):0 ^{for a]l g e}

^r('

then we nrust have

*:'" f

^{1. Ïndeed, 1et us assume}

^ln ₌ ^{n. Then}

^there

;;úi;; ãt"m"ot g ='tc

^defined

tw _E@,)=\¡, i-l' ''''rn

^{anð' we have}

which contradicts our hypothesis.

But this

means

that in

^the. interpolTtgr4

case there exist

e*aËil;'; + i ^ptints which form the set

^.4

(g*) of

critical

pcints from ^X.

4. Thc

alternatorY ease

If

^7ú

^{is of the}

^tYPe

^{l,{la' bl}'}

wronskians

ln

(3.2) has a constant- ^s-ig are

not

zero. 'Therefore

from

^(3.2)

f ¹

Points

in X at which ^ø*

^takes

This ìituation is

^called'

the ^case

e extend the

Theorem

2'2

as

TIIEoRÞM 4.1. Let

I(:

^spajn {gr, tYþe

l,,{la, b)), X ^c

re exisls øn ^{element go}

e fol'louing

is

^ø.nece;sa

e-sided' ^øþþro ximation

4

t(g)

: _f,r,sWl ^:f.r? ,

^o'

ff

^tG)

: 0 for

every

g e

X(,

then

we have

,m :,(r*,,,

^{' . ' \n*t}

..' ^%n*L

gt' " ^''

^g'\

frt,

,..' *¿-t'

^%¡+t'

tL+l

Dv,Í(*).

_i:1

(3.2), l¿: ?

7)'+1-iY,,r'V(

, *.*,)''(;', ^,r;,)

,(r;:, ',1".):

differs

fro- ,"ro.

Moteover,

v'e

have and ,,pfewfonskian"

(3.3)

l(l) : _\,,t'tv

In his work

T. PoPovrcru

of ^{the form (3.1)}

^which

^t10l

establishes

that the

unique functional

"å"ittt.t ^{on ?(} is defined bv ^(3.3)'

Likewise

gr(xt)

gr(xr) '

g,(xr)

gr(xr) ^. g*(xr)

g,(xr)

^.

'

^gr(x")

gr(x,) . g*(x,)

8t,.'"8,,Í

fry ,, '' Xnll

v

^8u

frt' .:,r;-)

r92 ^{lLIJA LAZAREVIC} 72 13 BEST ONE_SIDED APPROXIMATION 193

.

^(.e) There.d,o.es

not

exist

g €

span

{gr, ...,gn}

such thøt

o(r)g(r) >

⁰

forøl,l,xeA(g*).

. .

^.(þ)

.The

zero n-.uector

0ol il -in ^the

conaex kutl,

of

the set

of

^n-tuþl,es

{o(x)(gr(r),

^{. . .,} g"(x)) _|

x ^e

À(g*)}.

,l)

^Tkere eyi-sts q._linear functionøl l,

e ClXl* oÍ

the

form

(S.B) which

?o!¿^tf¿çt

l!g)

=

p

Íor

^{øU g-}

=.1L

^ukere

x, 1

^xz

1.

^.

. < r*+i, x¡ =

^E*

^(g*) U U

^C-

(g*),

oþc¿) \¿

)

⁰

for i : l,

^{. .}

., n I ^l,

^ønd. T¡T¿+t

<

⁰

_fitr i :'

ll-"..,

l.

(d)

(Al,t.ernøtion)

.There exist the þoints

^th

3

^xz

<

^{. . .}

A(g*) : E*(g*) U c- (g*)

such tha.t

o(i¡+r) : _--

o(x¡)-

for i: l, ...,

^n.

In this

case we have

the following

consequences.

- Corollar.y

^4.2.

^Let xt1...1lcn+l be

critical,

þoints from X

reløtiae

to

d.eaiøtion-function e*

: f - ^g*.

^{Then tke}

cofficiänts

ao'of gx

: :

_{g+(f ;}

t{.; X)

uerify

(4.1)

äousor-) : _f(x) - ^Ðnd*, i: l, ..

.,

n,+ |

uhere 8a ø.re the coordinøtes

of

the ølternøting-uector

8: (1,0, l, 0, ...) e e _ftr+r .9r of ^{tke similarty}

^uector

S:

(0,

1,0, 1,...) e

ft"+r.

- ^To-the

system of.'points

xt 1 ,.. 1

^fr,,+t corr"spotr.ãs

for the

functio-

nal L the

system

of

coefficients

from above of -f, ^i.",,

^gu(,f

^{; x(;}

^la,

^ól) : -S*(- ^{f ;}

^X(.;

^la,b1).

^This

may

be extend.ed.

to the interpolatory

case

with an arbitrary

compact set

X ç

^la.,

bl. ^Therefore in the case when the knots are ordered

as

th 1 ... 1!h+r

^{we can assert the}

following: if forthe vector $the

system (4.1) furnishes

us the

element

g*, then from the

same system one find.s,

with the vector

r¡ and.

for a

certain system frt

I

^{, .}

^, 1

^frn+t,

^the

^element

g*.

We remark

that

generally these

two

systems of knots are

not

the same.

Corollary

^4.3.

IÍnis

euen,then,theþoints xrønd, !6¡¡1 Øra critica.l,

þoints of the

sørne kind.,

i.e.,

both bel,ong

to E*(gn) or to C-(g*). For

n odd, tke sarne þoints aye critical,

of

the d,ifferent nøture.

Ind.eed.,

let us

srlppose

7¡:2k ^e N

and.

r f s:2k + l.

^According

to the alternatory propert¡ one results r:kll, s:å ot r:h,

s

:

å

f ^{1. In the first}

^{case .r1 anó.} xn¡1 belong

to

E*

(g.), while in

the second case these points are

in

C- (g*). Tf

n :

2h

- | ^e

^{^ðÍ and.}

^{r +}

^s

:

2h,

we give / :

s

: h. But this

means

that r,

^{and. !tn¡1 â.rê}

not of

the same

kind.

Moreover,

in

both cases the number of contact points (in C- (g*))

is.s:[3]+r.n

Lz

l

C o

r ollary

^4.4.

Let X :

_la, b),

I( _-span{gr, ..., g,)lbe

an inter- þol,øtory

of

tke tyþe

I _{lø, bl}

^{(i.e., X(}

is

a. Chebyskeu subsþøce

oJ

Clø, b)

on

_lø,

bl,

^{ønd, suþþose}

that gr: l.

Then,

if f is

non-þolynomiø|,

uith

resþect

to

^X(,,

lhe

d,euiøtion-function e*

: f -

^{g+(f ;}

^{K,; la, bl)}

^høs

^the

end.-þodnts a.

ønd b in its

set

of

øl,ternance A(g*).

Ind.eed, suppose

that

^x¿"

is extremal, i.e.,

e*(x¡,)

: _þ(f - ^go),

^and

fr¡o¡1

is a contact point, e*(xo,rt):O. Let us

suppose

that there is

an

extremal point

.ro between %¡o arLd- .f¿..'1

(the

same

study when

øo

is

^a

contact point). The function e* differs on

_lx¿",

ro) oI

constant fnnction

þ(Í

_points

- ^g*).

_is

_finite. ^This

Therefore we

^{is motivated} find ^by

a

^{the fact}

positive _number

^{that the}

c so

^number that the ^of

^extremalfunction a*

-

^c

: Í -

^(gn

*

^{c) vanishes}

^at three points from

ltc¿", x¿"+rf and. one results

that the

above

function has at

^Teast

n f ^{2 roots on}

fø,

ó]. But

this

contrad.icts

the fact that

^gx,

I c = I(

and, ^XC

+ f ^is]

interpolatory

of

d-imension

n | 1. Further,

1et

us

assume

that the

end-þoint

a is not critical point, i.e., 0 1

^en@.)

< _þU - ^{g*). Then we can find a}

^positive

number _{lø, xrl}

_as

c for _well which the function

_as

_{a root on lxr, rr].} ê*-c:f _This

_means

- _that ^(g*-þc)

_e*

^{has a root}

^on

- ^c

^has

^at

^least

n + | ^{roots on}

lø,

b), i..., f :

^gx

* ^{c. Bttt this is a} contradiction

and

the

pr

oof is

^pomplete.

!

The

above Corollary extend. a well-known result

by r. rorovrcru

t9]

in the

case

X :

_la,

b) and

70

is the

subspace

of

polynomials

of

the d.egree

n - ^l.

Àr, Fr,

\2,

_{Vz, . .}

.,

À,, _F"

or

[¿r, Àr, t\2, ]\2, . .

.,

_l¿",

l,

with

À¿

> ⁰

^and

^pj,< 0

and

r *

^s

: n + l.

(We select one

of the

above system such

that d* 7 ^{0. This}

^we

^shall

^show

^later). similarly, if

x',

<

e*

:.f - ^{B* with g*} : g*(f ;lt; ^{X), then the}

coefficients

of g* verify

n

(4.2)

Doos'þ;) : _Í@l) - ^r¿d*,,i : l, ..., n + ^|

where

r)¿,

¿:1,...,n+l are the

coord.inates

of

alternating-vectors

I-:

^(q,

_-7, ^0, _{-1, ...)} e /¡,+t respectivelyl : (-1, 0, -1,0, ^..

^.)

^e

^/lø+r.

If _{g* !s the}

element

of the

best one-sided approximation

from

^below of

f _,o" -X:

lø,b1, then

in

_13,p.

l2l it is

shown

that this is

equivalent

with the fact that - ^{g* is the}

^element

^{of the best}

one-sided ápproximation

- Reyue d'analyse numérique et de la théorie de l'approximation, tome 31 1974.

794 ^{ILI.]A LAZAREVIC 1.4} 15 BEST ONE_SIDED APPROXIMATTON 195

, ^'5.

^On eomputation

!rþ;r.,ø,.'1] ^fixed

^and

l ^{be the} functional

consideled

lnto _account that evefy element from

^7(]

is

determined

by ø

distinct

points,

rve

may

write

(5.3) g:

^L(x('l

xv ..', ^fri-r,

^!t¿+t,

" ',

^{tcn+ti g)'}

We

note that the

signs o(ør)

may be

determined as

follows:if

^(5.1)

is

considered

.as a

system

in the

unknowns

4u

^. '

.,

^a,,,

d*'

^tt-en

ti -

Àr if y¿)0

p¡ if _1¿<0,

ft' ., frn*t

) ^{,f;,', :,';;l.l}

v

and 1:

Then we

{i

ha

= {1,

^.

..,,n *

^{1} ly¿}

^{> 0},} J : {i ^e {1,,

VC

dx:

_{I *}

"(.) ,Cn' T ' ^frnt7

ì _{I i:r} i- ^!t:þt

^on

t(l) : I(Í

_.i,

-

^Bx)

= ì

_/-J

ieI

^oj9n) - ^sUtD *Ð

_t=J'v¡UQ¡)

-

^{sþ¡)) wheie}

^Do

^are

^the

co-factors

in the

d.eveloping

of the

denominator

by

the elementS

of the last row.

BecaUSe

the numerator

haS

a

^{constant sign}

and

the

denominator is a linear combination of (1

|

^{o(xt))12, we maJ¡ deter-}

mined the

sign

.

of

coefficients

pa

such

that

^d, has

a

^positive

value

and moreover

a minimal

one. Indeed.

Put ,

^.Ì:.

o(x,)

: $s" _(v(s;;,

. .:,r;:!,), nr,),

i:7,...,n'+7.

The

above method depends o1

a

functional ^I which enables us

to

fincl

d,*

and c(xo), i.

: l, ..., n I ^I.

^Professor

^{r. popovrcru in his work}

^con-

siãers simuÍtaneously

two

interpolatory-systems K

:

sþara

{gr'

' ^. .,

g,}

and W

:

span

{gr,

^{. . . , gn, g,,-rt} (r,vhere 8,+ r is selected}

in

a convenable manner) ^.

By

meãns oT

this

iãea rve

shall give a

more elegant solution.

Let

':n+l

u :

L(W

i xt,

^{. .}

., xnrl; f) :D

orsi h:r

and.

=

^ieI/._,

_^oUU) - ^s\t))

: d*D, \,'

¿eI

.r

yo

= E*(gà,

^z¡

₌

^C-(g*).

therefore,

if ^{n this}

^manner

*":"ã¡k,i¿ã that.l(/);o,

then:by me

_.the

^index

^s-et

11,...in* lconsiderthe

normaljzeð. ^d*. If l*

is

'v,,el1d.efined

then is known the deviation d'*:l.*U)'The

^{knowledge of}

the sets 1, I is equivalent with the

r.act

that

are known

the

subsets

D*(g*)

^anð. -C-(Sn).-,Taking

into account that the coefficients ou

_?Ï

3*.': D

_"ug¿

^{satisfy the}

^system

^oi

^equations

(5,1) qngiء)

= ^e@), i :

1,

"',n + ^| a:L(qfl;xt,

and.

let us

consider

,t+l

t frnll;./) :D

.'\h:L

bn8n,

where

, h:!1,-d,a,,,ri,,., ,i ,.i.

where ^d.

is a real

number. If.

d,:

do

is

selected such

that tiîe

coefficient

of gn¡t is

zero,

then the

element

(s.2) g(xo)

:

_f(xo)

Thus

g* is the

element

which

interpolates_

the function g''sn

^¿he

set x.

On tlié'' other hand, from the construction of g

as

well

as

by taking

^h,*

:

1¿

- d+a: Ð

^(øo

-

^{d,bo) go}

ILIJA LAZAREVIC 77 BEST ONE_SIDED APPROXIMAT]ON 197

196 16

belongs

h* :

g*(

(see

for

to X and satisfies the system (5.1).Therefore we

have

f

; ^IC ;

X). From the

above remarks and

by taking into

account

instance

_[8, p. 3a])

we

may write

k(*,) :f

É:1

urÍ@) -

^onb,

:lþ) -

^0¿g¡,

i:1,...,n+1.

From this it

follows

(s.z¡ _Í(x) - ^h(x¡):

^0¿8¿,

i: l, ...,tù + ^l.

Let ^us

^suppose

that lSrl* ^0, i:1,...,n f l. ^(For

^example,

fulfilled when

^7e

is interpolatory on X

^and,

/ ^{is not}

^polynomial

to

^7(.

^on X).

^Bçcause

h,: g¡,

we have

&n+t:

L".f";

xr, ...,

frn*l

i uf, b,+t:

^tX\o

^{i xt,} ..., xn¡yI

al,

iJ we

denote d'*

:

d'n1-1lb^¡1,

then

one

finds å*.

Because

the

generalized.

Iragrange operator

is linear

(see

for ^instance

18,

p,271), we may

write

(5.4) h*:8*(f ;x; X):

^¿(Xç

i xr ...,

xn+ri g)

this

^is

relative where

g is given by (5.2). We note that in

(5.4)

the

coefficient

of

^gn+r

iszero.

Itisof interesttoremarkthat,fromf(x):w(xr),i - l, ...,n + ^l, as well as

^l(g)

: O for all g e I(, we conclude that l'(f) : d*:

7 _,^nq. -

: _b*+rlw; xt, ..., Knt!;,f] is a dividèd

difference

(of order n

reTative

to the interpolatory

segment ^7¿

C

^1fP).

Because (5.3)

is

symmetric

relative to the knots

and.

on the

other

hand, by taking into

account

the

relationship between

g

^and.

/, ⁱⁿ

^the

following we intend to

represent

the

element

g of

best one-sided appro*

ximation in a

more convenient

form.

Namely,

let us

denote

8o:

_Íþc*)

- ^LP(t

^tçt,

^{..., !tn-t,}

^!ún+t

...t fi*11; Í)(rp), i : l, .,., n + ^l.

It ^is

^known

that

(see

for

instance _[8,

p.

45])

Í(x) -

^h(xn)

:

and.

from

(5.6)

we

conclude

that

d* if

^tt¿

₌

^E+(g*)

0 if x¡ =

^C

_-(8*)

¿l* dt,

8¡

if ieI iJ ieJ.

0¡:

^{l¡¡ I}

0

Thus

(5.5) implies

8È

,

_(';:. ^8n+t

xn+t

lN

^;

^xr,

^.

.., xn+ti fl.

r:Ðo;:Dt:¿*Dl

ft+l h:l ie I öi iel öa

,(

^{Ep ...,8n}

fr1, .. .' !lp-1' Í¡¡1'

that

is

Let

^0t,

...,

⁰ⁿ⁺¹

be

non-negative numbers so

that

(5,5)

Put

(5.6)

n+l

Doo:1.

h:r and

finally

I

lo:D

n+l

oþLpti

!út,

...,2tþ-t,

frh+t,

...,

^túo+ti

_f)

þ:t

ôÞ

for heI

(5.8)

0¡: D

_{þeI ò¿}^I

where

0i

must be d.etermined

in

order

that k :

g*(.f ; I(.;

X) of the

equalities

On account

0 for h=J.

L(K

!61, ..., zlh-b i6h+b ...¡ zïnir;Í)(X¿) :

i, h: l, ...,

^tt,

+ ^l,

f(x,)ifi*h f(xu)-8¿ifi:Þ

Therefore

g* is given by

^(5.6)

and

(5,8).

For the

non-restricted case, ^a

similar result was

obtained

by MorzKrN and sg¡nrue [7,

^{Theorem 2].}

In the

case

with

alternance we have 8;8r+r

( 0,'i: l, ..., n,

This implies

the

rema¡ks

from the

preceeding paraglàph. Likewise,

a similar

represen-

! ]LTJA LAZAREVIC. 1B 19

(5.17)

BEST ONE_SIDED APPROXIMATION

for for

198 r99

it

follows

tation may be given when X contains a finite ^number m2n{l

^of

distinct points. l-

^,

for,the

solution of the best one-sided

ows

^7e

is'an interpolatory

^subspace'

i4t

neMns exchange algorithm (see

'1 point for instance

distinct.

*f\,'...'*ff,, [1],

P. 173]).

of x. If we

denote ^g(0)

- ^g*(f ;rci ^xto)), th;n the

cl.eviation

funcfiln

f -

^gl0\

^is

^{now examined. over}

^X

^{and. g(o)}

:Ð."ugu is

compared

"with /'

ri þ_l

From the inclusion

^'

:"=;'. "--- '' '"u^or:

{g = ztlvi:e

^{j((o)' g(xx)}

=

rþc)})'

I {g =

^Ic

l\x = X, s(x)

₌

Í(x)) :

zl"

then the fact

^gto)

e

_{1% and}

tio"g

^¿(0)'

points of ¡tol ç X)

^enables

^{us to}

is not

as above, then

at

least one rel

is

replaced where

the violation is

^g

for

one

of the points of

X(o) in ^.

a

ce:

(5.10) one concfudes

that it is

possible

to

have simultaneously

(5.14) ^mø < ^{0 and}

^fl(o) <Þ(etot¡.

. "'

ⁱ

I.et

xo respectively ø0, be o.ne of

the

points which satisfies (5.10) respecti-

vely

^(5.11). Setting (5.1s)

'MP\

-

^dQ,

>

lm(0t ^1, MP\

-

^{fl(o) <! | m(o\}

l,

^,

"tt+

(s,16) where

i:1,,..,m+1, i,+io

0 -

aÙt

[*; ^ir

|

*0, if

ptor(<Þ)

:,:,T1i*)o(øfor) | s T:i

^I

^o(ø)

^I

:

_þ@)

for every Q e C[X]. In Particular:

^'

'

^:

dP)

-

þ(o)(e\o\): _e

min þsff -

^g(o))

^<

^min

^þ(f -

^glo)),

=

?0s(0)

^{e= 2(3}

i.e., .

.:

(5.9)

^dtot

^<

Þ(etot\'

Always there

is at

least

a point *o = x.-

^{x(0) such}

^that (5.10)

^sto\(xo)

:

ma'x.^.eto\(x)

-

^M(o\

xe X - ^X(o) as

well

as

a point

xs'

e X -

^{x(0) such}

^that

(5.11)

.

^s(o\(rn)

: _Tit,^,

^¿roryv,¡

:

stot'

' _*=k- x9l

ⁱ

By

means

of (5.9)-(5.10) we

^see thaü (4.12)

we have, prepared

the next

step

in

^o) 'toì

X(i).' ff x[\ = ^*0, ii"o

^xt'\

= E*(g(t') ãnd ^[tl -.c-(g"').

Similarly with the unifoim non-restr ^for

^instance

14, p.

^-1511),

it may be proved

(d'r't1"- (mt't)t

(Mt'\) t = ^1,2, ..., and

^(g(r))

î :1,2,...,

^(g(.)

^{e IÇ),} are

conver-

gent

when

r+ f

^co.

In the

case

with

alternaqce'

it is

easy

to

exchange

a ^point

^5Q't

e

f,@\

witlr

øgl. fndeed,

tetl øjfl,

arrd x\o)

be two points from ^X(0) so that

xp e (*l?t_,

,1ol¡. Since,

we know-the sign of

coefficient

relative to

^ßt)

which

apþears

in the functional l, further

we exchange

with

preservation

of the

alternance, one

of

*\o"\-r, nlo")

with

^ø$l

y(t\ - ^{{*f', ..., rlf,r¡}

2¡\tl t

tçto)

tÁ') (

{

t

6.

The conneetion þetween one-sided ^and. unconstrained approximation I¿et f(.

.:

span

{gr,

^{. . :..}

^g,} C

^{C-[X] be}

and g* : g*U;

Xt;

X), g* =

^g*U;'fC

^{i X)'} of the

one-sided- best approximation from

of the

unconstrained.

best approximation. Then we

have

lf

rve have 'simultafieóuslYr1

'

'

I

(5.13)

:, ' r'latott>

200

^ILIJA

LAzAREvIc

20 îHEORDM

6.1. Let

g*, g*,

!

^{be the} el,arnents d,escribed, øs aboue.

In

^order

to

exists ø þositiae ^constømt

c

suck thøt

(6.1) g**c:g:g*-c

it ^is

^necessøry

^ønil

sufficient

thøt gt:

^1'

Proof

. Let g* :8* *

^{2c where c}

> ^0,

^ar'd

,4(g*)

: E+(g*) U

^C-(g*),

A(g*): E-(g*) Uc*(en),

be the sets of critical points

rel

rtive to gx and g*. Then

C* (g*)

O

fl ^c_(g*) : _Q.

fndeed,

if we

assume

that the

intersection

ls

^non-volcl,

then C*(g*) : C-(e*).

Therefore

the

elements

g* and g* ^have

ltl*t

contact-points,

which implies g* :

grn (see

for instance t5]). It

follows

that we

have

2L BEST ONE_SIDED APPROXIMATION 201

(see

for

^instance

g* : g* l2c,

^{we [8,}

p.

34]). Substituting

these values

in the

equality obtain

(6.3)

:ç"

2a ^2c

-0

Because

Z

dependent

(i,:, ..',í:)*,' ^{in the}

determinant

in

^(6'3)

^the

^{rows are linear}

:'there

^are

the

constants Ào such

that

(6.2)

E-(e*) :

c-(g{,)

E*(g*) : c*(g*).

(6.4) pt,ogo@) :2c, i : l, ..

.,

n + ^l.

From the fact that

^7e

is

interpola

ory the equality

(6.4)

remain

valid

and for every x e X. This implies that

7e contains

the

constant func-

tions, i.e.,

_8r

:

1.

Írurthei, if gr:1and g*:g+(f tI(;X), ^then

^ga-

*d* =Z! ^a2!.th9

function f - ^(Si * ^{d*) takes the values} - ^d'¡

^and

^{.0 at n} I ^l-

^drstrnct

points. fn"reÌói" S*'i d*: g*:

^{g*(,f ;}

^rl'; X). It is clearlv that g:

: f ^{r* * s*). f, ^The

^case

^when y :

_lø,

bf ^was

investigated

in _i6l

where

the

read.er

finds many

references.

lVe note that in

general case (even

if

^gr

:

1)

the

following inequality

Takins into

account (6.2) and' Corollary

4.2

we conclurle

that

_9..¡,

ryg

^gT

ät

^b%

"¡i"i""¿ iron

_{1a.t¡ (or} ^(a.2))

by

means

of

one

of the ^pairs ($,

^r¡)

(8, ïl) of

alternating-vectors.

Evidently tlnat

^d'*

: d* : c' From

^(5'3)

i'e räay write, with the pair ^($,

^r¡)

lrl<1 d*d*d is valid, _[3, ^p.

^28].

g,x

:

gx(Í

i

^7(.;

^X) :

7. The

approxÍmation

with

^{positive elemcnts}

Let x

be a set on the real axis which contains

at

least

n + ¹

^distinct

n

points

arrd,

f :

_þ:1

D

^aogo

^{be a given}

^{element fuom}

iIL K is

^assumed

^to

be intetpolatory of the type I _{la, bl ^we

^denote

the

subJet

of

^-70

whicfr cóitaini onty ^on X'

^We

want

to find

a

pair (Pt, 0*)

^of

elements

the follow-

ing minimum

property

(7.1) P=P*=0, Q>8*>0 ^onX

and.

(7.2). l:

^P+

- ^{Q* on X.}

,g;;, ^'.'i.)

and

lt'

I

g*

: _-g*(-/; w; x)

^{-a 0}

,[et ^" "

^s"

\frt, '", it