OPTIMAL STARTING APPROXIMATIONS FOR ITERATIVE SCHEMES FROM CLASSES 0F RATIONAL FUNCTIONS Thesis for the Degree of Ph. D. MICHIGAN STATE UNIVERSITY JOHN BYRON GIBSON 1971 This is to certify that the thesis entitled Optimal Starting Approximations for Iterative Schemes from Classes of Rational Functions presented by John Byron Gibson has been accepted towards fulfillment of the requirements for Ph . D . degree in Mathematics Date 8-4- 71 0-7639 LIBRA R Y Michigan 3m University ‘5’ BINDING BY HOAG & SONS‘ ; MINI BINDER? INC. . LIBRARY amog‘ni SHIIGNIIT. IIOIIGI! ABSTRACT OPTIMAL STARTING APPROXIMATIONS FOR ITERATIVE SCHEMES FROM CLASSES OF RATIONAL FUNCTIONS BY John Byron Gibson Given a compact subset X of the closed interval [a,b], let C(X) denote the space of all continuous real-valued functions defined on X, normed by Hf“ = max {‘w(x)f(x)\} where w 6 C(X) and w > O on X. In the case w EXEX the norm is the usual Chebyshev norm and is denoted by H'Nm° Let K be a convex subset of C(X) and Q a continuous mapping of K into C(X). We shall then be interested in the problem of approximating g E 6(K) by elements of ¢(M) where M is a fixed subset of K. If we impose certain restrictions on Q, K and M, a Chebyshev type theory can be developed for this nonlinear approximation problem which is similar to the standard Chebyshev theory. The theory obtained has application to many iterative processes that can be used to approximate functions such as 1 exp(x) and x“, n = 2,3,... and consequently we make the following definition: Definition: An element p G M is called an optimal starting approx- imation (or best starting approximation) for g, with respect to Q and M, if Hg - §(p)“ S Hg - Q(q)“ for all q 6 M. John Byron Gibson In this paper we investigate the above problem for M a sub- set of K consisting of certain classes of rational functions. In Chapter I the aforementioned Chebyshev theory is developed. Classically, one would apply the characterizing alternation theorem we obtain to develop a Remez exchange algorithm for the computation of optimal starting approximations. However, if the operator 6 satisfies certain properties the optimal starting approximation for a function f can be calculated as a constant multiple of the best relative approximation to f in the case of relative error or as a translate of the best uniform approximation to f in the case of uniform error. In Chapter II the theory is applied to the Newton operator and optimal starting approximations are calculated for the functions xa, a 6 (0,1), exp(x) and Ln x in the manner described above. A number of additional iterative schemes are presented in Chapter III and analyzed for optimal starting approximations for the functions 1 x“, n = 2,3,... and exp(x). Recently D. Moursund has introduced the concept of a gen- eralized weight function which is a more general means of measuring error than that described earlier. Chapter IV is concerned with a development of the Chebyshev theory, analogous to that in Chapter I, for this type of weight function. Finally, in Chapter V an improved Newton iteration scheme for approximating exp(x) is presented and is shown to be Optimal in the sense of this paper. OPTIMAL STARTING APPROXIMATIONS FOR ITERATIVE SCHEMES FROM CLASSES OF RATIONAL FUNCTIONS BY John Byron Gibson A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1971 for his paper. imation helpful ACKNOWLEDGEMENTS I am deeply indebted to my major professor Gerald D. Taylor many suggestions and guidance in the preparation of this His enthusiasm for and insights into the area of approx- theory have inSpired me greatly. I would also like to thank Dr. Edwin Kaufman for his many comment S 0 ii TABLE OF CONTENTS Page INTRODUCTION OOOOOOOOOOOCOCOOOOOOCOOOOOOOOOOOOOOOO 1 Chapter I GENERAL THEORY FOR OPTIMAL STARTING APPROXIMATIONS 4 Section 1: Definitions and Basic Results ........ 4 Section 2: Existence, Uniqueness, and Characterization Theorems ............ 7 Section 3: Computation of an Optimal Starting Approximation ............... 34 II APPLICATION TO THE NEWTON OPERATOR AND BSOCIATED RESULTS O0.000000000IOOOOOOOOOOOOCOOOO. 42 Section 1: Introduction and General Theory ...... 42 Section 2: Optimal Starting Approximations for Roots, Exp(x) and Ln x ............. 47 Section 3: An Associated Operator ............... 51 III FURTHER EXAMPLES OF OPERATORS DEFINING ITERATIVE SQ-IEWS 0....0..0....O00......COOOOOOOOOOOOCOOOOOO 55 Section 1: Definition and Basic Results ......... 55 Section 2: Iteration Functions of Order 2 ....... 57 Section 3: Iteration Functions of Order 3 ....... 58 Section 4: Iteration Functions of Order 4 ...... 63 Section 5: A Sequence of Schemes for Approximating I/k .................... 70 IV OPTIMAL STARTING APPROXIMATIONS FOR A GENERALIZEDWEIGHT FIINflION OOOOOOOOOOOOOOOOOOOOOO 74 Section 1: Introduction and Examples ............ 74 Section 2: Existence, Uniqueness, and Characterization Theorems ............ 75 iii Chapter Page V AN IMPROVED NEWTON ITERATION SCHEME FOR APPROXIMATING EXP(X) WHICH IS OPTIMAL 83 Section 1: IntrOdUCtion OOOOOOOOOOO...0.0.0.0.... 83 Section 2: The Improved Newton Iteration Scheme . 84 Section 3: Execution of the Scheme .............. 108 BIBLIOGRAHIY 0.0.0.0...0.000000000000000. 00000 O... 110 iv INTRODUCTION In [15] D.G. Moursund examined the problem of approximating /k over an interval [a,b] (a > O) by applying the Newton-Raphson iteration scheme to classes of polynomial and rational approximants. For polynomial approximation the problem may be formulated in the following way: set K = {f E C[a,b]: f > 0 on [a,b]}, M = Pn n K where Pn consists of all polynomials of degree less than or equal to n, and define O: K a C[a,b] via §(h)(x) = %-(h(x) +-E%;39. Here 9 denotes a single Newton iteration for calculating /x starting with h(x). Then we are interested in approximating /x with the class {%-(p(x) + 3%;3)}, for p E M, using the relative error (the notion of relative error will be defined later). Moursund * was able to show that there exists a unique solution p to - * inf“!x ‘/3122(3)" ; p gi} and moreover that p is also the an m uniQue solution to infUI/X - 25mg) H t P E M} s m = 2.3...” where §k(h) = §(§k-1(h)). More recently, P.H. Sterbenz and C.T. Fike [24] and R.F. King and D.L. Phillips [7] both showed (independently) that p* is a multiple of E, the best relative approximation to /k on [a,b]. The above problem may be posed in a more general setting. Given a compact subset X of the closed interval [a,b], let C(X) denote the space of all continuous real-valued functions defined on x, normed by Hf“ = max {Iw(x)£(x)|} where w e C(X) and w > o XEX 1 on X. In the case w E l the norm is the usual Chebyshev norm and is denoted by H-“m. Let K be a convex subset of C(X) and Q a continuous mapping of K into C(X). We shall then be interested in the problem of approximating g E 9(K) by elements of @(M) where M is a fixed subset of K. G. Meinardus and G.D. Taylor [11] have considered the above more general problem for M a Subset of K consisting of members of a Haar subspace of C[a,b]. (The notion of a Haar subspace will be defined in the paper.) By imposing additional restrictions on a, K and M they were able to deve10p a theory for the above nonlinear approximation problem which is analogous to the classical Chebyshev theory. Moreover they were able to preserve the behavior of the prob- lem considered by Moursund and to obtain results similar to those obtained by Sterbenz-Fike and King-Phillips in the more general setting. Because of the application of this theory to iterative processes we make the following definition: Definition: p E M is an optimal starting approximation (or best starting approximation) for g, with reSpect to Q and M, if Hg - §(P)H S Hg - §(q)u for all q e M. In this paper we shall investigate the above problem for M a subset of K consisting of certain classes of rational functions. In Chapter I we develop a Chebyshev type theory for this highly non- linear approximation problem and in Chapter II we apply the theory to the Newton operator. A number of iterative schemes are given in Chapter III and analyzed for optimal starting approximations. The concept of a generalized weight function was introduced by D. Moursund in [13] and [14]. In Chapter IV we show that the Chebyshev type theory can also be developed for this more general means of measuring error. Finally, in Chapter V we present an improved Newton iteration scheme for approximating ex which is shown to be optimal in the sense of this paper. CHAPTER I GENERAL THEORY FOR OPTIMAL STARTING APPROXIMATIONS Section 1: Definitions and Basic Results In our development we wish to make use of the results and techniques of the classical Chebyshev rational approximation. Con- sequently we introduce the following definitions and results from the paper of Meinardus and Taylor [11]. Throughout this section we shall assume that X, K, M and Q are as described in the intro- duction. Definition 1.1: The operator Q is called pointwise strictly mono- tone at f e K if for each h,k e K we have |e(h)(x0) - {>(f)(x0)| < ‘§(k)(x0) - e(£)(xo)| for each x0 e x where either k(x0) < h(xo) 5 f(x or f(xo) S h(xo) < k(x0). 0) Lemma 1.2: Let Q: KI~ C(X) be pointwise strictly monotone at f E K. If k E K and at x E X, k(x0) # f(x then §(k)(x0) # o o) §(f)(xo). Proof: Let h E f in Definition 1.1.I Definition 1.3: The operator Q is said to be pointwise fixed at f E K if h E K with h(x = f(xo) for x0 6 X implies O) §(h)(x0) = wxxo). In general the notions of pointwise strictly monotone and pointwise fixed are independent. Indeed, define K C C[0,1] by K = {f(x) = ax2 : O 5 a s 1}. If Q1: K a C[O,l] is defined by ¢1(ax2) = x2 then Q1 is pointwise fixed at x2 yet not pointwise strictly monotone at x2. Now, if p2: K a C[O,l] is defined by 62(ax2) = x2 + (l-a) then 62 is continuous and pointwise strictly monotone at f(x) = x2. Indeed, if ax: < bx: 5 x3 then xO ¥ 0 and a < b s 1 so ‘§2(ax2)(x0) - x3‘ = 1 - a > 1 - b ‘§2(bx2)(xo) - xg| since Q2(x2) = x2. Each 8x2 6 K has the pro- perty that ax2 = x2 at x = 0; but §2(ax2)(0) e o = a2(x2)(0) 2 if a # 1. Hence Q2 being pointwise strictly monotone at x . . . . 2 does not imply 62 18 p01ntW1se fixed at x . Next we shall show that the composition of two continuous operators possessing the above properties is again such an operator provided of course that domains and ranges mesh correctly. Lemma 1.4: Let a: K a C(X) and Y: L a C(X) be continuous operators with §(K) C L, Q pointwise strictly monotone and pointwise fixed at f E K and Y pointwise strictly monotone and pointwise fixed at Q(f) E L. Then Y6: K A C(X) is a continuous pointwise strictly monotone operator at f which is also pointwise fixed at f. .ggggf: It is clear that we: K a C(X) is continuous and pointwise fixed at f E K. To establish the pointwise strict montonicity of VS at f let us first show that if h,k E K with k(x0) < h(xo) s f(xo) or f(xo) s h(xo) < k(x0) then either ¢(k)(x0) < Q(h)(x0) s §(f)(xo) or §(f)(x0) s §(h)(xo) < §(k)(x0). Since Q is point- wise strictly monotone at f we have that \§(k)(x0) - §(f)(x0)‘ > I¢ - ¢(f)(x0)l- Suppose that a < e(x0) < ammo) or §(h)(xo) < Q(f)(x0) < §(k)(x0). Then for O S a s l, the functions La(x) = ah(x) +~(1-a)k(x) are members of K (since K is convex) and furthermore Q(La)(x0) is a continuous function of a for each fixed x0 6 X. Thus, by the intermediate value theorem, there exists a0 6 (0,1) Such that Q(La0)(xo) = Q(f)(x0). Therefore, in view of 0) 0). This is a contradiction. Consequently we have either Q(k)(x0) < 0(h)(xo) S §(f)(xo) or Q(f)(xo) 5 Lemma 1.2, Ld(x = f(x Q(h)(x0) < §(k)(xo). An application of the pointwise strict mono- tonicity of Y at Q(f) yields the desired result. I In order to be able to iterate with the operator Q we must necessarily demand that Q(K) C K. With this restriction we are able to relate the notions of pointwise strictly monotone and pointwise fixed according to the following lemma: Lemma 1.5: If Q: R ~ K is a continuous operator on the convex set K which is pointwise strictly monotone at f E K then Q is point- wise fixed at f. lggggf: Suppose h E K and h(xo) = f(xo) for some x0 6 X. Clearly, if k(x = f(x for all k E K then Q(h)(x0) = Q(f)(x0) and so 0) 0) Q is pointwise fixed at f. If this is not the case then there 0). for a 6 (0,1). Now Hko - f“ a O as exists k e K Such that k(xO) # f(x Set k0 = of + (1-0)k and note that kd(xo) # f(xo) o ~ 1 and so He - s(f> \Q(h)(x0) - s(xo>l for all a e (0.1) and so IQ(h)(x0) - Q(f)(x0)| = 0. Hence Q(h)(x0) = s(£)(x0) and so Q is pointwise fixed at f.l For the sake of any iteration processes we may be interested in, we state the following corollary to Lemma 1.5: Corollary 1.6: If Q: K a K is continuous, Q(f) = f for some f E K and Q is pointwise strictly monotone at f E K then Qm: K a K defined inductively by Qm(h) = Q(Qm-1(h)), m = 2,3,..., satisfies §m(f) = f and am is pointwise strictly monotone at f. Finally we shall state a general existence theorem for best approximation in our setting. The theorem is very general and for specific operators is sometimes difficult to check. Theorem 1.7: Let K be a convex subset of C(X), M C K and Q: K d C(X) be continuous. Then correSponding to g E Q(K) there exists r* E M minimizing Hg - Q(r)H, r G M, provided there exists a compact subset M1 of M and a positive constant n such that s e M ~ M1 implies inf {Hg - Mr)“ : r e M} + n s Hg - Q(s)H. Proof: A continuous function on a compact set assumes its minimum.l Section 2: Existence, Uniqueness, and Characterization Theorens In this section we shall specialize M and K and develop an alternation theory for characterizing best approximations similar to the standard Chebyshev theory. From this development we are able, when we have existence, to conclude uniqueness using standard Chebyshev theory arguments. Before proceeding to the first characterization theorem we must establish some additional notation. Let X be a compact Subset of the closed interval [a,b] containing at least m + n +»2 points where m and n are fixed for the discussion at hand. Let Pn denote the set of all polynomials p with ap s n (5p denotes the degree of p) and set R;[a,b] = {E 2 P 6 P“: q 6 Pm: (p:Q) = 13 q > 0 on [3,131} where (p,q) 8 1 denotes the fact that the polynomials p and q are relatively prime. The following well-known lemma from Rice [20] will be used extensively: Lemma 1.8: Given r = 5-6 R:[a,b], T > 0 and any set {Xiz i = 1,...,r, r < 1 + max {m + 5p, n + aq}, xi < xi+1} . . . . . n of p01nts in X, there is a rational function r E Rm[a,b] such 6 that (i) Hre - rH m < w , L [a,b] and (ii) Sgn (r(x) - r (x)) = (-l)1+1 x E (x x ) i = O 1 .. r e , 1’ 1+1 9 3 3 '9 where x0 = a if t} # a and xr+1 =‘b if xr # b. Proof: Set¢(x) = H (xi-x). Now p(x) and q(x) are relatively prime i=1 and so there are polynomials p1(x) 6 Pn and q1(x) 6 PE such that y(x) = p(x)q1(x) - p1(x)q(x). The proof of this fact depends on the Euclidean Algorithm and can be found in Rivlin [21]. Let p(X) - epl(X) r€(x) _ Q(X) ‘—_ " €q1(x) where e > 0. Then _ = '6OIX) f(x) re(x) q(x) - eq1(X)) ° (1'1) Since q(x) > 0 on [a,b], 6 may be chosen sufficiently small, say 0 < e s 60’ so that the denominator of (1.1) is positive. Now, given T > 0, select 6 such that O < e s 30 and ‘6‘ < T. q(q-eql) m I II Then Hr - r H < T and, since (ii) is clear, the result is established.‘ 6 Theorem 1.9: Let Q: K a C(X) be a continuous Operator where K is a convex subset of C(X). Let M = K O R:[a,b] be a nonempty rel- atively Open subset of R;[a,b]. Finally, assume that Q is point- wise strictly monotone and pointwise fixed at f E K ~ M. Then r E M is the best starting approximation for Q(f) if and only if there exist points {xi}§=1 c X, N = 2 + max {m + 5p, n + aq}, for which (i) x1.< x2 <...< xN, (ii) IW(xi)(Q(f)(Xi) - Q(r)(xi))| = HQ(f) - Q(r)H. i = 1.....N and (iii) sgn(f(xi) - r(xi)) = (-l)i+lsgn(f(x1) - r(x1)), i = 1,...,N. Proof: (Sufficiency). Since f 4 M we know that there exists a point e x for which f(xo) r r(x0). Thus “Q(f) - Q(r)H # 0. x0 Suppose that |w(xi)(Q(f)(xi) - Q(r)(xi))‘ = HQ(f) - Q(r)H and sgn(f(xi) - r(xi)) = (-1)i+lsgn(f(x1) - r(x1)), i = 1,...,N. Then Q(f)(xi) # Q(r)(xi). Let r1 6 M be such that HQ(f) - Q(r1)H s HQ(f) - Q(r)H. At xi, i = 1,...,N, ‘w(xi)(Q(f)(xi) - Q(r1)(xi))‘ s ‘w(xi)(Q(f)(xi) - Q(r)(xi))‘. Now at each xi either r(xi) > f(xi) or r(xi) f(xi) then r(xi) 2 r1(xi) for otherwise r1(xi) > r(xi) > f(xi), which implies \w(xi)(Q(f)(xi) - Q(r1)(xi))| > \w(xi)(Q(f)(xi) - Q(r)(xi))‘ which is a contradiction. Similarly r(xi) < f(xi) implies r(xi) s r1(xi). Now r(xi) > f(xi) implies r(xi) 2 r1(xi) and r(xi+1) < f(xi+1) implies r(xi+1) s r1(xi+1). Therefore (r-r1)(xi) 2 0 and (r-r1)(xi+1) s 0 (or conversely) 10 for i = 1,...,N-l. Set 8 = rl-r = (f-r) - (f-rl). If s(xi) ¢ 0 then sgn s(xi) = sgn(f(xi) - r(xi)) (since Sgn(f(xi) - r(xi)) = sgn(r1(xi) - r(xi)), as noted above). If s(xi) # O and s(xi+1) = s(xi+2) =...= s(xi+j_1) = 0, while s(xi+j) # 0, then since x1,...,xN is an alternating set for f-r, (-l)k[f(xk) - r(xk)] is of one sign for k = 1,2,...,N and so sgn s(xi) = (-l)jsgn S O for all x E X. Then there exists 31 > O p(x) + 61 ‘ such that f(x) > r1(x) > r(x) where r1(x) = -—E?;7—-' Also, Since M is relatively Open in R;[a,b], there exists 32 > 0 with p(X) + 32 0 < 32 S 31 Such that r2(x) - W E M and f(x) > r2(x) > r(x). This implies HQ(f) - Q(r2)H < HQ(f) - Q(r)H, which is a contradiction. 11 Now let Il,Iz,...,IN, be a collection Of relatively Open intervals in [a,b] Such that xi 6 Ii’ T; n I. = ¢ for 1 ¥ j, 3 all extreme pointsN = {x E X : IW(X)(§(f)(X) ' Q(r)(x))I = HQ(f) - Q(r)H} : iU I1 and for each extreme point in Ii the =1 function f-r has constant Sign. Let NI =x n ( n I ) i=1 where Ii denotes the complement of Ii with respect to [a,b]. Y is a compact Subset of X and ‘w(x)(Q(f)(x) - Q(r)(x))\ < HQ(f) - Q(r)H for all x E Y. By continuity there exists p > 0 for which max ‘w(x)(Q(f)(x) - Q(r)(x))‘ s HQ(f) - Q(r)H - p. Next, XEY let wi = {x e x n f; : |w(x)(Q(f)(x) - Q(r)(x))‘ 2 HQ(f) ; §(r)fl and sgn(f(x) - r(x))= sgn(f(xi) - r(xi))} ._ N. where Ii denotes the closure of Ii in [a,b]. W = U W1 is a i=1 compact subset of X and so by continuity there exists an n > 0 such that ‘f(x) - r(x)‘ 2 n on w. Set = {x e x n‘fi : \w(x)(Q(f)(x) - Q(r)(x))l 2 fl§(f) ; Q(f)” and sgn(f(x) - r(x)) s sgn(f(xi) - r(xi))l NI and let 2 = U 2. Observe that \w(x)(Q(f)(x) - Q(r)(x))‘ < i=11 HQ(f) - Q(r)H for all x E Z by the construction of the intervals {TH}. Finally, set 12 ‘%={x€xnl1:WOHMDGO-QOHMHsJDG)-M0M 2 N. and let U = U U1. Then, by continuity, there exists 6 >»0, i=1 6 s p, such that max Iw<¢ 0 we can, using Lemma 1.8, select re 6 R;[a,b] such that (i) Hre - rH < T , Lw[a,b] (1 2) and (ii) sgn(re(x) - r(x)) = Sgn(f(xi) - r(xi)) for all x E Ii’ i = 1,...,N' By the continuity of Q we can select > 0 such that for 61 0 < e s 31, re satisfies (1.2) and max IW(X)(Q(f)(X) - s(r >(x))I s us 0 there exists a number N(P) (inde- pendent of x) Such that ‘w(x)(Q(f)(x) - Q(r)(x))‘ s p implies ‘r(x)‘ S N(P) where r E M and w is any continuous positive weight function on [a,b]. Remark 1: It may well happen that all r E M are uniformly bounded from above or below on [a,b]. In this case we will already have the desired upper or lower uniform bound on r(x) (for all r 6 M). The above lemma is easily modified to cope with the aforementioned situations. 14 2593;: Let t a [a,b] be arbitrary but fixed. Then there exists rt,st E M with rt(t) > f(t) and st(t) < f(t) such that ‘w(t)(Q(f)(t) - Q(rt)(t))| > P +-l and \w(t)(Q(f)(t) - Q(st)(t))‘ > P + 1. By continuity there exists 6(t) > 0 such that \x-t‘ < 6(t) and x 6 [sub] imply Iwm - p(rt>>\ > P and ‘w(x)(Q(f)(x) - Q(st)(x))‘ > P. The neighborhoods (t-6(t), t + 6(t)) form an open cover of [a,b] and so by the compactness of [a,b] there exists a finite subcover {(ti-6(ti), ti + 6(ti))}:=1. Set N(P) = max {Hr H , HS H} to obtain the desired result.‘ lsisk ti ti The next lemma is analogous to a result found in Rice [20, p. 75]. n 30 + alx +...+-a x n Lemma 1.12: Let r(x) = n 6 R [a,b], 0 S a < b b +-b x +x..+-b xm m 0 l m m where b +-b x +...+ b xm # 0 for all x 6 [a,b] and 2 b? = l. 0 l m . 1 i=0 If max Ir(x)\ s S then there exists N(S) such that x6[a,b] max lail S N(S), max Ibi‘ s N(S). i i n i n i Iza.x| IEMI i=0 1 i=0 1 h _ bm 1 Proof. ‘r(x)\ 2 m i 2 Om+l)B w ere B - max{ , ]. max Izb.x| . i xE[a,b] i=0 n . Hence (m+l)BS 2 (m+l)B max Ir(x)l 2 max I Z aixll . x6[a,b] xe[a,b) i=0 n . Thus the polynomial Z a,xl is uniformly bounded on [a,b] and so, i=0 by Markoff's Inequality, [1, p. 91], also the parameters ai. That is, there exists N1(S) Such that max ‘ai‘ s N1(S). By the i normalization of the denominator, max Ibil s 1. Setting N(S) = max{l,N1(S)} we have the desired result.l 15 Theorem 1.13: Let Q: C[a,b] a C[a,b] be a continuous Operator which is pointwise strictly monotone at f E C[a,b] ~ M and point- wise fixed at each R E C[a,b] where M = R:[a,b] (m,n fixed). Assume that for each x E [a,b], [Q(ri)(x)l a m whenever {r1} 9 M and ri(x) 4 12“: Then there exists a best starting approximation for Q(f) from M. 12539;: Let {r1} C M be such that lim HQ(f) - Q(ri)H = 1-00) inf HQ(f) - Q(r)H. Let us first normalize the functions ri(x) = rEM pics) m (110‘) so that gobij m . = l where q,(x) = 2 b.,xJ. Clearly there i j=0 i] j exists P > 0 such that HQ(f) - Q(ri)H s P for all i and so by Lemma 1.11 there exists N(P) Such that HriH s N(P) for all 1. According to Lemma 1.12 the coefficients Of the elements of {r1} are uniformly bounded. Therefore there exists a subsequence of {r1(x)} (which we shall also denote by {ri(x)}) such that lim ri(X) = ;(x) for all x E [a,b] except for zeros of the i—m denominator of ;(x). If (xi: i = 1,...,k} denotes the zeros of the denominator Of F. then it is clear that k s m. Using the uniform boundedness of the sequence {r1}, it is straightforward to Show that each x1 is a removable singularity Of r. Upon * cancellation, we Obtain a rational function r E R:[a,b] which we claim is the desired solution. First, using the pointwise fixed property of Q it is easy to show that if {ki} C C[a,b], k E C[a,b], xo E [a,b] and lim ki(x0) = k(xo) then lim Q(ki)(x0) = Q(k)(x0). 1“” l-coo Let 6 > 0 be given. Then there exists N = N(e) such that HQ(f) - put)“ s I + e for all i 2 N where 1 = inf HQ(f) - Q(r)H. rEM 16 k For any x0 6 [a.b] ~ d {xi}. Iw>I s 1 + 6 i=1 for i 2 N and so |w(x0)(p(£)(x0) - Q(r*)(x0))\ = 1m ‘w(x0)(Q(f)(xo) - Q(ri)(x0))‘ s 1 + e. Thus \Iw) - em)“ = i—ccn max |w(x)(Q(f)(x) - Q(r*)(x))l sup Iw - p>I xE[a,b] xE[a,b] x i xi s I + 6. Hence HQ(f) - Q(r*)H = inf HQ(f) - Q(r)H.I rEM In the next theorem we wish tO consider a characterization of the best starting approximation for Q(f) from a family of functions having restricted ranges. Much of the general theory for restricted range approximation by both polynomial and rational functions can be found in Taylor [25] and [26], Schumaker and Taylor [23], and Loeb, Moursund and Taylor [10]. It is interesting to note that the prob- lem of approximation with restricted range also encompasses one-sided approximation [4]. The theory of uniform approximation with restricted ranges is Of particular significance for the problem of obtaining starting values for various iterative schemes. This will become evident later on. For our considerations let {(x), u(x) E C(X) with L(x) < u(x) for all x E X. K. Taylor [29] has pointed out that this inequality restriction on L and u can be relaxed. Define K = {f E C(X): {(x) 5 f(x) 3 u(x)} and set M = K n R;[a,b] which we assume is nonempty. Theorem 1.14: Let Q: K ~ C(X) be a continuous operator which is pointwise strictly monotone and pointwise fixed at f E K ~ M where K and M are as defined above. Then r = 5-6 M is a best starting approximation for Q(f) if and only if there exists {xi[:=1 C X, 17 N = 2 + max{n + aq, m + 3p}, for which (i) x1l = HQ(f) - p(r>u then |W(xi)(Q(f)(xi) - Q(r)(xifll 2 IW(Xi)(Q(f)(Xi) - Q(r1)(xi))\- Since f 45 M we have that HQ(f) - Q(r)H > 0 so that sgn*(f(xi) - r(xi)) at o. If sgn*(f(xi) - r(xi)) = +1 then f(xi) > r(xi) and by the point- wise strict monotonicity Of Q at f we must have r1(xi) 2 r(xi). Likewise, if sgn*(f(xi) - r(xi)) = -1 then r1(xi) s r(xi). Hence we obtain the desired result as in the proof of Theorem 1.9. ONecessity). Suppose r E M is a best starting approximation for Q(f) and that r(x) has the desired behavior on a set Of points {xi}§;1 C X, N' < N, where N' is maximal and x1 < x2 <...< xN,. First we shall consider the case where w(x)(Q(f)(x) - Q(r)(x)) a x, ‘1‘ > 0, for all x E X and f-r has constant Sign. A technical difficulty which results in the general case necessitates that we consider this situation separately. Without loss of generality 18 assume that f(x) - r(x) < 0 for all x E X. Then there exists a > 0 such that f(x) < r*(x) < r(x) where r*(x) = 232%;i—E- and so HQ(f) - Q(r*)H < HQ(f) - Q(r)H, which is a contradiction. Let 11.12,...,IN, be a collection of relatively open intervals in [a,b] such that xi 6 Ii’ I] O I] = ¢ for 1 ¥ j, all extreme points I {x E X: Iw(x)(Q(f)(X) - Q(r)(x))l = N. HQ(f) - Q(r)H, r(x) = L(x), or r(x) = u(x)} c u Ii and for each i=1 * extreme point in each Ii the function sgn (f(x) - r(x)) has the Same value. Given T > 0 we can, according to Lemma 1.8, select n r6 6 Rm[a,b] such that (i) Hre - rH a < 'r , (1.3) L [a,b] and (ii) sgn(re(x) - r(x)) = sgn*(f(xi) - r(xi)) for all x 6 1i, i = 1,...,N' . We shall now Show that there exists 6 > 0 such that reE M and HQ(f) - Q(r€)H< HQ(f) - Q(r)H. Let ‘Y = X n ( U Ii). Y is a compact subset of x and Iw(x)(Q(f)(x) - Q(r)(x))l < HQ(f) - Q(r)H for all x E Y. Hence, by the continuity of Q, we can select 31 > 0 such that for 0 < e s 31, re(x) satisfies (1.3) and max IW(X)(Q(f)(X) - Q(r€)(X))\ < \Iw) - emu. In addition r(x) a XEY u(x) and r(x) # L(x) for all x E Y so there exists with 62 0 < e2 s e1 such that 0 < e s 6 implies {(x) S r (x) s u(x) e 2 for x E Y. Let wi = {x e x n I; : |W(x)(Q(f)(x) - Q(r)(x))] 2 HQ(flg Q(r)H and sgn(f(x) - r(x)) = sgn*(f(xi) ‘ r(xi))} l9 and set Vi = [x e x n Ti : r(x) = u(x) or r(x) = L(x)}, i = 1,2,...,N'. With these definitions we see that all extreme points contained in Ii are included in. Wi_U Vi' Using the strict monotonicity Of Q at f and the continuity of Q there exists S3, with 0 < 63 S 32, such that for 0 < e S 63. r (x) satisfies (1.3), c max Iw<><> - i>I < um“) - own and XEWiUVi e L(x) S r€(x) S u(x). Do this for i = 1,2,...,N' and let be such that O < a 64 4 S 63 and for 0 < e S 34, r (x) satisfies (1.3), c max IW(X)(Q(f)(X) ‘ Q(r )(X))I < HQ(f) - Q(r)H and XEWUV e L(X) S r€(x) s u(x) NI N. where W = U W. and V = U V.. Set 1 , 1 i=1 i=1 Zi = {x E X fl‘fi : [w(x)(Q(f)(x) - Q(r)(x))] 2 HQ(f) ; Q(r)H * and sgn(f(x) - r(x)) # Sgn (f(xi) - r(xi))} N. and let Z = U 21. By the construction of the intervals {Ii} i=1 we have that r(x) # u(x), r(x) # L(x) and ‘w(x)(Q(f)(x) - Q(r)(x))l < HQ(f) - Q(r)H for all x e 2. Finally, let u1 = {x e x n I, : Iwcxxumx) - o(x>>I s ”“0 gmh NI and set U = U U,. By continuity there exists .- l with 0 < as S 34 1-1 65 so that for x E 2 U U and 0 < e S 35, r (x) satisfies (1.3), e 20 |W(X)(§(f)(X) - Q(re)(X))I < HQ(f) - Q(r)H and L(X) S r€(X) S u(X)~ Combining the above results we have that for 0 < e S 35, re E M and HMO - Mrs)“ < HQ(f) - o(r)II.| Corollary 1.15: Under the conditions of the above theorem the best starting approximation for Q(f) is unique. Iggggf: Uniqueness is derived from the above characterization theorem in a manner analogous to that in which Corollary 1.10 was established.l Remark 1: The question of existence in the above setting is still unanswered. Thereom 1.13 is not applicable here since it requires that the domain of Q be c[a,b]. In 1955 S. Paszkowski (see [2]) considered the problem of approximating a given continuous function on an interval [a,b] by elements of an n-dimensional Haar subspace (to be defined) which were also required to interpolate the given function at certain prescribed points in [a,b] called nodes. He considered, using a classical approach, the questions of existence, uniqueness and characterization of best approximation. In 1968 Deutsch [2] extended and continued the Study of Paszkowski. Using duality theory, Deutsch was able to recover the characterization theorem of Paszkowski and to actually formulate exchange algorithms for computation. In 1969, Loeb, Moursund, Schumaker and Taylor [9] generalized the above work of Paszkowski and Deutsch to the following problem: let X be a compact subset of [a,b] and suppose {xi}:=1 C X satisfies P . . . . x1 < x2 <...< x . Let {mi}i=l be a set Of p031tlve integers With P P m = 2 mi < n and assume X contains at least n - m + p + 1 points. i=1 Suppose further that H is an n-dimensional extended Haar system of 21 order v, v = max (mi) + l, (which we shall define) and set i M = {p E H p(J)(xi) = ai., 1 S i S p and 0 S j S mi - 1}, J where {aij} is a set of m real numbers. Then the problem con- sidered was to find best approximations to elements of K = {f E C(X) : f(xi) = a l S i S p} i0’ by elements of M. The error of approximation was measured by a generalized weight function, a notion to be discussed in Chapter IV. We shall refer to the elements of M as p-point osculating Haar functions. A. Perrie [19] has examined a problem analogous to the above by replacing the extended Haar system by classes of rational functions. The approximants used by Perrie are referred to as p-point osculating rational functions. We shall now examine a problem analogous to that considered by Perrie for our Operator setting. Let X 9 [a,b] be compact, {yi}g=l a fixed set of p points in X where y1 < y2 <...< y * P P and {m,]? a fixed set of positive integers with m = m. < 1 i=1 i 0 i=1 n +~l (n as in R3). We shall assume that X contains at least * n +-m - m +'p + 2 points. Furthermore, let {ai]E=1 be any fixed set of p real numbers and define K = {f E C(X) : f(yi) = ai, i = 1,...,p}. Let aij’ i = 1,...,p, j = 0,1,...,mi-l be a second set of real numbers where aiO = ai, i = 1,2,...,p and set .. 1‘ .() _ . - M - {r e Rm[a,b] . r j (yi) — ai , o S J g mi-l, 1 s i s p}. Follow- j ing the discussion in Perrie, we shall refer to the elements of M as p-point osculating rational functions. As before we are interested in approximating g E Q(K) by elements of Q(M) where Q: K a C(X) 22 is continuous. In the case of ordinary rational approximation we know that for each f E C[a,b] there exists a best approximation from R:[a,b]. However, in the case of interpolating rational functions we can no longer insure existence as is demonstrated by the follow- ing example due to H.L. Loeb [8]: Define f0 6 C[0,1] as follows: 1 + 6x , x e [0, l] _ 1 l 2 f0(X) - 3 - 6(X - 3). x E [3 . 3 l+6(x-§), xE[-2-,l] 3 H 3 I 2 ~1= $.60 11 S A : X l O 3. 1% 1. l, w(x) E 1. Let K = [f E C[0,1] : Here a = 0, b = l, m = n f(0) = 1}. Obviously f0(x) E K. Define the Operator Q: K a C[0,1] via Q(f) = f. It is clear that Q is pointwise strictly monotone and pointwise fixed at f0 6 K. By the usual alternation theory for rational approximation g(x) E 2 is a best approximation to f0(x) from Ri[0,l]. Notice that 2 E M = {r E Ri[0,l] : r(O) = 1]. ‘91339; There exists no r E M, such that HQ(fO) - Q(r)H = Hr - f \ = dist (£0,M) = dist (Q(fo), Q(M)). OI 23 . 2nx + 1 Proof: For each n = 1,2,..., define rn(x) = nx + 1 , E [0,1]. Clearly r E M for all n since r (0) = 1. Also r'(x) = n > 0 n n n 2 (nx+l) and r (1) = 2_n_+__];< 2 for all n Hence 1 S r (x) S 2 for all n n +11 ' n n and for all x E [0,1]. Furthermore f0(l) - rn(l) > 1 and max [‘f0(x) - rn(x)‘ : x E [0, l-]] S l for all n. Therefore 1 Hf0 - rnH = max [|f0(x) - rn(x)l : x E [a , 1]}. Now {rm} approaches . 1 . . 2 uniformly on [6, l] and so lim HfO - rnH = lim max {‘f0(x) - rn(x>I =x or1.111= max {1563 - 2\ =x e 13. 111 = IIf - 211- Since M C Ri[0,l], HfO - 2H S inf {Hf0 - rH : r E M]. Hence inf {Hf0 - rH : r E M} = Hf0 - 2H. But, by uniqueness in Ri[0,l], there exists no r* E M such that HfO - r*H = Hfo - 2H = inf {Hfo - rH : r E M] and hence the claim.l In order to establish the characterization theorem for the above setting we need to introduce the following definitions and concepts. First we wish to define the notion of an n-dimensional extended Haar subSpace of order v Of C[a,b]. In doing this, we shall follow the notation and development given in [5]. For complete- ness we first define what is meant by a Haar subspace of C[a,b]. Definition 1.16: A finite-dimensional subspace H of C[a,b] is called a Haar subspace if each nonzero function in H possesses at most n-l zeros, where n = dim H. Let {ui(t)]:=1 be a family of functions in C[a,b] (with each sufficiently differentiable so that what follows is well-defined) and a S t1 S t2 S...S tn S b a given set of points. Define 24 fi1(t1) fi1(t2) .... fi1(tn)l * 1 u2(t1) u2(t2) .... u2(tn) ’COC’n - t1,...,tn O O O fin(t1) Gn(t2) .... Gn(tn) where for each fixed 1: u. t. if t, < t. 1( J) J-l J 3 G (t.) = ui (tj) if tj-r tj-r+1 ... tj, l n. Definition 1.17: The functions u1,...,un will be called an extended Chebyshev system of order v on [a,b] provided ui E CV-1[a,b], 1,...,n * i = 1,...,n, and U > 0 for all choices t S t S... S tn, 1 2 t1,...’tn ti E [a,b], where equality occurs in groups of at most v consecutive values of ti' With the above we are able to define the notion of an extended Haar subSpace. Definition 1.18: An n-dimensional SubSpaCe H of C[a,b] is said to be an extended Haar subSpace of order v, v S n, if there exists a basis for H which is an extended Chebyshev System of order v on [a,b]. Remark 1: It is straightforward to Show that H is an extended Haar subspace of order v if and only if each nonzero element in H possesses at most n - l zeros in [a,b] counting multiple zeros in the following manner: (1) if f(j)(z) = 0, j = O,...,v-1, we say that z is a zero of multiplicity v; 25 (2) otherwise we say that z is a zero of multiplicity = , (j) = _ m min {j. f (z) ¢ 0, j 0,...,v 1}. For a fixed r ='2 E Rn[a,b], we shall write P + rP to q m n m denote the subspace {p +1rq : p E Pn’ q 6 PE] of C[a,b]. It is well-known (see [19]) that Pn + er is an extended Haar subspace of order v = dim(Pn + rPfi) = 1 +-max [n + aq, m + 5p]. Define S(r) = {h E P +‘rP ' h(j)( ) = 0 i = 1 j = 0 m -1] n m . yi , ,...,p, ,..., i . It is clear that S(r) is a subSpace of Pn + rP&. Let us now restrict Pn’ Pm and r to X and view S(r) as a subSpace of C(X). The following lemma, whose proof is modeled after an analogous result from.the work of Perrie (see [19, p. 13]), yields the exact dimension of the subSpace S(r) of C(X). lemma 1.19: dim S(r) = l +-max {n +-aq, m + 3p] - m* (= d). lggggf: Let x1,...,xd be d distinct points in X which are dis- tinct from the interpolating points y1,...,yp. For each i, i = 1,...,d, choose hi 6 Ph + rPh such that hi E S(r) and 11 independent. For h E S(r), g = 2 h(xi)hi is an element of S(r) i=1 and h-g possesses at least 1 + max {n + aq, m + 3p] zeros in X. h (x ) = 6, , i,j = 1,2,...,d. The set {h,]§ is clearly linearly i j d 1 i=1 But the numerator of h-g is an element Of P and maX{n+aq.m+apl g. Thus {h1,...,hd} is a basis for S(r).l III SO h If {g1,...,gd] represents a basis for S(r) then for each x d x E X we shall write x to denote the vector (g1(x),...,gd(x)) E E (E1 = real numbers). If Y is a subset Of X and y is a real- valued function defined on Y, then H{y(y)y : y E Y] denotes the convex hull of the vectors w(y)y E Ed, for y E Y. 26 We conclude our preparatory discussion with an important result due to Salzer [22]. Lemma 1.20: Let f E CS(X) where s = max [mi - 1]. At points lSiSp where q(yi) # 0, the system 2(1) = (j) - .. - '= (q) (yi) f (Y1): J — Oals°°'smi 1: 1 13°°°9P9 is equivalent to p(j)(yi) = (fq)(j)(yi), j = 0,1,...,mi-l, i = 1,...,p. Finally we are able to establish the following characteriza- tion theorem. Theorem 1.21: Let Q: K ~ C(X) be a continuous operator which is pointwise strictly monotone and pointwise fixed at f E K ~ M where K and M have been previously defined. Then the following four statements are equivalent: * (i) r = £;-E M is a best starting approximation for q Q(f) from M. o o A * * (11) 0 E H[o(x)x : x E X(r )} where g(x) = sgn(f(x) - r (x)), * * X(r ) = {X E X = IW(X)(Q(f)(X) - Q(r )(X))| = x _ . * HQ(f) - Q(r )H], {g1,...,gd] is a baSis for S(r ) x and fi = (g1(x),...,gd(x)) where d = max{n + aq , * * m +tap ] +'l - m . (iii) There exist d + 1 consecutive points x < x2 <...< x 1 d+1 P in X ~ U {yi} such that i=1 (a) Iw(x,) - p(r*>(xi>>I = \Iw) - p(r*>\\. i = 1,2,...,d+1, 27 (b) sso{(f - r*(xi))Ail = <-1>i+1sgn{ - r*(x1))A1], i = 1,...,d+l, where 310(1) 310:2) 81(Xi_1) 810%“) 31(xd+1) gd(x1) gd(X2) °°'° gd(xi-1) 8d(Xi+1) "°° gd(xd+1) (iv) There exist d + 1 consecutive points xi 6 X ~ U {yi} i=1 such that * * (a) Iw(o(f>(xi> - p(r >(xi>>| = HQ(f) - ou. i = 1,2,...,d+1, * '+l (b) sgn[[f(xi) - r (xi)]fl(xi)] = (-1)1L sgn{[f(xi) - r*(x.)]fl(x,)} for i = 1,2,...,d+1, where i 1 m1 m u(t) = (y1 - t) ... (yp - t) P if p a 0 and n(t) E 1 if p = 0. Proof: (i) implies (ii): Suppose 0 E H[o(x)§ : x E X(r*)]. By the Theorem on Linear Inequalities [1] there exists h E S(r*) such that o(x)h(x) > 0 * * for all x E X(r ). Set h = p-r q where p E Pn and q E Ph. We then have that h(J)(yi) = O, i = l,..., p, j = 0,1,...,mi-l. * - * Set rx = £;f-LB'. Now there exists A0 > 0 such that q (x) - q ' Aq * Aq(x) > 0 for IAI S x0 and for all x E X since q (x) is positive and q(x) is bounded on the compact set X. IAI*‘ x0, we * * have er M Since r* - r1 = E;.- R;_;_L2: 19* r(P-r *QIB Lh <1 <1 - iq q ”(q -iq) q* -iq and so h(j)(yi) = 0, i = 1,...,p, j = 0,1,...,mi-l, implies that (j) *(j)(yi) = a... i = 1,2,...,p, j = O,l,...,mi-l. Since (y)=r U 28 min{a(x)h(x) : x E X(r*)} > 0. * X(r ) is compact, the number 6 Set E = “S(r) — Q(r*)H and x1 {x e x : o(x)h(x) > %n and 1 and X1 is 1 is a closed subset Of X and thus compact. Iw(x)(Q(f)(x) - Q(r*)(x))I > g]. Note that X(r*) C X Open; hence X = X ~ X 2 By the continuity of Q and the compactness of X2 there exists 11 such that 0 < A1 S 10 and IKI S A1 implies Iw(x)(Q(f)(x) - Q(rx)(x))I < E for all x 6 x2 since Iw(x)(Q(f)(x) - Q(r*)(x))I < E for all x E X2. Set * * E u = ianIHX) - 1‘ (X)I = IW(X)(Q(f)(X) - Q(I‘ )(X))I 2 ‘2' and x E X}- Note that p. > 0. Now choose 1,2 such that 0 < x2 S x1 and h x q 'Aq S %-< If(x) - r (x)I. Consequently IAI S A2 implies IAI S %-. For x E X1, Ir*(x) - rx(x)I S h * q 'Afl (f - r*)(x) and (f - rx)(x) have the same signum function for Hr" - r,\\ -- \xI x 6 X1. For A <;0 with IAI S x2 we have o(x)(r*(x) - rx(x)) = 10(th(X) * q (X)‘AQ(X) * for all x E X1 and so sgn(f(x) - r (x)) = -sgn(r*(x) - rx(x)) * < 0 for all x E X1. Therefore o(x)(r (x) - rx(x)) < O for all x E X1. Hence for f(x) > r*(x) we have f(x)>rx(x)>r*(x) and for f(x) < r*(x) we have f(x) < rk(x) < r*(x). Applying the point- wise strict monotonicity of a at r we find that Iw(x)(Q(f)(x) - Q(rx)(x))l < IWIX)(Q(f)(x) - Q(r*)(x))l s HQ(f) - Q(r*)H= E for all x E X1 and x as described above. Assembling the above re- sults we have Iw(x)(Q(f)(x) - Q(rx)(x))I < E for all x e x (i as above) and so HQ(f) - Q(rx)H < HQ(f) - Q(r*)H. Therefore rA * is a better starting approximation than r . 29 (ii) implies (iii): * Suppose 0 E H{o(x)fi : x E X(r )]. Then by Caratheodory's Theorem [l,p.17]there exist d1(d1 S d+1) positive scalars xi d 1 * with z A- = l and d consecutive points x ,x ,...,x E X(r ) i=1 1 1 1 2 d1 such that d l iElxio(xi)gj(xi) = 0 for J = 1,2,...,d. (1.4) l l i = 1,...,d, j = 1,...,d where x. = x., i = 1,...,d1 and d i i —' d {xi}i=d +1 0({xi}i:1 U [yi}:=1)= ¢. This then implies that there 1 We claim that d = d+l. Suppose d s d. Then det[gj(Xi)] = 0, exists a d-tuple a = (“1"°"ad)’ a ¢ (0,0,...,0) such that d ‘_ . d * Z a.g.(X.) = 0, i = 1,...,d. Set g = 2 o g,. Then g E S(r ) j=1jJ and so g has, in addition to simple zeros at the ;i, i = 1,...,d, zeros of order mi at the points yi, i = 1,...,p. In total, g * x x x * possesses at least d +-m = max{n + aq , m + 5p } + 1 - m +-m = x * max{n + aq , m +-ap ] +-1 zeros. But the numerator of g is an element of Pmax{n+3q*,m+3p*} and so g E 0. This is a contradiction and so d1 = d +'l. Rewriting (1.4) as d+l iizhio(xi)8j(xi) = ”A10(x1)gj(x1)9 J = 1929"°:d and solving by Cramer's rule, we obtain i+l ('1) X10(X1)Ai 3 A1 lio(xi) = i = 2,...,d+l . We now claim that Ai # 0 for all i. On the contrary suppose that Ai.= 0 for some i. Define hi by 30 we 31%) glam) glam) glcxdfl) hi(s) = . . Z . gd(s) gd(x2) ”°° gd(xi-1) gd(xi+1) "" gd(xd+1) Then hi(x1) = hi(x2) =...= hi(Xi-l) = hi( ) =...= = 0 hi(xd+l) * possesses at least d +-m Xi+l * and since hi E S(r ) we have that hi * zeros. But hi i 0 since Pn + r P5 is an extended Haar subSpace * * of order 1 +-max[n +>aq , m +~ap }. Hence we have a contradiction. * Now xi > O and q(xi) = sgn(f(xi) - r (xi)) and so the result follows easily. (iii) implies (iv): Let [21,...,zd_1] be an arbitrary set of d-l consecutive points in X ~ U {yi} and define i=1 81(8) 31(21) °’°°'° g1(zd_1) g(s) = . . . gd(s) gd(zl) ‘°'°°' gd(zd-1) * Note that g E S(r ) since g is a linear combination of the basis * elements of S(r ). Furthermore, g(s) has a nonzero coefficient by the remark at the end of (ii) implies (iii). By construction, * * * g(s) has d-l +-m = max{n + aq , m +|3p ] zeros counting multi- plicities. These consist of a zero of order m1 at each yi and a simple zero at each 21 (the zeros at 21 are simple since g i 0). Hence g changes sign at each 21 and changes Sign at yi if and only if m1 is odd. Set 21 = xi+2, i = 1,...,d-l, for the 31 choice Of xi's in part (iii). Then s1(x1) 31(21) gl(zd_1) 81(x1) g1(x3) gl(xd+1) g(xl) = : = = A2 gd(x1) gd(zl) gd(zd_1) gd(x1) gd(x3) gd(xd+1) Similarly g(xz) = A1. Now if yi1,...,yiq E (x1,x2), then m. +...+-m, m, +...+ m, 11 lq i1 iq sgn A2 = Sgn g(x1> = <-1> sgn g(xz) = <-1) Sgn A1 110(1) * = sgn N(Xz) sgn A1. Thus sgn{[f(x2) - r (x2)]fl(x2)} = 1': * Sgn A2 sgn{if = sgn{[f(x2) — r ]} Sgn 11 sgn u(x1> = * sgn u(xl) * sgn N(Xl) sgn{[f(x2) - r (x2)]A2] —-§§E—KI— = -sgn{[f(x1) - r (x1)]Al] -—;EE—KI. = -Ssn{[f(x1> - r*]n f(xi) implies r*(xi) 2 r(xi). Thus, using (iv), we have that [r*(xi) - r(xi)]ani) 2 O and [r*(xi+1) - r(xi+1)]n(xi+1) S 0 (or conversely) for i = 1,...,d. Set S = r - r*. If S(xi) # 0 and s(x ) = 0, while 1+1) =° ' '= S(xi-l-j-l s(xi+j) # 0, then since (-l)k[(r*(xk) - f(xk))n(xk)] is of one sign for k = l,...,d+l we have that sgn{[S(xi)]H(Xi)l = sgn{[f - r*(xi)]n(xi)} = (~113ssn{[f(xi+j> - r*(xi+j)]fl(xi+j)l = (-l)jsgn{[s(xi+j)]n(xi+j)]. Now we have two cases to consider. 32 First assume that the sum of the mk's such that yk E (xi.xi+j) is even. Then u(xi)n(xi+j) >10 and sgn s(xi) = (-1)jsgn S 0. Furthermore t < d = max{n + aq*, m.+-ap*] +'1 - m* since if t 2 d then b possesses at least 1 +-max[n + aq*, m + ap*] zeros which is impossible since the numerator of h is an element of P From the maxIrIi'oCI*om"*oP*l' * standard interpolation theory we know that there exists g E S(r ) 33 such that g(zi) = g(zi), i = 1,2,...,t. Since a(x)h(x) 2 0 for all x E X(r*), we claim that there exists l > 0 such that o(x)(h(x) +-Xg(x)) > 0 for all x E X(r*). For each i = 1,...,t, choose an open interval, 1(21), about 21 such that o(x)g(x) > 0 for all x E I(zi) and I(zi) fl I(zj) = ¢ for i ¥ j. This we are able to do since q(zi)g(zi) = (C(21))2 : 0 and o(x)g(x) is * N continuous at x = zi. Set Y = X(r ) fl ( fl {I(zi)]). Y is closed i=1 in [a,b], hence compact, and so o(x)h(x) > 0 for all x E Y. Let m = inf{c(x)h(x) : x E Y] and M = inf{o(x)g(x) : x E Y]. Note that m > 0 and M > -m. If M 2 0, let A > 0 be arbitrary; if M < 0, choose A > 0 such that m +'xM > 0. Then o(x)(h(x) + kg(x)) > 0 for all x E X(r*). Since S(r*) is a subSpace Of Pn + r*ph and h,g E S(r*) we have that h +txg E S(r*). Thus, by the Theorem on Linear Inequalities, 0 E H{o(x)§ : x E X(r*)] and so r* is not a best approximation to f E K ~ M. This is a contradiction.. Theorem 1.23: If r* E M is a best starting approximation to Q(f), then r* is unique. “2522:: Suppose r E M is Such that HQ(f) - Q(r)H = HQ(f) - Q(r*)H. Then if g(x) = sgn(f(x) - r*(x)) we have for x E X(r*): (i) if f(x) > r*(x) then r(x) 2 r*(x) and (ii) if f(x) < r*(x) then x ‘ * r(x) S r (x). Hence we conclude that o(x)(r(x) - r (x)) 2 0 for * * p(X) _ P (Xi all x E X(r ). Consequently o(x)(q(x) q*(x)) 2 0, so o(x)(p(x) - q(x)r*(x)) 2 0 Since q(x) > 0 on [a,b]. By Lemma * * 1.20 we have that p-r q E S(r ). Therefore Lemma 1.22 gives p(x) - r*(x)q(x) E 0 and so r E r*. I 34 Finally we shall give a generalization Of a theorem of de la Vallée Poussin, for the problem at hand, which is often useful in estimating the deviation of the best starting approximation to Q(f). * * Theorem 1.24: let f E K ~ M and let r = B;'E M be the best q starting approximation to Q(f) from M. If r E M, {xi]i:i a set . . . p d+l . Of d+l consecutive p01nts in X ~ U {yi], and IOiAi=1 is a set 1—1 of positive numbers Such that (i) IW(X1)(Q(f)(Xi) ' Q(r)(xi))I = A1, (ii) sgn{[f(xi) - r(xi)]n(xi)] = (-l)i+lsgn{[f(x1) - r(x1)]n(xl)], * then min ii S HQ(f) - Q(r >H- i x * Proof: If r E r the result is clear and so we suppose r i r Assume min Ai > HQ(f) - Q(r*)H. Therefore ii > HQ(f) - Q(r*)H, i = 1,...fd+l (where d = max{n + 3q*, m + 3p*] + 1 - m*) and so Iw(x,)>l > Iwo - o(xi>)l. i = 1,2,...,d+1. Now proceeding as in the proof that (W) implies * (i) in Theorem 1.21 we obtain the fact that r r which is a contradiction. Hence min xi S HQ(f) - Q(r*)H.| i Section 3: Computation of an Optimal Starting Approximation In this section we shall examine the problem of computation of a best starting approximation for an Operator 'Q. The characteriza- tion theorems we have developed, especially Theorem 1.9, are of particular importance in establishing computational procedures. From the classical theory an optimal Starting approximation would be computed using a modified Remes algorithm which involves solving a nonlinear system of equations with Newton's method of higher order. 35 However, if the Operator Q satisfies certain conditions a best starting approximation can be more easily obtained. Moreover, the best starting approximation may be independent Of the number Of applications of Q provided this iteration is well-defined. We now wish to consider sufficient conditions on Q for which this behavior occurs. The following definitions and results are due to Meinardus and Taylor [11]. Definition 1.25: Let Q: K a C(X) be a continuous operator. We say that Q possesses Property I at f E K provided for each r E K and x,y 6 x, £152.- £311 implies 2$£l£§2.= EIEISXI and f(x) ’ f(y) f(x) f(y) ’ r(y) r(x) r(y) r(x) . . _ Q r x f(y) < f(x) S l or f(y) > f(x) 2 1 implies 1 f(x) < Hm. f(y) ' Definition 1.26: Let Q: K a C(X) be a continuous operator. Q is said to be one-sided at f provided either Q(k) 2 Q(f) for all k E K or Q(k) S Q(f) for all k E K. Theorem 1.27: Let K be a convex subset of C(X) and Q: K a C(X) be pointwise strictly monotone, pointwise fixed and possess Property I at f E K where Q(f) f and f > 0. Norm C(X) by HhH = H%Hm (h 6 C(X))- LCC r 5 E R:[a,b] (m,n,a,b fixed) be the best relative approximation to f from R:[a,b] with deviation 1; that . f-r . f-s n , is, Hmf-‘H0° = 12f “-E—Nm = A. If M = K H Rm[a,b] is nonempty SElea Sb] _ n l l and relatively open in Rm[a,b] and St E M for 5 6 [1+1 ’ 1'1] l 1 . . then there exists 60 E (1+1 , I'AP) for which 60r is the best starting approximation for f (with reSpect to Q). 36 Proof: First we observe that A < 1 since arbitrarily small positive functions exist in R:[a,b]. From the standard Chebyshev theory we know that there exists N = 2 + max{n + aq, m + 3p} consecutive points, x1 < x2 <...< xN, in X such that (ii) sgn(f(xi) - r(xi)) = (-l)i+lsgn(f(x1) - r(x1)), i = 1,...,N. f(xi) - r(xi) f(xi) f-r f (i) Without loss Of generality we may assume that r(xl) > f(xl). It . . . . l _ is ea31ly seen, uSing (i) above, that 1+). r(xl) - f(xl) and 14;}:- r(x2) = f(x2) and in general 1 - A S If—Ef] S 1 + 'A- Hence, in r(x1)r(x2) Yr(X ) view of the above results, 2 5.112 2 and so -——1—-— 2 f(x x1) f(x) f(x x:) f(x1> 'Yr(x) Yr(X2 ) 1 1 _f_(;)_2 fx( ——)-2,where yEIm,fi],for all xEX. By Pro- perty I, swam Q(Yr) (x1) om) (x > 1-———— Smax l--—— ,l-—————2— f(x) f(xl) f(xz) f("1+2) ' r . decreases to a: an - —f-(x—2)- increases from 0 as y 37 decreases to 1:; . Similarly, 1 - ———?Y;Iy— increases from 0 y increases to -:—- an - —————————- decreases to 0 as y l x f(xz) 1 . 1 Q(Yr)(xl) d Q(Yr)(X2) increases to l:{ . Since both - -_—?Y;;7—- an - ___f?;;7_ are continuous functions of y there exists E —l— -—l— such ’ YO 1+), ’ 1-x Q(vor)(x1)I _ p(vor)(x2) o-p that 1 - f(x ) I — - f(x ) Hence f(x ) l 2 i g Q(Yor)(xi) _ Q(f)(X) - Q(YOrHX) _ Q(f) - Q(Yorj ' f(x ) " "'3" f(x) ’ f | 1 XEX co = HQ(f) - Q(yor)H. Finally, it is clear from the choice of y that sgn(f(xi) - Yr(xi)) = sgn(f(xi) — r(xi)). Thus, by Theorem 1.9, yor is the best starting approximation for f.I Definition 1.25 and Theorem 1.27 of Meinardus and Taylor have rather natural analogs in the setting of uniform approximation (“(10 '3 1)~ Definition 1.28: The Operator Q is said to possess Property J at f E K if for each r E K and x,y E X, f(x) - r(x) = f(y) - r(y) implies Q(f)(X) - Q(r)(X) = Q(f)(y) - Q(r)(y). and 0 S f(X) - r(X) < f(y) - r(y) or 0 2 f(x) - r(x) > f(y) - r(y) implies IQ(f)(Y) - Q(r)(Y)I > IQ(f)(X) - Q(r)(X)I- Theorem 1.29: Let Q: K ~ C(X), K be a convex subset of C(X), and M = K n R:[a,b] be a relatively open subset of R2[a,b] with m S n. Assume Q is pointwise Strictly monotone, pointwise fixed and possesses PrOperty J at f E K ~ M. If r E R:[a,b] is the best uniform approximation to f from R:[a,b] with deviation A 38 and if r +'c E M for c E ['Ash] then there exists c0 E ('131) for which r +-c0 is the best starting approximation to Q(f) from M. EEEBEF Since r is the best uniform approximation to f from R;[a,b], there exist N points, x1 <...< XN’ in X, N = 2 + maxfm + 5p, n +-aq], such that (i) If(xi) - r(xi)I = Hf - rH, i = 1,...,N .. i+l . (ii) sgn(f(xi) - r(xi)) = (-l) sgn(f(x1 - r(x1)), i = 1,...,N . Now f(xi) - r(xi) = f(xi+2) - r(xi+2), i = 1,2,...,N-2 and so by Property J Io - oI = IQ(f)(Xi+2) - p(r)(xi+2>l. i = 1,...,N-2. Also by Property J we see that for any c E [-I,x], IQ(f)(x) ' Q(r+c)(x)I S m3X(I§(f)(X1) ‘ Q(r+c)(x1)I, I¢(f)(X2)-Q(r+c)(x2)I). Note that for each r and x, Q(r+c)(x) is a continuous function of c. Without loss of generality assume f(xl) > r(xl). Using the fact that Q is pointwise strictly monotone and pointwise fixed at f E K we have that IQ(f)(x1) - Q(r+c)(x1)I is a strictly decreasing func- tion of c which tends to 0 as c tends to A and IQ(f)(x2) - Q(r+t)(x2)I is a strictly increasing function of c which tends to zero as c tends to 'A- Since both I§(f)(xl) ‘ Q(r+C)(x1)I and IQ(f)(X2) - Q(r+t)(x2)I are continuous functions of c there exists cO E (~K,K) for which |Q(f)(x1) - 9(r+co)(x1)| = IQ(f)(x2) - Q(r+t0)(x2)|. Thus IQ(f)(xi) - Q(r+c0)(xi)I = HQ(f) - Q(r+co)H, i = 1,2,...,N. Further- more. since co 6 01.1). sgn(f(xi) - (ti-co) (1(1)) = (-l)i+lsgn(f(xi+1) - (r+c0)(xi+1)) and so appealing to Theorem 1.9 39 we have the desired result. I Theorem 1.30: Let Q: K d K satisfy the following properties: (i) Q is continuous (ii) Q(f) = f (iii) Q is pointwise strictly monotone at f E K ~ M (iv) Q is a one-sided operator at f (v) Q possesses PrOperty I (Property J) at f . Then Qm = Q(Qm-l), m = 2,3,... has all the same properties as Q and, moreover, the best starting approximation for Q(f) is also the best starting approximation for Qm(f), m = 2,3,... . .ggggf: The first part of the conclusion follows from Corollary 1.6 and a simple inductive application of Property I (Property J). For the second part let us suppose, without loss of generality, that Q(k) 2 Q(f) = f for all k E K and that we are dealing with relative approximation. Now if r = 5- is a best starting approximation for Q(f) then there exist N points {xi}¥ 1___1;:x,N=2+ max[n + aq, m + 5p], such that x1 < x2 <...< xN and Q(r)(x.) - f(X.) (i) i i I 21£l_:_£I , i 2 1,...,N f(xi) f m (-l)i+lsgn(f(x1) - r(x1)), i = 1,2,...,N. <11) sgn(f(xi> - r(xi>) Now by applying Property I to these points m times it is clear that r is also the best starting approximation for Qm(f) = f .| In attempting to construct a theorem analogous to Theorem 1.27 for the case of restricted range approximation certain difficulties arise. The multiplicative shift of the best relative approximation to f from R;[a,b] may well remove us from the approximating class. 40 However in one particular setting a result can be obtained. If L(x),u(x) E C(X) denote the upper and lower constraining curves for the restricted range problem, take L(x) = f(x) or u(x) = f(x) where f(x) is the function we desire to approximate. Without loss of generality take L(x) = f(x) and set K = {h E C(X): f(x) S h(x) S u(x)}. This situation will be described as modified one- sided approximation from above since the usual one-sided approxima- tion would have u(x) E m. In this setting we are able to state the following analog of Theorem 1.27. Theorem 1.31: Let Q: K » C(X), K = {h E C(X): f(x) S h(x) S u(x)] where u(x) E C(X), f > 0 on X, and C(X) is normed by HhH = H%Hm. Further suppose that Q(f) = f, Q is pointwise strictly monotone, pointwise fixed, and possesses PrOperty I at f. Let r E M be the best relative approximation to f from M where M = K O R;[a,b]. Then r is the optimal starting approximation for f from M (with respect to Q). ‘nggf: The proof follows directly from Theorem 1.14 and the fact that Q possesses PrOperty I at f.| Remark 1: In applying the above theory one may find it more efficient (in terms of the computer) to compose different operators (each of which defines an iteration procedure) rather than iterating with a given Operator. In view of this we state the following: suppose Q: K ~ C(X) possesses PrOperty I at f E K, Q is one-sided at f and I: L ~ C(X) possesses Property I at Q(f) where Q(K) C L. If w(f) Q(f) = f then YQ possesses Property I at f E K. WlLJ this Observation and the results in Section 1 all of the theorems of this section may be restated for the composition Operator YQ or more 41 generally for the composition of operators Y1,...,Yk, provided the domains and ranges mesh correctly and each of the Operators Yi possesses the appropriate properties. CHAPTER II APPLICATION TO THE NEWTON OPERATOR AND ASSOCIATED RESULTS Section 1: Introduction and General Theory In this chapter we shall apply the theory of Chapter I for a special choice of Q, namely the Operator associated with the well- known Newton iteration scheme. First set 2 S = {f e c (ops): f',f" s4 o for all x > o and image f = (o,oo)l- The choice of (0,m) is quite arbitrary; actually, one could select (-mym) or some other region on which to work. Note that domain f”1 ==(O,m) Since image f = (0,m). For a fixed x E [a,b] C -1 , . (0,m) we can solve f (y) - x = 0 by Newton 3 method tO obtain the value of f at x where f E S. In particular, if y0(x) = y(x) is the initial guess to f(x) then inductively we define yn(x) by yn - {f'1(yn_1 - xlif'If‘1>31, o = 1,2,... (2.1) Of course we must insure that yn_1(x) > O, n = 1,2,... so that f.1 is defined. The sequence (2.1), which represents the Newton iteration scheme for determining the unique zero of the equation f-I(y) - x = 0, converges quadratically to f(x) provided the initial guess y0(x) is Sufficiently good. As mentioned, the above con- sideration is for a fixed value of x. Our goal is to be able to calculate f(x) for all x E [a,b] on a computer. To accomplish 42 43 this we shall select a class of functions M (Specifically M C R:[a,b] for our purposes) which are easily programmed and then select a member of M as the initial guess. Precisely, we wish to find an element r of M for which yn r(X) - f(x) f(x) yn S(X) - f(X) f(x) 5 co 00 for all s E M where yn S(x) denotes the n-th Newton iterate at 3 x with initial guess s(x). Numerically the above method would be applied to functions f for which f.1 is easily evaluated such 1 as f(x) = x“, n = 2,3,... . This particular problem was examined by D.G. Moursund and G.D. Taylor [16] and is a generalization of the subroutine used to calculate /r on a computer Such as the CDC-3600. We shall now Show that the theory we have develOped in Chapter I is also applicable to this problem as well as others. The first problem confronting us is that Of determining a suitable convex subset K of C[a,b] such that the operator N f defined by Nf(h)(x) = h(x) - {f'1> — x}{f'[f‘1(h(x>>ll maps K to K (into or onto). It is imperative that we examine two cases: Case 1: Fix f E S and assume that either f' > 0 and f" < 0 on (0,m) or f'< 0 and f” < 0 on (0,m). Let K = [h E C[a,b]: h(x) > 0 for all x E [a,b]]. 44 Setting N(x,y) = y - {f-1(y) - x]{f'[f-1(y)]] and calculating 32%;;113 it is easily seen that Nf at f and one-sided from above at f. It is also clear that is pointwise strictly monotone N ' K a K is continuous and Nf(f) = f. Observe that the class of f 1 functions f(x) = xn, n 2,3,... are suitable choices for f. Case 2: Fix f E S where either f' > 0 and f" > 0 or f' < O and f" > 0 holds on (0,m). The choice for K in this setting is somewhat more difficult since N is a one-sided operator from f below and consequently large values of h(xo), for fixed x0 E [a,b], may yield negative values for Nf(h)(x0). Since we wish to iterate with N and we have assumed the image of f is (O,m), we must f bound the members of K from above. Specifically, for fixed f E S as above, we wish to find, if possible, a function ¢(x) E C[a,b] such that if K = {h E C[a,b]: 0 < h(x) < ¢(x) for all x E [a,b]] then Nf: K e K. If we set N(X:Y) = y ‘ {f-1(Y) ‘ Xllf'lf-1(Y)]} (as above) and calculate 321%;123 it is clear that for each fixed x N(x,y) is a strictly increasing function of y for 0 < y < f(x) and a strictly decreasing function of y for y > f(x). Moreover, N(x,y) > 0 for 0 < y < f(x). Let us now assume that for each fixed x E [a,b], lim N(x,y) = -m. This guarantees us that y-Hu: for each x E [a,b] there exists yx > 0 such that N(x,yx) = 0 (clearly yx > f(x) for each x E [a,b]). To construct the func- tion ¢(x) mentioned above we shall make use of the Implicit Function Theorem. First we have that N(x,y) is defined on 45 1 2 1 1 [a,b] x E+_C E where E+_= {s e E : s > 0}. Let x0 6 [a,b] be arbitrary but fixed and let E E: be such that N(x0,y0) = 0. yo Then the following holds: (1) [a,b] X [y: y > f(x0)] = “(X0 is a neighborhood ’yo) of (x0,y0) in [a,b] X Bi, N(x,y) is continuous on n and M 2 _ if'lm - xlf'if‘liyil (X 93' ) ay . '1 0 0 f [f (y)] is continuous on “(xosy0) by the assumptions on f. (iii) EHAEJXI. # 0 . 3y (x0.y0) Hence, by the Implicit Function Theorem, there exist neighborhoods “x0 of x0, “yo of y0 and a function ¢O(x) defined on “x0 such that (iv) for all x e “x , ¢O(x) E fly , (x,¢0(x)) E “(X y ) 0 0 0,0 and whom) = o. (v) ¢O(x) is uniquely determined by (iv) (vi) ¢0 is continuous on “x 0 (vii) ¢0(xo) = YO . Now consider {Hx: x E [a,b]]. This is an open cover of [a,b], which is compact, and so can be reduced to a finite subcover “x ,...,Hx . 1 For each i = 1,2,...,n we have ¢i(x) defined on “x and con- i tinuous there. Suppose “x O fix # ¢ for i # j. We wish to Show that 1 J (x) = (x) for x E O . Let 2 E I n . Then ¢i $1 'hi 'Wj Ihi TKj N(z,¢i(z)) = N(z,¢j(z)) = 0 and ¢i(xi) = y1 > f(xi). 46 Claim: ¢i(z) > f(z). Assune to the contrary. Then ¢i(z) < f(z) since ¢i(z) = f(z) implies 0 = N(z,¢i(z)) = N(z,f(z)) = f(z) > 0. Define gi(x) = ¢i(x) - f(x). Then gi is continuous on TH with gi(xi) > 0, i 81(2) < 0. Hence there exists 5 E “x such that gi(g) = 0, i Therefore ¢i(§) = f(g) and so 0 = N(§,¢i(§)) = N(§,f(§)) > 0. This is a contradiction and thus the claim. Similarly ¢j(z) > f(z). Since N is decreasing for y > f(z) and N(z,¢i(z)) = N(z,¢j(z)) = 0 we have that ¢i(z) = ¢j(z). Consequently we are able to define a function ¢ on [a,b] via ¢(x) = ¢j(x) if x E “x., j = 1,...,n. The function ¢ is continuous on [a,b] J and ¢(x) > f(x) > 0 for all x E [a,b]. Set K = {h E C[a,b]: 0 < h(x) < ¢(x) for all x E [a,b]]. Then if h E K, Nf(h)(x) S f(x) < ¢(x) for all x E [a,b] and from the previous discussion Nf(h)(x) > 0 for all x E [a,b]. Hence, for the above choice of K, Nf: K a K and so iterating with Nf via N? = Nf(N?-1), m = 2,3,... is well-defined. As in Case 1 we know that N is continuous, Nf(f) = f and N is pointwise f f strictly monotone at f. Moreover, Nf is one-sided from below at f. Remark 1: For the function f(x) = ex (which falls in Case 2), the function ¢(x) = e1+x satisfies N(Xsel+x) 0 for all x E [a,b] where N(x,y) is defined by N(x,y) y(l + x - Ln y). Hence we set 1 K = [h E C[a,b]: 0 < h(x) < 6 +x for all x E [a,b]]. 47 With the preceding discussion in mind we can state the follow- ing analog of Theorem 1.9 for both of these cases (with the reSpective K's defined above). Theorem 2.1: Let f E S, K be as above and M = K n R;[a,b] (fixed m,n). Then rk ‘lfii E M is the unique best starting approximation for f with respect to the k-th Newton iteration if and only if there exists {xi]§=1 c [a,b], N = 2 +-max{n +qu, m + apk], with x1 < x2 <...< xN for which f - N:(rk) f (i) f(xi) - n‘f‘skxxi) . f(xi) a, i=1,2,...,N (ii) sgn(f(xp - rk) = <-1)“1sgn- rk(x1>>. i=1,2,...,N. Section 2: Optimal Starting Approximations for Roots, Exp(x) and Ln(x) In general the existence of a best starting approximation is a rather difficult problem which depends upon the particular function f and the interval [a,b]. For the Special case that f(x) = xa, o E (0,1) or f(x) = ex existence has been established and, more- over, the best starting approximation is independent of the number of iterations. For f(x) = xa, o E (0,1), set K = {h E C[a,b]: h(x) > 0 for all x E [a,b]] where 0 < a < b. The Operator N f is defined by Nf(h)(x) = 01%;" 1)h(x)+—l'—}:—— , for h E K. h" (x) 1 In the case of f(x) = ex, set K = {h E C[a,b]: 0 < h(x) < e +x for all x E [a,b]] and define Nf(h)(x) = h(x)(1 +-x - Ln h(x)) for h E K. If r E M denotes the best relative approximation to 48 ex from R:[a,b] with error A» then we must apparently require that A < Eii- in order to apply Theorem 1.27. However this re- quirement will be shown to be unnecessary. Before stating the next theorem due to Meinardus and Taylor [11], we introduce the following notation: for each a E (0,1), let to denote the best relative . . n . . . . approximation to xa from Rm[a,b] With dev1ation Ia; that is, x - r xa o = inf - S = A . xa n xa o s a b €Rm[ 9 1 m x Let r denote the best relative approximation to f(x) = e from n X r eX s Rm[a,b] with deviation 1; that is, x = inf n e e a) SERm[a,b] 00 Theorem 2.2: For m = 1,2,... the following is true: (a) The best starting approximation for m Newton iterations for the calculation of xa is Yoro where (1 + Ve-l - (1 - ia)e'1 0’ 1 V = 2 5-1 ’ B = 3 ° 2(p-l>ia<1 - he) (b) The best starting approximation for m Newton iterations for the calculation of ex is yr where y = expi§§ (21 + (l-i)tn(1-i) - (1 + X)Ln(l + i))] s 1 1- 5" “fig? 7‘ ——1 1-x2 Proof: The proof of (S) appears in [28] and will be omitted. For (b) we Shall apply Theorems 1.9 and 1.30. First we shall Show that N = N x possesses PrOperty I at f(x) = ex where N(r)(x) = e r(x)Q - Ln Eli-l) . If r E K (as defined earlier), y,z E [a,b] e 49 and r(y) = r(z) To 2 then we clearly have N(r)(y) = N(r)(z) 9y e eY ez obtain the second condition necessary for Property I we set m(t) = 1 - t +'t Lnt (for t > 0) and examine m'(t). Since ¢'(t) < 0 for 0 < t < 1 and m'(t) > 0 for t > 1, w(l) is the only local minimum for ¢(t) when t > 0 and hence the second con- dition for Property 1 is also satisfied. Next we shall show that the best relative approximation, r, to ex belongs to K = [h E C[a,b]: 0 < h(x) < e1+x for all x 6 [a,b]}. This follows from the fact that (1438‘s r(x) s (1 + we" and 0 < x < 1. Pro- ceeding as in the proof of Theorem 1.27 we find that yr has an error curve of the type described in Theorem 1.9 where 1 y = eé-ibzx -l-— . The value of y is found by solving the 1-12 equation N(Yr)(x1) N(Yr)(x2) l - --j;———- = 1 --——-::———- l 2 e e x1 x2 e where r(xl) = (1 + x)e and r(xz) = (l - x)e . Since 0 < y < 2 we have that yr 6 K and so by Theorem 1.9 yr is the best starting approximation for ex with respect to N. Furthermore, by Theorem 1.30, yr is the best starting approximation for ex with respect to Nm (m = 1,2,...).I The aforementioned Property J is a rather natural analog of Property I for the case of uniform approximation. The Newton operators used for approximating the functions f(x) = eX and f(x) = xa, a 6 (0,1) fail to possess Property J and hence Theorem 1.29 does not apply. However, the Newton Operator for approximating 50 f(x) = Ln x does possess PrOperty J as will be shown. Incidentally, the Newton Operator for approximating Ln x fails to possess Property 1. We now turn our attention to the operator N E NLnx' For 0 < a.( h, set K B {h E C[a,b]: h(x) >.Ln x - l for all x 6 [a,b]} ' = . __X_-_ a: _ [Ln x-h(X)] and define NLn x(h)(x) h(x) 1 +-eh(x) h(x) l + e for h E K. It is straightforward to show that N E NLnx : K a K, is pointwise strictly monotone at Ln x and is one-sided from above. To prove that N possesses Property J at Ln x we define w(t) = (t-l) + e-t and examine m'(t). Since > O for t > 0 m'(t) = 1 - e-t = O for t 0 , the desired result is obvious. < 0 for t < 0 With the above we can prove the following result: Theorem 2.3: Let N a NLn x denote the Newton operator for approxi- mating f(x) = Ln x, K = {h E C[a,b]: h(x) >.Ln x - 1 for all x 6 [a,b]} where 0 < a < b and M.= K n R;[a,b] where m s n. The best starting approximation (from M) for k Newton iterations for the calculation of Ln x (in the uniform norm) is r* + co where r* is the best uniform approximation to Ln x from REEa,b] with deviation A (we assume 0 < 1 < 1) and c0 = Ln filfl%—A . .EEQQES We have already noted that N is pointwise strictly monotone at Ln x, pointwise fixed at Ln x, possesses Property J at Ln x, maps K to K, and is one-sided from above. Since x<< l we also have that r* 6 M. Proceeding as in Theorem 1.29 we find that r* +-c0 has an error curve of the type described in Theorem 1.9 where c0 = Ln‘§l%E-L . The value of cO is found by solving the 51 equation \Nan x)(x1) - N(r" + c>(x1>\ = \Nun x>(x2>\ for c, where f(xl) - r*(x1) = x and f(xz) - r*(x2) = -x- Since * ,Elfl%_k.> l we have that cO > O and so r + c0 6 M. ThuS, by * Theorem 1.9, r +cO is the best starting approximation for Ln x * with respect to N. Furthermore, by Theorem 1.30, r + c0 is the . . . . k best starting approx1mation for Ln x With respect to N , k = 1,2,... . Hence we have the desired result.| Section 3: An Associated Operator Let us once again turn our attention to the Newton operator N a N x defined by N(h)(x) = h(x)(l +~x - Ln h(x)) (h E K as previgusly defined) used for approximating f(x) = ex. Iterating with this operator is computationally impractical since the time required for the evaluation of the function Ln x is approximately that for the evaluation of ex (say on the CDC-3600). To improve the situation we would like to replace the logarithm function in the above formula by a rational function r E R; with m,n sufficiently small as to make the rational function more computationally desirable. At present the value of this scheme is somewhat questionable. How- ever, if we define Nr(h)(X) = h(X)[1 +‘X - r(h(X))] , for h an element of some convex set K' with Nr: K' a K' and r to be determined then we can show that an optimal starting approxi- x . v . mation rv(x) to e With reSpect to Nr (v = 1,2,...) eXists. 52 Let x 6 [a,b], 0 < a < b. Observe that for h(x) s ex (h 6 K' c K) we have N(h)(x) 2 h(x)(1 +‘x é Ln ex) = h(x). Since ex+1 - ex is a continuous function on the compact set [a,b], there exists 6 > 0 O 6 such that ex+1 - ex 2 60 > 39- for all x E [a,b]. Furthermore, for fixed x, N(x,y) = N(y)(x) is a continuous function of y(x), is monotone decreasing for y 2 ex and N(x,ex+1) = 0. Hence 6 + N(x,ex 1 - 59) = 60(x) > 0. Set K' = {h E C[a,b]: eo(x) S h(x) s 6 ex+1 - 59}. By compactness and continuity considerations, eo(x) > O for all x 6 [a,b] and so there exists a > 0 such that 30(x) 2 a- 6 Similarly, there exists 6 > O for which ex+1 - 59-5 6. Thus we x+l 60 have 0 < a < B and a s 30(x) S h(x) s e - §—-S B for all h E K'. Let r(y) be the best one-sided uniform approximation to Ln y from below from R;[a,5] and suppose X = “Ln y - r(y)“ m . L [0’38] Define the operator Nr by Nr(h)(x) = h(x)(l +ix - r(h(x))) where h E K'. It is clear that Nr(h)(x) 2 N(h)(x) for all h E K' and x e [a,b] since a s h(x) s B for x 6 [a,b] and r(y) 5 Ln y for all y 6 [a,b]. Claim: If r defined above belongs to a sufficiently large class of rational functions (that is, m + n is sufficiently large) then N : K? ~ K'. r £991: For com S h(x) s e". Nr 2 N(h)(x) 2 h(x) 2 60(X) and so Nr(h)(x) 2 30(x) for h E K' (regardless of the class r belongs to). Now choose m,n sufficiently large, say - . . . x+1 x m = m0, n — no, such that m0 + n0 is minimal and e - e 2 6 6 (l-x)§Q-+-xeb+l. This we can do since ex+1 - ex > 59- for all x 6 [a,b] and A a O as m,n a m (in fact as n a m). We shall 53 now consider Nr only where r is the best one-sided uniform approxi- n mation to Ln y from below from R:[a,B] 2 Rm0[a,B]. For such r, 0 x+l 60 Nrchux) - N(h)(x) = boom h(x) - r(h(x))) s w(x) s Me - 2—> s 6 b+l x e - A 2—0 K6 16 Therefore Nr(h)(x) s N(h)(x) + x eb+1 - -§9.g ex + x eb+1 - —§9 6 X6 6 S ex+1 _ (1_x)§g _ eb+1 + x eb+1 _ _§g = ex+1 _ 59" Hence Nr: K' a K' for r described above and so we are able to iterate with the operator Nr. With the above definitions of 60, r, 1 and K' we are able to state the following existence theorem for the operator Nr' Theorem 2.4: Let K' and r be as above for the fixed interval [a,b] and let M = K' n R;[a,b]. (Here r is fixed and subject to the above restrictions and m,n are arbitrary but fixed.) Then for any arbitrary but fixed natural number k there exists 3* E M such that “w(ex - N:(s*))H m s “w(ex - N:(S))H m for L L a,b] all s E M Where w is any continuous positive weight function on [a.b [a,b]. (D Proof: Select a sequence {sn}n=l’ sn G M, such that k . k 1m l\w>um = mf Hw>um (M, = M ., > ndm SEM L [3’ which exists by the definition of infimmm. Note that sn 6 M for 6 all n implies a s 30(x) s sn(x) s ex+1 - 59 s B for all m . . x 6 [a,b], n = 1,2,... . Thus {sn(x)}n=1 is a uniformly bounded sequence of rational functions and hence, by Lemma 1.12, there exists a uniform bound on the coefficients of all the sn(x). Therefore 54 there exists a subsequence of {Sn}00 (which we shall also denote n=1 w o — — a a by {Sn}n=l) such that lim sn(x) - s(x) (a rational function) for [I'm all x 6 [a,b] except for points which are the zeros of the denominator of s(x). If {xiz i = 1,...,L} denotes the zeros of the denominator of s then it is clear that L s m. Using the uniform boundedness of the sequence {s1}, it is straightforward to show that each xi is a removable singularity of 8. Upon cancellation, we obtain a * n rational function 3 E Rm[a,b] which We claim is the solution we 6 * seek. Observe that eo(x) S s (x) s eX+1 - EQ- and so 30(x) S 6 * N:(S )(x) s ex+1 - 59-. We also have that if x0 6 [a,b] and * * 11m sn(x0) — 8 (x0) then lim Nr(sn)(XO) = Nr(s )(xO). Inductively W n_m * We may conclude that if x0 6 [a,b] and lim sn(x0) = 5 (x0) then n—m * lim N:(sn)(x0) = N:(S )(xo). Let c > 0 be given. Then there exists n-Ioo N = N(e) such that “w(eX - N:(sn))\\co S I +‘e for all n 2 N where I = inf “w(ex - N:(s))um. For any x0 6 [a,b] ~ U {xi}, SEM x i=1 ‘w(x0)(e O - N:(sn)(x0))‘ S I + e for n 2 N and so X X \w(xo>(x0>>\ = ii: \w>H = max \w>\ = r m x€[a,b] r sup \W(x)(eX - N:(s*)(x))‘ s I + e. Hence ”w(eX - N:(s*))\\co = x€[a,b] x# xi inf “w(ex - N:(x)>\\m . I sea CHAPTER III FURTHER EXAMPLES OF OPERATORS DEFINING ITERATIVE SCHEMES Section 1: Definition and Basic Results In Chapter II we were concerned exclusively with iteration using Newton's method. We shall now consider other iterative methods for the solution of equations and examine them for various properties which have been defined. First we introduce the important concept of order which affords us a means of classifying the iterative schemes which we shall discuss. The following definition is due to Traub [30]: Definition 3.1: An iteration function ¢fz E1 a E1 defined by ¢f(xk) = xk+1, k = 0,1,2,... for finding a root 0 of the equation f-I(y) - x = 0 (fixed x) is said to be of order p (or have order of convergence p) if there exists a nonzero constant C such that ~ C as k a m. The number C is called the asymptotic error constant. Lemma 3.2: If the order of an iteration function exists, then it is unique. Proof: Assume the iteration function Tf has two orders, p1 and p2. Set p2 = p1 + 6, 6 > 0. Then ‘¢f(xk) ' 0‘ = lim ‘¢f(xk) ' 0‘ 1' = im Pf+6 C2 , k—coo P 2 k—oco 55 56 1¢f(xk) - a‘ m p = O, which is a contradiction. I 1 and 11 k—aoo ‘xk ' 0" Remark 1: The iteration functions with which we are concerned are continuous one-point iteration functions; that is, each successive ' a iter te xk+1 iterate xk. No old information is reused. Remark 2: A detailed discussion of order of convergence and related is obtained using only information from the previous topics may be found in Traub [30]. With each iteration function ¢f(x we can associate k) = Xk+1 an iteration operator of: S H S C C[a,b] Via Qf(sk) = Sk+1 for approximating the continuous function f E C[a,b]. The subset S of C[a,b] depends upon f and [a,b]. We now embark upon a study of iteration operators 6 associated with Known one-point iteration f functions ¢f for f(x) = ex and f(x) = xp, p > 1, p an integer. The one-point iteration functions ¢f which we shall be concerned with are order-preserving Pade rational approximations to a certain class of iteration functions generated by inverse hyperosculatory interpolation at a single point. This material first appeared in a paper of Traub [31] and is presented in detail in Chapter 5 of his book [30]. The iteration functions mentioned are all of integral order and many are.widely known and have other origins (suitable reference will be made if such is the case). Since linear conver- gence (convergence of order 1) is not very interesting nor practical we commence with a study of iteration functions of order 2. We shall refer to the schemes generated by iteration functions (operators) as iterative schemes. 57 Section 2: Iteration Functions of Order 2 1. First, we shall only mention that the Newton iteration function already discussed has order of convergence 2. 2. The only other iterative scheme of order 2 which seems to exist in the literature is Newton's method for computing roots using the P function g(y) = X-S—§-, p > 1, p an integer. Applying Newton's Y method to this function, we obtain the iteration function ¢f(xn) = x P [Tn ((p+1) - ii). For 0 < a < b. define K = W“ 6 C[a’bl‘ 1 o < h(x) < ((p+1)x)p for all x 6 [a,b]} and @f(h)(x) = X P héJ-{l-((p+l) - £E£§22—-) for h E K. With these definitionslit isl P easily checked that Q is continuous, é ° K a K and §f(xp) = x . f f° Set y(t) = %'((p+l) - tp). Then ¢'(t) = £31 (l-tp) and so < O, t > 1 y'(t) = 0, t = 1 Therefore of is pointwise strictly monotone > O, 0 < t < 1 . l l at x , p = 2,3,..., possesses Property I at xp and is one-sided from .1 below at xp. (It should be remarked that the function y(t) analyzed above actually only yields the fact that 9f possesses Property I. However, the argument to obtain 6f pointwise strictly monotone is entirely analogous and shall be omitted. This format will be followed throughout our analysis.) In order to apply Theorem 1.27 we must 1 require that if rp denotes the best relative approximation to xp from R;[a,b] (m,n arbitrary but fixed throughout this discussion) . . ._l__ ._l_. With deviation xp then 6rp E M for 6 E [1+xp a 1_xp }. To insure 1/p - this we require that 1 s (p+1) which is apparently a rather P (p+1)1/p + 1 58 severe restriction on 1 for large p (that is, r must be a very P good approximation to xllp). If we so restrict xp’ then Theorem 1.27 1 1 . o d ° —_ — is applicable an there ex1sts yp €.(1+mp 9 1_xp > such that y r P P is the best starting approximation for x p with respect to of. Since iteration is well-defined and of is a one-sided operator we have that yprp is the best starting approximation for x1]p with k reapect to 6f, k = 1,2,... . Analyzing the proof of Theorem 1.27, it is clear that yp is the unique solution, in the above interval, to the equation ®f(YPrP)(X1) - 1 = @f(vprp)(xz) _ 1 x1/p x1]p l 2 1/ 1/ . where rp(x1) = (1+7‘p)x1 p and rp(x2) = (l'kp)X2 p. Solv1ng, we 1/p d ZIP(p+1) f' h = In t at Y” (1+x )p+1-<1-x >p+1 P P Section 3: Iteration Functions of Order 3 1. The first iteration scheme of order 3 to be considered is attributed to Halley (see [30]) and, as pointed out by Traub, has the distinction of being one of the most frequently rediscovered iteration functions in the literature. A recent rediscovery is due to J.S. Frame [3]. If we wish to find a root of the equation g(y) = f-1(y) - x = 0 (fixed x) then the iteration function ¢f is defined by s(x“) xn+1 = ¢f(xn) = xn - ° , g") g (XII) + 2 g I (xn) S9 A. First, let us define g(y) = Ln y - x. Then g(y) = 0 is equivalent to y = ex (for fixed x). For this choice of g the Halley iteration function becomes 2 + x - Ln x x = ¢ (x ) = x n n+1 f n n 2 - x + Ln xn In order to approximate eX on an interval [a,b] (a,b arbitrary with a < b) let us put K = [h(x) E C[a,b]: h(x) > ex-2 for all x E [a,b]} and define the associated iteration operator = 2 +-x - th(x)} . . ._ §f(h)(x) h(x) [ 2 _ x +‘Ln h(x) for h E K. With these defini tions Q K a C[a,b]. If we wish to iterate with the operator 6 f: f then we must further restrict K. We shall omit the restriction and remark that it is straightforward. Clearly 6f is continuous for h e K, §f(ex) = ex and Q is pointwise fixed at h E K. Setting 2 - Ln t -2 . ¢(t) ='t [a—quE—E] for t E (e ,m), we find that ¢'(t) = 2 - LL“ t) s 0. Thus y(t) is decreasing for t > e-2 and so (2 +-Ln t) . . . . X 6f is clearly p01ntWise strictly monotone at e and possesses Property I at ex. In order to apply Theorem 1.27 we must require n l 1 that 6r 6 M — K D Rm[a,b] for 6 E [1+X , 1'}.J where r denotes x n . the best relative approximation to e from Rm[a,b]. To insure 2 e - 1 . . . this we must demand that 1 < -§--’ which is a very mild restric- e + 1 tion on 1 since we always have I < 1. Let us remark that it may indeed be the case that we need not restrict k at all as was dis- covered earlier in the discussion of the Newton operator for approxi- x . . mating e . With the above restriction the best starting approx1ma- tion for ex with reSpect to Qf is a multiple, y, of the best 60 X . . . . . relative approximation to e and is given implic1tly by @fwocxl) + eforxe) x1 x2 e e = 2 X and x are such that r(xl) = (1+k)e 1 and r(xz) = where 2 x1 x2 (1-x)e . This equation reduces to solving 2 - Ln y(lfll _ 2 32140-2.) _ Y(1+K)['2 + Ln y(l+k)} .+‘Y(1 >01.2 + Ln y(l-x)] — 2 which would be solved numerically on a computer. It is important to note that in this case the best starting approximation need not be independent of the number of iterations of 6f since 6f is not a one-sided operator. B. If we desire to find R/x (for fixed x), p 2 2, p an integer, then we are confronted with finding a zero of the equation g(y) = yp - x. In this case the Halley iteration function is given by (p-1>x" + x 1 = ¢f(x ) = x n . “ (p+1)x: + (p-l)x For the operator setting let K = {h E C[a,b]: h(x) > 0 for all X E [a,b]} where 0 < a < b and set §f(h)(x) = It is clear that éf (p+1>" + (p-1>x h(x) [(1)-Damon" + (p+i>x Jf r h E K. .1. XP is continuous and §f(xp )= p = 2,3,... - S€t w(t) = P t [(1)-nu + ipfli (p+1>t" + (1)-1) } where t > 0. Differentiating, we obtain tp-l tp + (p-l) for t > 0. Consequently Qi is pointwise strictly monotone at x 2 ] 2 0 and hence w(t) is increasing 1 w'(t) = (p2-1> [ P l 0‘ file! and possesses Property I at x . Since §f(hn)(x0) a 0 as hn(x0) a 0 for each fixed x0 6 [a,b] and of is monotone we have that of: K a K. Thus, repeated application of 6f is well-defined. If 1 l M = K H R:[a,b] then Brp E M for 6 6 [.T:I; , I:X;H} Where rp 1 denotes the best relative approximation to x /p from R;[a,b] with deviation AP. Therefore, by Theorem 1.27, the best starting l/p approximation for x , p = 2,3,... from M with reSpect to Q l 1 1+ ’ 1- xP xP f the uniQue solution hi < ) to the is r for Yp 9 Y1) equation eprrpuxi + ef(yprp>(x2> 1/p [Ilp = 2 X1 X2 1/p 1/p = 1 = 1" . o where rp(x1) ( +1p)x1 , rp(x2) ( )(p)x2 . As in part A , the best starting approximation need not be independent of the number of iterations of 6f. In the present literature the above scheme for roots is often ascribed to Bailey (see [30]). 2. The second and final scheme of order 3 which evolves from the work of Traub is defined by the iteration function s(x“) g"gz 0 for all x 6 [a,b]} and define @f(h)(x) = E§£2.[1 +-(Ln h(x) - x - l)2] for h E K. Clearly Q is continuous, 6 ° K a K and §f(ex) = ex. Setting f f' W(t) ='% [1 + (Ln t - l)2] for t > O and differentiating we 2 obtain ¢'(t) = %(Ln t) 2 0. Hence W(t) is increasing for t > 0 . . . . X and so of is p01ntWise strictly monotone at e and possesses Property I at ex. If M = K n R;[a,b] then 5r 6 M for 6 Elliii" I%i-] where r denotes the best relative approximation to ex from R;[a,b] with deviation x. Thus the best starting approximation for ex from M with reSpect to of is yr for some V E (Ii—x , fix) (y is obtained by solving a certain transcendental equation as in the above Work). Since the operator of is not one- sided, the best starting approximation need not be independent of the number of iterations. l/p B. For computing x , p = 2,3,... the iteration function is defined by X (l-p) 2 2 xn+1 = ¢f(xn) = 41—... i (£21; .. L) + Lil—12.22 ] 2p x 2 -1 2 p 5 (1-p) where g(y) = yp - x. For 0 < a < b, set K = {h E C[a,b]: h(x) > o for all x 6 [a,b]} and define ¢f(h)(x) = 2 2 lighot :1 - __x__p) + E—OS-Z'gl] , for h E K. With these 2p P (h(x)) <1-p> definitions, 9f: K.a C[a,b] and so, as mentioned earlier, K needs to be further restricted if we wish to iterate with of. Clearly 1/p 1/p 6f is continuous and §f(x ) = x . Setting 63 2 2 ¢(t) 3 kg- t[(£§% - t-p) + LEE-l] for t > 0 and differentiat- Zp (l-p) ing we find that ¢'(t) = (29-1)§2-D [I - l—pl > 0. Thus if is P t pointwise strictly monotone at xl/p and possesses Property I at xllp. Hence we may apply Theorem 1.27 as before and shall omit the details. The lack of one-sidedness of § may again destroy indepen- f dence of the best starting approximation upon the number of iterations. Section 4: Iteration Functions of Order 4 Next we consider a class of iteration schemes with order of convergence 4. The first three schemes which we shall examine are derived from the previously mentioned work of Traub. l. The first fourth-order iteration function is defined by 2 s(x ) s"(x ) s(x ) s"(x ) X =¢(X)=x -—;—-'1— 1+ “ n + 2—1—“-—- - n+1 f n n g (xn) 2gr(xn) g'(xn) 2g (xn) m 2 g (xn) ] s (xn) 6g'(x ) u 2 n [g (xn)] A. For approximating eX for some fixed x this iteration function becomes 1 2 1 3 xn+1 - ¢f(xn) I xn[1 - (Ln xn - x) +-2(Ln xn - x) - 6(Ln xn - x) j where g(y) = Ln y - x. To approximate ex on the entire interval [a,b] (a < b) set x' = {h e C[a,b]: h(x) > o for all x 6 [a,b]} and define ef by ef(h> = h(x)[1 - (Ln h(x) - x) +%(Ln h(x) - >02 - %(Ln h(x) - x)3] for h E K'. As before of is continuous and §f(e") = ex. Set Mt) = t[1 - (Ln t) +%(Ln t)2 - 6““ t)3] for t > 0. Upon differentiation we obtain ¢'(t) = - g(Ln t)3 and so 64 x it is clear that 6f is pointwise strictly monotone at e , possesses x . . X . Property I at e and is one-Sided from below at e . As With the Newton operator in approximating ex, 6 being one-sided from below f implies that large values of h(x) (fixed x) yield negative values for §f(h)(x). By the Implicit Function Theorem the equation Qf(h)(x) = 0 defines h(x) > ex as a continuous function of x. In our case the desired h(x) is obtained by solving 1 - (Ln h(x) - x) + %(Ln h(x) 4 x)2 - %(Ln h(x) - x)3 = 0 for h(x). If to is the unique real zero of l - u + % u2 - é’UB = 0 then x+r h(x) = e 0. Note that l < r0 < 2. Setting K = {h E C[a,b]: x+r 0 < h(x) < e O for all x 6 [a,b]}, we have that 6f: K a K. If r denotes the best relative approximation to ex from R;[a,b] with deviation 1 then the best starting approximation for Q f, _ - - __1_ _1_] k - 1,2,... is yr prOVided 6r 6 M for 6 6 [1+1 , 1'1 . To x insure this we require that 6r(x) s 6(1+)\)ex s %iL-ex < e 0, or r '1 0- equivalently 1 < r With this restriction on 1 the best 0 e +1 starting approximation is yr where y is computed by solving @ (Yr)(x ) Q (N/I‘Hx ) X X f 1 = f 2 where r(xl) = (1+x)e 1 and r(xz) = (l-x)e 2. x1 x2 e e Upon simplification we find that y is the unique solution in (Ii; "I%:) to the transcendental equation ' l 2 1 3 (1+x)[1- Ln y(1+1)+§(tn y(1+>.)) -g(Ln Y(1+>.)) J = (l-x)[1-(Ln Y(1->.)) + %(Ln y(l-mz - %(Ln Y(1->.))3] . 65 l/p B. For the approximation Of x , p = 2,3,... the iteration function is given by P _ P _ 2 P _ x senate: .n * .eeep-u "n n+1 f n p xp 2p xp 6p2 P n n n where g(y) = yp - x. For 0 < a < b, set K = {h E C[a,b]: h(x) > 0 for all x E [a,b]} and define the associated iteration Operator Of by Q (h)(X) = - M[(g!!(xz )p-x + P-1 £h(x))p-x)2 + f p (h(x))p 2P (h(x))? (p-1M22-11<®(X))p-X)3 _ p] 2 6p (h(x))p for h E K. of is continuous and §f(x1/p) = xllp. Set 2 3 ..._£ _ 19 2:1 _ 1P Q-IMZP-l) .19 Mt) p10 (9) + 2p(1 (9) + 2 (1 - (9) -p] 6p for t > 0. p 3 Then ¢'(t) = '1 2 '1 3 '1' (5—3;) and so W(t) is increasing 6p t for t > 1 and decreasing for O < t < 1. Therefore 6 f l strictly monotone at x /p’ p = 2,3,..., possesses Property I at x is pointwise 1/p and is one-sided from above. The one-sidedness of of yields Of: K q K and hence we are able to iterate. Setting M = K H R;[a,b], . l l we obtain that Or E M for 6 E , where r denotes F 1+1? l-xp p l the best starting approximation to x /p from R:[a,b] with deviation xp. Hence, according to Theorems 1.27 and 1.30, the best starting l/p approximation for x , p = 2,3,... with reSpect to 6:, k = 1,2,... , l l . . . is yprp for yp E (11):: , ti) the unique solution to the equation 66 Q(Yr)(X) g”’ (g">2 (gap)2 1' 2 + "1‘7 ' 2 2 2(8'(xn)) 4(g'(xn)) (g'(xn)) 6g (xn For the approximation Of ex we have g(y) = Ln y - x and the xn+1=¢f - a a o a = = 1 - iteration function is given by xn+1 ¢f(xn) xn [ (Ln xn - X) 1 1 2 Set K = {h E C[a,b]: h(x) > 0 l + -2-(Ln xn-x) + flan xn-x) for all x E [a,b]} where a < b and define ef(h>(x) = h(x)? - (in “’0 " "l l for h e x . l + %(Ln h(x) - x) +-%§(Ln h(x) - x)2 Then 6 is continuous, Q - K a K and Qf(ex) = ex. Setting f' _ _ Ln t ¢(t)-t[1 1+-]-'Lnt+-1—(Lnt)2} 2 12 f l 4 w(m t) we find that ¢'(t) = 2 0 for all t > 0. (l + '2; Ln t + i—2(Ln t)2)2 Hence 6f is pointwise strictly monotone at ex and possesses 67 Property I at ex. The conditions of Theorem 1.27 are all satisfied and so we are able to conclude that the best starting approximation for eX on [a,b] (with respect to 6f) from M = K H R;[a,b] is a positive multiple (y) Of the best relative approximation to ex on [a,b] from R;[a,b]. Let r denote the best relative x approximation to e on .[a,b] with deviation X- Then the value of y we are seeking is Obtained by solving the equation 6 (vr) (X ) Q (vr) (X ) x f 1 +- f 2 = 2, where r(xl) = (1+x)e 1 and r(xz) = X1 X2 e e x (l-x)e 2, which would be effected numerically on a computer. Since 6f fails to be one-sided the best starting approximation need not be independent of the number of iterations. 3. The final iteration function with order of convergence 4 obtainable from Traub's work which we shall consider is defined by g(xn) [yap + 2g'(xn) 6g'(xn) 4(g'(x ))2 g'lxn) n =¢£(xn)=X ' . xn+1 “ g" ) 23 (Kn) 371x“) 2(g'(x ))2 6g (xn) n For the approximation of ex (fixed x E [a,b]), g(y) = Ln y - x and the iteration function is defined by (Ln xn - x)(Ln xn - x - 6) xn+1 = ¢f(xn) = xn 1 + 2(Ln xn - x +'3) ] ° TO approximate ex on the entire interval [a,b] set K = [h E C[a,b]: h(x) > em.-3 for all x E [a,b]} and define the associated iteration Operator §f(h)(x) = my + Le;(:§xg(;)xggn+hgi - x - 6> ] where h t K. It is 68 clear that 6 is continuous and 6f(ex) = ex. Furthermore we shall f . . X demonstrate that 6 is one-Sided from above at e and consequently f ___ (Ln t)(1n t - 61] 1_ ef(x) c K. Set ¢(t) t [1 +- 2(Ln t +_3) for t > 3 . 3 e Differentiating, we obtain w'(t) = ‘LLn t) 2 and so 6f is 2(Ln t +-3) . . . X X p01ntWise strictly monotone at e , possesses Property I at e and is one-sided from above at ex. TO be able to apply Theorem 1.27 3 we must further demand that 1‘1 83-1 e +1 where A denotes the error . . . . . X assoc1ated With r, the best relative apprOXimation to e on [a,b] 1'1 . . . . from Rm[a,b]. As noted before, this restriction is extremely mild since we always have K < 1. With this restriction Theorems 1.27 and x 1.30 are applicable and hence the best starting approximation for e k on [a,b] with respect to 6f, k = 1,2,... is yr where y is the ef(vr)(x1> ef(vr)(x2> unique solution to the equation x = x in the 1 1 e e 2 interval (II): , 1.3:) (x1,x2 as before). For our definition of 6 this reduces tO solving a third degree equation in Ln y. f 4. Finally we shall examine an iteration function also Of rational form which has order of convergence 4 and is due to Kiss (see [30]). As above we shall only consider the iteration function Pf correspond- ing to g(y) = Ln y - x. The iteration function Of Kiss is defined by s(x ) < 8"(Xn) g(x ) g'(xn) 2g'(xn) g'(xn)) X =¢(X)=X- “*1 f n “ g"(xn> s(x“) g“(xn)g2 , + g ‘xn’ g7’21) 6g'(g'(xn>)2 For the special choice g(y) = Ln y - x we have 69 ( ) [ (Ln xn - x)(1 + %(Ln xn - x)) ] x = ¢ x = x 1 - . n+1 f n n 1+(Ln xn-x) +-%(Ln xn - x)2 . X . TO approx1mate e on the interval [a,b] Where a < h set K" = {h E C[a,b]: h(x) > 0 for all x E [a,b]} and define 6f by (Ln h(x) - x)(1 + %(Ln h(x) - x)) Qf(h)(x) = h(X) [I - 2 X for h E K". 1 + (Ln h(x) - x) +-%(Ln h(x) - x) It is easily shown that 1 +-(Ln h(x) - x) +~%(Ln h(x) - x)2 # 0 for Ln t(1 +-%-Ln t) all h e K" and x 6 [a,b]- Set 1(t) = t 1 ' 1 2 1+Lnt+'3-(Ln t) 1 3 3 - gun t) (Ln e t) for t > 0. Then ¢'(t) = 2 . Note that (1 + (Ln t) + §<1n oz) ¢'(t) = 0 for t = 1 and for t - e-3. To inSure that Of will be pointwise strictly monotone at ex and possess Property I we shall demand that t > e-3. If we set K' = [h E C[a,b]: h(x) > ex.3 for all x E [a,b]}, we have that Qf: K' a c[a,b], 6f is continuous, Qf(ex) = ex, 6f is pointwise strictly monotone at ex, possesses Property I at ex and is one-sided from below. For each fixed x E [a,b], §f(h)(x) is decreasing for h(x) > ex and increasing for h(x) < ex and §f(h)(x) = 0 at h1(x) = ex3/6, h2(x) = exi/6. If We set 2 x+2 K = {h e c[a,b]: ex' < h(x) < e for all x 6 [a,b]} then it is easy to show that 6f: K a K and the aforementioned pro- perties Of 6f are preserved. In order to apply Theorem 1.27 we n 1 1 must require that 6r 6 M - K n Rm[a,b] for 6 E 11+1.’ 1'X J . . x where r denotes the best relative approximation to e from R:[a,b] with deviation x. This requirement is equivalent to 70 2 k <.E§_:_l ‘Which is again not a severe restriction. Applying e + l Theorems 1.27 and 1.30 (subject to the above restriction) we know _1_ _1_ 1+), ’ 1-), best starting approximating to ex on [a,b] from M (with respect k f, that there exists a unique y E2 ( ) such that yr is the to 6 k = 1,2,3,...). The value of y is Obtained by solving the ef(vr>(x1> ef(vr)(x2) equation = -—- where x and x are such that x1 x2 1 2 e e x X r(xl) = (1+1)e 1 and r(xz) = (l-x)e 2. For the given operator 6f this equation becomes 2 (1+1) [ 6 - (Ln y(1+>.D 2] ... 3 + 3Ln y(lfl) + (Ln y(1+x)) _ 6 - (Ln y(l-n.»2 (1 i) 2 3 + 31a y(I-x) + (Ln y(l-i)) and we are confronted with solving a certain quartic equation in tiny- Section 5: A Sequence of Schemes for Approximating /x In this section we shall consider a sequence of iterative sOhemes for approximating 1/x which were introduced by G. Merz [12] and subsequently analyzed by Meinardus and Taylor [11].. The itera- tion function(s) of Merz are defined by (%+Mmk+annhfi (xn +,/'x)k - (xn - [x)k xn+1 = ¢k(xn) = /x for each fixed integer k 2 2 (¢k would be written in the 16% earlier notation, where f(x) =./r). Let us note that, for each k, ¢k possesses a purely algebraic expression. Merz has shown that for 71 each fixed integer k 2 2 the above sequence {xn} converges to /x starting with any initial guess x0 > 0 and furthermore the order of convergence is k. Observe that for k = 2, ¢2(y) = %(y +»§) which is the well-known Newton iteration scheme. It is interesting to note that ¢k(¢m(y)) = (y) and so Qk-m one has the choice of repeated iterations with a lower order formula or fewer iterations with a higher order formula to obtain the same final iterate. Since we wish to approximate /x on an interval [a,b], 0 < a < b, we consider the associated iteration Operator(s) as before. Set = n e c1a.b1= be) > o for an x e 1am and define ek(h)(x) =/x (h(x) +f"): + 0‘93 1"): for h e K. (h(x) +/X)k ' (h(x)- 'k/X) 6k: K a K, Qk /x for each k2 2. Set ¢k(t)=£1+t):+ (1 9: for t >0. (1+t:)k - (1-t)k Upon computing ¢£(t) it becomes clear that for k even, 6k is pointwise strictly monotone at Jx, one-sided from above at /x and It is easily seen that is continuous and 6k(/x)= possesses Property I at Jx. Likewise, for k Odd 6k is pointwise strictly monotone at /r and possesses Property I at /r. Hence, by Lemma 1.5 and Theorem 1.27 we have that for each k the best starting approximation for /r on [a,b] from M = K H R:[a,b] (with respect to 6k) is a multiple Of the best relative approxima- tion to 1/x on [a,b] from Rn[a,b]. Furthermore, if k is even we have that Q m = Q: = §k(§: 1), m = 2 ,3,... have the same starting k value by Theorem 1.30. If r denotes the best relative approximation to /&:on [a,b] with deviation 1, then yr is the Optimal starting approxi- 72 1 l , tion for 6km (k even), m = 1,2,... wherev E (lilti- , n) is the 9 (Yr)(x ) Q (Yr)(x ) . . . k l k 2 unique solution to the equation - l = - Jkl /k2 where x1 and x2 are such that r(xl) = (1+11/k1 and r(xz) = . . 1 .31. (I'KXCXZ- USing the fact that k is even and y E (.L+1 , 1‘1 ) , r we obtain y = ('rLTE) Hence (I—ljf) 1: is the best starting l-x 1-x approximation for every even ordered scheme. For the case k = 2 and R:[a,b] replaced by Pn[a,b] this result was earlier Obtained (independently) by P.H. Sterbenz and C.T. Pike [24] and R.F. King and D.L. Phillips [7]. Additional background concerning these and associated results appears in Taylor [27]. In the case that k is Odd, 6k is pointwise strictly mono- tone at /r and possesses Property I at /x but is no longer one- sided. Hence we may no longer conclude that the best starting approxi- mation for /r is independent Of the number Of iterations. Computing the best starting approximation for a single application Of 6k (according to Theorem l.27),we Obtain yr where y satisfies the @ (Yr)(x ) Q (Yr)(x ) . k 1 k 2 equation - 1 = l - and r, x1, x2 are as fx1 fx2 before. This reduces to solving 1 k K—J-J‘“) (—J—-‘*”“) + 2 1 + xv - Y 1 - Xv - Y . . l 1 and the unique solution y E (m , Iii) must (apparently) be found using numerical methods on a computer. Note that y, and hence the best starting approximation, depends on k which is not the case for k even. Since 9 m = 6:, 6: possesses Property I for k m = 1,2,... . Thus Theorem 1.27 is applicable for any number Of 73 iterations of QR. For k Odd, the best starting approximation for 6m, m = 1,2,... is y r where y is the only solution of k m m m m k k 1 - Xym + ym 1 + me + ym + = 2 in the interval 1+Mm-Ym l-xvm-Ym _1_ _1_ 1+1’1-x Remark 1: In this chapter we have been concerned with approximation using the relative error. The iteration functions could also be analyzed in the uniform approximation setting. In this case we would be checking for Property J. However in view Of some earlier remarks we should probably examine the function g(y) = ey - x; that is, consider an approximation Of the function f(x) = Ln x on some interval [a,b] (O < a < b). CHAPTER IV OPTIMAI.STARTING APPROXIMATIONS FOR A GENERALIZED WEIGHT FUNCTION Section 1: Introduction and Examples In [13], [14] D.G. Moursund introduced the concept of uniform approximation using a generalized weight function. The original development here was concerned with polynomial approximation. Applica- tions pertaining to the notion Of a generalized weight function and concerning both polynomial and rational approximation appear in [15], [16] and [26]. Definition 4.1: Let X be a compact metric space. A real-valued function W(x,y) defined on X X (-m,m) is called a generalized weight function if: (i) W(x,y) is continuous on X X (-m,m) (ii) Sgn W(x,y) = sgn y for all x E X (in particular, W(x,0) = 0). (iii) For each x E X, W(x,y) is strictly monotone increasing in y with lim [W(x,y)\ = m. y-OCD The problem.which we shall consider is the following: given x : [a,b], f e K c C(X) and M = K n R:[a,b] (m,n fixed), find * x . r E M such that “W[x,6(f)(x) - Q(r )(x)]“ = inf “W[x,§(f)(x) - r611 Q(r)(x)]“ where 6: K a C(X) is continuous and “W[x,§(f)(x) - e(r>(x)]\\ = max \WEx,e(f>(x) - i]\. XEX 74 75 Before proceeding to the basic results we shall give some examples Of generalized weight functions (here we take 6 to be the identity operator). y corresponds to ordinary uniform approximation. Example 1: W(x,y) Example 2: W(x,y) E f%;)' corresponds to ordinary relative error approximation provided f ¥ 0 on X (f is the function being approximated). Let X be compact, X G [a,b], K C C(X) and 6: K a C(X) a continuous operator which is pointwise strictly monotone and point- wise fixed at f E K. Definition 4.2: The Operator 6 is said to be sign-preserving if for each k E K, sgn(f(x) - k(x)) = sgn(6(f)(x) - Q(k)(x)) for all x E X. Definition 4.3: The Operator 6 is said to be sign-reversing if for each k E K, sgn(f(x) - k(x)) = -sgn(§(f)(x) - 6(k)(x)) for all x E X. Section 2: Existence, Uniqueness, and Characterization Theorems In this section we shall be concerned with existence, unique- ness, and characterization of optimal starting approximations using a generalized weight function. Theorem 4.4: Let K be a convex subset Of C(X) and 6: K a C(X) a continuous Operator which is pointwise strictly monotone and point- wise fixed at f E K ~ M. Suppose further that 6 is sign-preserving, sign-reversing or a one-sided operator and let W(x,y) be a generalized 76 weight function on X. Then, for M = K H R:[a,b] relatively Open in Rgla,b], r E M is a best starting approximation for Q(f) relative to W(x,y) if and only if there exists {Xi}§=1 C X, N = 2 +-max[n + sq, m + 5p], for which (i) x1 < x2 <...< xN, (ii) \WExi.e(f)(xi) - s(r>(xi)]\ = Mme) (x) - n(r)(x>]\\ (iii) sgn(f(xi) - r(xi)) = (-l)i+lsgn(f(x1) - r(x1)), i=1,2,...,N O nggfi: We shall prove the theorem for 6 a one-sided Operator from below and for 6 sign-preserving and remark that the other cases follow in a similar manner. Case 1: Q(f) 2 Q(h) for all h E K. (Sufficiency) Suppose there exists {Xi}§=1 C X such that \WExi.e(f>(xi> - e1| = \\WIx,i(x> - Mono)“ and sgn(f(xi) - r(xi)) = (~l)i+lsgn(f(x1) - r(x1)). Note that f E M implies that there exists xO E X such that f(xo) # r(x Thus ). o o(£)(x0) 9‘ Q(r)(xo) and so \w[x0,o(£)(x0) - Q(r)(xo)“ e O which implies HW[x,6(f)(x) - 6(r)(x)]u ¥ 0. Let r* E M be such that * \\WIx.n(f>(x) - n(r >(x>]u s \\WIx.n(f>(x> - amen“. Since Sgn WIX.®(f)(X) - Q(r)(XH = Sgn(¢(f) (X) - ¢(r)(X)) = 1 0r 0 for all x e x and all r e M we have W[xi,(f)(xi) - 6(r*) (xi)] = IWIx,.n(xi) - i(r*)(xi)]\ - WEx,.e(f> - n(r> s Q(f)(xi) - Q(r)(xi) since W(x,y) is strictly monotone increasing in y for each fixed x E X. If r(xi) > f(xi) then r(xi) 2 r*(xi). * Otherwise r (xi) > r(xi) > f(xi) and so 77 Q(f)(xi) - i(r*>(x,> = |e(f>(x,> - n(r*>(x,>| > \e(f)(x,) - n\ = Q(f)(xi) - Q(r)(xi) which is a contradiction. Similarly r(xi) < f(xi) * * implies r(xi) S r (xi). Thus, by the standard argument, r - r * possesses at least N-l zeros and 30 r E r . Hence we have the desired result. (Necessity) Assume there exists {x9221 s: X, N' maximal, N' < N on which ‘W[xi,§(f)(xi) - t(r)(xi)]l = HWLx.n(£>(x> - e(x>1H and sgn(f(xi) - r(xi)) = (-l)i+lsgn(f(x1) - r(x1)). About each xi construct a relatively open interval 11 such that all extreme pognts = {x e x: |W[x,§(f)(x) - Q(r)(x)]‘ = uw[x,e(f)(x) - e(r)(X)]H} C U 11’ _. _' i=1 I H 1k = ¢ for j i k and for all extreme points in each Ii J the function f—r has constant sign. In what follows, we make explicit use of the fact that ‘W[x,§(f)(x) - 6(r)(x)]\ = W[x,§(f)(x) - é(r)(x)]. Let Y = x n ( n 1,) i=1 where Ii denotes the complement Of Ii with reSpect to [a,b]. Y is a compact subset of X and W[x,6(f)(x) - Q(r)(x)] < HW[x,6(f)(x) - Q(r)(x)]“ for all x E Y. Hence by the continuity of 'W (as a function Of x) there exists p > 0 such that m::'W[x,Q(f)(x) - Q(r)(x)] s Hw[X,e(£)(x) - d(r)(x)]u - p. x For each i, let Vi = {x E X n I1:W[x.§(f)(x) - @(r)(x)] 2 er-X’QG) 0% ' 20') 00-1“ and sgn(f(x) - r(x)) = sgn(f(xi) - r(xi))} . 78 Nl NOW V = U V1 is a compact subset Of x and, since f(x) - r(x) i 0 i=1 on V, there exists n > 0 such that [f(x) - r(x)‘ 2 n on V. let 2, = {x e x n f,: W(x.n(f>(x) - t(1-Mm 21MXM92- “001111 and sgn(f(x) - r(x)) # sgn(f(xi) - r(xi))} . Observe that W[x,§(f)(x) - 6(r)(x)] < HW[x,6(f)(x) - 6(r)(x)]u for all N. xEZ = U Zi by the construction of the intervals {Ii}. Finally, let i=1 u1 = {x e x n f1: W[x,§?(f)(X) - t(1-mo] s WL""’®"°,' “”0935. N and set U = U Ui' Then by continuity there exists 6 > 0, 6 s p, Such that max WIXs§(f)(X) - Q(r)(X)] S HWIX,§(f)(X) - Q(r)(X)]H - 6- xEZUU Given T > 0 we can, using Lemma 1.8, select r E R:[a,b] such that (1.2) holds. By the continuity of 6 and W we can select > 0 e1 such that for O < e s 61’ re satisfies (1.2) and max WIX.¢(f)(X) - Mr >(x)] < \\W1x.i(f)(x) - i1n - g . XEYUZUU 3 Next, by continuity of f and r, we can select 32, 0 < €2 S e1, such that for 0 < a 5 e2, r lies strictly between f(x) and e N' r(x) on V = U V . Then, since 6 is one-sided from below at i=1 N' f, we have 6(f)(x) - Q(re)(x) < @(f)(x) - Q(r)(x) on. V = Vi i=1 where 0 < s S 32. Hence W[x,§(f)(x) - é(r€)(x)] < WIX:§(f)(X) ' 9(T)(X)] 5 lexr§(f)(x) ‘ Q(r)(x)]u on V if 0 < e S 62. Therefore max W[x,§(f)(x) - @(re)(x)] < XEV HW[x,§(f)(x) - Q(r)(x)]u. Consequently for e Such that 0 < e S 62, 79 r is such that e lex,§(f)(X) - Q(r€)(X)]H < lex,§(f)(X) - Q(r)(X)]H- Finally, since M is relatively open in R:[a,b], we can select 33 with 0 < 63 S 92 so that r63 6 M and “WEX,§(r)(x) - Q(re3)(x)]H < HW[x,§(f)(x) - Q(r)(x)]H and hence the result. Case 2: Q is sign-preserving. (Sufficiency) Suppose that there exists {xi}§=1 C X such that |W[x1, - p(xi)]\ = \\W[x,p(f>(x) - s(x-Hm“ and sgn(f(xi) - r(xi)) = (-l)i+lsgn(f(x1) - r(x1)). Let r* E M be such that HWEx,p(i>]n s HWEx.p - i]u. Suppose r(xi) < f(xi). Then r(xi) s r*(xi) for otherwise r*(xi) < r(xi) < f(xi) and so p(f)(xi) - Q(r)(xi) < p(£)(xi) - Q(r*)(xi) which implies \WEx.i(f)(xi) - i]l = WExi.p - p(r*)(xi)] > Wlxi,§(f)(xi) - s] = \Wlxi,§(f)(xi) - p(r)(xi>]\. which is a contradiction. Similarly r(xi) > f(xi) implies r(xi) 2 r*(xi). * Thus, as in Case 1 above, r E r and we have the desired result. NI (Necessity) Assume there exists {xi}i-l :x,N' (xi) - p(rxxinl = \Mx,p(£> - imam = \\W[x,i(x> - i1m c U 1 i: Ij fl Ik = ¢ for j i k and for all extreme points in each Ii the function f-r has constant sign. Construct the sets Y, V, Z and U as in the proof for Case 1. Using the same arguments as in the above proof we can find 6 > 0 Such that 80 max |WEx.p(f)l| s \\W[x.6(f>(x) - p(r>l\\ - p . xEYUZUU By Lemma 1.8 we can select re 6 R2La,b] satisfying (1.2). By the continuity of Q and W we can select > 0 such that for 6l O < e s 61’ re satisfies (1.2) and max 1w[x,o(t)(x) - p(re)(x)]\ s HW[x,o(f)(x) - o(r)(x)]u - %-. xEYUZUU Next, by continuity of f and r, we can select 32, O < e2 S e1. such that for 0 < e s 32, re lies strictly between f(x) and r(x) NI on V = U V.. If f(x.) < r(x ) on V. then f(x) < r (X) < r(x) i=1 1 l i 1 g for all x 6 vi and so o(£)(x) - Q(r)(x) < @(f)(x) - p(r€)(x) < o (0 < e s 62) which implies \W[x,o(f)(x) - “r900“ e -w[x,p - il < -W[x,§(f)(X) - il = lW[x.i(f)(x> - Q(r)(X)]\ and so \Wlx,§(f)(X) - Q(re)(X)]\ < lex,§(f)(X) - Q(r)(x)]“ on Vi' Similarly, if f(xi) > r(xi) on Vi we obtain \WEx,p(x> - pcx>l| < \\W\:x,p(x> - p(x>l\\ = inf \\WEx,s - p(s>lu (4.1) $6M. reduces to determining r E M such that HQ(f) - Q(r)H = inf “Q(f) - @(s)H where HhH = max ‘w(x)h(x)\, which is the problem S€M XEX studied earlier. A question which arises is the following: can the problem (4.1) be cast in terms of another generalized weight function w for which the solution is already known? In the problem (4.1) we are approximating Q(f) be elements of Q(M) with reSpect to the generalized weight function W. Suppose we could find another 82 generalized weight function N such that the problem (4.1) would reduce to finding r E M Such that ufi[x,g(x) - r(x)]H = inf “fi[x,g(x) - s(x)]u where Q(f) = g. This problem has already 384 been studied by Moursund and Taylor [17]. CHAPTER V AN IMPROVED NEWTON ITERATION SCHEME FOR APPROXIMATING EXP(X) WHICH IS 0 PI‘IMAL Section 1: Introduction In a recent paper I. Ninomiya [18] suggested a modification of the Newton-Raphson method for calculating square roots which re- duced the error at each step of the algorithm. This method was generalized by R.F. King [6] to a modified Newton method for cal- culating integral roots. Both Ninomiya and King show that the improved Newton iteration converges by a factor of approximately [1 2 faster than the usual Newton iteration (comparing the n-th iterate of each). R.F. King notes that in actual practice one would not use this scheme for calculating a p-th root on a machine which has p as its floating base since in this case an exponential add order is much faster than a multiplication, and it would usually be better to use Newton's method with an extra iteration (if necessary). G.D. Taylor [27] has shown that the suggested modification of Newton's method above for integral roots is optimal in the sense of our work. We shall now show that an analogous modification of Newton's method for f(x) = ex yields an improved iteration scheme for approximating this function. Let [a,b] be a fixed interval and K a convex subset of C[a,b]. Recall that if N(h)(x) = h(x)(1 + x - Ln h(x)) (h e K) 83 84 is the Newton Operator used to approximate ex on the interval [a,b] then N(h)(x) s ex for all h E K and x 6 [a,b]; that is, N is one-sided from below. With this in mind we are able to con- struct an improved Newton iteration procedure for computing ex which is optimal and which differs from the usual Newton method by a multiplicative factor at each step. At each step of the algorithm the multiplicative factor has the effect of "translating" the pre- vious Newton iterate upward sufficiently to halve the relative error. Section 2: The Improved Newton Iteration Scheme Let [a,b] be a fixed interval as above and define K by l+x . K = {h E C[a,b]: O < h(x) < e for all x 6 [a,b]}. For fixed nonnegative integers m and 5 let R: denote the usual class of rational functions defined on the interval [a,b] (See Chapter I). Set M = K n R: (assume M # ¢) and define N(h)(x) = h(x)(l +ix - Ln h(x)) for h E K. This is, of course, one Newton iteration for calculating eX starting with the initial guess h(x). n n , _ Set E+'= {(c1,...,cn) : (c1,...,cn) E E and c1 > O, 1 - 1,...,n} where En denotes Euclidean n-Space. For (c1,...,cn,h) E Ei'x K formally define the sequence y0(X) = h(X) (5.1) yk(x> = ck N(yk_1>. k = 1.2.... which may have no meaning for some choices of c1,...,cn. ° = o 1 0 Define Sn {(c1,...,cn,r) . ci 6 E+, r E M and yn_1 E K}, that is, (c1,...,cn,r) 6 Sn if and only if y1 = c1N(r) E K, y2 - c2N(y1) = c2N(c1N(r)) E K,..., yn_1 = cn_1N(yn_2) 6 K. Thus Sn consists of 85 all tuples (c1,...,cn,r) for which r E M and the iteration above . . . + is well-defined. Now define Tn: Sn a C [a,b] = {f E c[a,b]: f(x) > O for all x E [a,b]} by Tn(c1,...,cn,r)(x) E yn(x) (yn(x) given by (5.1)). Observe that (c1,...,cn_1,cn,r) 6 Sn implies that (c1,...,cn_1,c,r) E 1 Sn for any c E E+, (c1,...,ck,r) E Sk’ k = 1,2,...,n and Tn(c1,...,cn_1,cn,r) = chn(c1,...,cn_1,1,r) = an(Tn_1(c1,...,cn_1,r)). We shall show that there exists a unique best approximation to ex in the relative norm from Tn(Sn); that is, there exists (cin),...,cén),r*) 6 Sn for which eX - Tn(c§n),...,c§n),r*)(X) ex - Tn(c1,...,cn,r)(x) X e X e I (5.2) for all (c1,...,cn,r) 6 Sn with equality holding in the above if and only if c * = cin), i = 1,2,...,n and r E r . i — . . . x Let r(x) denote the best relative approx1matlon to e on [a,b] from R: with deviation A0; that is, f'x - eX r x - eX ex = 1n£_ ex = X0 - {5-3) rER m Clearly O < l0 < 1 so that f E M. The unique best approximation (n) ,3 (n) T (c1 ,...,cn n ) to ex from Tn(sn) is given by the following set of recursive relations: l l-xk 2)\k 1 = e 1+1k k = 0,1,... (5.4) I 2 l-xk 86 = 1 ' Bk'1(1 ' Kk_1)[1 ' Ln Bk-1(1 ' kk_1)] xk 1 + Bk-1(1 - kk-1)[1 ' Ln Bk-1(1 ' )hk_1)] , k = 1,2,... (5.5) 2 = , k=1,2,... 5.6 k Bk_1(1 - lk_1)l1 - Ln ek_1(1 - ik_1)] + 1 ( > Ck = Bkdk, k = 1,2,...,n-1 (507) cs“) = on (5.8) and * ._ r (x) = Bor(x) . (5.9) In passing from n to n+1 the tuples (cin),...,c§n),r*) and (n+1) (n+1) * , (c1 ,...,cn+1 ,r ) are related as follows. cg“) = C€n+1), i = 1,...,n-l , 1 1 (5.10) C = a cis) n n n and (n+1) (n) (n) * _ (n+1) (n+1) * c +1 N{Bn(Tn(C1 ,...,cn ,r ))} — Tn+1(c1 ,...,cn+1 ,r ) * Note that r is the best starting approximation for calculating x . . . . e With the usual Newton iteration; that is, * x n X Nn(r )gx) - e 1 s N (r)(x) - e t (S 11) x x e e O * for all r 6 M. with equality holding if and only if E r , where r n-l N(r)(x) - r(x)(1 +-x - Ln r(x)) and Nn(r)(x) = N(N (r))(x), n = 2,3,... Finally we have that Bk is such that ek(1-lk)[1-tn ek(1-lk)] = ek(1+lk)[1-tn ek(1+lk)]. k = 0.1.2.... (5.12) 87 Lemma 5.1: Let Nx be defined by Nx(t) = t(1 + x - Ln t) for t >|O. Let x,y be two given real numbers and let e,¢ be such that 0<9 . > ey ey Nx (t sex) and for O >Nx . ey ex ex N (tqey) Y N (tmey) ex Ny(q£y) Proof: Set f(t) = —X——____ . ___—___. - ey N (teex) ey x 1 _ I Q =§[1-L2:9] -QP[1-anp]. Now consider the function h(t) = t(1 - Ln t) for t > 0. Upon differentiation, we obtain h'(t)<0 if t>l,h'(t)>o if t m > 1 it is clear that f(%) < 0. We also have that f'(t)=52 [Lute-mtg; <0 if t# 9 t(1 - Ln he) Similarly, set Hence the first result. <0er N (teex) y N (Sex) S(t) = —§-;—-——‘° e - x e Ny(tqey) ex =‘g [}%—§4%§—%% J - 9(1 - in e) . 88 Using (5.13) and the fact that %< e < 1 it is clear that g(i) < O. Now g'(t) = fi- Ln tw - Ln t9 > O for 0 < t < la Thus the t(1 - Ln tm) w second result. I * * Theorem 5.2: (cin),...,c§n),r ) for cg“), i = 1,...,n and r * given by (5.7)-(5.9) is an element of Sn and Tn(c§n),...,c§n),r ) is the unique best relative approximation to ex from Tn(sn) for each n = 1,2,... . Furthermore Tn(c§n),...,c§n),r*)(x) - ex x = kn , (5.14) e (D * Tn(c§n+1),...,c§n+1),r ) intersects ex in [a,b] and n+1 n+1 * x x N(Tn(c§ ),..., i ),r ))(x) - e S N(Tn(c1,...,cn,r))(x) - e x x e e oo oo (5.15) for all (c1,...,cn,r) E Sn with equality if and only if ci a c§n+1), * i = 1,...,n and r E r . This last inequality states that * Tn(c{n+1),...,c§n+1),r ) is the unique best relative starting approxi- mation to ex for the Newton operator N, from the class Tn(sn)° Proof: We shall proceed by induction on n. For convenience we shall use the following notation: for (c1,...,cn,r) 6 Sn set W, = .iiiiicsi... W M} ex y€[a,b] ey m(r) = x: _(_)___r x - ex = min LI. ' ey} ex yEEa,b] ey l'll: I h .l I All ‘5‘ {I 89 T (c ,...,c ,r)(x) - ex M(c1,...,cn,r) ={x: n .1. n X e ____ max Tn T1(1.r>(x> ' (5‘16) max +' min xE[a,b] ex xe[a,b] ex J T1(1,r> Since T1(l,r)(x) = N(r)(x) we have that 1 2 max x > xEEa,b] e l1(1.r>(x) min with equality holding in the above if and only xE[a,b] ex . . X . . if r intersects e . With the above selection for c, we have T1<1.r> T1<1.r)(x> c max x - l = l - c min x . Thus x€[a,b] e x€[a,b] e 90 (ex - T1(Csr) (x)) i1(c.r>(x) max = l - min -——-——————— = 1 - xE[a,b] ex x€[a,b] ex T1(1.r)(x) T1(1,r)(x) (T1(c,r)(x)-ex c min --—-::--'= c max -—-——————- - l = max xE[a,b] e x€[a,b] ex xE[a,b] ex Now let c1 6 E: ‘be such that c1 > c. Then for x E M(l,r) we have T1(c1,r)(x) - ex - ciT1(1,r)(x) - ex x _ X e e T1(c,r)(x) - ex e l wise, for c1 6 E+_ and c < c it is clear that T1(c,r) is a l strictly better relative approximation to ex than T1(c1,r). Hence if T1(c,r) is to be a minimal solution then c must be as in (5.16). Next suppose r E M intersects eX and let 2 * c = [ T1(],r)(x):1 where we shall assume that r i r . 1 +' min ---—-—-- x x€[a,b] e * Since r is the best starting approximation for the Newton operator to ex we have (using T1(1,r) E N(r)) x x * e - T1(1.r) max > max xE[a,b] ex xE[a,b] ex or equivalently, * T1(19r)(x) TIC-9r )(X) min x < min x . (5.17) XE[a,b] e xE[a,b] e * . x . f(x) . Let us now Show that r intersects e . Since -—;7- has a max1mum e value of (1 +.K0) and a minimum value of (l - lo), we must show that 50(1 - 10) < 1 < 50(1 +‘10)- We shall verify the second in- equality and the first follows by an analogous argument. 91 Claim: 30(1 +‘l0) > 1 . _lu. 1 ' kor)“ 1 J1 - is“ (I - “>52; - e . Taking logarithms we find that 50(1 + X0) > 1 1 + x0 1 - x0) 2x0 Proof: Recall that 60 = e< and so 30(1 + x0) = l Nln—I is equivalent to Ln ( -—-—-—- > --—'. Consider the function 1.+ X0 KO-l l-x 2x . . . . f(x) = Ln 11;. - ;:l for 0 < x < 1. Upon differentiation we find that f'(x) = 2x > 0 for O < x < 1 which implies f is (x - l) (x-l-l) increasing for 04< x < 1. Now f(0) = 0 implies f(xo) > O and so the desired result. Notice that the above argument is independent of the index of B and l and thus we may conclude that Bk(1-Xk) < l < Bk(1+1k), k = 0,1,2,..., a fact we shall make use of later. * Hence r intersects ex and so by (5.17) c* = 2 < c . (5.18) [ i1<1.r*) - e c T1<1.r*> - s T1 - ex X e X 1 Y1 e e co * This shows that if r E M intersects ex and r i r , then T1(c,r) is not a best relative approximation to ex from T1(Sl). Let us * now show that c of (5.18) is equal to oil) of (5.8). First '1: T (lar )(x) * min 1 = min E.$§l.(1 +-x - Ln r*(x)) = xE[a,b] ex xE[a,b] ex 92 * * * x x O O x 0 0 it is easily shown that the minimum desired is 80(1'XO)[1'LD 50(1-y0)] = 50(1+10)[1'Ln 80(1+10)]. Therefore c* = 2 * = T1(1.r )(x) X l + min xEEa ,b] e 2 (1) c as required. 80(1-x0)[1-Ln 30(1-x0)] + l ’ l Now it still remains to consider the case where r E M does . X . . not intersect e on [a,b]. First we shall examine the case where r(x) > ex for all x E [a,b]. Set IX '8 min x = a > O . (5.19) xE[a,b] e Using Property 1, it is easily shown that m(r) = M(l,r) and M(r) = m(1,r). Furthermore it is evident that r(x) = (1 +~a)ex on m(r). Now let 2 denote the best one-sided relative approximation to f(x) = (1 +a)ex on [a,b] from above from the class Rg. Clearly ? E M if there exists r E M for which r(x) 2 (l +a)ex on [a,b]. Thus for every r E M satisfying r(x) 2 (1 +a)ex for all x E [a,b] we have mo - (1 + pie" (1 + a)ex f(x) - (1 + erx (l + (31/)ex S m as with equality if and only if r a f. The function f(x) = 2351- is q(x) uniquely characterized by a set of points {xi}:=1 C [a,b] satisfying asx1<... max X xE[8,b] (1+a)e xE[a,b] (1+a)e r(x ) f(x ) Select x0,x1 6 [a,b] such that x0 = max Elfl-, x1 = e O xE[a,b] e e l . r(x ) f(x ) N(r)(x ) N(?)(x ) max Efiil' Then 0 > 1 > 1 and so -———-—9-< -—-——J;' x x x X x xE[a,b] e e 0 e l e 0 e 1 since the function f(t) = t(1 - Ln t) is increasing for t < l, decreasing for t > 1. (5.20) Now, since xO E M(r) = m(1,r), x1 E M(f) = m(l,?), T1(1.r)(X) T1(1.?)(X) min < min xE[a,b] ex xE[a,b] ex T1(1.r)(X) T1(1.?)(X) We now claim that max x = max x . We xE[a,b] e xE[a,b] e x can see this as follows. Let x1 6 m(r). Then r(xl) = (1+a)e 1, X0 r(xl) Select x0 E [a,b] such that f(xo) = (1+u)e . Then x = e 1 f(x ) T (1st)(x ) T (1.?)(x ) x0 and so 1 x 1 = 1 x O . Therefore, 0 1 0 e e e 94 T1(1.r)(X) g T1(1,r)(x1) T1(1.?)(x0) T1(1.?)(X) max = = max X X x xE[a,b] e e l e 0 xE[3,b] e X since m(r) = M(l,r). Thus E < c and so X e ' T1(C5r)(x) T1(1,r)(x) A T1(1,r)(x) = c max ————-————-— - 1 > c max -—————————— - ex xE[a,b] ex xE[a,b] ex T1<1.i-) e" - plan‘s) (x) =anax -l=max ___—-1: xE[a,b] ex xE[a,b] eX ex Thus the only possibility for a minimal solution in this case is T1(E,r). . . . x Now r, the best relative approx1mation to e , has a char- acterizing sequence a s x < x <...< x s b, d = m +'m + 2 - 6, l 2 d 6 = min(m - as, m - 5q_) where 17 = E , on which x q ‘- i r(xi) - e g x _ ex x = x = lo. 1 = 1,...,d and i e e m — xi — xl r(x.) - e . r(x ) - e 1 1+1 1 , '58“ x = (-1) sgn x , 1 = 1,..., d. Set i 1 e e 1+u - . . 11 = l:i_ . Then xlr turns out to be the best one-Sided relative 0 d approximation to (l+a)ex on [a ,b] from above as {xi}i=1 is a characterizing sequence for x1?“ which satisfies the conditions of * a best one-sided approximation. By uniqueness, r 5 A ; a-sz—-£— E 1 1"1‘05 0 * 1+0! 1 e h =-——-.Nt that —-—-—< <-———— 1‘ ” ere A 90(1-10) ° 8 50(1-10) * 60(1-10) ’ a X * . x r(x) > e for all x E [a,b] and r intersects e . * We shall now make use of Lemma 5.1 to show that T1(c§1),r ) . . x is a (strictly) better relative approximation to e than (D 95 * * * * * T1(E,2) T1(E,Xr ). Clearly M(r ) = M(Xr ) and m(r ) = m(xr ). * * Let x1 E m(r ) and x2 E M(r ). Then x x r*(x1) = ooe 1 lr*(x1> = 190(1-10>e 1 * x2 * x2 r (x2) = eocl+io>e 1r (x2) leo<1+io>e . With the notation in the Lemma, set x = x1, y = x2, tp = BOO-Flo). 8 = 80(1-k0), t = X- Then X 2 Nx (80(1+10)e > 1 * l * . Tlc .r )(x) T1( .r >|NXZ(XBO( +X0)e ) . exl = T1(1,xr*)(x2) . ex1 x x x 1’ * e 2 Nx1e 1) e 2 Tl( 1‘ )(Xl) (5.21) { T1<1.1r*>}{ Tl(l.ir*>(x>}'1 = inin x max xE[a,b] e xE[a,b] ex since m(1,xr*) = M(xr*) and M(1,xr*) = m(hr*) as xr*(x) > ex for all x E [a,b]. Hence, by (5.21), T1(8,xr*)(x) - ex = 1 - T1(E,xr*)(x2) = 1 - E T1(1,Xr*)(x2) X X X e on e 2 e 2 1 'k 2 T1( .ir )(x2) x2 = 1 - e * * [llama )(xl) T1(1.xr mp] + X X e l . e 2 = 1 - i x {1 11(1.ir >(x1) e 2 ] + x . * e 1 Tlamr >(x,> 96 (1) 2 — T1(C1 3r *2)(X )= > 1 - x - 1 - x x 1 + e 2 e 2 e m T1(1,r*)(x2) T1(ci1),r*)(x)-ex thus showing that T 1(c(1),r* ) is a better relative approximation to ex than T1(E,2). A similar type of argument applies to the case where r E M satisfies r(x) < ex for all x E [a,b] and we shall omit the details. This case will be considered in the induction step. Collecting the above results, we find that we have established the following: T1(ci1),r*) is the unique best relative approximation to ex from T1(Sl)' To complete the case n = l we must establish * (5.14) and (5.15). For (5.14), let x1 6 m(1,r ). Then X T1.r* >- el = e 1 C(1>T (1. r *> 1 _ cil’i1<1.r*) X X X e I e 1 e 1 2 = 1 '{:ao(1-io>[l-tn 60(1-io)l +i:}{5o(1')o)[1 ‘ ‘“ 80‘12“} 1 - 60(1-10>[1 - tn 80(1-10)] = =)\ 1 + 80(1-10)[1 - Ln 80(1-10)] 1 0 Next we must show that T 1(c(2 ),r* ) intersects eX in [a,b]. ex - T (c‘ ) r *)(x> From an earlier result, max x = xE[a, b] e T >(x> - e X e m m * (c,r) E S1 with equality if and only if c = C(2) and r E r . X e Since (1-x1)ey s T1(c(1),r*)(y) s (1+)1)ey for all y E [a,b] (2 ) we have that 31(1- x1)ey s T 11(c ,r *)(y) S 51(1+)(1)ey for all N (81(1-11)ey) Nx(81(1+11)ex ) y 6 [a,b]. Recall that y y = X for each e e pair of points x,y E [a,b]. Let (c,r) E S1 be such that i 2 * N(T1(C»r))(x) - ex N(T1(c§ ).r ))(x) - eX S . This implies x x e e oo oo 31(1-11)ey s T1(c.r)(y) s 81(1+11)ey. Therefore (1-11)ey s T (-. r)(y) s (1+1 )ey B1 and so 2. _ Y T1(Bla r)(Y) e ey -)1 s 5 x1 . This allows us to conclude that T1(£-, r) is as good a relative x (1) * 1 approximation to e as T1(c1 ,r ). By the uniqueness of (1) W1( ,r*) wehmm 98 cil) a 3;, r E r*; that is, c = $1c(1)= ClZ)’ r E r*. Before we proceed to the induction step let us establish the following result for which we shall have need. Claim: ak<§ for k=0,1,2,... . l 1-1 K— Proof: Since Bk = 8(171-715) k l k _1__ 1" 1-)(k Zxk 1+1k , or equivalently Ln 1+in<— 1 bk k(Ln 2 ). it suffices to show that x NIy—i (I'M) 2hr 1 < 1+) k I 2 l-xk It is clear that 0 < xk < 1. Set f(x) = --Ln iii- -Ln -- for l+x O < x < 1. Upon simplification, f(x)= %i§-1n 123.- Ln(l-x) +’Ln 2. Now f(0) = O and f'(x) = I%;-[l +--l;-Ln l§§-]. It is easily shown that 1 +~I%;-Ln 13x > O for 0 < x < 1 and so f'(x) > O for O < x < 1. Hence the desired result follows. Now assume the theorem is true for k = n. First let us show n+1 n+1 . that (C; ),...,c (+1 ),r* ) E Sn +1, or equivalently yn = c(n+1) * n N(yn _1) E K since r E M from before. By assumption (aim),...,c(n ),r* ) 6 Sn and 30 Y n-l . (n+1) _ (n) = (n) defined. Now cn — Bncn and so yn B c N(yn_1). Clearly n n Oi< C(n) n E K. Thus N(yn_1) is well- < 2 and O <‘N(yn_1) S ex since N is one-sided from beIOW. ThuS, by the claim, 8 nC§n) < 2.. 2 = e and so 0 < yn = 2 (n) c(n)ex1+x BnC n N(Yn _1) 5 BnC e and so yn E K. We shall now show c(n+1) c(n+1) (n+1) and * ,...,c n+1 ,r r*) f 1 ,...,c n+1 r given by (5.7)-(5.9) is the unique best relative approximation to (n+1) that Tn+1(c1 x e from Tn+1(Sn+1). As in the case n 1 we shall show that r) E S where we allow c to vary, for any (c1,...,c n+l’ n+1 n+l’ I I III-i ll 311‘ 99 Tn+1(c1,...,cn +1,r)(x) is closest to ex in the relative norm only when cn+1 = T (c 1 r)(x)2 T ( 1 )( ) (5°22) n+1 1’°"’cn’ ’ . n+1 Cl"°°’cn’ ,r :x ] max x +' min x xE[a,b] e xe[a,b] e T (c ,...,c ,1,r)(x) where max n+1 1 x n s 1 with equality only at those X€[a,b] e points y where Tn(c1,...,cn,r)(y) = ey. This is true since Tn+l(c1,...,cn,l,r) = N(Tn(c1,...,cn,r)). For the above choice of Cn+1’ X1 6 M(c1,...,cn,1,r) and x2 6 m(c1,...,cn,1,r) we have V x1 e -n+1(C1!"°!Cn’Cn+19r)(Y) = Tn+1(cl"°°3cn,cn+19r)(x1) - e ey x1 00 e x2_ : e -Tnn+1(cl,...’c 9Cn+19r)(x2 ) x2 e Now if cn+1 > cn+1 then for x1 6 M(c1,...,cn,l,r) x1 x1 Tn+1(c1,...,cn,En+1,r)(x1) - e >’Tn_'_’1(c1,...,cn,cn+1,r)(x1) - e x x e 1 e 1 Tn+1(c1,...,cn ,cn +1,r)(x) - eX x C e (I) Similarly, if en+1 < Cn+l’ then for x2 6 m(c1,...,cn,l,r) x2 e - Tn+1(c1,...,cn,8n+1,r)(x2) Tn+1(c1,...,cn,cn+l,r)(x) - e x x e 2 e a: and thus the desired result. Next we must show that c of (5.22) n+1 II III Ala-PI Ififil... ' till. III 1 I 1' illll': '1' Ill 51 l III- 100 (n+1) n+1 (n+1) (n+1) gives the correct value of c correSponding to c1 ,...,cn Tn(c{n),...,c§n),r*)(x) - exl X e Tn+1(c C(n+1),...,c§n+1),1,r*)(x) * and r . By the induction assumption l on = A . Furthermore the minimum of n ’ ex occurs on the set M(c§n+1),...,cn (n+1), r*) U m(c (n+1),...,c§n+1),r ) and is given by Bn(1-1n)[1 - Ln Bn(1-xn)]. Hence c(n+1) _ 2 cn+1 1 + Bn(1-xn)[1 - Ln Bn(1'xn)] : satisfies (5.22) and suppose as desired. Next let (c1,...,cn+1,r) 6 S where Cn+l n+1 Tn(c1,...,cn,r) intersects ex on [a,b]. Then by the induction assumption we know that (C (n+1),...,c§n+1),r*))(x)- exl N(Tn(c1,...,cn,r))(x) - ex ‘ S N(Tn X e X e 00 +1 in )=°i’ * i = 1,...,n and r E r . Suppose that (c1,...,cn,r) ¢ (C§n+1),...,c§n+1),r*). Then for all (c1,...,cn,r) 6 Sn with equality only if c , Tm+1(c1,...,cn ,1, r)(x) (C (n+1) (n+1) min _< min * Tn+1 ""’Cn alar )(X) x x€[8,b3 e xEEa.b] ex (n+1) and so c n+1 > cn+1 . (n+1) c(n+1) ,..., cn+1 ,r* Thus, for x E M(c1,...,c and 1 n+1’r) 26 M(c1 T X x1 n+1(C1:ooo,Cn+1,r)(X)'e l = Ch+1 Nr1(T (C 1n,o..,C ,r))(x 1) - e x X e l 1 on e (n+1) (n+1) 1N(Tn(c1 ,...,cn X 2 e w>> -e 101 (n+1) (n+1) c(n+1) > Cn+1 N(Tn(c1 "°"c r*X))( 2)_ex2 x2 e +l +1 * _ Wn+l( (n )""’°§:1 )’r )(x) ’ ex _ x2 8 co Finally we consider the case where (C1:°'°’°n+1’r) E Sn+1 for which Tn(c1,...,cn,r)(x) does not intersect ex on [a,b]. Let us first consider the case where ex " Tn(C1,...,Cn,r) (X) min X = a > 0 ; XE[3,b] e that is, ex > Tn(c1,...,cn,r)(x) for all x 6 [a,b]. Set ex - Tn(c1,...,cn,r)(x) max = a . x xE[a,b] e Since Tn(sn) C C+[a,b] we have that B < l and so a < B < 1. T (c ,...,c ,r)(x) . First max n 1 n = 1 - a- - Bn(1+)\1) X€[a 1)] ex (n+1) (n+1) Now max ”m(clr ,...,c:n ,r *)(x )= xe[a,b] ex rn(x> )‘max xE[a,b] ex Tn x€[8,b] ex T (c ,...,c ,r)(x) min “ 1 n , (5.24) XE[a,b] ex C —2-,r)(x) is a better relative starting for otherW1se Tn(cl"°"cn-l’x . . x _ approx1mation to e for the Newton operator than 18 (n+1) C(n+1) r* n 9 1 ,..., )(x). Here we have used the fact that Tn(c m(c1,...,cn,r) = m(c1,...,cn,1,r), M(c .,cn,r) = M(c1,...,cn,1,r) (5.25) 1,0. which is established using Property 1. Choose xo,x1 6 [a,b] such + * that x0 6 M(C1n 1),...,XC§H+1),I ) and x1 6 M(c1,...,cn,r). Then, by (5.23), ,...,XC T (Cin+l) (n+1) n n .r*> Tn(x1) X X e0 e1 and so, by (5.25), Tn+1(c§n+1)a - - ° acin+1):xcr€n+1)a 1:r*) 0‘) max = xE[a,b] ex +1 Tn+1(cin ),...,c:n+1),xc§n+1),l,r*)(xo) = Tn+1(c1,...,cn,1,r)(x1) _ x0 x1 e e 103 T (C 00- C ,1,r)(x) wax n+1 1’ x’ n . x€[a,b] e E [a, b] such that yo 6 m(c(n+1) ,...,XC§n+1).r*) Choose y0,y1 and y1 E m(c1,...,cn,r). Then (n+1) (n+ 1) * 1 > Tn(C1 ,...,xcrl ,r )(yo) > Tn(c1’000,cn,r)(YI) e e and so Tn+1(C1:° ° ° ,cn,1,r)(x) = Tn+1(c1:' ' ° :Cn913r)(y1) min x x€[8,b] e ey1 (n+1) (n+ 1) * < Tn+1(cl :°'°a)\cn 1:1. )(yo) - y e 0 1 1 Tn+1(c§n+ ),..., c§“+,1)r*)(x) min x€[a,b] e where we have made use of (5.13) and (5.25). Hence 8 < c n+1 n+1 (c (n+1) (n+1) 1 * where E corre3ponds to ,...,cn_1 ,xc§n+1),r ) and n+1 cn+1 to (c1,...,cn,r). Thus x ( +1) (n+1) (n+1) . TCH+1( n 300°:Cn_1 .16 n s cn+1,r *)(x) X e (n+1) c(n+1) (n+1) * (C a°'°ac AC :19): )(X) = E x Tn+1 n- -1 n _ 1 n+1 xE[a,b] ex co _ . Tn+1(c1,...,cn,1,r)(x) _ Cn+1 max x - 1 x6[a,b] e Tn+1(c1,...,cn,l,r)(x) max x - 1 xE[a,b] e < Cn+1 104 X e ' Tn+1(°1’° ' ° ’cn+1’r) 0:: X e (D Thus, we must show that 1(c(n+l) c(n+l ) ,...,c n+1 ,r *)(x) is a (strictly) better relative approximation to ex than T n+1(c C1n+1) (n+1) ,...,cn-l , M(n-H') 3 an , cn+l’r *)(x). Here we shall make use of the second part of Lemma 5.1. Set x = x1, y = y1, e = Bn(l-xn), v = Bn(l+1n) and _ _ Li. 1 k — t where x - Bn(1+xn) . Observe that O < K < . In order to apply the lemma let us make the following observations. For n+1 +1 * +1 +1 x16 M(c ( ),...,c§n ),r ) and x2 6 m(c (n ),...,c§n ),r ), 1 3 a n 1 1- x = J = a (In > x n n 1 e x (n+1) (n+1) l and so Tn(c1,...,cn ,r *)(x l)= Bn(1+1n)e . Also Tn(c{n),...,c§n),r*)(x) - ex — . 1. ex - x“ imp 1es c(n+1) 1 1 Tn(c§n+ ),...,cr(1'_"{), ir,r*)(x) - eX x n = x“ which in turn yields e X a: T n(c: (n+1),...,c(n+1),r* r)(x2)= Bn(1-)‘n)e 2. Applying the lemma, N( (1- >ex2> N( (l- >ex2 "1 a. k. > mm X. > , e X X X e 2 e 2 N(xan(1+xn>e 1> or equivalently, 105 (n+1) (n+1) (n+1) (n+1) N(Tn(c1,...,cn U))(x N(un(c1,...,cn h))(2) x2 > x2 O e e , CXI um: (C(“+1>,,..,c§“+1>,r* Mac > Now Tn+1(c§n+1) , . . . ,ciiil) ,xCrfin-H‘) ,En+1,r*) (x) - eX e)? E (n+1) C(n+1) (n+1) * = 1 - Cn+1TC1n+1( 9°" C-I'l 1 5 Ken ,1,!" )(X2) X 2 e = 1 .. 2 N(XTr1 (C (n+1),...,cr(ln+1),r* ))(x1) (:2 + 1 X e 1 110:11n (C(“+1),...,c (n+1), r"‘))(x2 ) > 1 - 2 1 + N(T (c{“+1),...,cr(1“+1),r* ))(x2) (n+1) C(n+1) _ 1T°1n+1( ""’C n+1 ’r *)("2) .. x2 e x ’ e . (n+1 (n+1) . ' . show1ng that Tn+l(cl ),...,c cn+1 ,r *)(x) 18 a (strictly) better . x (n+1) (n+1) relative approx1mat ion to e than '1‘n+1(<:1 , . . . ,cn_1 , c(n+1) .. cn , Cn+1’r *)(x). Similarly, the case where Tn(c1,...,cn,r)(x) x > e leads to the same result. 106 Gathering the above results, we have that +. Wu+l< (n 1),...,CS:I1),r*) is the unique best relative approximation to ex on [a,b] from T To complete the induction we n+1(Sn+1) ° must verify the following: (n+1) (n+1) Wn+l( ,...,c n+1 ,r *)(x) - ex - (5 26 ex - xn+1 ’ ° ) Tn+1(C C(n+2),...,c (:12),r* )(x) intersects ex on [a,b] (5.27) and N(Tn_l_1(C(n+2),...,cr(1r_:_-{2),r*))(x)-ex S x e N(T (C ,...,C ,r))(X) "' ex n+1 1 n+1 (5.28) x e m for each (c1,...,cn+1,r) 6 Sn+1 with equality if and only if . = c§n+2), i = 1,...,n+1 and r E r*. 1 1 To establish (5.26) observe that for x1 6 m(c(n+1),...,c§n+1),r* n+1 n+1 1(c( ),...,c(+1),r*)(x) - eX x _ e m x 1 n+1 n+1 n+1 = e ' CIE+1T ) T°n+1(( )’”"°r(1 )’1’r)("1) x1 e 2 = 1 -{Bn(1-)\1)[1-Ln Bn(1-)\1)]+1 {Bn(1‘)\n)[1'{ln Bn(1')\n)]> 107 1 - Bn(1-xn)[1 - Ln en(1-xn>] - 1 + Bn(1-xn)[l- Ln Bn(l-xn)] g >‘n+l ° (n+1) (n+1) Similarl 1(C "H’Cnfl r*)(x) - ex = x for y, ex n+1 m X E M(C§n+1),...,c§n+1),r*). By the induction assumption Téc§n+1),...,c (n+1),r* )(x) intersects ex on [a,b]. Now (n+1) C(n+1) (l-x )s “+1(c1 ,...,cn+1 ,r *)(X) 5 (1+ ) and so n+1 ex xn+1 (n+2) (n+2) (1_ )5 TCn+1(1 v" Cn+1 13%)“) 5 (1+ ) Bn+l N1+1 ex E3n+1 >‘n+1 ' n+2 n+2 n+1< ( ),...,cr(1+1),r*)(x) Since x is a continuous function of e x it assumes all values between. Thus there exists x0 6 [a,b] (n+1) C(n+2) * *0 such that M+l(c ,...,c n+1 ,r )(x 0) = e and so (5.27) is established. Finally (5.28) follows as in the case n = 1. Indeed, by (5.26) (1- xny+1)e s T +1(<:(‘“+1’...., 51:1); )(y) s (1+xny+1)e for all y 6 [a,b]. Consequently (n+2) c(n+2) y “M(c .. c+1 ,r*>(y> san+1<1+xn+1>e e s T y. Bn+l(1-xn+1) Recall that y x Ny(Bn+l(1-xn+l)e ) _ Nx(Bn+-l(l'Ii-a‘nfll-l)e ) X By e for each pair Of points x,y 6 [a,b]. Let (C19°"9cn+1’r) E Sn+1 108 satisfy N(Tn+1(c1,...,cn+1,r))(x) - ex ex S N(Tn+1(c‘“+2)..... c§:’{2>,r*))(x) - e" x . e This can only happen if - V y Bn+1(1 xn+1)e S Tn+1(cl’°°°’cn+1’r)(Y) S Bn+l(1-'.)‘n+l)e ' Thus y Tn+1(c19'°°:cna ;n+lar)(Y) ’ e -x S n+1 S n+1 ey xn+1 c +1 and so T +1(c1,...,cn, —2-,r) is as good a relative approximation n Bn+1 x n+1 n+1 , to e as Wu+l< ( ),...,c§+1 ),r ). By uniqueness of Tn+1(cc(n+1),...,c (:11),r* ) we have that c1 = c§n+2), i = 1,2,...,n+l * and r E r . This completes the proof of the theorem. Section 3: Execution of the Scheme In this section we shall show how this iterative scheme would be programmed. Suppose we wish to calculate ex for x 6 [a,b] within a tolerance of e > 0. First we calculate X0 and F, (where m and E are specified) with: - x r x - e . = inf m rER k0 = 109 and then calculate the sequences {Bk):=0 and {xky:=0’ comparing the value of xk with e at each step: _L 1-xk Zxk 1 Bk = e 1+xk , k = 0,1,2,... «11-x: x 1 ' Bic-la‘hwi)‘:1 ' L“ Bic-1(1"‘1<-1)J k . Let n be the first integer for which e3> x“. For this n cal- culate cén), k = 1,2,...,n using dk = 2 , k = 1, ..,n Bic-la'kk-ifl1 ' L“ Bk-1(1-xk-1)] + 1 n cé ) = Bkdk , k = 1,2,...,n-l C(n) g d n n * .. and r (x) = Bor(x) . We then store the values Ci“), k = 1,...,n. The algorithm is: * y0 = r (x) yk(x) = c£§)yk_1(x)(l flx - Ln yk_1(x)), k = 1,2,...,n . Remark 1: ‘We would like to point out that Theorem 5.2 is of theoretical interest since it is one of the few cases where we can find a best approximation from an algebraic combination of approxi- mants. B IB LIOGRAPHY 10. ll. 12. 13. BIBLIOGRAHIY E.W. Cheney, Introduction to Approximation Theory, McGraw-Hill, Inc., New York, 1966. F. Deutsch, Uniform Approximation with Interpolatory Constraints, J. Math. Anal. Appl. 24 (1968), pp. 62-79. J.S. Frame, A.Variation of Newton's Method, American Mathematical ‘Monthly, Vol. 51 (1944), pp. 36-38. W. Rammerer, Optimal Approximations of Functions; One-sided Approximation and Extrema Preserving Approximations, Doctoral Thesis, University of‘Wisconsin, 1959. S. Karlin and W.J. Studden, gghebyscheff Systemmz With Applica- tions in Analysis and Statistics, Interscience Publishers, New York, 1966. R.F. King, Improved Newton Iteration for Integral Roots, Math. Comp. 25 (1971), pp. 299-304. R.F. King and D.L. Phillips, The Logarithmic Error and Newton's Method for the Square Root, Comm. ACM 12 (1969), pp. 87-88. H.L. Loeb, Un Contre-exemple a un Resultat de M. Claude Gilormini, C.R. Acad. Sci. Paris, Ser. A 266 (1968), pp. A237-A238. H.L. Loeb, D.G. Moursund, L.L. Schumaker, G.D. Taylor, Uniform Generalized Weight Function Polynomial Approximation'With Inter- polation, Siam J. Numer. Anal. 6 (1969), pp. 284-293. H.L. Loeb, D.G. Moursund and G.D. Taylor, Uniform Rational Weighted Approximations Having Restricted Ranges, J. Approx. Theory 1.(1968), pp. 401-411. G. Meinardus and G.D. Taylor, Optimal Starting Approximations for Iterative Schemes (to appear). G. Merz, Padésche Nflherungsbrfiche und Iterationsverfahren hBherer Ordnung, Doctoral Thesis, 1967. D.G. Moursund, Chebyshev Approximation Using a Generalized Weight Function, Siam.J. Numer. Anal. 3 (1966), pp. 435-450. 110 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 111 D.G. Moursund, Computational ASpects of Chebyshev Approximation Using a Generalized Weight Function, Siam J. Numer. Anal. 5 (1968), pp. 126-137. , Optimal Starting Values for the Newton-Raphson Ca1- culation of ,/x, Comm. ACM 10 (1967), pp. 430-432. D.G. Moursund and G.D. Taylor, Optimal Starting Values for the Newton-Raphson Calculation of Inverses of Certain Functions, Siam J. Numer. Anal. 5 (1968), pp. 138-150. , Uniform Rational Approximation Using a Generalized Weight Function, Siam J. Numer. Anal. 5 (1968), pp. 882-889. I. Ninomiya, Best Rational Starting Approximations and Improved Newton Iteration for Square Root, Math. Comp. 24 (1970), pp. 3 91 '404 e A. Perrie, Uniform Rational Approximation with Osculatory Interpolation, Doctoral Thesis, University of Oregon, 1969. J.R. Rice, The Approximation of Functions, Vol. I, Addison- Wesley Co., Reading, Mass., 1964. T.J. Rivlin, An Introduction to the Approximation of Functions, Blaisdell Publishing Co., Waltham, Mass., 1969. H.E. Salzer, Note on Osculatory Rational Interpolation, Math. Comp. 16 (1962), pp. 486-491. L. Schumaker and G.D. Taylor, On Approximation by Polynomials Having Restricted Ranges, MRC Tech. Summary Report 835, Madison, Wisconsin, January 1968. P.H. Sterbenz and C.T. Fike, Optimal Starting Approximations for Newton's Method, Math. Comp. 23 (1969), pp. 313-318. G.D. Taylor, Approximation by Functions Having Restricted Ranges III, J. Math. Anal. Appl. 27 (1969), pp. 241-248. , 0n Approximation by Polynomials Having Restricted Ranges, Siam J. Numer. Anal. 5 (1968), pp. 258-268. , An Improved Newton Iteration for Calculating Roots Which is Optimal (to appear). , Optimal Starting Approximations for Newton's Method, J. Approx. Theory 3 (1970), pp. 156-163. K. Taylor, Contributions to the Theory of Restricted Polynomial and Rational Approximation, Doctoral Thesis, Michigan State University, 1970. 112 30. J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. 31. , On a Class of Iteration Formulas and Some Historical Notes, Comm. ACM 4 (1961), pp. 276-278. 3461 m1 ms ”0 m3 “0 Ilfl'lulmmm