The Characterization of Best Nonlinear Tchebycheff Approximations Citation Rice, John Rischard (1959) The Characterization of Best Nonlinear Tchebycheff Approximations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/J15M-W835. https://resolver.caltech.edu/CaltechETD:etd-02102006-083607 Abstract NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document. Consider a continuous function, F([...]) of n parameters and [...]. Such a function is said to have Property NS if the following theorem is valid for every continuous function, f(x): THEOREM: F([...]) is a best approximation to f(x) if and only if there are n+1 distinct points, [...], such that [...]. Depending an the basic assumptions on F, several sets of necessary and sufficient conditions are given for F to have Property NS. These conditions involve unisolvence and related concepts. The definition of Property NS is generalized and necessary and sufficient conditions on F are given for F to have this generalized property. The latter theory includes most common nonlinear approximating functions. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Erdélyi, Arthur Thesis Committee: Unknown, Unknown Defense Date: 1 January 1959 Record Number: CaltechETD:etd-02102006-083607 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-02102006-083607 DOI: 10.7907/J15M-W835 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 594 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 10 Feb 2006 Last Modified: 18 Oct 2023 23:17 Thesis Files Preview PDF (Rice_jr_1959.pdf) - Final Version See Usage Policy. 4MB Repository Staff Only: item control page

