APPROXIMATIONS 0F FUNCTIONS OF SEVERAL VARMBLES: PRODUCT TCHESYCHEFF APPROXiMATIGNS Thes§s for the Degree of Ph. D. MlCHiGAN STAN-Z UNNERSITY STANLEY EDWIN WHNSTEI‘N 1.967 LIBRARY ' "'3' Michigan 5 rate University THC-35‘s This is to certify that the thesis entitled APPROXIMATI ONS OF FUNCTIONS OF SEVERAL VARIABLES: PRODUCT TCHEBYCHEFF APPROXIMATIONS presented by Stanley Edwin Weinstein has been accepted towards fulfillment of the requirements for __Bh_._D_._degree mMAfihemfiics Come med Major professor Date 8/ 1/ 67 0-169. u U A\U ABSTRACT APPROXIMATIONS OF FUNCTIONS OF SEVERAL VARIABLES: PRODUCT TCHEBYCHEFF APPROXIMATIONS by Stanley Edwin Weinstein In this thesis we define a Tchebycheff—like approx- mation to a continuous function F of two or more variables, which we call the Product Tchebycheff approximation, and which possesses the desired property of uniqueness. Let D be a compact set in E2 and let F be continuous on D. Let Dx and Dy denote the projections of D onto the ) -_- x-axis and onto the y-axis respectively and let Dx(yl [xer(x,yl)eD]. Let i i l’ in be a Tchebycheff 2)...) system of continuous real-valued functions on Dx' For each yeDy we define the continuous function F by 1 F (X) = F(x,y1) 5'1 Then F possesses a unique best uniform approximation in 1 i1, @2,..., in, namely n P = Z3 a,(y ) Q. We define a restriction on the set D, which we call Q» 5!. ha H‘Q I. .e A in Nv ‘ adv I s 2‘ Stanley Edwin Weinstein property K. This class of sets includes all compact con- vex sets as well as all sets which are cross products of compact sets. If D possesses property K then the deviation function p defined on Dy by p(y) = Keg:?y) l Fy(x) - PA(y)(X)| is continuous. Moreover if we further restrict the point y1€Dy such that the set Dx(yl) contains n or more points then the coeficients al(y),a2(y),...., an(y) are all con- tinuous at yl. We define the Product Tchebycheff approximation on sets which possess property K and such that for each ysDy DX(y) contains n or more pelnts. Let $1, $2,..., Wm be a Tchebycheff system on Dy' Then each Function aj possesses a unique best uniform approximation m . = Z) .. . , ' = 1 2,..., . Q3 i=1 alel J , n The polynomial :3 n _ m PT = Z) Qné. = Z3 L1 a..¢ e, 3:1 J J jzl i=1 13 1 J / is called the Product Tchebycheff approximation to F on D, relative to the variable y. Two algorithms for the computation of this approximation are presented along with several examples. It is also shown that by a suitable choice of base Stanley Edwin Weinstein functions, the resulting Product Tchebycheff approximation will approximate F arbitrarily close. The Product Tchebycheff approximation is extended to continuous functions of three or more variables. APPROXIMATIONS OF FUNCTIONS OF SEVERAL VARIABLES: PRODUCT TCHEBYCHEFF APPROXIMATIONS By Stanley Edwin Weinstein A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1967 \n‘ / / SQ \_\ S\ ‘ be cg ACKNOWLEDGMENTS I wish to eXpress my sincere gratitude to Dr. David G. Moursund for his patience and guidance in the preparation of this thesis. The numerous discussions we had during the research was of an immeasurable value to me. I would also like to thank Dr. G. D. Taylor and Dr. C. S. Duris, both of whom have contributed several helpful suggestions. I acknowledge the support of Michigan State University who made available to me the computing facilities used in the calculation of the examples in this thesis. TABLE OF CONTENTS ACKNOWLEDGMENTS. . . . . . . . . . . . . . . . . . . Chapter I. INTRODUCTION: THE PROBLEM OF THE LACK OF 1. 2. II. THE P TO 10. BIBLIOGRAPHY . UNIQUENESS OF A BEST APPROXIMATION . . . The Best Approximation Problem . . . . . Tchebycheff Systems, Haar's Theorem. . . RODUCT TCHEBYCHEFF APPROXIMATION A CONTINUOUS FUNCTION. . . . . . . . . . Introduction . . . . . . . . . .‘. . . Property K . . . . . . . . . . . . Continuity of the Coefficients al(y),a2(y),...,an(y). . . . . . . . . The Product Tchebycheff Approximation. . The First Product Tchebycheff Algorithm. The Revised Product Tchebycheff Algorithm. The Degree of Product Tchebycheff Approximation. . . . . . . Approximation on a Domain which does not Possess Property K. . . . . . The Product Tchebycheff Approximation to a Continuous Function of Three or More Variables. . . . . . . . . . . Conclusion . . . . . . . . . . . . . . iii Page ii but-J 1A 16 26 45 60 68 78 83 87 92 93 CHAPTER I INTRODUCTION: THE PROBLEM OF THE LACK OF UNIQUENESS OF A BEST APPROXIMATION Section 1: The Best Approximation Problem The central theme of this thesis is the problem of finding a best approximation to an arbitrary element F in a normed linear space:7,| I. This can be formulated as follows: Definition 1.1.1: Let ;?,l I be a normed linear space, and let ¢1,¢2 ...,¢n be a set of n linearly independent _ , elements of 5'. Given an arbitrary element F23, the problem of finding an A* = (al*,a2*,...,an*)eEn, such that IIF - 31*Pill "has [A n IIF- >3 a¢|| 11 i=1 11 for all A = (al,a2,...,an)eEn, is called the best approximation (b.a.) problem. Both the point A*eEn, and the corresponding polynomial PA* = "MS * 3: ¢1 i l are referred to as best I I approximations to F. Definition 1.1.2: If ¢l,¢2,...,¢n are n linearly in- dependent.e1ements of the linear space 57, then the set of all linear combinations n PA = : ai¢i ; A = (al,a2,...,an)eEn is a linear subspace of :7, of dimension n, called the space spanned by ¢1,¢2,...,¢n, or the span of ¢1’¢2""’¢n’ which is denoted by < ¢l,¢2’...,¢n > c We now restate the b.a. problem with the use of definition 1.1.2. B. A. Problem (Restated) 1.1.3: Find the point(s) of the~ subspace < ¢l,¢2,...,¢n > which are closest to Fe:7, where the distance between any two elements F F2e37 is defined 1, by d(Fl,F2) = ||Fl - F2|| In this thesis, we are primarily concerned with the following case of the b. a. problem: Let D be a compact set in euclidean k—dimensional space Ek’ and let-71 = C(D), the linear space of all con- tinuous, real-valued functions on D, with I I defined on C(D) by IIFII = sup IF(x)I for each FeC(D). XED This norm is called the uniform, Tchebycheff or minimax norm. A corresponding solution to the b.a. problem is called a best uniform, best Tchebycheff or best minimax approximation to FeC(D) on D. The existence of a solution to this b.a. problem is a direct implication of the existence of a solution to 1.1u3; see Davis (5). We now consider the question of the uniqueness of the solution to this b.a. problem. Section 2: Tchebycheff Systems, Haar's Theorem Definition 1.2.1: The family of real-valued functions ¢l,¢2,...,¢n, is called a Tchebycheff system on D if and only if for A = (al,a2,...,an)eEn the polynomial PA = IIMD ai¢i i l vanishes in at most n-l distinct points of D unless Definition 1.2.1 is equivalent to saying that ¢1’¢2"'°’¢n is a Tchebycheff system on D, if and only if the determinant ¢l(xl) ¢2(Xl) oo. ¢n(xl) ¢l(x2) ¢2 ... ¢n4 ¢2(x) - Then, as in example 1.2.6, ¢1’¢2 is not a Tchebycheff system on D. However the function FeC(D) defined by F(x) = 1 + x2 has a unique best uniform approximation in ¢1’¢2’ namely PA“ which is defined by PA*(x) = l + x2' We now state two corollaries to Haar's theorem. Corollary 1.2.9: Let D = [a,b], a < b and let ¢l(x) = l ¢2(x) = x ¢n(x) = xn'l Then as in example 1.2.“, ¢l’¢2’°°"¢n is a Tchebycheff system onwD and-thus by Haar's theorem, for each FeC(D) there exists a unique algebraic polynomial P*=a* A 1%"81 s a 2 ¢2 + C O O + a ¢ which minimizes the quantity max IF(x) - PA(x)I . Xe[0,1] Corollagy 1.2.10: Let D = the x-axis modulo 2r and-let ¢l(x) " l ¢2(x) = cos x ¢3(x) = sin x ¢2n(x) = cos nx ¢2n+l(x) = sin nx Then, if F is an arbitrary continuous function with period 2n, (that is, F(x + 2n) = F(x), for all real x), there exists a unique trigonometric polynomial P*=a* A l¢l+a + 0.. +a* * 2 ¢2 2n+1¢2n+1 which minimizes the quantity max IF(x) - PA(X)I xeD The following example (see Buck 02) ) presents a function which possesses a non-unique, best uniform approxi- mation. Example 1.2.11: Consider the Banach space of continuous, real—valued function on the compact set D . [0,1] x [0,1]: E2, with | I, the uniform norm. 10 ¢2(X,Y) = X ¢3(X.y) = y ¢u(X,Y) "' X2 ¢5(x,y) = Y2 ’ and let F be defined by F(X.y) = xy. Using results from functional analysis, Buck first shows that min llF—PAII 1%— AeE5 where as usual for each A = (al,a2,a3,au,a5)eE5 PA = al¢l + a2¢2 + a3¢3 + au¢u + a5¢5 He then observes that l 2 2 l l IIXY - I§(x + y ) ' EIII = y and ley - (X + y - §~0, there exists a 6 = 6(6) > 0, such that y1,y22D , and- y Iyl - y2I < 6 implies that if (xl,yl)eD (xler(yl)) thenthere exists an XZer where Ix2 - xlI < e and (x2,y2)eD (xzer(y2)). Remark 2.2.2: The following definition is equivalent to (2.2.2) A compact set D is said to possess property K relative to the variable y if given 6 >0, there exists a 5 - 6(a) > 0, such that yl,y2eDy, and ly1 ; y2I < 5 implies that if (xl,yl)eD (xler(yl)) then there exists an xZer where o[(xl,y1);(x2,y2)] < sand (x2,y2)eD 17 Note that here and throughout the remainder of this thesis the letter "a" will be used to denote the usual Euclidean metric on the space under consideration at that~ time. on, will denote the usual Euclidean metric on Euclidean n space En’ for any positive integer n. Proof: If_as in Definition 2.2.2 0[(xlsyl)3(x23y2)3 < 5 then Ix2 - xll 1 o[(xl,yl);(x2,y2)] < e which satisifies 2.2.1. On the other hand if yl,y2eDy with Iy1 - y2I < 61(2/2) as in Definition 2.2.1, we can choose 6 = mln(dl(e/2),s/2) Hence yl,y2eDy and Iyl - y2I <‘6 implies that there exists an xzer(y2) where °[(xlsyl)3(x23y2)] : IX2 - xll + Iy2.' le Ram MW) 'u m which satisfies 2.2.2. We may-similarly define property K relative to the variable x. We shall see in Example 2.2.5 that property K relative to x and property K relative to y-are not equivalent. 18 Example 2.2.3: Any rectangle D a'{(x,y): a i x.:‘b, c :.y: d} has property K relative to the variable y as well as property K relative to the variable x. Example 2.2.4: Let D = the intersection of the hori- zontal band H .{(x,y): a i y i.b} a,b with a family of a finite number of non-horizontal lines. Figure 2.2.1 Then D has property K relative to the variable y. Note that as a special case of this any single line segment (we need not exclude a horizontal line seg- ment) has property K relative to both x and y. 19 Example 2.2.5: Let D = {(x,y): x +-y = 1 and 0 :_x i l or x = 0 and 0 :_y i 1}. D -1 Figure 2.2.2 Then given a > 0, if (xl,yl)eD then (1) (xl,yl) = (0,yl) for some 0 :_y1 i 1 or (2) (x,yl) = (1 - yl,yl) for some 0 :.yl i 1 In case (1) Let 6 = 6(6) = 1 then for any y2eDy = [0,1],Iy2 - le < 6 = l and (0,y2)eD implies I0 - OI -.O which satisfies 2.2.1. In case (2) let 6 = 6(6) = a then for yZeDy = [0,1] if Iy2 - le < 6 = c then for x2 = l - y2m IX2 - xlI a I1 - y2 ’ (l ‘ yl)| = lyl ' y2I < 8 and definition 2.2.1 is satisfied. Thus if we choose 6 = min(l,e), Definition 2.2.1 is satisfied relative to the variable y. 20 However, if we choose 5 = and (xl,yl) = (0,0), mnenma then xzer ande2 - xlI - x2 < implies that if x2 # 0, then-there is one and only one.corresponding y2, such that (x2,y2)eD, namely y2 = 1 - x2, and therefore, . l IY2,' yll = y2 = 1 - x2 > 5. Hence, D does not possess property K, relative to the variable x. Theorem 2.2.6: Let K1 and K2 be compact sets in E Then, 1. ,D - K1 x K2 (LE2 has property K relative to both x and y. Proof: Clearly D1 which is the cross-product of two com- pact sets, is itself compact in E2. Now given e > 0 and an arbitrary point (xl,y1)eD, then xleKl and yleKz. For any yzeDy = K2 we have the point (xl,y2)eD. Thuslxl - xll = 0 < e and 5 may be chosen arbitrarily large. A similar argument shows that D has property K with respect to the variable x. The rectangle of Example 2.2.3 is a special case of Theorem 2.2.6, where K1 - [a,b] and K2 a [c,d]. Theorem 2.2.7: Any compact convex set DCZE2 has property K relative to both x and y. £3322: We first show that property K relative to y holds at a given point in D. Since-Dy is the projection of the compact convex set D, it.is a closed bounded interval, say Dy ' [ymin’ymaxJ' 21 Now let a > 0 be given and let (xl,yl) be an arbi- trary point of D. If yl #-y min then by the convexity of D the point- (x2,y2) = (axl + (1—e)i, oyl +_(1-a)y ) min also belongs to D for each fixed ae[0,l], (where f is )). Now, we can choose some point ian(ymin m I\)|m OI‘ Then since Iy2 - yll = (l-Q)Iyl ‘ yminl and (1-a)le - xI >4 [\J I >4 l-' II we have (1) for y2e[ymin.yl] E ly2 ' yll < 62 “‘IX2 ‘ Xll < 2 ' 22 On the other hand, if y1 - ymin then the interval [ymin,yl]reduces to the point yl and then (1) holds tri- vially for any choice of 62 > 0. Now, we.can similarly find a 63 = 63(e/2) such that (2) For y2e[y1,ymax1 E Iy2 ‘ le < 63 IX2 - xll < 5 ° We can choose 61 = min(62,63). Then (3) For y2eDy = [ymin.ymaxl — a ly2 ' yll < 61 " Ix2 ‘ xll < 2 Hence property K holds relative to the variable y at the point (xl,yl). We will now extend this to 31’ an open neighborhood of (xl,yl). ' 6 ,1 Let S1 = {(x,Y):|x-xl)|< % and Iy-yl|< -§—} and let (fsy)fislnD0 Then ” If - xlI < 3 _ 51. and ly - yll < 77 5 For y2€Dy and yeSIIIDy where Iy2 — §| < i; we have 6 6 l |<| ‘|+I‘ I—-l-'+—I- a y2 ' yl _ Y2 ' y a y - yl < 2 2 1 Thus by property K at (xl,yl) there exists a point (x2,y2)eD whereiIx2 — xil < E . 23 Hence Ix2 - fl 1 Ix2 - xll + le - xI < 6/2 + 5/2.= e We have shown that for arbitrary f,§)eslle, and arbitrary ' 1 ( 6 e > 0 there exists a 6 = 6(8) = 77‘ such that for y2eDy where Iy2 - yl < 5 there exists a point (x2,y2)eD where Thus property K relative to the variable y holds in all of 81. This argument can be repeated for any point (xu,yu)eD and its corresponding open neighborhood Su' By the com- pactness of D a finite number of such neighborhoods S S2”"’Sn is sufficient to cover D. 1, We choose 6 6 6 1 2 k 5 = mint’2’2"“’"2_] (where 61 corresponds to (xi,yi)eD and its associated neigh- borhood S for i = 1,2,...,k) and Definition 2.2.1 is i satisfied. Hence, D has property K, relative to the variable y. By a similar argument we can show that D also possesses property K, relative to the variable x. Note that convexity is not a necessary condition for a set to possess property K as is evidenced by examples 2.2.A and 2.2.5 and Theorem 2.2.6. 2“ Theorem 2.2.8: Let D be a compact set in E2, which possesses property K, relative to the variable y. Let yl be a fixed point of Dy’ and let xll,xl2,...,x be n distinct points 1n of Dx(yl)’ where n is an arbitrary positive integer. Then, there exists a 6 = 6(yl) > 0, such that y2eDy and Iy2 - yll < 6 implies that there are n disjoint closed intervals S S 1’ 2,...,Sn such that (1) xlieSi i = 1,2,...,n and (2) There is a point X21€Dx(y2) where X21581, i = 1,2,...,n. Proof: Let a = min lei - xljl > 0. i > j i = 2,...,n J: 1,2,...,n-l Note that 6 depends on yl. Then by property K, there exists a 6 = 6(e/3) > 0, (depending on yl) such that if xlier(y1) then yzeDy and Iy2 “le < 5 implies there exists an x2ier(y2) satisfying |x2i - xlil < e/3, 1 = 1,2,...,n. Hence S1 = {Xerzlx - x i e/3} satisfies the de- 11' sired conditions (1) and (2). 25 Corollary 2.2.9: Let D be a compact set in E2, which possesses property K, relative to the variable y. Let yl be a fixed point of Dy such that Dx(yl) contains :_n points for some arbitrary positive integer n. Then, there exists a 5 = 5(y ) > 0 such that y 5D and 1 2 y Iy2"le < 5 implies that-Dx(y2) contains :_n points." The following example, illustrates a compact con-. nected set which does not possess property K relative to either x or y. This example will be frequently referred to in later sections. Example 2.2.10: Let D = {(x,y):x = 0 and 0 :_y 1’1 or y = 1 and 0 i x i 1}. (1 A Figure 2.2.3 ,26 Then, by a similar argument to that found in the later part of Example 2.2.5 we can show that D does not possess property K relative to x or y. An alternative proof is to use Corollary 2.2.9. If we choose y1 = leDy = [0,1] then Dx(yl) has 1 2 points. However, for all y2e[0,l), Dx(y2) has only 1 point. Therefore, D does not possess property K relative to the variable y. A similar argument shows that D does not possess property K relative to the variable x. Section 3: Continuity of the Coefficients al(y),a2(y),...,an(y)v In the remainder of this chapter, for each yleD let F and yl I '31 spectively, and for each A = (al,a2,...,an)eEn let y, be as defined in 2.1.1 and 2.1.2 re- P = A a1¢l + a 2¢2 + as. + an¢no Definition 2.3.1: For each yleDy let = 1 f F - P p(yl) AZE ll yl Allyl n We know that if FeC(D), then Fy eC(Dx(y1)). Also if 1 ¢l’¢2’°"’¢n is a system of n real-valued, continuous functions on Dx’ then they are likewise real-valued, continuous functions on Dx(y1)’ and therefore we know that there is some polynomial P which is a best A l I ° Iy approximation to Fy . Consequently, we have the l l existence of a polynomial P such that ’ A1 27 = F - P Theorem 2.3.2: Let D be a compact set in E2, which possesses property K, relative to the variable y, and let ¢l’¢2’°"’¢n be a Tchebycheff system of real-valued, continuous functions on Dx' Let FeC(D). Then p(y) is a continuous function for D . YE y Proof: Let yl be a fixed point in Dy and let e> 0 be given. Then for all y2eDy II :IIF -P II y2 A2 y2 y2 A1 y2 ’ where P is a best I I approximation to F , i =_l,2. A1 yi yi (Note that because Dx(yi) may contain less than n points, PA might not be a unique best approximation.) 1 Now, let 51 = 51(e,yl) correspond to e in the definition of the uniform continuity of the function G defined on D, by G(x,y) Fy(x) - PA (x) E F(x,y) - PA (x). l 1 Also, by property K relative to the variable y for the set V D, given 51(e,yl) 0, there exists a 52 = 52(5l(e,yl)) > 0' such that for yzeDy Iy2 - le < 62 implies that for each x2er(y2), there is a corresponding xler(yl) Satisfying, 28 o2[(xl,yl);(x2,y2)] < 51(e) This in turn implies that IFy2(x2) - PAl(x2)I < lel(xl) - PA1(x1)I + e Combining these results we have, (1) given e >0, and y1 fixed in Dy there exists a 52‘= 52(5l(e,y1)) > 0 such thaty2eDy and ly2 - yll < 62 imply that for some x2er(y2) and a corresponding xler(yl) p(y2) - o = m2) < 5 Hence, Iy2 - le < 52 =2 Io(y2) — o(yl)I = Io(y2)| = 0(y2) < e , since p(y) is a non-negative function. Case 2: Dx(yl) contains 1 n+1 points Then by Theorem 2.2.8 and Corollary 2.2.9, there exists a 53 = 53(y1) > 0, such that y2eDy and Iy2 - le < 6 implies that (l) Dx(y2) contains 1 n+1 points and these points x2 l,x ...,x ‘each belongs to a corresponding 9 2,2’ 2,n+l closed internal 81’32""’Sn+1 where 81/333: 5, i f j. Now, by Haar's Theorem, Fy and F each has a unique 1 5'2 best uniform approximation on their respective domains. Denote these approximations by PA and PA respectively. As before we have 30 Then, since the zero polynomial is a possible approximation toFy , we have || :IIF y2 A2 y2 y2 y2 Therefore, P < F -P . F II A lly2_l| ,2 A2||y2 || ,leyz < 2 F _ ||y2||y2 1 2M Now, consider the set 61: {A2:PA is the best I - |y 2 2 approximation to Fy2 for some y2€Dy where Iy2 - yl| < 53}, We first assert that dis a bounded set. We begin by finding expressions for the coefficients a2l,a22,...,a2n, where A2 = (a2l,a22,...,a2n)ed. The function G defined on the compact set S = SlXS2X...XSn, by G(x1,x2,...,xn) = ¢1(xl) ¢2(xl) ... ¢n(xi) ¢1(x2) ¢2(x2) ... ¢n(x2) ¢l(xn) ¢2(xn) ... ¢n(xn) is continuous there and therefore assumes its minimum absolute value m at some point (fi,§',...,§h)es. Since ¢l""’¢n is a Tchebycheff system on Dx’ if m = 0 then for some i # J, E: = f3. However, £1881 and 31 ~ xJeSJ and SillsJ = t. Therefore, m > 0. Now, for yzeDy and ly2 - yll < 63 and the corresponding point A2251, we consider the determi- nants PA2(X21) ¢2(x2l) ¢n(x21) D1 = . . PA2(x2n) ¢2(x2n) ¢n(x2n) ¢1(x21) PA (x21) ¢3(x21) ¢n(x21) D2 = I 5 5 ¢1 0, there exists a 5“ 8.54(e) > 0 such that if (xl,yl,A2) and (x2,y2,A2)erazgthen "n+2[("1’yi""‘2)5("2’5’2’,”‘2)J < 5A implies that, IFyl(xl) - PA2(xl)I < IFy2(x2) - PA2(x2)I + e. Also by property K, relative to the variable y, for the set D, given 6A(€) > 0, there exists a 55 a 65(6A(E)) > 0 such that for y2eDy Iy2 ‘ le < 55 implies that for each x er(yl) there is a corresponding 1 xzer(y2) satisfying, 02[x1.y1);(x2.y2)] < au or equivalently, °n+2[(x1,y1’A2)3(x2’y2éA2IJ < GAIE) ’ which in turn implies that IFy (x1) - PA2(xl)I < IFy2(x2) - PA2(x2)I + e. 1 We_can choose 56 = min(53,55) > 0. Then combining these results we have, (2) given e'> 0 and y1 fixed in Dy such that Dx(yi) con- tains-1_n$1 points, there exists a 56 - 56(e,y1) > 0 such that for y2eDy 3A Iy2 - le < 56 implies that, for some x1 = xl(y2)er(yl) and a corre- sponding x2 = x2(y2)€Dx(y2), 0(y1) - p = llel - PAlllyl - HF,2 - PA2IIyl < IIFyl - PAZIIyl - Ile2 - PAZII,2 = IFyl(xl) - PA2(x1)I - IIFy2 - PA2IIy2 < IFy2(x2) - PA2(x2)| +e - ||Fy2 - PA2||y2 _ HF,2 - PA2I|y2 + . - HF,2 - PA2l|y2 Now we choose 5 = min(52,56) and we have for case 2, by (1) and (2) Iy2 - yll < 6 implies that Io(y2) - o(yl)l < e . We will use the continuity of p(y) to prove.the continuity of A(y) under suitable conditions. With this goal in mind we state the following theorem due to Remez (16) Theorem 2.3.3 (Remez): Let D be a compact set in El’ which contains 1 n+1 points. Let F€C(D) and let 51(x) a 1, x,...,¢n(x) E xn_l. Let I I be the uniform ¢2(x) * be the best I norm on-C(D), and let P I approximation A to F on D. Then, given a > 0, there exists a 5 = 6(6) > 0 such that 35 IIF-P _<_I|F-PA*II+ 0, there exists a 5 = 6(6) > 0, such that IIF-PAII ¢2 37 ¢l(x) PA(X1) ¢3(xl) ¢n(xl) D2"= I 5 ¢l(xn) PA2M By the continuity of IIPAII as a function of AeEn, given a = IIPA,II - 2M we can find a 5 = 5(e,A') such that AeEn and o(A;A') < 5 38 imply that IIPAII > IIPA.|| - . IIPAvII " (IIPAtII ‘2M) 2M. This implies that {AeEn:o(A;A') < 5}CT'. Therefore, T' is open and T is compact. For some M > M, we define the set A T = {AeEn:IIP 1 2M}. We can similarly show that T is All compact. Let 4* = {A*eEn:P * is a best I A I approximation to F on D}. For each A*261* ||PA*|| 1 IIFII + IIF - PA*|| 1 2||F|| = 2M. Therefore, EDT: 4* 7‘ o. The linear independence of ¢l’¢2""’¢n on D implies 2M ~ that llolll # o. If P = TTIITT 51, then IIPII = 2M. Therefore, T - T is a non-empty subset of T - 613. . Now, given e> 0, we define the set Te = {AeT:o(A;A*) 1 e, for all A*eéz*}, and note that 39 for a sufficiently small T6 is a non-empty compact subset T rI Figure 2.3.1 Since IIF - PAII is a continuous function of AeEn, it assumes its minimum 98 > p on the compact set Te. Choose 5 = min(oE - 9, 2M - M - 6). Then AeEn and IIF — P < p + 5 All imply (l) IIF - PAII < 05 and (2) IIF - P < 2h - M. Therefore AeITe by the definition of-pe. Also 2h — M > IIF - PAII 1 IIPAII - M implies that 2M > IIPAI This implies that let. A0 Hence AeT - TE, and therefore o(A;A*) < e, for some A*eél* . If yl is a fixed point of Dy such that Dx(yl) con- tains less than n points, then Fy does not possess a 1 Iyl approximation in 51,¢2,...,¢n. unique best I Therefore, A(y) is not well defined at yl. This problem is considered at the end of this section. We-presently restrict our attention to the case where Dx(yl) contains n or more points. In the remainder of this chapter the phrase "let D, F, and ¢l’¢2"°"¢n be as usual" will be used to mean that D is a compact set in E2, which possesses property K rela- tive to the variable y, FeC(D) and ¢l’¢2""’¢n is a Tchebycheff system on continuous real-valued functions on Dx' Lemma 2.3.5: Let D, F and ¢1’¢2"'°’¢n be as usual, and let y1 be a fixed point of Dy, such that Dx(yl) contains n or more points. Then given a > 0 there exists a 5 = 5(e,yl) > 0, such that y2eDy and Iy2 - yll < 6 imply that IIF - P II < 0(y ) + e. yl A(y2) yl l Al Proof: By Corollary 2.2.9 there exists a 51 = 51(y1) > 0, such that y2eDy and Iy2 ‘ le < 51 imply that Dx(y2) contains n or more points, and there- fore A(y) is well-defined at ya. As in Theorem 2.3.2 we can show that the set 61 -‘{A(y2)eEn:y2eDy and Iy2 - le < 51} is bounded. Then as before let 52 - 52(e/2) > 0 correspond to the definition of the uniform continuity of the function G, defined on DXZ by G(x,y,A) = Fy(x) - PA(x). Also, by property K, given 5 = 52(5/2) > 0 there 2 exists a 53 = 53(52) > 0 such that y2eDy and Iy2 ' le < 63 imply that for each_xler(y1) there is a corresponding xeer(y2) satisfying °2[(x2’y2)3(xl’yl)] < 52’ or equivalently °n+2[(x2’y2’A(y2))3(xl’yl’A(y2))] ‘ 62' Choose 5“ = min(51,53). Then we have shown that for each yZeDy Iy2 - le < 64 A2 implies that there exists an xler(yl) and a correspond- ing_xZer(y2) such that llel _ PAIV2IIIyl e IFyl(xl) - PA(y2)(x1)I 1 p(y2) + 8/2. Let 55 a 65(6/2) > 0 correspond to the definition of the uniform continuity of p(y) on Dy. Choose 5 = min(5u,55) > 0. Then ychy and Iy2 - le < 6 imply that ll < m ) + e/2, y1 A(yz) Pl 2 < 9(y1) + C. We can now prove that under a suitable hypotheses A(y) is continuous at yleDy. Theorem 2.3.6: Let D, F and o1,¢2,...,¢n be as usual and let y1 be a fixed point of D , such that Dx(yl) contains y n or more points. Then the function A(y) as defined in 2.1.3 is continuous at yl. A3 £3321: Dx(y1) is a compact set in El’ and FyleC(Dx(yl)). ¢1’¢2""’¢n a Tchebycheff system on Dx implies that it is a Tchebycheff system on Dx(y1) which in turn implies that it is a linearly independent system on Dx(y1). Therefore, by Theorem 2.3.4 given a > 0, there exists a 51 = 51(5) > 0 such that IIF -P II < p(y ) + 6 yl A yl 1 1 implies that OEASA(yl)] < 6 Now by Lemma 2.3.5 there exists a 5 = 5(5l(e),yl) > 0 such that yZeDy and Iy2 “le < 6 imply that IIF -P + 5 V1 A(y2)||yl < 9(yl) 1’ which in turn implies that 0[A(y2);A(yl)J < e Corollary 2.3.7: Under the hypothesis of Theorem 2.3.6, al(y),a2(y),...,an(y) as defined in 2.1.3, are all con- tinuous at yl. 44 We have previously mentioned that A(y) is not well- defined for yleDy, such that Dx(yl) contains less than n points. Example 2.3.8 below illustrates such a situation. Example 2.3.8: Let D = {(x,y):O : x i 1 and y 1 o and y‘g l - x}. — I Figure 2.3.2 Let F(x,y) = J? and let 51(x) = l, 52(x) = x. Then for o 1 y1 < 1, Dx(yl) = [0.1 - yll and /1-y l l ¢1 + P A(yl) = ————-—— /l - y 1 For y1 = l, Dx(yl) = {0} and P(O,a) = u¢2 is a best I I- approximation to F , for each real a. y1 y1 45 Hence A(y) = (al(y),a2(y)) = /1 -1y 1' ) 8 3 /l - y for 0 i y < l, and is not well-defined at y = 1. Moreover, there is no value we could assign to A(l) to make A(y) continuous at y = 1. Section 4: The Product Tchebycheff Approximation Corollary 2.3.7 motivates our seeking a polynomial approximation to each of the coefficient functions, al(y),a2(y),.--.an(y). Definition 2.4.1: We will say that D, F, ol,¢2,...,¢n, and wl,w2,...,wm satisfy condition P.T., if (1) D, F and ¢l’¢2""’¢n are as usual, (2) For each yleDy, the set Dx(y1) contains 1_n points and (3) wl,t2,...,wm is a Tchebycheff system of continuous real-valued functions on Dy which contains m or more points. These are the necessary conditions to define the Product Tchebycheff approximation. Definition 2.4.2: Let D, F, ol,...,¢n, and tl,...,w m satisfy condition P. T. Then by Haar's theorem for each k = 1,2,...,n, the continuous function ak(y) has a unique best uniform approximation on D . We will denote this y corresponding best approximation by 46 QA= A k i aikwi; k-= (alk,a2k’°"’amk)€Em° IIMB 1 The polynomial n PT = 2 Q ¢ A A i=1 J 3 is called the Product Tchebycheff (P. T.) approximation to F on D, relative to the variable y. We can similarly define the P. T. approximation to F on D, relative to the variable x. The following example shows that these two approximations (in cases where both are defined) need not be the same. Example 2.4.3: Let D = [-l,l]x[-1,1]. 2 Let F(x,y) = -2yx + y for -l 1 y i 0 ' 2yx for O < y i l and let ¢l(x) = l PICY) - 1. Then FeC(D). I For -1 i yl 1'0 max F (x) = -y min F (X) = y XEE-lal] yl l , XEE'lalj yl l =a PA(yl)(X) = 0. Therefore max P (x) = min P (x) = 0, ’ ye[—1,1] A(5’1) ye[-1,l] A(3’1) => PTA(x,y) = o. 47 Now, we define F and P analagously to F B PTB(x,y) = - I . Throughout the remainder of this chapter the P. T. or product Tchebycheff approximation will refer to the product Tchebycheff approximation, relative to the vari- able y. 48 In Chapter II, Section 9, the P. T. approximation is extended to functions of three or more variables. In Chapter II, Section 8, we define a similar approximation on sets which do not possess property K. We now consider a special case of product Tchebycheff approximation: Theorem 2.4.4: Let the compact set D(_’_E.2 have property K, relative to the variable y and let FeC(D). Let ¢1(x) - 1, wl(y) - 1. ' Then the product Tchebycheff approximation to F on D is defined by PTA(x,y) = I- max max F(xl,yi)+ min F(xl’yl) yleDy xler(y1) xler(y1) + min max F(xl,yl) + min F(Xley1)] yleDy xler(yl) xler(yl) ‘Proof: For each yleDy (1) PA(y1)(x) al(yl)¢l(x) = al(yl) 1 I 5 max F (x1) + min F (xl)] y y le‘Dx(yl) 1 x1er(yl) l 1 I = —’ max F(x y ) + min F(x y ) 2 1’ l 1’ l leer(yl) XIEDXUII) 49 Also (2) PTA(x,y) = I-max al(yl) + min Ial(yl)I ... yleDy yleDy We combine equations (1) and (2) to obtain the de-. sired result. If we just restrict D to be an arbitrary compact set in E and F to be an arbitrary bounded function on D, then 2 with 51(x) E ¢l(y) E 1 PTA(x,y) = I[sup sup F(xl,yl) + inf F(xl,yl) y xlEDx(yl) xleDX(y1) + inf sup F(xl,yl) + inf F(xl,yl) yleDy xler(yl) xler(yl) The following example illustrates some of the ideas presented up to this point: Example 2.4.5: Let D = [0,1]X[0,1] and let F(x,y) = x + y, ¢l = 1. elm = 1. For yleDy = [0,1] max F (X) l + y , min F (X) = y xe[0,l] yl 1‘ l Xe[0,1] yl =e PA(yl)(x) = a1(yl)¢l(x) = al(yl) 50 Therefore, max al(yO) = g- , min al(y) = %. ye[0,1] YEIOJ-I => PTA(X,Y) = 10 Note that in this example the Product Tchebycheff approximation to F is also the unique best uniform approxi- mation to F by a constant. We will see that in general the P. T. approximation is not a best uniform approximationt However, in Chapter II, Section 7, we investigate the Pt T. approximation using suitable sequences of base functions {oj}, {ti}. We shall show that by choosing n and m prOperly the P. T. approximation can be made arbitrarily close to a best uniform approximation. Now p(y = F - P ‘ ' ‘ 1) II y]. A(y1)IIyl = max I(X+y) - (-é-+ y)I Xe[0,1] _ l _ 2 , Hence, both p(y) and A(y) = (al(y)) are continuous on Dy, as was asserted in Theorems 2.3.2 and 2.3.6. We now consider an example in which the set D does not possess prOperty K, relative to the variable y and in which both pxy) and A(y) are discontinuous on Dy. 51 Example 2.4.6: Let D = {(x,y):x = 0 and 0 :}y i 1, or 0 :_x 1.1 and y = 1}. It was shown in Example 2.2.10 that D does not possess property K relative to either x or y. Now, let F(x,y) = x + y, 51(x) = l, wl(y) = 1. Then for 0 i yl < 1 Fyl(x) = 0 + y1 = y1 on Dx(yl) = {O} , and therefore, PA(yl)(x) = al(yl)¢l(x) For y1 - l, Dx(l) - [0,1] Fl(x) = x + l and therefore, PA(1)(x) = al(l)¢l(x) al(1) %[max (x + 1) + min (x ‘I' 1)] erO,l] Xe[0,1] =3. 2 Therefore a1(y) is discontinuous on Dy - [0,1]. 52 Now, for 0 :.yl < 1 My ) = IIF - P II 1 yl A(yl) yl = IIyl ‘leIyl = O. For y1 = 1 9(1) = IIFl’PA(l)IIl = .3. max I(x + l) - 2I xe[0,1] = 1 2 Therefore, 5(y) is discontinuous on D = [0,1]. y Theorem 2.4.7: Let D, F and tl,¢2,...,¢n,wl,w2,...,wm, satisfy condition P.T., and let PT be the Product A Tchebycheff approximation to F on D. Then for any real constant A, the polynomial APTA is the Product Tchebycheff approximation to the function AF on D. Proof: For each yeD let y n P = Z a A(y) 3,1 J(y)¢i be the best I - Iy approximation to Fy' Then the best I - Iy approximation to AFy is n APi ‘ JEIIaJIy)¢J . 53 Thus the coefficients of ¢l’¢2"'°’¢n in APA(y) are respectively lal(y),1a2(y),...,Aan(y). Let QA be the best uniform approximation to the continuous function aJ(y) on Dy, for j = 1,2,...,n. Then AQA is the best uniform approximation to Aaj(y) on Dy’ for j = 1,2,...,n. Hence the Product Tchebycheff approximation to AF is n AQ ¢ =AzQ «I AM J=1AJJ M3 J=l APTA. The following example illustrates that the Product Tchebycheff approximation and the unique best uniform approximation may be distinct from one another. Example 2.4.8: Let D = [-l,l]x[-I,l] and let F(x,y) 2 X y ¢l(x) = l,wl(y) = l . 1 Then, Dx = [-l,l] and Dy = [-§,l]. PA(y)(x) = a1(y)¢1(X) = al(y) = 1 max xzy + min x2y 2 x [-1,1] x E-l,ll _ 1 1 - 2E0 + y], for -2 1 y 1 0 IEy + 0], for o < y < l = g for yeDy = [-%,l] “Unwayxflaudiie . I.-. a “nigh '1‘ 54 Therefore, PTA(x,y) = QAl(y)¢l(x) = Q (y) A1 = 1_max % + min % 2 1 1 yeE'E’sl] y€["'2"sl] e + <-I—> = l 8‘ o The unique best uniform approximation to F on D is; [max x2y + min x2yI ng’y)ED (X,Y)€D_ NIH -1 I l\.)|l—’ 1 + (-I) h- - 1 n- . we also note that the best uniform approximation to x2 on Dx = [-l,l], by a constant is %, and the best uniform approximation to y on Dy = [-%,l], by a constant is I. The product of these two constants is I, which is the Product Tchebycheff approximation to x2y on D = Dxny by a constant. This result is generalized in the following theorem. Theorem 2.4.9: Let D,F and ¢1’¢2’°°"¢n’ wl,w2,...,wm satisfy condition P.T., and let 55 F(x,y) = H(x)G(y), on D = DXXDy. n a u _ Let PA* Jilaj ¢J and QB“ be the best uniform approxi mations respectively to H on Dx in ¢l,¢2,...,¢n and to G on Dy in wl,w2,...,wm. Then, the Product Tchebycheff approximation to F on D is PTA = PA*QB*. Proof: For each fixed yleDy, the best I y approximation 1 to F = G H is yl (yl) PA(yl) = G(yl)PA* n "can aJ*G(yl)¢J J l . For each J - 1,2,...,n, the best uniform approximation to the coefficient function aJ*G on Dy is * aJ QB*' Hence n PT - 2 a A 3-1 3 QB*¢3 fl |C_.I. “915 ...: m LI. 3 L30- L____J £3 [fl * 56 We now consider a special case for which there is a finite algorithm to find the Product Tchebycheff approxi- mation. Corollary 2.4.10: Let D = [-l,l]x[-l,l] and let F(x,y) = xnym ¢l(x) = l, ¢2(x) - xJ..., ¢n(x) . x11"1 w1(y) - l. w2(y) - yd..., wm(y) = ym‘l. Then, the Product Tchebycheff approximation to F on D is PTA(x,y)"(21-nTn(x) - xn)(21'me(y> - ym) where Tn and Tm are the well-known Tchebycheff polynomials defined by Tk(x) - cos(k cos-1 x), k - 1,2,... . Proof: The best uniform approximation to xn on Dx - [-l,l] is Zl'nTn(x) - xn, and the best uniform approximation to l-m m y Tm D for x = 1 1 3 3 y1 —-—-< O for x = 2 . ( 3 Therefore, 2 2 IIF - (l + —y )¢ II = max. IF (x) - (l + —y )xl yl 3 1 l yl xe[l,2] yl 3 1 =11 3 To decrease the norm of the error we must find a polynomial ax, which is negative at x l and positive at x= 2. However, a-l < O=> a < 0 é§a°2 < 0. q.e.d. (assertion) The best uniform approximation to the coefficient function 1 + gy, on D by a polynomial of the form a + by y 18.1 + gy itself. Therefore, PTA(x,y) = (l + éy)x. Now the best uniform approximation to x on Dx by a polynomial of the form ax is PA*(X) = x9 and the best uniform approximation to'y on Dy by a polynomial of the form a + by is ' QB*(y) = y. l /_ H 60 Therefore, PA*(X) + QB*(y) = x + y at (1 + g-yhc = PTA(x,y). Similarly if we let F and D be as above and let ¢l(X) l, ¢2(x) = x wl(y) y . then we can show that the Product Tchebycheff approxi- mation to F on D is PT as defined by A _ 2 PTA(x,y) - (l + §x)y # x + y Section 5: The First Product Tchebycheff Algorithm Most best uniform approximation problems require an infinite algorithm for their solutions. One of the more frequently used procedures is the Remez exchange algorithm, sometimes referred to as Remez' second algorithm. We precede the description of this procedure with a definition and theorem which form an integral part of the underlying theory. Definition 2.5.1: Let D be a compact set in E and let 1 FeC(D). Let ¢I,¢2,...,¢n be a Tchebycheff system of continuous functions on D, and let I I be the uniform norm on D. Then xleD is called a positive (negative) n extremal or an E + (E-) point for F - P = F - 2 81¢ A 1_11. l 61 if F(xl) - PA(xl) = IIF - PAII (F(xl) - PA(Xl) = -llF - PAII). Theorem 2.5.2: PA is the best uniform approximation to F. on D if and only if there are n+1 points p, then we choose A (k+l) (k+1) (k+1) x1 < x2 < ... < xn+1 in D 62 such that (1) each xJ(k+l), J = 1,2,...,n+l is a relative maxima or minima of F - PA(k) (2) for some xmax {xJ(k+l)} IF(XmaX) ‘ PA(k)(xmaX)| = IIF " PA(k)|| and (3) sgn[f(xJ(k+l)) - PA(k)(XJ(k+l))] (-l)J+lsgn[F(xl(k+l)) - PA(k)(xl(k+l))] 9 J = l,2,...,n+l Repeat step (2). The convergence of this procedure is outlined in Remez (l7), and proved in Novodvorskii and Pinsker (13). Verdinger (26) shows that if F is differentiable then the rate of convergence is quadratic. In practice some a > O is prescribed and the iterations are terminated when (k) < E e F - P - ll A(k)|| 0 Fraser and Hart ( 6) suggest that it is often ad- vantageous to choose the extrema of Tn’ (the Tchebycheff polynomial of degree n) for the set {xJ(°)}, when D = [-1,1], or equivalently let when D = [a,b] . The de la Vallee Poussin algorithm for finding the best uniform approximation is described in Rice (18) as follows: Let X = {xi:i=l,2,...} be.a dense subset of the compact set D, and let Xm = {xizi = l,2,...,m}13 léAJ ¢J is the Product Tchebycheff approxi- mation to F on D = {(x,y) eD: er} . Now given e>O, we see by Theorem 2.5.5 that we can choose Y in Dy such that the density of Y in Dy is sufficiently small ' to have max |é (y)-A (y) | < a / max |¢ (x)I yeDy A3 A3 xeDX J For J = 1,2,...,n. Hence, max 'PTA(X,Y) ’ PTA(X9y)I (X,Y)£D n = max 2 [£2 (y) -Q mm (x) (x,y)eD J=l A3 A3 J E 2: Therefore, if Y is chosen so that the density of Y in Dy is sufficiently small then PTA provides a good estimate for PTA. A program utilizing this algorithm was written for the Control Data Corporation 3600 digital computer, with the following restrictions: (1) Y = {yiz i = 0,1,...,100} (2) For each yieY, the corresponding set Dx(yi) was a closed bounded interval. (3) ¢1(X) W1(Y) 1, ¢2(X) I N x,..., ¢n(x) H ‘<', 1, ¢2(y) y,---, wm(y) The norm of F - PTA was estimated by N* where, 66 D = [a,b] , h = b-a X 1 Too D = [c,d] , h = d—c y 2 166 * A and N ‘= max IF(X,y) - PTA(X,Y)| x=a,a+hl,...,b y=c,c+h2,...,d In all cases single-precision arithmetic was used. Some of the results obtained are described below. I. F(x,y) = __l__ D = [0,1] x [0,1] x+y+l ’ ‘*- ‘ Y = {0.oo,o.01,o.02,...,1.00} b = [0,1] x Y n=3,m=3 PTA(x,y) = .03156u1979 x2y2 - .3075877279 x2y + .3102885292 x2 + .3689560988 xy2 + .2346341978 xy - .7160087106 x + .33u8278992 y2 - .8141539737 y + .9855581665 , N* = .09333756560. II. F(x,y) = ___l__ D = [0,1] x [0,1] x+y+10 Y = o.oo,o.01,o.02,...,1.oo fi = [0,1] x Y. (a) n = 2, m = 2 67 PTA(x,y) = .00909090909u xy - .01283994207 x - .009065006705 y + .09978401812 , N* = .00396501u850. (b) n = 3, m = 3 RTA(x,y) = .0025u690u012 x2y2 + .0023138653u1 x2y + .0005u96653156 x2 2 + .03203501519 xy - .02999156816 xy - .005997745788 x + .0008660139u67 y2 — .009951005503 y + .09999485663 , * N = .003938859616. III. It was noted in example 2.3.8 that if F(x,y) = /x ¢l(X) = 1, ¢2(X) = x and D= {(x,y): Day 51 and 03x31 - y}, Then PA(y) is not well-defined at y = 1. We will approximate F on D as follows: Let D = DllJ D2 where _ 1 - y} U I! IA >4 A 1 {(x,y): .99 s y s 1 and 0 U I IA - {(x,y): O s y 5 .99 and 0 x S 1 - y} 1.0 0 (see Figure 2.5.1). Q1 I Ch 68 We approximate F on D by the constant 1 1 max /E + min /§ 2 xe[O,.Ol] Xe[O,.Ol] l = 5 [.1 + 0] = .05 , and we approximate F on D2 by a product Tchebycheff approxi- mation as follows: Y = {0.00,0.0099,o.0198,o.o297,...,0.99} D = {(x,y): er, 0.5x £1 - y} n = 2, m = 2 PTA(x,y) = - 1.010101010 xy + u.539406039 x - .1136363637 y + .13650u7380 , * N = .1365047380 Section 6: The Revised Product Tchebycheff Algorithm The Remez exchange algorithm described in 2.5.3 seeks to find a set of n + l alternating extremals which charac- terize the unique best uniform approximation. If we desire to find the Product Tchebycheff approximate we must find PA(y)’ the unique best uniform approximation to Fy on Dx(y), for a number of distinct values of yeDy In this section we shall show that for yl,y2eDy, a set of characteristic extremals for F will often - P yl A(yl) be a good initial guess at a corresponding set for Fy - 2 PA(y2),‘whenever'%2:is sufficiently close to yl. We shall assume throughout the remainder of this section that D,F and o1, ¢2,..., ¢n,1pl, ¢2,...,wm satisfy condition P.T. 69 Definition 2.6.1: Let R be the continuous function defined on D by R(x,y) = Fy(x) - PA(y)(X) Then p(y) = max |R(x,y)| . Xer(y) Definition 2.6.2: For each yeDy we define E(y) = {xer(y): |R(x,y)| = o(y)} . the set of all extremals for F - P y A(y) E(y) is a non-empty compact subset of Dx(y). Definition 2.6.3: For each yeDy and each s > 0 we define E(y)E (whereo[x;Y] = inf 0[X;y]) er {Xerz o[X;E(y)] < 8} Theorem 2.6.4: Given 5 > 0 and yleDy, there exists a 6 = G(e,yl) > 0 such that y2eDy and ly2-yll < 6 imply that E(y2) CZE(yl) 6 Proof: Case 1: E(yl)E I) Dx(yl)° 2 Then for each xleDX(yl) o[x13E(yl)] > 5 By property K, there exists a 6 = 6(5/2) > 0, such that y2€Dy and ‘ -....Qy 3... ‘4. l..l....4s..\\i.b.,f III” I}... a Mod! ill-I'll". 1| 7O IY2 - yll < 5 imply that for each X2EDX(y2) there exists a corresponding xler(yl) satisfying < E: le - x2l 2 . This implies that o[x2;E(yl)] E |x2 - Xll + oEXl;E(yl)] < E + g = 5 Therefore, Dx(y2)C: E(yl)E Then since E(y2)<: Dx(y2) we have D and Y2 5 y |y2 - yll < 5 imply that E(y2) C E(yl)€ Case 2: E(yl)€‘i>Dx(yl) 2 or equivalently Dx(yl) - E(yl)E is a non—empty compact set. 2 Let M = M(e,yl) = '~max |R(x,yl)| < p(yl). XEDX(Yl)-E(yl)_€_ 2 Then by the uniform continuity of p(y) on Dy’ since p(yl)-M > 0 there exists a 61 = 61 (9(yl)-M)'> 0 such that '-—--- 2 2 D and y26 y |Y2 _ yll < 61 71 imply that ”(yl) > 0(y1) -(p(yl)-M) = p(yl)+Ivl 2 2 Now by the uniform continuity of R on the compact set D, there exists a 62 = 62 (E£X%llg) > 0 such that (Xleyl):(X2:y2) 6D and °[(xl:yl)3 (X2ay2)]< 52 imply that -M |R| < |R| + p(Y1) Also, if x2er(y2) - E(yl)€ > then ol[x2,E(yl)] — 6. Then XleDX(yl) and ogt; (x2,y2>1 < 3 imply that le ' X2l < 2 Therefore, o[x1;E(yl)] Z o[x2;E(yl)J - Ixl - X2| > e — nflm V E 2 which implies that xler(yl) - E(yl)E 2 C Now if we choose 53 = min (62,3) > 0 then by property K, there exists a 54 = 6u(63) > 0, such that yzeDy and lye ' yll < 6“ 72 imply that for each x2er(y2) - E(yl)e there is a corresponding x eDX(yl) such that l 0[(xl,yl); (x2,y2)] < 63 Therefore, xler(yl) - E 0. y2ch and IY2 - yll < 6 imply (l) 9(y2) > 9(yl)+M 2 and (2) For each xaer(y2) — E(yl)E |R(X2ay2)l < 0(y1)+M< 0(y ) ’ ———§——— 2 or equivalently E(y2)(q [DX(y2) - E(yl)€] = i .. s .... r greyhvflfmflq!‘ 33‘ “Him-..."; .0 ' vault . 1 ...-III -EEL-rrr 73 Then since E(y2)(::DX(y2) we have E(y2) (:E(yl)e We now consider the implications of theorem 2.6.4: Example 2.6.5: Let D = [0,4] x [0,2] and let F(x,y) = ysinnx, for 0 E y s 1 ysinwx, for 0 S x f 1 and 1 < y 5 2 sinnx, for l < x S 2 and 1 < y E 2. Let ¢l(x) = 1. Then for 0 E y E l — 1- 3: .5_=_1 llelly — y, and Fy‘2} — - Fy}2) Fy(2) Fy‘2, Therefore the best uniform approximation to Fy by a constant is 0 and E(y) = {2%, g: g" %} ° IA Also for 1'< y 2 IIF II V y y, and Fy‘2}= - Fy(2)= y. Therefore the best uniform approximation for Fy by a constant is 0 and E(y) = {%, %} See Figure 2.6.1. 74 Figure 2 6 1 75 5 = _ l = Note that Fy(§) Fy 2 l < y, which implies that g and % are not extremals for Fy ' PA(y) = Fy Now if we choose 6 = % and y1 = lEDy = [0,2], then by theorem 2.6.3 there exists a 6 = 6[%,1)> 0 such that y2e[0,2] and |y2 - 1| < 6 im lies that all extremals of F - P = F p y2 A(yz) y2 l of E(l) = {i i E are within 2 2, 2, 2, l\)|\] . H4 Any choice of 6 > 0 will do. In particular we can choose 6 = 1. Consider y2 = g . 1 1 Es) = awn = 9 Therefore, each point of E[%) lies within % of some point of E[%}. However there is no point of E‘%) which lies within % of g or g which belong to E[%). This can be explained by the fact that while _ 3 _ l _ |y2 - yll - I? - 1| < 5(59yl) ‘ 5(5) l) - l we can not have %.< 6(e,y2) = a(-1—, 52-) lyl - y2l However y2e[0,2] and l<-l- 2 who ly3 - y2| = ly3 - 76 imply that _ l 3 3 _ mp4 who Therefore, we can choose 6(%, g) = Corollary 2.6.6: Let ¢l(x) = 1, ¢2(x) = x,...,¢n(x) = xn-l, and assume that (i) d F (x) + o for all y eD n+1 yl l y and for all xer(yl). Then there are n + 1 continuous functions xl(y),x2(y),...,xn+l(y), such that xl(y), 0 there exists an integer n > 0 and a corresponding polynomial n PA = Z a.¢. 3:1 J J such that ”F - PA“ < e . Remark 2.7.2: {03} is closed in E} if and only if the set of all finite linear combinations of the Dj's is a dense subset of 3’ . ...:IEinit... ...»..qu .. . . Q . .7 fit"... . .ILLI. ... 79 Remark 2.7.3: By Weierstrass' First Approximation Theorem we know that {1,x,x2,...} is a closed sequence in C(D). Remark 2.7.4: By Weierstrass' Second Approximation Theorem we know that {l,sinx,cosx,sin2x,cos2x,...} is a closed sequnece in C the linear space of all real- 211’ valued continuous functions such that F(x+2n) = F(x) for all er1 Theorem 2.7.5: For each n > 0 and m > 0 let D, F and ¢l’¢2’°"’¢n’wl’w2"°"wm satisfy condition P.T. and let Q {¢ } and {w } be closed sequences in C(D ) and C(D ) 3 3:1 1 i=1 x y C” respectively. Then given a > 0 and F eC(D) there exists an N = N(e) and an M = M(e,n) for each n > N(e), such that n > M and m > M imply that IIF - PT < 8 All where PTA is the Product Tchebycheff approximation in ¢l,¢2,o-.,¢n,wl,w2,...,wm, and ||~|| is the uniform norm on D. Proof: max |F(x,y) - P (x)I — eD A(y) 80 max max F (x) - P (X) yeD [,8Dx(y) ' y. A(y) '] V max p(y) D y5 y By the uniform continuity of p(y) on Dy, given 6 > 0, there exists a 6 = 6(5/4) > 0, such that yl,y2eDy and lyl-y2| < 6 imply that o(yl) < 0(y2) + 6/4 . Since Dy is compact we can choose a finite set Yk = {yl.y2.o--.YK}CDy such that for each yeDy, there exists a corresponding yieYk satisfying ly - yil < MW“)- This implies that 0(y) < p + e/u Now since {¢J} is closed in C(DX), given 6 > 0, there exists an Ni = Ni(e/4) such that for n > Ni p(yi) < e/4, for i = 1,2,...,k. Choose N = max (Nl’N2""’Nk)' Then n > N implies that p(yi) < e/4 for i = 1,2,...,k. 81 Then for each yeDy there exists a corresponding yieYk such that p + e/u s e _ E < F'*H" 2 Therefore n > N implies that max |F(x,y) - P (x)I = max p(y) <5- (x,y) A(y) yeDy 2 ° Now since ¢l’¢2’°'°’¢n is a Tchebycheff set on Dx’ they are linearly independent there. Therefore “‘23“ = max I¢J(X)I > 0: forJ = 1,2,...,n. xer By the closure of {w1}in C(Dy), given a > 0, there exists an M = M (e/2nII¢JII), such that m > M implies that J J J max la (y) — Q (y>| < e/2nll¢ II . y Dy J AJ J where QA is the best uniform approximation in J wl,w2,...,¢m to aJ on D . y Choose M = max (Ml,M2,...,Mn). Then m > M implies that I | I n n I max P (X)-PT (x,y) = max 2 a (y)¢ (X)- 26% (y)¢(X) (X.y)eD A(y) A (x,y)eD J=l J J J=llh J n = max I Z a (y) - Q (Y) ¢ (X) (x,y)eD i=1 3 A3 I J I 82 n - E 2 max |a(y)-Q (3') ¢ (X) i=1 eD I 3 A3 I J I n s 2 max laJ(y)--QA (y)| ° max |¢J(X)| 3:1 YED J xeD y X nII II E < 2 a 2n ¢ ¢ =._ 3:1 J J 2 Hence n=>N and m > M imply that IIF — PTAII = max |F(x,y) - PTA(x,y)I (X,Y)€D 5 max |F(x,y)-P (x)I+ maxIP (X)-PT(X,Y) (X.y)eD A(y) (xmweD A(y) A l e E _ < -2- + '2' " E. Corollary2.7.6: Under the hypothesis of theorem 2.7.5 given e > 0 and FeC(D) there exists an N N(e) and an M M(e,n) for each n > N(s), such that n > N and m > M imply that IIPT - P* | < e A where PTA is the Product Tchebycheff approximation and P* is a best uniform approximation Chi¢1,¢2,...,¢n,wl,w2,...,wm) to F on D. Proof: Let N = N (c/2) and M = M(e/2,n) correspond to the N and M in theorem 2.7.5. Then n > N and m > M imply that '3’ fl IIPTA - P || < IIF - PTAII + ||F - P ll < 2 IIF - PTAII < 2 E 2 = E 83 At the present time there is no known effective scheme for computing best uniform approximation to a function of two variables. Present research is being directed towards schemes somewhat like the Remez algorithm. A good initial guess is needed if such an iterative procedure is to converge, and if the computation time is to be reasonably short. The previous results (i.e. Theorem 2.7.5 + Corollary 2.7.6) suggest that in certain cases the Product Tchebycheff approximation may be a good initial guess to a best uniform approximation. Section 8: Approximation on a Domain Which does not Possess Property K The Product Tchebycheff approximation as defined in Chapter II, Section 4, applies only to sets which possess prOperty K. We shall briefly discuss the problem of approxi- mation of functions on certain sets which do not possess property K. Let D be a set which does not possess property K. Suppose there is an invertible transformation T which maps such that the set T(D) possesses property K. E into E 2 2’ If FeC(D) then FT-leC(T(D)). Suppose also that T(D), FT"1 and ol,¢2,...,¢n,wl,w2,...,wm satisfy condition P.T.. Then FT"l has a Product Tchebycheff approximation PTA on T(D). We can use PT to approximate F on D by defining A F(x,y) = PTA [T[(X,y)]] . 84 Example 2.8.1: Let D be the shaded area in Figure 2.8.1. I 8A "3 6' _;_ / ' D III , Figure 2.8.1 Then D does not possess property K. Let Tl: (x,y) + (xl,y}) be the rotation of the x and y axifis counterclockwise through an angle of 45°. Then Tl(D) possesses property K. 1 _ ,5 1 _ ,— x — __ (x+y), y - _§ (y-x) 2 2 -1 Therefore Tl : (xl,yl) + (x,y) where 1 1 l l x = /2 (x -y ) y = 12 (x +y ). ‘2 ’ 2 For this set D we shall consider the approximation of F(x,y) = x + y. Then FT;l(xl,yl) = F [E (xl-yl), [Z (xl+yl) 2 2 = [2 (Xi-5’1) + {Z (xl+yl) 2 2 = /2 x1 on Tl(D). 85 l 1 Let ¢l(xl) 1: ¢2(X ) = X wl(yl) 1. Then we can easily see that the Product Tchebycheff approximation for FT"l on T1(D) is PTA (x1,yl) = /2 x1 1 Therefore we approximate F on D by Pl(X.y) = PTAI (Tl[(X.y)l PTA [Z (x+y), [Z (y-X) l - 2 2 = x + y. «2 («2 (x+y) 7 Now let T2:(x,y)-+(x",y") be the rotation of the x and y axis clockwise through an angle of 45°. Then T2(D) possesses property K (see Figure 2.8.2). \V Figure 2.8.2 86 x" = 12 (x—y), y" = 12‘ 2 2 H Therefore T : (x",y") + (x,y) where 2 x = /2 (x"+y"), y = {Z (y"-X") 2 2 -1 Then FT2 (x",y") = F K; (X"+y"), 1% (y"-x") i: (x"+y") + 12 (y"-x") 2 2 N; = /2 y" on T2(D). Let ¢l(x") 1, ¢2(x") = x" l. " wl(y ) Then the best uniform approximatioh to -1 ' FT2yn(X") = /E Y" on T2(D)Xn(y") is n = n PA(y")(x ) 5 y ° Therefore the Product Tchebycheff approximation to -l FT2 on T2(D) is NIH PTA (x",y") max /2 y" + min /2 y"] 2 y .. e(%/2,5/2I y"eI%-v/2-,g-/2I ' = 1 2 1 a 2I3 . 3] 1 Therefore we can approximate F on D by P2(x,y) PTA2(T2[(X.Y)J) PT /2 (x—y), /2 (x+y) “If? “2 I = l . 87 This example illustrates that this technique may possess the undesirable property of lacking a unique solu- tion. However we can specify the transformation used and we can bridge the communication gap. There are a few other difficulties which we may - encounter. It may prove difficult to find a transforma- tion T such that FT‘l will have a Product Tchebycheff ap- proximation on T(D). Also, the resulting approximation PT T is not in general a polynomial. However if T is a A linear transformation, then PT T is a polynomial and thus A possesses the desirable properties of a polynomial approxi- mation. Section 9: The Product Tchebycheff Approximation to a Continuous Function of Three or More Variables We now extend the Product Tchebycheff approximation to continuous functions of three or more variables. For ease of notation we shall restrict our attention to the three variable.case. The further extension is straight- forward. Let D be a compact set in B We define the follow- 3. ing compact sets. Dx’D ,D the projections of D onto the x,y and z axtua Y 2’ respectively. Dz(x1’yl)’ the projection of the intersection of the set D and the line x = x1, y = y1 onto the z - axis. 88 D the projection of D onto the x,y plane. x,y’ Definition 2.9.1: Let FeC(D). Then for each (xl,y1) 6 DK 3 y we define the associated function F on D (x ,y ) by Xl’yl z 1 l Fxl’yl(Z) = F(xl,yl,z). Let ¢l’¢2"°"¢n be a Tchebycheff system of con- tinuous functions on Dz' Definition 2.9.2: For each (x such that Dz(xl’yl) l’yl) 5 Dx,y contains n or more points, Haar's theorem shows the existence of a unique polynomial "MS PA(Xl,yl) ‘ J l 33(X1’y1)¢3 ’ where A(xl,yl) = (al(xl,yl),a2(xl,yl),...,an(xl,yl)I 6 En , which is the best uniform approximation to the continuous function F on its domain of definition D (x ,y ). xl,yl z 1 1 We now extend the definition of property K to DC3E3, and we can show that with the addition of this prOperty A(x,y) is continuous on D . x,y Definition 2.9.3: The compact set D in E is said to possess 3 property K, relative to the variables x,y if and only if given a > 0, there exists a 6 = 6(e ) > 0 such that (x1,yl), (x2,y2) a Dx,y and 02[(xl’yl); (X23y2)] < 5 l ‘1‘ III' ‘I III! |1I I: 'III III [I ‘1’ ‘IIIIIIII . I'll. '1 '1' all" I 89 imply that for each zleDz(xl,yl) there is a corresponding z2eDZ(x2,y2) satisfying Iz - le < s 2 Definition 2.9.4: For each x ) in b let x y ’ l’yl p(x ,y ) = inf Sup IF (2) - P (z)| - l l AeEn zeDZ(xl,yl) Xl’yl A The following two theorems are extensions of theorems 2.3.2 and 2.3.6. The proofs are omitted since they do not incorporate any new concepts. Theorem 2.9.5: Let D be a compact set in E3, which possesses property K, relative to x,y and let ¢l’¢2""’¢n be a Tcheby- cheff system of real-valued continuous functions on Dz. Let FeC(D). Then 0 is a continuous function on Dx y’ 3 Theorem 2.9.6: Let D, F and ¢l’¢2"'°’¢n satisfy the hy- pothesis of theorem 2.9.5 and let (xl,yl) contains n or more points. Then A(x,y) is continuous at (x1,yl). Corollary 2.9.7: Under the hypothesis of theorem 2.9.6 al(x,y),a2(x,y),...,an(x,y)‘as defined in 2.9.1 are all continuous at xl,yl). Now as in Section 4 we are motivated to seek poly- nomial approximations to each of the continuous functions al,a2,...,an. In this case we will approximate each aJ, j = 1,2,...,n by a corresponding Product Tchebycheff approximation of degree two. 90 Definition 2.9.8: We will say that the compact set DCE3 and 61’62’°'°’ek’wl’w2’°°°’wm’¢l’¢2’°°°’¢n satisfy condition P.T. relative to x,y if and only if (1) D possesses property K relative to x,y, (2) ¢l’¢2’°°°’¢n is a Tchebycheff system of continuous real-valued functions on Dz, (3) For each (x )eD , the set D (x,y) con- x,y z l’yl tains n or more points, (4) The compact set Dx,yc;E2 and 61,62,...,6k, wl,w2,...,wm satisfy condition P.T. relative to x. Definition 2.9.9: Let the compact set DCZE3 and 61,62,...,6k, ml,w2,...,wm,¢l,¢2,...,¢n satisfy condition P.T. relative to x,y. For each j = 1,2,...,n let QA be the Product J Tchebycheff approximation to the continuous function a on J Dx,y relative to x, (with base functionsel,e2,...,6k and wl,w2,...,wm). Then the polynomial n PT = X A j=l QAJ¢J is called the Product Tchebycheff approximation to F on D relative to x,y. Note that this approximation depends on the order in which the variables x,y,z are specified. As was illustrated 91 in example 2.4.3 two distinct orders may produce two dis- tinct Product Tchebycheff approximations. We conclude this section with a simple example which illustrates the ideas we have presented. Example 2.9.10: Let D = [0,1] x [0,1] x [0,1], and let F(x,y,z) = x + y + z 61(X) = 1, wl(y) = 1, ¢l(z) = 1. Then for each (xl,yl)e[0,l] x [0,1], we approximate F 2 = x + + z xl,yl( ) l yl on [0,1] by its best uniform approximation P A(X1.y1)(z) = 31(x1’y1)¢1(2) = al(xl,yl) - 1 ‘ Xi + yl + 2 Next we approximate al(x,y) = x + y + % on [0,1] x [0,1] by its Product Tchebycheff approximation relative to x, QAl(x,y) = % 61(X)wl(y) _ 3 2 Therefore, the Product Tchebycheff approximation to F on D relative to x,y is PTA(x,y,z) = QAl(x,y)¢l(x) I U) . i I'llllllln III-l. I'llniililll‘llli 1" ll I'll-III 92 Section 10: Conclusion Let w(x,y) be a positive continuous weight function on D. Then we define p(y) = inf Sup Iw(x,y) F‘(x) - PA(x))I AeEn xer(y) y to be the deviation of a best weighted approximation to Fy on Dx(y). We can show that extensions of theorems 2.3.2 and 2.3.6 hold for this more general problem. Therefore we can extend the Product Tchebycheff approximation to a weighted Product Tchebycheff approximation. This thesis can also be extended to arbitrary norms and to the approximation of a function and its partial derivatives. 10. 11. 12. 13. N. BIBLIOGRAPHY I. Achieser, Theory of Approximation (English trans- lation), New York, Frederick Unger, 1956. C. Buck, Linear spaces and approximation theory, On Numerical Approximation, ed. Rudolph Langer, Univ. of Wis. Press, 1959, 11-23. C. Buck, Survey of recent Russian literature on approximation, On Numerical Approximation, ed. Rudolph Langer, Univ. of Wis. Press, 1959, 341-359. W. Cheney, Introduction to Approximation Theory, New York, McGraw-Hill, 1966. J. Davis, Interpolation and Approximation, New York, Blaisdell, 1963. Fraser and J. F. Hart, On the computation of rational approximations to continuous functions, Comm. ACM. 5(1962), 401—403. Golomb, Approximation by functions of fewer variables, On Numerical Approximation, ed. Rudolph Langer, Univ. of Wis. Press, 1959, 275-327. Haar, Die Minkowshische Geometrie and die Annaheruug an stetige Funktionen, Math. Ann. 18 (1918), 294-311. G. Lorentz, Approximation of Functions, New York, Holt, Rinehart and Winston, 1966. John C. Mairhuber, On Haar's theorem concerning Chebychev approximation problems having unique solutions, Proc. Amer. Math. Soc. 7 (1956), 609-615. David G. Moursund, Application of numerical maximization and minimization techniques to Chebyshev approxima- tion, SIAM Rev. 9 (1967), 100-106. P. Natanson, Konstruktive Funktionen theorie, Deutsche Ubersetzung von K. Bogel, Berlin, Akademie Verlag, 1955. P. Novodvorskii and I. S. Pinsker, The process of equating maxima, Uspehi Mat. Nauk. 6 (1951), 174-181. 93 14. 15. l6. 17. 18. 190 20. 21. 22. 23. 24. 25. 26. 27. 94 R. R. Phelps, Uniqueness of Hahn-Banach extensions and unique best approximation, Trans. Amer. Math. Soc. 95 (1960), 238-255° Anthony Ralston, A First Course in Numerical Analysis, New York, McGraw—Hill, 1965. E. Ya. Remez, General Computational Methods of Cheby- shev Approximation, United States Atomic Energy Commission, Washington, D.C., 1962. E. Ya. Remez, Sur le calcul effectif des polynomes d'approximation de Tchebycheff, Compt. Rend. 199 (1934), 337-340. J. R. Rice, The Approximation of Functions, Vol. 1, Reading, Mass., Addison-Wesley, 1964. J. R. Rice, Tchebycheff approximation in several vari- ables, Trans. Amer. Math. Soc. 109 (1963) 444-466. T. J. Rivlin and E. W. Cheney, A comparison of uniform approximations on an interval and a finite subset thereof, SIAM J. Numer. Anal. 3 (1966), 311—320. T. J. Rivlin and H. S. Shapiro, Some uniqueness prob- lems in approximation theory, Comm. Pure Appl. Math. 13 (1960), 35-47. T. J. Rivlin and H. S. Shapiro, A unified approach to certain problems of approximation and minimization, J. Soc. Indust. Appl. Math. 9 (1961), 670-699. I. J. Schoenberg, On the question of unicity in the theory of best approximation, Ann. New York Acad. Sci. 86 (1960), 682-692. Edward L. Stiefel, Numerical methods of Tchebycheff approximation, On Numerical Approximation, ed. Rudolph Langer, Univ. of Wis. Press, 1959, 217-232. John Todd, Introduction to the Constructive Theory of Functions, California Institute of Technology, Pasadena, California, 1961. L. Veidinger, On the numerical determination of the best approximations in the Chebyshev sense, Numer. Math. 2 (1960), 99-105. Burton Wendroff, Theoretical Numerical Analysis, New York, Academic Press, 1966.