THE CHARACTERIZATION OF BEST NONLINEAR TCHEBYCHEFF APPROXIMATIONS Thesis by John Rischard Rice In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1959 ABSTRACT consider a continuous function, F(a, p Bop vee y Bay x) of m parameters and x ¢ [0,1]. Such a function is said to have Property NS if the following theorem is valid for every continuous function, f(x): THEOREM: Flak, a, see 5 af, x) is a best approximation to f(x) if and only if there are n+1 distinct points, cc < Qovee Sy < ne %. oF, sae #9 o< , Xo + 1, Such thet a aS» ? age ;) « £l¥ m « [Ploke, oF, cee a* Be fz. = + Max iP(at, a, oo » ark, x) = £(x)]. xe[O,1] 1? 82 Depending on the basic assumptions on F, several sets of necessary and sufficient conditions are given for F to have Property NS. These conditions involve uaisolvence and related concepts. The definition of Property NS is generalized and necessary and sufficient conditions on F are given for F to heve this generalized property. The latter theory includes most common nonlinear approximating functions. ACKNOWLEDGMENTS I am indebted to Professor A. Erdélyi for guiding the research presented in this thesis and for offering invaluable criticism of the text. My thanks are extended to Miss Rosemarie Stempfel for her patience and efficiency in typing the manuscript. CHAPTER I Let two real functions f£ and F be given such that £= f(x) is a continuous fumction for x ¢ [0,1] and & i » *) is a continuous function of n parameters and x ¢ [0,1]. For simplicity of notation the point 1 2 Dy 2 man os . (a, a, .-» 5 @ ) im Euclidean nespace, E» is denoted by a. The domain of the parameters of F is denoted by P, a subset of Ent The main problem in the theory of approximation of continuous functions may be stated as follows: Determine a* ¢ P so that the deviation of the function Fla,x) from f(x) shall be minimized, Naturally one mst define the deviation of F(a,x) from f(x) and different definitions lead to different theories. In this thesis the deviation of F{a,x) from f(x) is taken to be max lF(a,x) - f(x)|. ALL maxima and minima are taken over x <¢ [0,1] wmless otherwise stated. F(a*,x) is said to be a best approximation to f(x) if max|F(a%*,x) - ¢(x)| < max|F(a,x) - f(x)| for all ae P. The results of this thesie remain valid if [0,1] is replaced by any other closed and bounded interval. P. L. Tchebycheff [3], [15] was the first to study approximations using this definition of the deviation and the =~ De resulting approximations are called Tehebycheff approximations. a Tehebycheff developed his theory extensively for F(a,x) = aX, * gant) and Flax) = (3 Kye aXy"-"-1) uring the period 1855 k=O k=n+1 to 1890. He obtained results for specific examples of f(x) and he also treeted general problems such as the uniqueness and characterization of best approximations. The studies of Tchebycheff were continued in the early part of the 20th century by many mathematicians including S. N. Bernstein, E. Borel, M. Fréchet, A. Haex, P. Kirchberger, Ch. de la Vallée Poussin and L. Tonelli. These methematicians extended the theory in various directions such as: epproximation in two variables [14], approximation in complex variables [10], [14], approximation on a finite point set [11], the existence of best approximations [16], the uniqueness of best approximations [5], [16], approximation by trigonometric functions [9], [4]. Dy 1920 an elegant theory of Tehebycheff approximation had been developed for F{a,x) depending linearly on the parameters (2], [12]. Some of the main points of this Linear theory are given in the following resume. Let T be a set of n functions b,x), B(x), wee 9 6 (x) a " % ‘ ‘ re Z 2 contimious on [0,1] and let P(a,x) = }” a” g,(x) be called a ie=1 T-polynomial. P(a,x) is said to be a non-trivial T-polynomial > 6. T is said to be a Pehebychef? Set if every -~3- non-trivial polynomial has at most n-1 zeros. max|F(a,x) - £(x)| is said to alternete n times if there are n+l points <x <x. See) Sx | <4 such th F .) = £(x,) Ogx, <x, <x,., $1 such that B(a,x,) f(x, = (F(a,x5,4) ~ £(x 5421 = + max|F(a,x) - f(x)|. Alternance is @ basic concept in the theory of Tehebycheff approximations. The following theorem answers the principal questionsof a general nature in the theory of linear Tchebycheff approximations. THEOREM: Let T be a Tchebycheff set and let f(x) be an arbitrary function comtinucus on [0,1]. Then A. £{x) possesses a best approximation, B. a necessary and sufficient condition that Pla 5 »x) be a best approximation to f(x) is that mex |P(a,,x) ~ £(x)| elternetes at least n times, C. the best epproximation to f(x) is unique. ode eemaeh olan as te ons © any Boke % would be desirable to have an explicit method for J “?. a <a determining best approximations, out none exists. Theorem 5, which characterizes best approximations, provides the principal means of attacking the actual approximation problem [8], [12], (13). It is natural to try to extend the theory to cases where F(a,x) does not depend linearly on the parameters. Strangely enough little has been done in this direction except that the existence of best approximations had been shown for large classes of non-linear F and the special case we Eh ae Dk, ee gk yee F(a,x) = (S- ax )/( a ) had been treated by linear techniques. The first step towards a non-Linear theory was made by T. GS. Motakin [7] who introduced the concept of unisolvence. The interpolation problem for a family of functions consista in determining a function of the family which assumes arbitrarily prescribed values at n arbitrerily prescribed distinct values of x ¢ [0,1]. An nepareameter family of fumetions is said to be unisolvent if the interpolation problem has a unique solution and if the parameters characteriging the solution depend con- tinuously on the points. The cefinition of unisolvence refers to three independent propertics. These are the existence of a solution to the interpolation problem, the uniqueness of this solution and the continuous dependence of the solution on the deta. If F is linear and P = Eo then these properties are equivalent. Motalsin noted that if the family of curves defined by F(a,x) were unisolvent then results analogous to A, B, ¢ hold. The only other occurrence of unisolvence in approximation theory is in connection with an algorithm for best approximations [9]. Unisolvence and related concepts will play an important role in this thesis. The thesis will give some general results on the sheracterigation of best non-linear Tehebycheff approximations. It will go further then to give conditions on F sufficient for the generelization of the classical linear theory to be valid. ad i) ee Under various basie assumptions on fF, it will give criteria which are both necessary and sufficient for the generalization of Theorem B to hold. A similar problem in the linear theory has been solved ¥ # py A. Haar [6]. He has shown for F(a,x) = >_ ay g, (x) thet a k=l necessary and sufficient condition on F for best approximations to be unique is that B(x), #{x), eee 5 G(x) form a Tchebycheff set. This is tc say that a necessary and sufficient condition for Theorem C to be valid is that $0), G(x), ae B(x) form a Tehebycheff set. Let ¥ be a set of basic assumptions on F. A natural generalization of Theorem Bis: Let F satisfy Y and have Property X. Then the alternation of max|F(a®,x) - ¢(x)| at least n times is a necessary and sufficient condition for F(a*,x) to be a best approximation to f(x). The problem considered in Chapter II is as follows: givma set Y¥ determine a Property x woich is both necessary and sufficient for this theorem to hold for ell £(x). This problem is solved for three sets of basic assumptions on F. The first set essentially assumes only that F is continuous. The resulting Property X is quite complicated. The second set assumes thet the family of curves defined by F is closed under pointwise convergence. The resulting Property X is very closely related to unisolvence. The third set assumes a stronger closure property for the fanily of curves defined by F. The reguliing Property X is unisolvence. Also given in Chapter IIT is a theorem from the field of real variebles which states: a uniformly bounded infinite set of continuous functions which mitually intersect at most a times contains a pointwise convergent sequence. In Theorems 5 and 6 results are obteined eimilar to Haar's result with Theorem ¢ replaced by Theorems A and 5. In Chapter III the degree of wnisolvence is Gefined as a function of the parameters. F is said to be uniesolvent of degree k at a’ ¢ P if F is uiileolvent for all sets of k points on the graph of Fla®,x), x <« [0,1]. The extension of Theorem B is then taken to be; Let F satisfy Y and have Property X. Then a necessary and sufficient condition that F{a%,x) be a best approximation to f(x) is that max|P(a*,x) ~ f(x)| slternates inde an i at leagt k times. Here k is nob assumed to be a congtans. The second set of conditions from Chapter IL are taken for ¥. Iv ie then shown thet Property X is “wnisolvence of degree k at att! and is both necessary and sufficient for this theorem to be valid for all f(x). This theory is of great practical interest and includes mogt common non-linear apyroximating functions. CHAPTER II 1. Euclidean n-dimensional space is denoted by E3 points in =& ore denoted by a, b, etc. and the coordinates of a are (a', a’, woe > a). Curly brackets, { 3 , denote a set and {x| we is read as "the set of x such that... ". Sequences are denoted by square brackets. All maxima and minima are taken over x <¢ [0,1] wumless otherwise stated. The veal. function F = F(a,x) is defined for x ¢ [0,1] =: amd ae P where P is a subset of Ea F is continuous in the sense that given a ¢ P, x, ¢ [0,1] em@ ¢ >O there is a $ >0o such that ae P, x ¢ [0,1], la, ~ al + lz, -~x| < § implies that jP(a,.x,) - F(a,x)]| <c. It is assumed that if a f#a* then Fla,x) # Fle®,x) for some xc [0,1]. The genge of F, R, is definéi' to be the set {(x,Fla,x))| x ¢ [0,1], ac p} in x,y plane. f(x), e(x), etc. will denote continuous functions on [0,1]. The Tehebyecheff Approximation Problem for a continuous function, f(x), may be steted as; Determine a*¥ ¢ P such that max|P(a*,x) - £(x)| < mex|Fle,x) - f(x)] for all ae P. A solution, F(a*,x), to the approximation problem is called a best approximation to f(x). The concept of “alternance” plays a major role in the classical theory of Tchebycheff a “imation developed for polynomials and Tchebycheff sets. The aim of this chapter is to «~ B= sbudy ‘alternance’ in more general. situations and to characterize it there. The following definitions are required. DEFINITION 1; max|F(e,x) - f(2)| is said to alternate k times if there are k+1 points oS, < x, S eee S Hy <1; : %. aunt ”" wo , om 5G e toe 5 such thet P(e*,x 5) £(x,) (Fla®, x,.,) e(x5.4)) = + max|F(e%,x) - ¢(x)|. If mex|F(a*,x) - f(x)| alternates k times but not k+1 times then max|F(a%,x) ~ ¢(x)| is said to alternate exactly k times. DEFINITION @: F hes Property N if for every continuous f(x), the alternance n times of max|F(at,x) - ¢(x)| is a necessary condition for Fle*,x) to be a best approximation to f(x). DEFINITION 3: F has Property S if for every continuous f(x), the alternance n times of max|F(a%,x) - f(x)| isa sufficient condition for F(a*,x) to be a best approximation to f(x). DEFINITION 4: F has Property NS if F has both Property N and Proyerty 5. From the lest definition it is seen that the problem of character- izing “alternance’ is the problem of characteriging Property NS. -~9- 2, The two properties needed to characterize Property NS are given in Definitions 5 and 6. DEFINITION 5; F has Property Z of degree kif a # a® implies that F(a,x) - F(a*,x) has at most k-1 geros The phrase “of degree k" is omitted if k=n is understood. DEFINITION 6: F has Property A if given a” ¢« P, {x,l0 2x, <x, <0 <x = tf and ¢ with | i . a. i) there are a ¢ P such that for x ¢ [0,1] v 8a F(a®,x) - « < F(a, »x) < F(a*,x) < F(a,,x) < F(a*,x)+ ¢ ii) there are a,, a, ¢ P such that |F(a,,x)-F(a*,x)|<e, i) [F(a, x) - F(a®,x)| <e¢« for x ¢ [0,1] and F(a,,x) ~ F(a*,x), F(a,,,x) - F(a*,x) change sign from x -¢ to x, + ¢, and have no zeros outside (x, - €, X, + ely G = 15 2, oe y» K Further F(a, ,0) > F(a#,0) > F(a,,0). The first theorem characterizing Property NS can now be stated. THEOREM 1: F has Property NS if and only if F has Property A and Property 2. The proof of Theorem 1 follows from a series of four lemmas. LEMMA 1: If F has Property A then F has Property N. ~ 10 « PROOF; Assume thet F has Property A but does not heave Property N, i.e., Fla*,x) is a best approximation to £{x) end max|P(a%,x) ~ f(x)| does not alternate n times, If max|F(a*,x) - £(x)| does not alternate at all, let x, be a point where |F(a*,x) - f(x)] assumes its mximm. Say F(a*,x, Jet(x, )>0, then by 1) of Definition 5 there is an a, 2 €P so that O < Fla®,x) ~ Me <e. For ¢ sufficiently smill it is seen thet F(a,2X) is a better approximation to f(x) than F(e*,x). Hence max|F(a%,x) - £(x)] mst alternate at least once if F has Property A. ee The interval [0,1] may be divided into # subintervals eye y Om x Su, Sere Sap sd, <n so that i) P(a¥, x5) ~ £(2 ry 2 =O, = 1, 2, eae , Pi eG 21) mex[F(s*,x)-2(x)] alternates exactly once on amy two adjacent subintervals but does not alternste in any one subintervel. Let Os = max(P(a*,x)-£(x)) - min(F(a®,s) - f(x)} with the maximum end minimm taken over Bag & { fe bi ° - ; ° — 7" pM ad * Us; Ts see 9 Amie About each % a y = Ty ang eee 4 ~i there is an interval ml ~&p “a + e 4 such thet in this interval jen? g aa Oy Ts eee 2 Af -1. Les 7 3 = max |Fla*,x)~£(s)/ e ee ar t max |Ple*,x) - £(x)|) end determine ac P by 44) of Definition 5 so thet F(a,x) - Fle*,x) changes sign from X,~¢ tO xX, +e, J = 1, 2, woe » P-1 with max|P(e*,x)-F(a,z)| <¢. Further choose the sign of F(a*,0) - F(a,0) so that |F(a%,x) - £(x)| > [r(a,x) - t(x)| im (0, x, - ¢€)} the same «oe FT = inequality will then hold outside of (x 5 eG X 5+ ce], § = 1,2,000,f~1. F(a,x) is a better approximation to f(x) then F(e*,x) which contradicts the assumption and proves the lemma. LEMMA 2: If PF has Property Z then F has Property S. PROOF: Assume that max|F(a*,x)- f(x)| alternates n times and that there is an ae¢ P such that max!F(a, x) ~ f(x)| < max|F(e*,x) - £(x)]. Let {x14 = 1, 25 aoe » Btls * 5 < sf be a set of points in [0,1] such that B(a¥,x,) “ f(x) = (F(a*,x, 4) - #(x54)) = + max|P(a*,x) - f(x)|. Then egn(F(a%,x.) ~ F(a,x;)) =~ sgn F(s*, x54) ~ Fla,x,.,)) which implies that Fla*,x) - Fla,x) has at least n zeros contradicting Property Z. LEMMA 3: If F hes Property NS then F has Property Z. PROOF: Assume thet F has Property NS and thet there are a, a% <¢ P such that Fla,x) - Fla®,x) has nor more zeros. Let Mix) = 4 (F(a,x) + Fla®,x)]; | = 4 max|F{e,x) - F(a*,x)| and let O$x, <x <cer<x, <1 ben points where F(a,x)-Fla*,x) = 0 along with one point where F(a,x) - F(a*,x) 40, sey F(a*,x,) > F(a,x,) for concreteness. Set § = min(x, 2X5 “Ky gece a 1x4) with x, or 1- x, , omitted if they are zero. A fMmetion f(x) continuous on [0,1] will be defined as follows: f(x) = M(x) in the intervals ix, + 5 5% 5,4 - 51, J = 1, 2, ese 4 23 f(x) = (x) in [o, x, -§] if x, > 0; e(x) = M(x) in «= 12 « [%o4 t & i] if Kay < 13 in the remaining intervals £(x) satisfies e(x,) F(a, x 5) + (01) 8" (al) and |¥(a,x)-f(x)| Al, [r(erx) - (x) <A cor x fx. Now max|F(a%,x) - £(x)| alternates exactly n times and max|F(a,x) - £(x)| alternates exactly n-2 times. By Property S F(a*,x) is a best approximation to f(x) and since max|F(a,x)-f(x)| = max|F(a*,x) - £(x)| so is F(a,x). This contradicts Property N and proves the lemma. LEVMA ks If F has Property NS then F has Property A. 2 i 3 Fe < =z see x = PROOF: Let a* ¢« P, {x,l9 Xo us < $41 '} 4< n= and ¢« be given with O<¢< 4 min(x 547%). . j j j =O, 1, «06 » f « A construction showing the existence of a of Definition 5 will be described, the existence of Ais B, and a, follow by similar constructions. A function f(x) will be defined as follows: f(x) is continuous on [0,1]; in (x, + Ey Big ~e], J = Vy 2, ove , f 1; £(x) = F(at,x)4(-1)"* 1), end f(x) is linear in each of the remaining intervals. Since max |F(a%,x) ~ £(x)| alternates at most f times, F(a*,x) is not a best approximation to £(x) by Property N. Hence there is an @, ¢P which is a better approximation to f(x) than F(a*,x). 3 This implies that max |F( 2. 5x) ~ F(a®,x).| < ss - Further F(a,,x) ~ £(a%*,x) has no zeros outside of the intervals [x prox jrel ’ j= 1, 2, oo » # and alternates in sign from ken e to Xi + €s j=, 2, coe p Poe It is clear that Theorem 1 follows from these four Lemmas. A difficult problem associated with this theorem is the problem of possible improvement. Tt is difficult to lmow whether there is somecther property, apparently simpler or more restrictive, which, along with Property Z, is equivalent to Property NS. The following example shows that it ie unlikely that theorem 1 can be improved upon in this sense. This example shows thet there exists @ one parameter function F with Property NS which is unlikely to satisfy any set of conditions simpler than those given for Property A. Let the number p be of the form oft" where ce is odd. Then the index m(p) of p is defined to be m. The mltiplication of a set P of real numbers by a constant a is defined by aP = japlp « P} end p, + aP means {, + ap] pe Pf . Let P= fz 28g 21, 2 oo f ufof.p, 4s derinea recursively from P. k= ry # am ; arm ‘ ‘ ae oH} . 2 . set p+ P,/2 NP? P.. is defined to be the union of all such sets as follows; let p« P. 4 and fom the for pe Py se. - Ley P=(J p,. Tt may be shown that P isa k= nowhere dense courrbable set, P is taken as the parameter space of F with F(a,x) = a for ae«P. Every point of P is the limit from both the left and right of points in P, giving F Property A. Hence F so defined has Property A, Property 2 end Property MS. e 1). 3. With further assumptions on the function F a much simpler and more elegant characterization of Property NS may be given. As 2 preliminary a theorem in the field of Real Variables is proved, a theorem of some interest in itself. THEOREM 2: Let {ex} be a uniformly bounded infinite set of functions continuous on [0,1] with Property Z. Then { £ (x)} contains a pointwise convergent subsequence. The proof is broken inte four paris. In the following when a sequence of functions is chosen whose fumetion values converge at a particular point, it will always be chosen so that the convergence is monotonic at that point . LEMMA 5: Let fc} be a uniformly bounded infinite set of functions continuous on [0,1] which are mrtually non-intersecting. Then fe (=)} contains a pointwise convergent sequence, PROOF: Consider { £ (0) } which is a bounded set of real mumbera and hence conteins a convergent monctonic sequence [f,(0)|k = 1, 2) ee. ]. Since (f,,(0)] is monotonic so is [£,(x)] monotonic for every x ¢ [0,1]. Since (f,(x)] is bounded it follows that [2,()] is convergent for every x ¢ [0,1]. = 1 = LEMMA 6: Let fed} be a uniformly bounded infinite set of functions continuous on [0,1] with Property Z of degree 1. Then {2} contains a pointwise convergent sequence. PROOF: For simplicity the sequences f, ph®), fy pl), eee and Bypl*), Engl), eee are Cenoted by Fy and Gy and their limits et x are denoted by Ep (x) and Gp{x) if these limits exist and if Fp, Gp are monot onic at x. Fy Cc Gy will be used to indicate thet F £ is a subsequence of G y with the order Choose a sequence F, from £(x)} such that F (0) ang F oh) exist. If F, is increasing at both © and 1 or decreasing at both points then the fyumetions of {e,, mc); must be mutually non-intersecting and Lemma 5 stabes that Po is a point- wise convergent sequence, If Pe converges in opposite directions at O and 1, then choose FCF, such thet F, (4) exists. The direction of convergence of B, at x= 4 mist agree with the direction of convergence of F, at either 0 or 1, Hence a subsequence BC F, may be chesen which ie pointwise convergent in an interval of Length A as in Lemne 5. Choose PoC G, so that F, converges at the midpoint of the remaining interval, Agein the direction of convergence of F, at the midpoint mist agree with the direction of convergence at one of the endpoints. As in Lemma 5 there is a ~ 1G = subsequence G(T F, which te pointwise convergent except in an interval of Length : ° In this way an infinite number of subsequences ¢,296,D°"° = Gp > *** way be found uhers yp is pointwise convergent except possibly in an interval of length a? » The diagonel sequence of this sequence of sequences may be formed and it converges at all points of [0,1] with possibly one exception. in case the dlagonal sequence fails to converge at one point then a further subsequence is chosen that converges there also, LEMMA 7: Let fe (x)} be a uniformly bounded infinite set of functions continuous on [0 v1] with Property Z and such thet for every x ¢« [0,1], every monotonic infinite sequence from {é £ (x) ig monotonic decreasing. Then {£,()} contains a pointwise convergent sequence , PROOF: The proof is by induction on the degree of Property 2. The Lemma has been established for n=0 and n= 1, Ii will be shown that if the lemma is true for Property 2 of degree k then it is true for Property Z of degree k+2, Select a sequence F, from {2} which converges aod at x= 0, De le By is monotonically decreasing at these points. The assertion is now made that F Oo either nas a subsequence which & is convergent in [0, 3) ex one which is convergent in (4,1 ]. -~7- Assume that there is no convergent subsequence in i a =>, 1]. Then there is an x 2 _ lL 4 7 ra Ci 1¢ [Ss 1] such that F(x, ) does not exist. Choose subsequences F.C. ; GC F 0 such that F,(x,) < G,(x,) For some k,, £1. 1%) < G,(x,) and therefore there is a subsequence KC G, such that every function of Hy intersects £, .(x) in ch, x,) and (x,,1). k,1 2 1 1 Hy does not converge in 4, 1] and hence there is an X_» Say in (x,.1], such that H, (x) does not exist. Choose sj 3 H 6 # 9 gad a = PLC Hy» GC i, such that F(x) < G,(z,) Again for some ky» #, ab%2) < G{x,) and hence there is a subsequence H, CG, such that every function of H, intersects f. (x) in (x, 2X) Fee and (x,,1). in this way an infinite sequence F* = (f,, p20 =1,Byse0, Sp “ey Z of degree k. The induction hypo is applied in [0, 4) to obtein a pointwise convergent gub- sequence G% Cc FS . It has thus been shown that there is a sequence Gs from { £ (x) which converges in an interval of length i. The entire construction is now repeated to obtain Ge C Ge which converges in half of the remaining interval. Continuing in this way @ sequence of sequences Ge GF D ses is obtained which converge except in intervals of length 4, L, ese « The Glagonal process is used as in Lemma 6 to obtein a subsequence which is pointwise convergent in [0,1]. a Po It is clear thet this lewma is also true when decreasing is replaced by increasing. PROOF OF THEOREM 2; The proof is by induction. The induction hypothesis is that the theorem is true for Property Z of degree k. For k = 0 the theorem follows from Lemmas 5 and 6. It is assumed that {#,,(%) } has Property % of degree k+1. If€ there is a subset of { £ (x)} satisfying the assumptions of Lemma 7 the proof is complete. If there ig no such subset then there is a sequence P from {¢,(«)} which has opposite directions of convergence at two points, x, and x,,. Let A be ae 1 the set of points in [0,1] such that all subsequences of Py are monotonic decreaging or all are monotonic imcreasing at these points. A is non-void since it contains x, and x,. If A # [0,1] then 1 & x, may be chosen in A and x, not in A such that Ix, - x,| is arbitrarily omall. I€ A= [0,1] then A may be divided into two non-voeid sets; one with all increasing subsequences and one with 4 BI all decreasing subsequences, Then X, may be chosen in the first — set and Xy, in the second so that x. ~ x, | is arbitrarily emall. In either case there is a subsequence F,C Be and X39 Xy € {0,1] such that xy <x 49 F, has opposite directions of convergence at x. and x), and (x. 9%)] has length lees than 5 ¢ Since every member of Fy intersects every other member of F, at least once in [X35 xy] » in each of the intervals [0,x5] and [x yell F, has Property 2 of degree k. By the induction 1 hypothesis there is a subsequence F,(C Fy which converges point- wise in these intervale, - 19 = I? F, satisfies the assumptions of Lemma 7 in [x54] the proof is complete. If not, a repetition of the above argument shows thet there is a subsequence F2C F, which converges outside of (x, 9%¢] where the length of [3.59%] is Less then i. Thies process is repeated to obtain an infinite number of sequences F, DF, eee > se* where Fp is pointwise convergent except in an interval of length less than at. me diagonal sequence may be taken as in Lemma 6 to obtain a point~ wise convergent sequence in [0,1]. h, The assumptions on F with regard to the dependence of Fla,x) on a have so far been rather weak. In cases of general interest F satisfies mich more stringent conditions. These conditions are i) a closure property of some kind for the family of functions defined by F and ii) a regularity property for P. Two such conditions are exactly defined in the following DEFINITION 7: F is said to be clesed if P is connected end if F is closed under pointwise limits, i.e., Lim F(a,.,x) = G(x) with (x, G(x)) ¢ R implies that ke co there is an a. e¢ P such that lin a= 8 and hence L* irre Oo F(a, ,x) = G(x). The aim of this section is to characterize Property NS with the additional assumption of closure on F. If P is a comnected set then FR is seen to be a perticulerly simple region. Let L(x) = {(x,F(a,x)) fe € P} . Since F is contimaous and P is connected L(x) is a line segment and R = U , L(x). Let Lt) be the interior of L(x) x¢[O, in the one dimensional topology and let R, = U L oh)» LEA 8: If P is comnected and F has Property NS then given a*eP there is an ¢ 20 such that (x, Fla*,x) = ¢) « R, for all x. PROOF: Since F has Property NS,by Theorem 1 F has Property A. By 1) of Property A there are @,, 8, ¢€ P such that F(a, ,x) < Pla*,x) < Fla,.x)- Let ¢, = min|F(a, x) - F(a*,x)|, Ep = min|F(a,,x) - Fla*,x)| and ¢ = 5 minle,, Eg). Since P is connected it is clear that (x, Fla*,x) + ¢) ¢ R, for all x. The following property will be used in the character- ization of Property NS. DEFINITION 8: F is said to be locally solvent if given Ogx, <x, << x, $1, at e P and ¢ >0O there is a 1 2 $ (av, Ep Xya Eos vee » x) >O such that ly, - Fa¥,x,)1< 8 implies the existence of a solution ae P to Fla,x > =¥; with max|F(a,x) ~ F(a*,x)| <. DEFINITION 9: F is said to be locelly unisolvent if F is locally solvent and has Property Z. LEMMA 9; If P is comnected and F ia locally unisolvent then R= Ree PROOF; Assume that (20294) é R, with y= F(a%,x,). By the Local solvence of F ‘there is a § (2% )%2 wae ) > O and a,, @ ¢ P such thet F(a,,%,) = F(a*,x,) + 4 bo F(a,.X,) = F(e*,x,) “ i 8 6 . This is a contradiction and proves the Lemma. The purpose of Lemma 9 is to show that Property NS and Local unisolvence each imply that RF = Ey if P is connected. A zero x, of f(x) is said to be a simple zero if f(x) changes sign at x, and a double zero if f(x) does not chenge sign at 5 The following le shows that if F is Locally unisolvent then Property 2 is valid counting the miltiplictty of gered s cannot have more than n-1 seros counting multiplicities, PROOF; Let {x13 = 1, By woe kt be the set of geros of F(a,x) - F(a¥,x). Assume, for concretenses, that x, isa double gero and Fta,x) - Fla*,x) > O near x,. Since F is 1 locally solvent there is en a, « P such that F(a, x5) = F(a,x;) J #1, Fla,,x,) < F(a,x,) and max| F(a, sx) ~ f(a,x)| <<. For ¢é ouffielemily amall it is clear that 4) {x13 = 2, 3, eee; Kt are geros of F(a, x) ~ F(a,x) ii) every double zero of F(a,x) ~ Fle*,x) is either a double zero of F(a, .x) ~ F(a*,x) = 22 = or has been replaced by two simple zeros. iii) F(a, 5x) ~ F(a*,x) has two simple zeros near x Hence, counting multiplicities, the 1° number of geros of F(a, >x) ~ F(a*,x) is the same as the mumber of zeros of Fla,x) - Fla*,x). This process is contimed to obtain e,,¢P such that F(a,,x) ~ F(a*,x) has all siuple zeros and the munber of geros of P(e») ~ F(a*,x) and Fla,x) - F(a*,x) is the same counting multiplicities. This completes the proof. \ Property NS can now be characterized by THEOREM 33 If F de closed then local unisolvence is a necessary end sufficient condition for F to have Property NS. The fact that F is closed leads to the following stronger form of Lemma 4. LEMMA 11; Let F be closed and have Property NS. Then given a®*¢ P, ¢ >G and a set {x ,lo=x, <x <0 <x, 1 < Xenq 13 k<nf there are A,» By € P go that i) F(a*,x) - F(a, 5%)s F(a*,x) - F(a,,x) change sign at the Xa dg = 1, 2) see , K and at no other points. ii) |F(e,,x) - Fla*,x)| Se, |F(a,.x) - Fla*,x)| S « iit) either F(a, »*) ~- F(a*,x) = 0, F(a, ,x) - F(a%,x) = 0 or sgalF(a,,x) - Fla¥,x)] = - sgn{F(a,,x) - F(a*,x)]. PROOF; The proof is given for a,, the proof for a a? follows in the same way. By Lemma & it is possible to take ¢ small enough that (x, Fla*,x)2¢) ¢R, for all x. Let i Loe < + mh - cee -: ~ e. y, min(x, , Xo - Kyo cr ae x.) where x 7 or nx, is omitted if they are zero. A sequence of functions [fy(x)|P zs Ps? 4, “1, ves ] will be defined so that fp(x) continuous In [0,1]; im the intervals [x + $>%; io j= 2, 3, vee » Ket, fpix) = = P(e®,x) + (- ips £; e x tp(x) = Fle%,2) +& in [0, x, eae: fom <1, fg (x) = F(a®,x) + (-1)* 3 in txts & G eyod ie linear in each of 7 the remaining intervals. F(a*,x) is not a best approximation to any fp) for max|F(a%,x) - fp (x)! alternates at most k times. jowever it will be show that there is a b pe P such that F(bp x) is a best approximation to fp (x). Consider a Sexquericg (F(b, peli = 1, 8, «6 | for which us max|F(bp. 5x) ~ £9(2)| : int mala) . +p. (Flo, %) forms a bounded infinite set of continuous functions. This set has Property Z by Lemma oe Theorem 2 may be applied to extract a | convergent subsequence of [ely qexl. By the closure of PF the subsequence has a Limit, Hop » which is a best approximation to fp (x). In the seme way [F(bp x) |P = fos ft coe | has a limtt F(a,,x). Clearly 0 < (P(a,,x) - F(e*,x)] (-1)8 < (-1)) « in (x, pe jar)? 3 = 0, 1,2, ee ,ke If a, # ea then it is seen thet F(a,,x) ~ F(a%,x) changes sign at the X59 j 21, 2, oes y kK and nowhere else. it remains to be shown that a, # a. Since mast| F( p .x) “ fi plx)| alternates n tines, max |F(bp 52) ~ Flat,x)|> = we UL ow by the closure of F lim by = a,» Since max|P(a,x) ~ F(a*,x)| 8 my 2 is a continuous function of a it follows that lim max|F(b,,x) 5 eo ~ Flat,x){ = mae | F(a, x) » Flaw,x) | 24 and a, A a, DEFINITION 10: F(a,x) is eeid to be between F(a,,x) and F(a, 5%) if | F(a,e*) ~ Fla,x)| + [Pla,x) - F(a,,*)| = [P(a, 2x) ” F(a,,x)| for all x « [0,1]. LEMMA 12: Let F(a, »x) ~ F(a,,.%) change sign at ne-1 distinct points and let Pla, .x,) # Flay.x,)+ ie F is closed and has. Property NS then given y between. F(a, ox 5) and Ff a, yt) there is an ac P such that Fla,x) =y amd Fla,x) is between Pla, x) and Plagst). PROOF: Sinee FB. has Property NS it follows from Lemma 3 that F has Property 4 end. hence F(a, yx) = F(a,,x) has exactly ne1 Zeros. | | | For conereteness agsume F(a, s,) > F(a, s%,) and let I= (r(a,.x,), F(a, ,*,)) end A be the subset of I for which the lemma ia true, - It will now be shown that A is a closed set, Let ty ld = Vy By oe 5 v3 ¢ Aj’ be given with iim v5 = Vor Corresponding to ty 3] there is a sequence (r{a,,x)|Fla piv yl of functions between Flay)x) and Fla,s%). Theorem 2 is applicable to this sequence and hence [Fla peed has a pointwise eonvergent subsequence. Since F is closed this subsequence has a limit Fla,,x) and Pla,.x,) =¥, which implies y, < A. ~ 25. \ It will now be shown that I-A is emty. I-A Is an open set. If I-A is not empty it contains an open interval (¥ 27, ) with y,.y, ¢4+ Since y,<¢ A there is an a, ¢ P so that F(a, 5%,) =¥, and F(a, »x) is between F(a, .x) and F(a,,%)- By Lemma 11 there is an a, ¢ P such that F(a, 5x) is between F(a, »x) and F(a,,x) and ¥o < Fla,,x,) <y,- This contradicts the existence of an open imterval in I-A and A= TI, LEMMA 13: If F dis closed and has Property NS then F is Locally solvent. PROOF; The proof is conducted by an induction argument. The statement to be verified by induction is: Let a@*¢ FP, ¢>0 and @ seu f«,| Os x, < Eo Sse k x < if be given. Then there tsa §(a%, «, ky x5) >O such that ly v5 Flat) S j=, 2, «.. , EX implies that there is an ae P guch that F(a,x,) =e, d = 1, 2, +e+ , Kk; [Fla,x) - Ple*,x)] <e¢ and : o Pa,x,) = B(a*,x 5), j = kel, ee. , & The induction is on k and for k =n «the statement implies that F is locally solvent. For k= 1 this statement will be established from Lemmas Viand 12. Let F(a, 2x) and F(a, sx) be determined by Lemma 11 g0 that Fla, 0X5) = Pla, .X 5) = Fla*, % 5) j= 2, By vos 4 23 [F(a, ,x) ~ Flat,x)| <<, [F(a 2%) ~F(at,x)] <¢ and F(a, .x,) > Fla®,x,) > Fla Oy 9%, ). Since F(a, , x), Fla, x) intersect at n-1 points it is not possible that F(e,,x,) = Fle%,x,) or ~ 2 ~ P(ay,%,) = F(a®,x,). Take S(a®, > 1, x) = min(|F(a, x, ) ~ Fla#,x,)|, |Fla..%,) - F(a*,x, )|} and the statement follows for k=1 by Lemma 2. | In order to proceed with the general induction step seme auxiliary facts will be established. Let # = (y', y*) «ee 5 ¥*) k Ls, 2, eee 5 x . Define two subsets, Py) and PAY), be a point in E, end let A = {sl ly* - F(a*,x, )| < 5 (a*,¢,k,x.), Pea of P as follows: |F(a,x) - Flat,x)| << for ae PY), ae PA(Y)s Flax) = y Pa,x,) zs F(a¥,x5), j=, ...,, ae PAY), @¢ PAY); Fla,x, 4) > Pla, x, 4). ae Py); F(a,x,,,) < Flat, 1), ae PAY). Let S (5) “Sg (Fla,x,,,) - Fle*x,,,)), 59) = sup (F(a*,x,, 4) ~ F(a,x,.,))- It follows from Lemma 11 that acP(7) P,(y) and PAF) are non-empty and that 5 (3) > 0, 565) > 0. F(9,(7), x) ~FCge, x) F(4,(¥), x) ~FCQX x) 50) Xo7 7 Kren . Me Keay Keay m= Ky = 27 - It will now be shown that for any y,eA there is a neighborhood, N(F o) , of ¥. such thet ¥ ¢ N(¥,) implies sya dt = nave 4 rt n 55) z 2 55). There is an a, ¢ P,(¥,) such that i * : ae F(a, r%4) > Pla*,x,..) +5 S 9%) Hence by the induction state- nent applied to F(a, 5x) there is a CS CHME k, x5) >O guech that for every 7 with ly! - ysl < 8, there is an Ffla,x) so that i) Fla,x,) =y%, J = 1, 2, ok it) F(a,x;) = F(a, ,x,) Y a F(s%,x, ), J = Be, «0. ym, ili) Fla,x Xe) = F(a ) 1?" ke 2 F(a*,x,,) + 4 é, (¥,)« Further |F(a,x) - Fla,,x)| < vi and for t sufficiently small [F(a,x) - Fla*,x)| <¢. Hence 5, defines a neighborhood, NY, )} so that for every point y of NY, ) there is an a e Ay) with Fla,x, ) 2 Fla*,x,.,) + 4 55.) “E+i It will now be show that §. (5) is bounded away from wero for YyeA.e A is a compact set whieh has an open covering by neighborhoods , (NGF « at » Hence A has a finite covering MG, ), «0+» MF) ond J,(F) ZA mint [F,), 5G) 55,1 = 5, > 0, A similar ergwacnt shows that 55 (7) 2 S2 > Of The general induction step can now be made with the preceding construction and Lemma 12. For K> 1 ‘take S(a*, ¢, kel, x * 4) = min{t é, ’ 4 Sos S (2, e, k, x,)1. - Given any set Fs = 1, 2, see 5 ket, |Fla¥,x,) “ y"] s §(e*,c,k+1,2,)} then there are a,,a, ¢ P such that i} Pla, 2X5) mi Flay x,y", j os ly 2, eae 9g Ky ii) F(a, »%,,,) = Fla*,x,,,) + § (a¥,c,k+1,%5), - 2 - P(a,, %,,,) S Fla*,x,,,) -§ (a®, cy ket, %5)3 iii) Fla, x) F(a,,x,) = Fla*,x,), j = k+2, oe. » nj; iv) [P(a,,x) ~ Fle*,x)|<, [P(a,.x) ~ F(a*,x)| <e¢. By Lemma 12 there is an a This concludes the induction step and it follows from the induction 3 e P such that yt! »x) is between F(a, ,x) and F(a,,x). end Fla statement for k=hn thet F is locally solvent. LEMMA 14: If F is closed and locally unisolvent then F has Property N. PROOF: Assume that max|F(a*,x) - f(x)| alternates exactly k times, k <n. It will be shown that F(a*,x) cannot be a best approximation to f(x). If max|F(a*,x) - £(x)| is not assumed at both O and 1 then one of the intervals [o, §], {1- 8,1], say (0, 5] for concrete- ness, is chosen with & determined so that for x € [0,8] and some €, > 0, we have |F(a%,x) ~ £(x)] < max|Pla%,x) ~- £(x)] - Eo: Let O = XS Xi S Kay S subintervals so that i) F(a*,2 ,) - #(x,) =O, j = nek, n-K+1,006,N-13 nso <x = 1 divide [0,1] into kei ii) max|F(a*,x) - £(x)| alternates exactly once in any two adjacent subintervals but dees not alternate in eny one subinterval. Choose n-k-1 distinct points, EA = 1, 2, vee 5 Kel, x; <Xiif in [0,5]. Let a, = max(F(a#,x) ~ £(x)) - min(F(e,x) - £(x)) with the maximum and minim taken over (x 59% ], J = na-k-1, nek, ccs , Rel. d+ Let 1; = max|F(a%,x) ~ £(x)] - 4 Oa» j = M-k-1, D-k, ose y i+] hd a 7 ai and ¢ = min('? ray? coe B n-1? B ea)e Let x! denote a point where max|F(e*,x) - f(x)| ie attained. ~ 29 - Since F is locally solvent there is an ae P such that F(a,x) - Fla*,x) changes sign at Xy3 § = 1, By eee » Bet and IF(a,x') - £(x')| < [P(a*,x') - f(x')| with max|F(a,x) - Fla%,x)|<e. Since F(a,x) - Fla®,x) cannot have any more geros Fla,x) is wiiformly closer to f(x) than F(a*,x) except in [0, § ]. There- fore Fla,x) is a better approximation than Fla*,x) to f(x). if max|F(a*,x) ~- £(x)| is assumed at both O and 1 let the interval {[0, $) be replaced by ae § oh nate! where {x,13 =O, tek, coe , ah, $ 5 cj1 0s Yj and ¢ are defined in a manner analogous to the preceding construction, For nek-1 even nek and determine ae¢ P so that [F(a,0) - £(0)| < |F(a*,0) ~ £(0)|, ehoose n-k-1 points fr sles ~ 5 < x, < Xv Qeoe QE , < Xf lF(a,1) - £(1)] < [R(a*,i) - £(4)], [Pla,x) - Fla*,x)| <¢ and F(a,x) ~ F(a*,x) changes sign at the 2 5 j= 1, 2y ove » Nels F(e,x) is a better approximation than Fla*,x) to £(x). For n-k-2 3 nek-1 ~ “n= and determine a so that [f(a,0) - £(0)| < |F(a®,o) - £(0)|, even choose nek-d points (51% -§ < Xo ax, Sore Sy a xX icf |P(ayt) = £(1)| < |P(e#,1) = £1) |, [Fla,x) = Fle*,x)| < efor x ¢ [0,1] and F(a,x) - F(a*,x) changes sign at the X53 j= 2, 3, oo , ml. Fla,x) - Fle*,x) cannot have another zero without having two more, counting multiplicity, and hence Fla,x) is a better approximation then Fla*,x) to f(x). This concludes the - proof. PROOF OF THEOREM 3: The stetement of Theorem 3 may be considered as a set of four statements, namely Lemmas 2, 3, 13 and 14, all of which have been established as truc. ~ 30 — 5. In Theorem 3 Property NS is cheracterized by mainly iocel properties of the function F. If e stronger closure condition ig imposed on F then Property NS can be characterized by "global" properties of F. This stronger condition is satisfied by the common forme of F, DEFINITION 11: F is said to be solvent if F is locally solvent and if given a set {xp9 do $k, <¥y Sere Sx, 1 1 (x, “) € nb then there is a solution, a ¢ P, to the equations F(a,x,) = Oye J cd Vy 2, eee » Neo DEFINITION ie: F is said to be unisolvent if F is solvent amd has Property 2. DEFINITION 13: F ie n-point closed if P is connected and if F is closed under pointwise convergence at any n points, a implies the existence of an a, « P such that. Fla, »,) =, ww It is seen that if F is nepoint closed then F is closed, THEOREM 4; If F is nepoint closed then unisolvence is a necessary and sufficient condition for F to have Property NS. Lemmas 2, 3 and 14 still apply here as in the proof of theorem 3 and only Lemma 13 needs to be replaced. LEMMA 15; If F is n-point closed and has Property NS then F ia éclivent. set of n points which shall remain fixed through the first portion of this proof. Relative to this set define U i «gy ey far} «3 =) ry “So u tay os & Bos ate Set we Qe Pt » Hecall the definition of Lt) in the discussion pre- ceeding Lemme 8. Let L(x) be the closed interval obtained by shortening L(x) by ¢ eb each end. Let we = {ly cE, y? é £(x,)f ° We is seen to be an n-dimensional parallelepiped. It will be shown that ¥ AO U=W, for ell ¢ sufficiently smell. “It follows from the n-point closure of F that wi U is a closed set in £ ~ Since n-point closure implies closure it follows from theorem 3 that F is locally unisolvent. Let Vo be any point of wu. Since F is locally solvent it follows that there is a 6(y., 2X > > 0 defining en n-dimensional cube about y, which is in U. Henee w(\ U is an open set relative to Woe “ Since FR = Re is non-empty it is cleaz that for some ) Ee, > % wf ) U is non-empty. Therefore wf lu is a non-empty set ‘0 ° which is both open and closed relative to Wand W. ues Woe ° ° a) It is clear that for ¢« < fo? #7 U is non-empty and hence W U-aW for ee. Nl € ~ "oO Since R= Roy ery set {yly" & L(5), gj = ty 2) woe y nf is represented by e point in We for some «*¢ 3° Therefore there j isan ae P so that F(a,x5) = y", J = 1, 2, oo » ny for any get {v(x 99) é€eH, §= 1, 25 «ee ; a}. -~ 32 — 6. It has been seen that the nature of P plays an important role in thie theory. In the claseical theory for Tchebycheff sets it is alwaye assumed that P = Boe From the example following Theorem 1 it is seen that P need not be E in order for a linear approximating function to have Property NS. The question then neturally arises; can Theorems A and B of the introduction be true for a linear approximating function with P 4 E? Tt hes been shown [6] that Property Z is a necessary and sufficient condition for Theorem C to be valid. Theorem 5 gives conditions on P and F in order that either Theorem A or Theorem B be valid for a linear approximating function. The question raised above is answered negatively by Theorem 6. moe THEOREM 5; Let F(a,x) = 2. a" 8, (x) where 2, (x) is 32] continuous on [0,1]. If éet(g,(x,)) #0 for each set {Se 2 eoe fhe s s & {x13 1, 2; 5 Ts x, < Saat? xs € [o,1]} then i) F has Property NS if and only if P is open, ii) Every continuous function has a best approximation if and only if P is closed. PROOF: Since the preof of this theorem is straight forward put involved only a sketch of the proof is given. 1) If P is open then clearly F is locally solvent and hence has Property NS. Assume F has Property NS and that P contains one of ite boundary points, a,. Let fx 513 = 1, 2, oem, Xe [o,11} be a set of n distinct points. Consider the mapping, T, from £ m - 33 ~ onto E, defined by t(a',a, see 9 a") = os at Bs (x, )> Ia] n 5 a BAX), vee L ae g,(x,)). Since det(g,{x,)) 40,7 a1 wel ‘ : mand 2 a thy is a one-to-one continuous mapping. Any neighborhood of Ta p85e 2098, ) contains points which are not the image under T of points of P. Therefore F cannot be locally solvent near F(a, r¥)e ii) Let p= int max|F(a,x) - £(x)] then it can be shown, [1] acP | Me page 10, that there is an M<-« such that ja"| >M implies =] pede. max|F(a,x) - £(x)| > @+1. f(x) hes a best approximation if there is en a*e« P such that max|F(a*,x) ~ f(x){ = inf max|F(a,x)-f(x)|. a ace Let By = falecr, > lan] <1} . Clearly a mey be restricted to i= values from P,,. If P is closed then inf max|F(a,x) - £(x)| * ach, is attained and f(x) possesses a best approximation Assume P is not closed and that P #¢ E+ Let a, be a boundary point of P ot contained in P. A function f(x) is defined so that vax! a5 5 (x) ~ f(x)| alternates n times. Then clearly ing nox |F (2,3) ~ f(x), < aux! og & 5 a; (x) ~ £(x)|. Te f(x) ae possesses a best approximation, = at 8.(x), then aa (a5- *) g(x) ie] i=] hae at least n zeros which contradicts Geil Z, (x, }) #0 This completes the sketch. ms THEOREM 6G: Let Fla,x) = a~ @, (x) where B(x) is con- i tinuous on [0,1], Theorems A and B are both valid for F if end only if (a,(x012 = 1, 2, 200 5 a} ie a Tehebycheff set wo 3h m PROOF: It is a classical result that Theorems A and B are valid if { 9,(=)} ig a Tehebyeheff set. and P = Ey Tt will be shown that i) if det(d, (x >) =O for some set {x 3} of distinct pointe end P=, then Theorem B is not valid ii) it det (g(x) ae O, P¢ gE, and Theorems A and B are valid then P is the empty set, It follows directly from Theorem 5 that if det (9, (x,)) 40 forall {x 33 then the validity of Theorems A and B imply P = iL. i) Since P=E, and det (d(x .)) = 0 there is a non-trivial T-polynomial with n zeros. This contradicts Property Z and hence Theorem B. ii) The same proof as in Theorem 5 applies to show that P ig both open and closed. Hence P is the Gapiy set. This concludes CHAPTER ITI 1. Often when one ia using common non-linear approximating functions it develops that Property NS is lacking. Yet the character- ization of best approximations is nevertheless very closely related to Property NS. ‘Three exemples are given below which illustrate this situetion. The aim of this chapter is to generalize unigsolvence and related concepts and to develop a theory for these situations. 2. The following examples illustrate different forms of F which do not have Property NS but for which a simple theorem cheracteriging best approximations can be given. on [0,1]. Since the numerator and denominator may be multiplied by MMH 4. 4 a common factor it is assumed that 5 (e")" = 1. P is, then, k= taken to be the subset of the unit sphere of aay m2 for which DH 4 4 . ak e-O \ £0 for x ¢ [0,1]. kan fhe classical theorem characterizing best approximations is ({1], Chapter 2); ~ % - "B(a,x) = s(x) (a xO 4g eee a UDRP xP 4 oe + dD) where Oa Sn, osP sn, weP #9, at Zo, pw? #0 is the best approximation to f(x) if end only if meax|F(a,x)-f(x)] alternates at least mim+2-d times waere d = min(a,@); if F(e,x) 20 then 6 = a" % points of P where both the numerator and denominator are of Lower degree there is an effective loss of parameters, This can be due either to the cancellatimof common factors or to the coefficients of the leading terms being zero. It can be shown that F is not locally solvent near such points end therefore max|F(a,x) - f(x)| cannot alternate nim-2 times for all f(x). EXAMPLE 2: Let F be of the form &,X Flajx) sa,e* + a, end let P be defined ty |a,| <=, |a,| <a, [23] <, When a, = 1 it is seen thet F depends only on a,+8, and F is not locally solvent near F = coustant. EXAMPLE 3: Let F be a polynomial and P be taken as a proper subset of £ n° For example, let F(a,x) tal 4 ame + ax” with jal} <o, la"| < 10, ja*] <|. From Theorem 6 a it follows that F does not have Property NS. F fails to be locally solvent on the boundaries of P,. 3. In each of these examples F fails to be locally solvent at some exceptional points of P. However it is seen that there is still some degree of local solvence at these points. This leads ome to the concept of degree of solvence given in the following éefinitions - 37 - DEPINITION 14; F is golvent of degree mst at ¢ P if given & set {x10 $x, <2. <<a, sit and ¢ >O then there isa §(a%, «, Hyp eee y x.) > O gsneh that ly, ~ F(a*,x.)|< 5 implies that there is a solution, a ¢ P, to F(a,x,) “Vy j= 1, 2, oo , m with max!/P(a,x) ~ Fla*,x)] <¢. Thus, the degree of solvence may vary from point to point in P. The definitions of Peoperties NS and Z may be generalized im an analogous mennes. DEFINITION 15: F has Property NS of degree mat a* ¢ Pir, for every f(x), the alternance m times of max|F(a*,x)-£(x)| is a necessary and sufficient condtion for Fla*,x) to be a best approximation to f(x). A point, a* < P, is said to be of degree m if F has Property NS of degream>O at at, DEFINITION 16: F has Property Z of degree mat ate P if for exy a # a*, Fla*,x) - Fla,x) has at most m-1 zeros, DEPINITION 17: F is unisolvent of degree mat a*¥¢ P if i) F hes Property Z of degree mat a* and F is solvent of degree m at a%; i1) F is not solvent of degree m1 the analog of the classical statement characterizing best approximations is; Let a be of degree m, then P(a%*,x) is a best approximation to f(x) if and only if mex|P(e*,x) - t(x)| alternates m times. ~ 38 - kh, The aim of this section is to relate the degree of a point in P and the degree of unisolvence of F at that point. LEMMA 16: If P is comected and if the degree is defined for every point of P then given a* « P there is an ¢ >0 such that (x, Fla®*,z) 4¢) ¢R for all x ¢ [6,1]. LEMMA 1 od 66 t¢ FP is connected and if PF is solvent of positive degree at every point of P then R= Rye These two lemuac may be proved by a slight modification of the proofs of Lemmas 2 and 9. LEMMA 18: Let PF be closed and let F be wnisolvent of positive ‘degree at every point of P. If F is unisolvent of degree m eat e* then the degree of a®* is m. This lemma may be proved by a Slight modification of the proofs of Lemmas 2 and 14. The converse of Lemma 15 is more difficult. A series of lemmas will be established which culminate in Lemna 22 which is the converse of Lemma 18. The following lemma is a generalization of Lemma 3. LEMMA 19; Let the degree be defined for every point of P. If a* is of degree mthen F has Property Z of degree m at a*, PROOF: Assume there is an ae P such thet F(e,x) ~ F(a*,x) has mor more gerogs. Then as in the proof of Lemma 3 there is couwtinuous function, f 62) , such that max|F(a®,x) - f 6%) | alternates exactly m times, max|F(a,x) -f (2) alternates exactly m-2 times and max |E(a%,x) of 6) = maxlP(a,x) - £,(x)|. Let £,(x) be the cortinuous funetion analogously defined so that max|F(a* »x)~£(x) | alternates exactly m-2 times, max|F(a,x) - f(x) | alternates exactly m times and max|F(a*,x) - Z{x)| = max |Fla,x) ~ one Since ea® is of degree m, Fla*,x) is a best approximation to £ ,b) and hence Fla,x) is also a best approximation to f ,(x)- Therefore the degree of a is lesa than or equal to m2. Hence Fla,x) is a best approximation to f(x) and so is Fla*,x). But since max|P(a*,x) ~ £(x)] alternates exactly m-2 times e* cannot be of degree m. 7 | fhe following lemma is the generalivetion of Lemma 11 and hes the same proof as Lowma 11. LEMMA 20: Let F be closed and let the degree be defined for every point of FP. Then given a* ¢ P, ¢ > O and a set {x,l0 eX, G8, Sey Seer <x, = i} there are a,, a, ¢ P such thet i) Fla*,x) - Fla, ,*), Fla%,x) - F(a, ,x) change sign at the x, and at no cther points, 414) lr(a, »x) ~ Fla*,x)| <6, lr(a, 2) - Fla®,x)| 4 ¢, iid) either Fla, .*) ~ Fla ,x)=0 F{a,,x) - Fla¥,x) = 0 or sgn{F(a,,x) ~ Fla*,x)] = ~ sgalF(a,,x) - Fla*,x)]. ~ LO The next Lemma shows an interesting property of some special a Ey gubsete of P and provides a means of generaliging Lemmas je and 13. LEMMA 21: Let F be closed and let the degree be defined for every point of P. Define P = {ela e P, degree of a > x} Then P, dis an open set. k of these zeros and set xu, = 0, x, 21. Let § = min mer 3 xelx pe ] iP(a®,x) - Fla,,x)|, t=, 1, 2, «2+ » ki. It is clear that for ei if maxiP(a 2) - Flat,x)[ < § ‘then Fla,x) - F(a, ,x) 8 a 05 oF a i bag at Teagh K-1 zeros. Since PF is camiimucue there is a neighborhood of a*, Nfa*), euch thet if a ¢ N(a*) then max|F{o,x) - Fla#,x)] < & and Fla,x) - F(a, »x) has at least k-1 zeros, By Lemma 19 the degree of a is lavger than or equel to Kk. LEMMA 22: Let F be closed and let the degree be defined for every point of P. If a is of depree mthen F is unisolvent of degree mat a*, PROOF: Let 6 be the quantity defined in the proof of Lemma 21 and get A = {yz ¢ [G,1], |F(a*,x) - y] < 5}. From the proof of Lemma 21 it is seen that every F(e,x) entirely in a is of degree mor more. Lemae G2 is now proved by restricting conaider~ ation to functions entirely in A and by using the proofs of Lemmas 12 aml 13. a. oe The statement of the generalization of Lemma 12 is; "Let F be closed and let the degree be defined for every point in P. Let e* ¢ P be given with degree mand let Fle*,x) - Fla,x) change sign at m1 points with F(a,x,) # F(a*,x,) and let max|P(a*,x) ~ F(a,x)| <§. Then given y between Fla,x,) and F(e*,x,) there is an a, ¢ P such that F(a, ,x,) =y and F(a, x) is between Fla,x) end Fla%,x)." The only part of the statement that ie not a streightforward generalizetion of Lemma 12 is the condition thet max|F(a*,x) - Fla,x)| < 5. this condition implies that a is of degree mor more ami the proof of Lemma 12 may be used to prove this generalization of Lemma 12. The generalization of Lemma 13 may be proved with a Slight modification of the proof of Lemma 13. In the Induction argument of the proof it is merely necessary to take ¢« < 5 and the seme proof is valid for the generaligetion. In view of Lemma 19, thie concludes the proof of Lemma ce, The preceding lemmas have established THEOREM 7: If F is closed then the following statements are equivalent: i) F is uniscolvent at every point of P and is unisolvent of degree mat a, | ii) The degree is defined for every point of FP and the degree of a* is m. ~ EP « 5, Theorem 7 directly relates the characterization of best approximations to the degree of unisolvence of F. Since unisolvence is directly connected with the explicit definition of F this gives o natural means of studying the characterigation of best approximations. It is interesting to examine the variation of the degree for the three examples previously considered. a n nk n4m nem-k MPLE 4: Let PL. = {alecr, Go = t+ @ sQ ss soe = of N= 7 fe] oy mm and pisfalacP,a =a m fee om g =o}. If ec PB, f a ¢ P,., then the degree of a is nemk and if ae P' the degree of a is nri. If a is in none of these sets then the degree of a is nem. EXAMPLE 2: Every poimt of P is of degree 3 except those for which a = e these points are of degree 2. Note that F is not closed in this example for as a, “> .o the Limiting function is discontinuous. However, it can be shown that the theory developed here is still valid. EXAMPLE 3: The interior points of P are of degree 3. The interior points of the two Gimensionel faces are of degree 2 and the points on the one dimensional edges are of degree 1. In this example if P were defined by |al| <, |a”| < 10, le?! <1 then F would have Property NS with n= 3. However best approximations would not exist for every conmtinucus function as they do with the present definition of P. (1] {2} (4) (5] 7] [8] N. I. Achleser. &. Bernstein. Approximation des For Réelle. Paris (1926). Part 3-2. Leipgig (1927). Pg M. Frechet. Sur l'Aporoximation des Fonetions Continues Périod- . 7 iques par les Sommes TrigonomStriques Limitees, Ann. Sei. Ec@le Norm. Sup. Ser. 3, Vol. 25 (1908), pp. 43-56. A. Hear. Die Minkowskische Geometrie uid die Anngherung an stetige Functionnen, Math. Amn. Vol. 78 (1918), pp. 2311. P. Kirehberger. Thesis. Gottingen (1902). T. S. Motgkin. Approximation by Curves of a Unisolvent Family, Bull. Amer. Math. Soc. Vol. 55 (1949), pp. 789-793. tq. Sh. Pinsker and E. N. Novodworskii. On a Process of Equeligetion of Mexima (Russian), Uspehi Mat. Nauk. Vol. 6 (1951) pp, 174-181. ~ bb - {9] Ch. de la Valiée Poussin. Sur les Polynomes d' Approximation [10] [11] [12] et la Représemtation Approché d'un Angle, Acad. Roy. Belg. Bull. Gl. Sei. vel. 12 (1910), pp. 808-844, Sur les Polynomes d'Approximation 3 une Varisble Complexe, Acad. Roy. Belg. Bull. Cl. Sei. Ser. 5, Vol. 1 (1911), pp. 199-211. Sur la uéthode de L' Approximation Minimum, Amn. Soc. Sei. Bruxelles Ser. 1, Volk. 35 (1911) Legons sur l'Approximation des Fonctions d'une Verieble Réelle. Paris (1919). {13] Ya. L. Remez, On a Method of Tchebycheff Type Approximation of Functione (Russian), Ukr. An. (1935). [14] L. Tonelli. I Polinomi d'Approssimazione di Tchebychev, Ann. Mat. Pura Appl. Ser. 3, Vol. 15 (1903), pp. 47-119. [15] A. Vassilief. _P. LL. Tehebychef et son Oeuvre Scientifique. Turin (1898). [36] J. W. Young. General Theory of Approximation by Functions, Trans. Amer. Meth. Soc. Vol. 8 (1907), pp. 331-344.