DIRECT CHEBYSHEV APPROXIMATION by JOHN ROBERT HENDERSON B . A . , The University of British Columbia, I960 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T OF . T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF ARTS in the Department of MATHEMATICS We accept this thesis as conforming to the . required standard THE UNIVERSITY OF BRITISH COLUMBIA May, 1963 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree t h a t the L i b r a r y shall'make' i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r -m i s s i o n f o r e x t e n s i v e c o p y i n g of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department- or by h i s r e p r e s e n t a t i v e s . . I t i s understood t h a t copying, or p u b l i -c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department of '\6-Th-e. I ^ w ^ l v' c S The U n i v e r s i t y of B r i t i s h Columbia, Vancouver 8, Canada. Date Abstract The Approximation P r o b l e m and s p e c i f i c a l l y , " d i r e c t " rational Chebyshev approximation i s discussed. A brief summary i s made of " d i r e c t " Chebyshev approximation. The remainder of the thesis i s devoted to various aspects of a "Remes-type" A l g o r i t h m for rational Chebyshev approximation, as proposed by F r a s e r and Hart. It i s fi n a l l y concluded that the inherent di f f i c u l t i e s of the method would generally outweigh the advantages of the rational approximation which it obtains. We accept this abstract as conforming to the required standard - iv -Ac kno wl e dg me nt . I wish to thank D r . T . E . Hull and D r . D. Derry for thei valuable criticisms of the presentation of this thesis, and the Mathematics Department, University of British Columbia, for a Summer Grant (1962), and a Teaching Assistantship over the pa two years (1961-1963). i i Table of Contents Page I Notation 1 II Introduction 2 III Basic Theorems 8 IV Methods of Direct Chebyshev Approximation 10 A) A Method Using Zeros of the E r r o r Curve 10 B) Iterative Methods Using the Absolute Extreme of the E r r o r Curve 11 C) Programming Methods 13 D) Other Methods 15 V The Re mes Rational Algorithm and Associated Problems 17 A) Difficulties of the Iterative Procedure 18 B) Difficulties of the Overall Procedure 24 C) Other Problems - Timing 2 6 - Stability 28 VI Numerical Results 31 VII Conclusion 33 VIII Bibliography 34 i i i T a b l e s , D i a g r a m s , G r a p h s : E r r o r B o u n d s f o r A p p r o x i m a t i o n o f e x ( T a b l e I) F o l l o w i n g p a g e 6 T h e R e m e s R a t i o n a l A l g o r i t h m ( F l o w D i a g r a m I) " " 17 ( N o t a t i o n f o r F l o w D i a g r a m II ( M o v e m e n t o f C r i t i c a l P o i n t s ( F l o w D i a g r a m II) " " 18 C o m p a r i s o n o f k , n c ( T a b l e II) M M 2 8 S t a b i l i t y a n d W o r d l e n g t h f o r e x ( G r a p h I) " " 3G ( S u m m a r y o f M o v e m e n t o f C r i t i c a l P o i n t s S i n ( 3 , 3) a p p r o x i m a t i o n o f e x ( G r a p h s o f s a m e ( G r a p h s I I - V ) " " 32 E * f o r v a r i o u s f u n c t i o n s ( G r a p h s V I - V I I I ) " " 32 - 1 -N o t a t i o n T h e f o l l o w i n g a r e the m a i n c o n v e n t i o n s and n o t a t i o n u s e d t h r o u g h -out the t e x t : - P ( x ) / P ( x ) , Q(x) denote p o l y n o m i a l s ; R(x ) z / Q ( x ) d e n o t e s a r a t i o n a l f u n c t i o n ; f(x) i s r e t a i n e d f o r the f u n c t i o n b e i n g a p p r o x i m a t e d . T h e a p p r o x i m a t i o n i n t e r v a l i s i n g e n e r a l Ca,b3 o r m o r e s p e c i f i c a l l y C- 1, 13 . - A n a s t e r i s k " * " d e n o t e s " C h e b y s h e v " o r " b e s t u n i f o r m " . - A s u b s c r i p t d e n o t e s a m a x i m u m d e g r e e e.g. dev^es a C h e b y s h e v (best u n i f o r m ) p o l y n o m i a l of m a x i m u m d e g r e e n . (k) - S u p e r s c r i p t s e g . V '(x) denote e i t h e r a d e r i v a t i v e o r d e r o r the n u m b e r of a s tep of a n i t e r a t i v e p r o c e d u r e . In any p a r t i c u l a r c a s e , the c h o i c e b e t w e e n t h e s e a l t e r n a t i v e s w i l l be c l e a r . ttc. = m-»-m + 2. i s two m o r e than the s u m of the m a x i m u m d e g r e e s of a r a t i o n a l f u n c t i o n ^ n ^ . 5 Q m ( x ) - En ,m"f o r s i m p l y E * n , m o r E*f i f t h e r e i s no a m b i g u i t y , Pn*(x ) denote the C h e b y s h e v e r r o r i n a p p r o x i m a t i n g f by Q m » ( x ) • " ( n , m ) a p p r o x i m a t i o n " d e n o t e s a n a p p r o x i m a t i o n of the f o r m *n{f\. U m ( x ) - 2 -Introduction In numerical work i t i s commonly desirable to replace a "complicated" continuous function by a " s i m p l e r " one; one which represents i t " s u f f i c i e n t l y w e l l " for some p a r t i c u l a r purpose. In this way the "complicated" continuous function i s "condensed" into a more tractable form. "Complicated" i m p l i e s there are d i f f i c u l t i e s concerning the length of time required for function evaluation and/or, with computer space l i m i t a t i o n s , for the commands required. F o r example, the solution of a p a r t i c u l a r l y complicated f i r s t order di f f e r e n t i a l equation can be represented to some extent by tabulated values for equal increments i n x ( i . e . by interpolation), but possibly considerably more accurately by a low degree polynomial approximation determined by its zeros XJ at specially chosen points. The sense of the approximation, i . e . recognition of what details of the function we are w i l l i n g to give up for " s i m p l i c i t y " , i s i m p l i c i t i n the phrase "s u f f i c i e n t l y good approximation". This art of choosing a suitable norm has too many ramifications to even begin to consider here, but it i s for example brought out by the difference between least squares and Chebyshev approximations. The main advantage of least squares approximations i s the s i m p l i c i t y by which they can be obtained - - a feature which i s p a r t i c u -l a r l y evident i n the hist o r y of approximation theory. Laplace posed one of the f i r s t Chebyshev approximation problems (solution of an inconsistent set of l i n e a r equations) i n 1799. His procedure for solving the problem as i t stood was completely i m p r a c t i c a l and - 3 -remained so until 1804 when Legendre substituted the L 2 (least square) norm for the Chebyshev norm. With the success of his procedure, the use of the least squares norm has never slackened. On the other hand, Chebyshev approximations provide a known upper bound (the least possible for the p a r t i c u l a r interpolation class used) on the e r r o r expected when using them. This i s probably the usual goal, but unfortunately,with present algorithms the work required to generate such approximations of any p r a c t i c a l u t i l i t y i s so great that it i s prohibitive without the aid of d i g i t a l computers. With this inaccessible character, it is natural that interest i n algorithms for Chebyshev approximation has been revived only in the last few y e a r s . As far as.Chebyshev approximation algorithms themselves are concerned, we w i l l distinguish two fundamental types. The distinction i s i n terms of where the e r r o r of the approximation genera-ting algorithm (as distinct f r om the e r r o r of the approximation itself) i s generated. The two types are: 1) " i n d i r e c t " algorithms with an i n i t i a l e r r o r introduced by the approximation generating algorithm, and 2) " d i r e c t " algorithms with e r r o r of the procedure being i n t r o -duced during a final i terative procedure. Although this terminology i s somewhat ambiguous, it i s retained i n honour of Maehly [ l 5 l , a modern pioneer in the approximation algorithm f i e l d . D iagramatically, this difference can be represented as follows: - 4 -D i r e c t Algorithms (usually, non-terminating iterative procedures) e r r o r of in d i r e c t methods A ty p i c a l pair of such methods i s "Economizing" (an indirect algorithm) as proposed by Lanczos [ l 3 l and the direct procedure known as the Remes A l g o r i t h m for polynomials [2 l] which w i l l be discussed l a t e r . In the remainder of this thesis only direct algorithms w i l l be discussed. The class of " s i m p l e r " functions, i . e . the subspace of approxi-mations, has commonly been taken to be polynomials of specified maxi-mum degree although 'other subspaces of trigammetric polynomials, classes of exponential functions,and rational functions have been con-sidered. Disregarding piecewise polynomial functions, since only the basic operations of (+,x) are available, rational functions are essent i a l l y the most general function form for digital computer com-putations. For this reason, this thesis w i l l be r e s t r i c t e d to rational function approximation and the special case of polynomial approximation. Two further points should be noted. There i s considerable value i n making transformations before applying approximation Indirect Algorithms (commonly having a finite number of steps) i n i t i a l app roximation - 5 -algorithms. Unfortunately, however, there i s no general rule available which gives the ideal transformation required. Some indication i s given by the T a y l o r series remainder t e r m in the case of polynomial approxi-mation. The choice of the appropriate transformation is another " a r t " , w e l l exemplified by Hastings C9!l . r Secondly, there i s a problem of motivation. What i s the value of considering rational function approximation algorithms when i n comparison (as w i l l be seen later) analogous polynomial algorithms t ha-ve none of their troubles? The answer of course i s the degree of approximation. Hopefully, the extra freedom allowed i n the choice of f o r m w i l l significantly reduce the maximum e r r o r (E*)- In practice, varying degrees of "reduction" are observed (see graphs in Numerical Section). A more analytical insight into this problem is given by the following considerations: Let R(x) = Pn(x) be such that Qm(x) Pn(xj) ,. .. . ,\ = f(xj) at n c - l points x; ...... ...I) take an a r b r i t r a r y y such that -I i x, <y < X*,-i - ' and consider: g(x) = f(x) Qm(x) - Pn(x) - S^MQM'W] . (Y-KYX-*IY • M*,-^ then g(x,.) = g( X a.) = .... = g{*nc_i) = g(y) = 0 i . e . g(x) vanishes n c - i times on £-1, l3 , so that by successive (n - 1) applications of Rolle's Theorem, g v c" ' ( x) vanishes at least once i n (-1, 1) i . e . there exists a 9 6 (-1,1) such that g ^ n c _ 1 ^ ( 9 ) = 0 r, ^ P n (x ) now let f(x), Q m ( x ) coincide in particular at the ttc-1 zeros of Tvv-i Lt>> - % ( V ^ e ' cos Ov-i^ e 5 x - cos © '-2.) from which, taking absolute values, f i v. V - ' ...3> Pn* where denotes the irreducible Chebyshev approximation to f on [.-1, l] , and Qm is determined by 2), | ) . Equation 3) gives some idea of the relative value of polynomial and rational function Chebyshev approximations. To proceed further with the general case, one needs an expression for min |Qm*(x)| and a means of eliminating Qm(x) from the right-hand side of 3). The solution of these problems does not seem to have been attempted. For two special cases (m = 0 - the polynomial case - and m = 1) we can readily get a somewhat deeper insight. For polynomials (m = 0) the two above-mentioned difficulties disappear and we obtain from 3), This result has been given by Shohat [25"] who has also produced a lower bound: />H>) assuming f ( ^ l ' (Q) > 0, by a consideration of 3) in the polynomial case, without introducing absolute value. A sample application of these bounds for e x , x 6 [-1, 1] is given in Table I, the "true value" being obtained numerically from the Remes polynomial algorithm. In the case m = 1 we have Qm(x) = Q,(x) = 1 + Qzx- ^ w e Pn(x) assume that our choice 2) produces r^j(x) with no pole in the interval (see Theorem introducing Section V), then | < | so that Table I E r r o r Bounds on En(f) for e x — According to Shohat xet-1, 11 Polynomial True Value: Degree Upper Bound ^ En* (e x) £ Lower Bound 0 .272 X 10' . 154 X 10' .368 X 10° 1 .680 X 10° .279 X 10° .920 X IO" 1 2 .113 X 10° .450 X IO" 1 . 153 X IO" 1 3 . 142 X 10" 1 .553 X 10"2 . 192 X 10"2 4 . 142 X I O - 2 .547 X IO" 3 . 192 X IO" 3 5 .118 X ID" 3 .452 X 10-4 . 160 X IO" 4 6 .843 X I Q ' 5 .321 X IO" 5 . 141 X IO" 5 7 .527 X 10" 6 .200 X 10" 6 .713 X IO" 7 8 .329 X i o - 7 .111 X IO" 7 .445 X IO" 8 9 . 183 X 10" 8 .552 X 10-9 .248 X 10-9 10 .915 X I O " 1 0 .250 X I O " 1 0 . 124 X I O " 1 0 _ 7 -In p a r t i c u l a r , for e x, x 6 C-l, l l we have &y - pji!k>l ^ i r ^ i L ± _ - - — — ...7) where Q 1 * ( x ) = 1 + 0.2*x Thus, we have E E * , which i s not an extremely attractive result, but i t i s thought that p a r t i c u l a r functions f may be much more rewarding. The following work has two purposes: 1 ) to describe b r i e f l y the main direct polynomial and rational function algorithms for Chebyshev approximation on finite i n t e r v a l s , and 2 ) to discuss in some detail c ertain aspects (stability, timing, and problems unique to rational approximation) of a method of rational Chebyshev approxi mation as proposed by F r a s e r and Hart £7] , with the object of evaluating its p r a c t i c a l implementation. 8) I - 8 -Basic Theorems Before turning to the various algorithms, we w i l l divert our attention slightly to some of the basic theorems upon which the algorithms are constructed. In the f i r s t place, existence and uniqueness are guaranteed for rational function approximations: PS(x) Theorem: There exists a unique Chebyshev approximation Q ^ ^ J to a continuous function f(x) on Ca>b3 . Proof: The reader i s r e f e r r e d to C. de l a Vallee Poussin &0] and Chebyshev [3] for the m = o (polynomial) case, and to Chebyshev [3] , Rice t23] in the general case. C h a r a c t e r i -zations are given by the following theorems: Pfi(x) , Theorem: The Chebyshev rational function approximation Q m ( x ) * 0 reduced to lowest terms, to a continuous function f(x) on Pn(x) \a., b"] i s characterized by f(x) - Q ^ ^ J assuming with alternating sign the value I to - I at not less than n + m+2 - min ( ) points i n [a, b3where h-jl ^*n-V are the highest powers of x o c c u r r i n g i n Pn(x), Qm(x) respectively whose coefficients^? 0. Proof: See Achieser [l\ and Rice [23, p. 3-60J . As a special case, for polynomials, we have m = o (and H- 0 ) so: Theorem: The Chebyshev polynomial approximation PK(x) to a continuous function f(x) on [a,b] i s characterized by f(x) - Pn(x) assuming - 9 -with alternating sign the value: at not less than n + 2 points in ja, b] The latter two theorems determine certain "critical points which in turn, determine the best approximation - - s o defining an approximation algorithm. The following theorem is of a different nature. It is stated here not only because it is the basis of an approxi-mation algorithm but also because of the insight it gives into the nature of Chebyshev approximation. polynomials of degree n) define L 'P ' f as the least pth degree approxi-mation to f on [a, b) (in a manner analogous to the least squares (p = %) approximation). Then: Proof: Theorem: There is a subsequence of p = 1 ,2 , . . . which converges to the Chebyshev approximation to f on [a, b] . In the polynomial case, the stronger result of L^P^f itself -Chebyshev approximation has been shown by Jackson [l0\ . The general case is given by Polya [191. - 1 0 -Methods of D i r e c t Chebyshev Approximation A) Methods Using Iteration on the Zeros of the E r r o r Curve These methods were proposed by Maehly |[l53 for both polynomial and rational function approximation. Let ( ^ i \ > • - • n c - i with ^11 Xi < X^<U < +1 be n c - 1 otherwise a r b i t r a r y i n i t i a l points. The successive application of the following two steps defines an i t e r a t i o n procedure: ,x ^ (k) P n ( k ) ( x ) 1) Pn , or more generally, ~ (k), . i s determined on the Qm v '(x) kth step by: >0O 2 ) Modify \ ^ \ (each method giving a d i s t i n c t i t e r a t i o n procedure), so obtaining \ ^ so that e v n " M k ; w i l l tend to be of equal value on the next (k + l)th step. In the polynomial case, i t i s to be noted that i s a lin'ear system having associated with it an (n+l)th order Vandermonde determinant i n the ix^\ • Thus, if the are kept distinct and i f f(xj) ^ 0 simultaneously for a l l j = l , 2 , . . . n c - l , then the l i n e a r system i s always non-singular and the ite r a t i o n can i n p r i n c i p l e be continued indefinitely. Under certain severe assumptions Maehly has shown where k i s some constant and xj'" denotes the position of XJ for the best Pn*(x) Chebyshev approximation ^ r - . This result forms the basis of a rule Qm (x) for step 2) above, which reduces (increases) | > ^ — "X ||M \ ^'JV'VI ^ i s too large (too small) i n comparison with other values (j = 1, 2 , . ..n c-2). E m p i r i c a l l y he noted that the use of this rule gave quadratic convergence for both polynomial and rational function approximations. B) Methods Using Iteration on Absolute E x t r e m a of E r r o r Curve .As an example of such a method let us f i r s t consider what is commonly known as the "Exchange Method" e.g. Stiefel [26, p.220]. For nth degree polynomial approximation the procedure i s as follows: 1) Select any n c = n + 2 points • _\ « yj'ic ... < +1 2) Solve: thus obtaining the best approximation Pn'°'(x) on the finite set \ X J ( o ) ^ - [l2, p.223] 3) Determine an x* such that: 4) Let: W) ~ \\*?\ ~*?\ "\*'\ where x ^ 0 ) i s so chosen that Pn'°' ( x ^ 1 ) ) - f ( x j ^ ^ ) takes alternating sign for j = 1,2,3, ...nc= n + 2. This i s always possible by the "Exchange Theorem" ^ S t i e f e l [26, p.220], Novodvorskr and P i n s k e r [ l 8 ] . Step 2) i s repeated with superscript increased by one; etc. , the procedure being repeated indefinitely. - 12 -A c c o r d i n g to V e i d i n g e r [27, p. 10o], the g e n e r a l p r o o f of convergence of Re mes [2l] c a n be us e d to show that the above-de s c r i b e d p r o c e d u r e i s c o n v e r g e n t . It a l s o f o l l o w s f r o m [18] i f E^°^0. A n o t h e r m a i n v a r i a t i o n on t h i s theme i s R e m e s Second A l g o r i t h m f o r p o l y n o m i a l a p p r o x i m a t i o n , i n w h i c h the f o l l o w i n g change i s made i n step. 3): 3) L e t \yt \ 4w\iXi.-Mtr\ w i t h -\•• >,<yv < . . . < y ^ , = +1 be the n + 1 z e r o s of P n ( o ) ( x ) - f( x ) , along w i t h f c l} . R a t h e r than m o d i f y $ X J ^ ° ^ by a s i n g l e p o i n t x*, n c points xjj^ = 1, 2 , . . . n c) a r e cho s e n s u c h that yj •£ yg4, \-\$ y^ i X £ y<4l Step 4) then becomes : ^« l> l j •' • ^ « 4') ^ x j ( D ? ~~Uf\ A s s u m i n g that N o v o d v o r s k i and P i n s k e r ' s p a p e r [18*] p r o v e s the con v e r g e n c e of t h i s a l g o r i t h m , V e i d i n g e r [27]has shown the co n v e r g e n c e to be q u a d r a t i c i f 'f 6 C . The d e t e r m i n a n t a s s o c i a t e d w i t h the l i n e a r s y s t e m ob t a i n e d u s i n g t h i s a l g o r i t h m ^ 0 - a fea t u r e w h i c h w i l l be evident i n l a t e r d i s c u s s i o n . S e v e r a l other m o d i f i c a t i o n s of Remes Second A l g o r i t h m have a p p e a r e d i n the l i t e r a t u r e : B a r t h [2], H a s t i n g s [9], M u r n a h a n and W r e n c h [ l 7 ] , Selfridge[24"] . F o r the m a i n p a r t these c o n s i s t m e r e l y of t a k i n g ^XJ*"^ at the p o s i t i o n s of l o c a l r a t h e r than ab s o l u t e e x t r e m a of the e r r o r c u r v e . P a t h o l o g i c a l c a s e s c a n a l w a y s be c o n s t r u c t e d to defy such a l g o r i t h m s - i . e . a c o m p u t e r p r o g r a m can a l w a y s be beaten! A s t r a i g h t f o r w a r d g e n e r a l i z a t i o n of the R e m e s Second A l g o r i t h m to r a t i o n a l C h e b y s h e v a p p r o x i m a t i o n has been p r o p o s e d by F r a s e r and 13 H a r t . R a t h e r t h a n s o l v e t h e l i n e a r s y s t e m P n t x j ) - ( - 1 ) J E = f ( x j ) j = 1 ,2 , . . . n c = n + 2 t h e n o n - l i n e a r s y s t e m - ( - I ) ' E = f ( x j ) j = 1 ,2 , . . . n c = n + m + 2 Q m ( x j ) w h e r e 1 - Q m ° ( x ) = Q m ( x ) h a s c o n s t a n t t e r m = 1 o r r a t h e r , P n ( x j ) - [ fc-O* E - Kx^") <L(*0 H ^ e : ^ i ) i » » > * , - ~ * c i s s o l v e d b y i t e r a t i o n o n E . T h i s a l g o r i t h m w i l l be c o n s i d e r e d i n s o m e d e t a i l i n S e c t i o n V . C ) P r o g r a m m i n g M e t h o d s T h e r e l a t i o n s h i p b e t w e e n p r o g r a m m i n g m e t h o d s a n d a p p r o x i -m a t i o n a l g o r i t h m s i s r e a d i l y s e e n b y c o n s i d e r a t i o n o f the f o l l o w i n g l i n e a r p r o g r a m m i n g a p p r o x i m a t i o n p r o b l e m : P r o b l e m : F i n d t h e n t h d e g r e e C h e b y s h e v a p p r o x i m a t i o n to a c o n t i n u o u s f u n c t i o n f ( x ) , x 6 £- 1, l l . I n o t h e r w o r d s , w e w i s h to c h o o s e j = 0 , 1 , 2 , . . . n s u c h t h a t m a x 1 HA "X 3 - i x 1 - ^ f o r s m a l l e s t p o s s i b l e . 3 A g a i n e q u i v a l e n t l y , w e w a n t to m i n i m i z e ^ u n d e r t he r e s t r i c t i o n s o f t h e 2 ( n - 2 ) i n e q u a l i t i e s : s o o b t a i n i n g a b e s t a p p r o x i m a t i o n o n t he f i n i t e s e t ^ x j ^ , j = l , 2 . . . n c . A s f o r p r e v i o u s l y m e n t i o n e d m e t h o d s , t he ^ x j ^ a r e m o d i f i e d t o i n c l u d e p o i n t s o f m a x i m u m d e v i a t i o n , a n d t h e p r o c e d u r e i s r e p e a t e d , e t c . A l t h o u g h o f s o m e c o n s i d e r a b l e i n t e r e s t , s u c h p r o g r a m m i n g m e t h o d s h a v e o n e o b v i o u s , y e t s e r i o u s d i s a d v a n t a g e : t he e x c e s s i v e - 14 -amount of work required. In p a r t i c u l a r , consider the solution of the above-mentioned problem using the simplex algorithm. As the number of operations (multiplications or divisions) required per vertex using this method or any of its variants i s approximately n 2 , the total maximum number of operations per ite r a t i o n is approximately: as compared to the constant number of approximately: per iteration by solving the corresponding line a r system. An advantage of the above-mentioned types of approximation procedures i s their generality. They can be used i n any type of approximation where a basis: ^ • e.*V \ l,» y . > v V ' ^ o r n t h d e 8 r e e polynomial approximation, can be selected for the n-dimensional subspace of approximations . However, they cannot be applied to approximation by rational functions. F o r rational approximation, one must turn to Concave, Convex and/or Dynamic Programming rather than L i n e a r Programming. This i s an exceptionally recent approach to the approximation problem (the e a r l i e s t papers appearing i n 1958). Consequently, only isolated algorithms have been proposed, so far, without the publication of any numerical r e s u l t s , and moreover, except for [43 (see also below) without proofs of convergence. A ty p i c a l sample of the l i t e r a t u r e i s Loeb [l4l, for approximation using the quotient of l i n e a r forms. Let us now consider the rational approximation algorithm of Cheney and Loeb [53, [43. For (n,m) approximation on a finite set 15 -we make the following definitions: for any r e a l valued vector c = (cj), i = 1,2,..n c =n4m+2 we define: The algorithm i t s e l f i s then defined by iteration on step 2) after the i n i t i a l step 1) i n the following scheme: 1) Choose any c(°) = (c.(°)) with |Co|<| , 6 = > > X> . .. v\c and corresponding Q(c(°),x) > O for Xs£-I>i] 2) Knowing c(^), minimize as a function of c: by means of convex programming, so obtaining a vector c = c ( k + 1 ) . F o r other than a finite set, the minimization of 9) presents formidable d i f f i c u l t i e s . The authors of this method have proven it s convergence [ 4 l . D) Other Methods One class of other methods (known as de l a Vallee Poussin Algorithms) are those which obtain the best approximation as the li m i t i n g case, as the numbers of points increases, of best approxima-tion on a finite set. That i s , suppose (in the nth degree polynomial case) that P n^(x) i s the best (Chebyshev) approximation to f(x) on a finite subset of points s£-»>r] . We want to take: o The methods of finding P n l ( x ) are numerous, see for example Stiefel [l2, pp.2 17-232); such methods being based on "Exchange Theorems" s i m i l a r to the one previously mentioned. Convergence of the de l a Valine Poussin A l g o r i t h m has been shown under quite general condi-tions on f(x) and the approximation subspace [22*]. Rate of convergence - 16 -for optimal selection of the q points has also been considered t.2Z]. De l a Vallee Poussin [20], [22] also proposed an equivalent algorithm; finding at each step the Chebyshev approximation to an equivalent sys-tem of inconsistent equations. The problem on a finite point set has been considered by several authors: Zuhovickii [28], Cheney and Goldstein [8*], [6], Rice (see above), and StiefelC261. The latter has an excellent summary of available methods . As a last method to be considered f rom the class of more or les s r e a l i s t i c proposals, there i s the Polya algorithm, i . e . an algorithm based on the last theorem quoted i n the previous section. - 17 -The R e m e s R a t i o n a l A l g o r i t h m and A s s o c i a t e d P r o b l e m s M e n t i o n has been made p r e v i o u s l y of t h i s n a t u r a l e x t e n s i o n of the R e m e s P o l y n o m i a l A l g o r i t h m to an a l g o r i t h m f o r r a t i o n a l f u n c t i o n a p p r o x i m a t i o n . In m o r e d e t a i l , the method i s as f o l l o w s f o r the Pn(x) a p p r o x i m a t i o n of f by r a t i o n a l f u n c t i o n s ^ V '. . Qm(x) 1) S e l e c t a r b i t r a r y \ xj ^ j = 1, 2 n c = n + m+2 and i n i t i a l E-(°) w i t h — \ * V, < v 4 < . . . <, X ^ < | 2) Set up the n o n - l i n e a r s y s t e m : n n { ? i \ + (-I)' E = f(x.) j = l , 2 , . . . n c Qm(xj) J 3) I t e r a t e o n E ^ , 4= 1,2, ... ( i . e . p e r i t e r a t i o n s o l v e the c o r r e s p o n d i n g n c non-homogeneous l i n e a r equations i n n c v a r i a b l e s ) i n the scheme: P*(x^ E * - teal ^ K->* Eu1, f(x^ . • • \ where f o r u n i q u e n e s s 1 + Qm°(x) = Qm(x) i s t a k e n to have constant t e r m = 1 (for a " b e s t " i r r e d u c i b l e a p p r o x i -m a t i o n the constant t e r m ^ o , o t h e r w i s e t h e r e i s a pole at x=o and .'. we c a n take i t =1 without l o s s of g e n e r a l i t y ) . (0) H o p e f u l l y L i m E v e x i s t s . 4) Move the XJ i n a manner analogous to the R emes Exchange f o r the P o l y n o m i a l A l g o r i t h m ; i n p a r t i c u l a r the o r d e r i n g 10) i s p r e s e r v e d . 5) Repeat step 2) e t c . T h i s p r o c e d u r e i s o u t l i n e d i n F l o w D i a g r a m I, and has been coded i n a v e r s i o n of F o r t r a n II f o r U.B.C.'s I.B.M. 1620. F l o w £ > a ^ & * r x L . N O Sol vs. C o r r y ^ ^ ; « < Y6S Wave. +Wc No - 18 -As far as the programming i s concerned, there are two distinct parts: 1) solution of a system of non-homogeneous equations (this was done by Gaussian elimination with row interchanges), and 2) the di f f i c u l t one - movement of the c r i t i c a l points x j to extrema points of the e r r o r curve. This was done by a stepping procedure - where there i s a set upper bound to the number of steps allowed between any two successive c r i t i c a l points on [-1, l ] . The second flow diagram (II) i l l u s t r a t e s the procedure (for s i m p l i c i t y , with fixed endpoints). Pn(x) Besides the p o s s i b i l i t y of the approximation of f by Q ^ X ) having exactly n c c r i t i c a l points (see the characterization theorem), two basic problems are evident, a satisfactory answer to the f i r s t one being i t s e l f prerequisite to a solution of the second. 1) Under what conditions on f does the iterative scheme 12) converge for a p a r t i c u l a r choice of n, m, x^ , E^°^? 2) Does there exist a convergence proof for this algorithm along the lines of the Novodvorski and P i n s k e r proo or of Rice's proof [23]? Anticipating our discussion of the second question, i t s answer i s , i n brief, no, and in fact, various types of simple counterexamples can be constructed. That we s t i l l might have convergence for some highly r e s t r i c t e d class of functions f, i s s t i l l an open question. A) D i f f i c u l t i e s of the Iterative Procedure Our minimum hope, and as i t turns out, our basic l i m i t a t i o n , i s expressed in the following theorem: Theorem: The non-linear system N o t a t i o n f o r F l o w D i a g r a m II The f o l l o w i n g n o t a t i o n i s u s e d i n the next d i a g r a m : - h denotes the step s i z e i n the stepping p r o c e d u r e to f i n d the poi n t s of m a x i m u m d e v i a t i o n of the c u r r e n t e r r o r c u r v e . Thus i n g e n e r a l , f o r each k, fl^hr \ X ^ - Y ^ \ where n j i s the m a x i m u m number of steps a l l o w e d and xk has i t s u s u a l meaning (the k t h a p p r o x i m a t e c r i t i c a l point on C - l , 1]). - n c = n + m + 2 a l s o has i t s u s u a l m e aning. - k i s c o n s i s t e n t l y u s e d i n denoting x^; j i s u s e d i n denoting steps of magnitude h beyond x^, i . e . x^ 4 jb . - e k j = e (xk 4 jh) = val u e of the e r r o r c u r v e at xk 4 j h . - X L B denotes a " l o w e r bound" on x^ f o r a p a r t i c u l a r k, and i s u s e d to p r e s e r v e the o r d e r i n g p r o p e r t y of the [x^\. It s h o u l d be noted that a l l d e t a i l s of output, t e s t f o r c o n v e r g e n c e , e s t i m a t i o n of e r r o r , e t c . have been o m i t t e d , f o r the sake of c l a r i t y , i n F l o w D i a g r a m I I . P l o w D*i d<^r±w\ NO YES wait 44 A 4 p»r»Wo\.'e. _ NO To < ... . NO - 19 -has at most one solution Q m ( ^ ) with no pole in [-1, l ] (and this solution is then, necessarily irreducible). Proof: Suppose not; i.e. suppose we have two solutions C Pw' (x> , ^ l*> > e' where <#»!to , Qy^(x) both ( P^'to •> M ^ E " have constant term = 1 then since £ ) J l u ^ 0 , #J! (x^ * 0 for any KK « f^Cx^ « fl»> Cxp _ jJ \ upon subtraction so that, p ; ^ Assume E E1 , and without loss of generality, that (E"-B,V) fl^M $ V ! > > 0 throughout [-1, l ] and consider the polynomials: [ Kto <^"w - Kto ^ ' w we note that the former alternately agrees, and agrees except for sign with the latter at at least n c = n-m-2 points in [-1, l ] . Hence P^M - P*' Cx) Q Cx"1) must have at least n c - l = n+m-1 zeros in £- 1, l] which is impossible for E"^ E* > since it has maximum degree m+-n "S 0 which implies E ' E i . '. E is uniquely determined. We appeal to the next Pn(x) theorem (page 2 0) to show that the corresponding ^ ^ ^ is also unique. That the corresponding solution Q ^ ^ ) p' i x \ is irreducible follows immediately since if —• is a $w>-K (.*) solution of the non-linear system, then so also is P V K ^ ^ V * ^ and we can apply our uniqueness result. Hopefully then, our iterative procedure generates this solution, whenever it exists. - 20 -There are then, three problems associated with the iterative procedure: i) the possibility of L i m not existing; ii) the possibility of producing Q^ |^ ) o n some <& th step in the iterative procedure 12) such that Qirf^ Hx ) - 0 for some Xs^-iiQ ( i . e . an "approximation" with a pole in the approximating i n t e r v a l ! ) , this is a s p e c i a l case of the non-linear system 12) having only solutions with poles i n Ca, b3 and wil l be included in that discussion; i i i) the possibil ity of singular l inear systems 12) arising and the associated p r o b l e m of 11) having no solutions at a l l . Before turning to these p r o b l e m s , we first note that a solution Pn(x), Qm(x), E of the non-l inear system 11), if it exists, is generally uniquely determined by the value E . T h e o r e m : If E satisfies the non-l inear system 11) and f (xj )Jp (-l)-'E for at least one j (j = 1, 2, . . . n c ) then E determines Pn(x), Qm(x) uniquely. Proof: E satisfies the non-linear system and therefore there is at least one solution ^ P ^ W ^ ^ l x ) ^ ^ ^ ^ of: Ph *[W&- q w °(x^ *ir*k + n*C> ... 13) which is a l inear system of n c non-homogeneous equations in n c - l variables, and therefore has at most one such solution. M o r e o v e r , any solution of 12) obviously satisfies 13). A s a consequence of this result, we wil l commonly speak of E as being "the" solution of a particular non-linear system 12). The following simple result is also of interest: Pn(x) T h e o r e m : Pn(x), Q m ( x ) , E , (J m (x) irreducible is a solution of 12) iffit is a solution of: P^Cx^+ t-o'e * M * ^ * fCxj) •••'^ - 21 -Proof: We note that 14) is simply a rearrangement of: PwCxO + ( - ^ E < L ( X O * ^ ( x ^ . . . ^ Now if jPn(x), Qm(x), E ^ is a solution of 12) then it clearly is a solution of 13). On the other hand, if ^Pn(x), Qm(x),E^ is a solution of 14) or equivalently of 15) then it will be a solution of 12) if Qm(xj) 0 for all j (j = 1, 2, . . .n c). But if Qm(xi|) = 0 for some j in 15) imply-Pn(x) ing Pn(xj) = 0 so that Qm(x) would be reducible . Turning to the first problem, we see that the instances of LiwsE not existing are numerous. Not only might we get a singular system for some Ji , and therefore in practical application not be able to take the limit,! but even if only non-singular systems do arise, the limit need not exist since its existence is in no way dependent on how near \x.$\ are to the $xj*| . Noticing that: Ph(*£ A- \ t - ^ E ^ *(x0\ <C(*0 + * H*b ^>V-if non-singular jean be considered of the form E^»p(k^ ^\ where F is a rational function of degrees (m,m), the following two theorems shed some light on the situation. For proofs see Montel [163. Theorem: Let ^ 0.^= "j 0*""! define an iterativeprocedure in which we assume there is no round-off, and suppose in the neighbourhood of a double point ft, (a point such that c^ -. ) exists and moreover, |<j*(,S.^| <• I i.e. is "attractive", then for |fl.-4ol sufficiently small, the procedure con-verges to Ot . Theorem: Under the same assumption as the above theorem but with l^ '^ l >> rather than | ^ (K))* | , i.e. 5. is "repulsive", the initial iterates OLo^ , will diverge from 0t . - 22 -Note however that the latter theorem does not say we have ultimate divergence. F o r example, Montel gives a simple counterexample: let g(x) 1 x(x-2)jthen 0 i s a repulsive double point and we have both: , &^ = .^. = 3 and J7 + \ , o.| ' X ? ^-s . * 0 Applying these ideas to (n,m) approximation, our iterative procedure i s defined by: where ^ \ * ^ ^ F r o m which (dropping superscript): I Vt Xi • • • • +1 10 That f can readily be suitably chosen so that \ p '^g^ ^. ) i s more readily seen by considering the special case of (p)\) ', here the iterative scheme 16) i s defined by: ^ • • u r ^ + M ^ ' - V i . e " } . L i , . , . Solving 17) for E ^ \ thus obtaining the form E ^ = F ( E ^ " ' *), and imposing the r e s t r i c t i o n 1 Pl(e)l < I (where F -Fd^ ) ), we obtain the following condition for convergence after some lengthy algebra: •7) - 2 3 ~ E v e n i n t h e c a s e ^ x j ^ = ^xj*"^ , E - E** i t i s e v i d e n t t h a t s u i t a b l y c h o s e n f n e e d n o t s a t i s f y t h i s c o n d i t i o n . W e n o w t u r n to t h e l a s t - m e n t i o n e d p r o b l e m . T h e i t e r a t i v e s c h e m e 13) g i v e s r i s e o n a n y p a r t i c u l a r s t e p ( the s u p e r s c r i p t h a s b e e n d r o p p e d ) t o a d e t e r m i n a n t o f c o e f f i c i e n t s o f t h e f o l l o w i n g f o r m : I X x X? • • • X^ Uth i x^ '1> It i s w e l l k n o w n t h a t t h e d e t e r m i n a n t 19) ^ O i n t h e p o l y n o m i a l c a s e ( m = o ) . T h e d e t e r m i n a n t t a k e s t h e f o r m : I Xj y * Y? " I . 10) 1 Xvwl ' ' w h e r e - I 4 X, < Xt< X-\< . - . < X^ 4 4 E x p a n d i n g t h i s d e t e r m i n a n t b y t h e l a s t c o l u m n , w e n o t e t h a t i t i s t h e s u m o f n + 2> V a n d e r m o n d e d e t e r m i n a n t s , a l l h a v i n g t h e s a m e s i g n ( (-0* ) d u e t o t h e o r d e r i n g o f t h e ^"X^ a n d h e n c e t h e d e t e r m i n a n t 2 0 ) *f 0 . B e f o r e c o n s i d e r i n g t h e m o r e g e n e r a l f o r m 1 9 ) , l e t u s c o n s i d e r w h e r e ?M s S W f +, X f > ^ s Z ^ t l X 1 w - 24 -By an i m p l i c i t function theorem e.g. Kantorovitch QtQ we know that 21) does not have a solution ^ t>|» ^ ^ E ^ i f the Jacobian of the system vanishes at ^ Is^a^E^ . Now since, Jacobian = det where C-^£-^i*. l-o'e ^ ( x i ) we note the vanishing of the above determinant,22) i s (assuming JQm(x)| •>£ ^ XeC-'iB ) simply a generalization on the problem presented by 19). However, the property exhibited by 20), for m=o, does not generalize to V*> | i n either of these cases, as can eas i l y be seen by taking a Laplace expansion of the last m-1 columns. That i s to say, not only might an inverse f a i l to exist on a pa r t i c u l a r iteration, but also no ultimate solution need exist. B) D i f f i c u l t i e s of the O v e r a l l Procedure In order to discuss why we do not have convergence for the Remes Rational Algorithm, apart f r o m those reasons associated with the non-linear system, we w i l l consider the problem i n the light of the convergence proof of Novodvorski and P i n s k e r Cl8] and Rice [23] for the Second A l g o r i t h m of Remes. Definition: The set \ ^ C x u . i s said to form a Chebyshev set in C- 1, l ] i f the difference U ^ x i - U ^ (U^rf 1M\ having more than n zeros i n [-1, l ] i m p l i e s flj = 4.'c, or equivalently, i f ( C c £ ) -(<Pc i s non-singular for every set of distinct X J . - 25 -The above-mentioned proofs hold for sets of unisolvent functions (Rice 23, p.3-55), which are slight g e n e r a l i -zations on Chebyshev sets (in p a r t i c u l a r LO^c,*^ need not be li n e a r i n the ^(x -) ). S p e c i f i c a l l y , the following two properties are required: 1) If A,tt)-^ (£> ha s more than n zeros (counting m u l t i p l i c i t i e s ) then A ,W »_ 2) Any n+1 points S (fc J „ „ A ^ a r b i t r a r y r e a l numbers uniquely determines a A(fc)eJl* which consequently (Rice 23, p. 3-56 ) depends continuously on the points i n the following sense: let correspond to Cfcij&ii) '>*•>•"*+\ then for a l l 6>o there exists an -v\>o such that: |Ai-A^ | * ^ ) for a l l tat-»»0 In order to generalize 1) to a two parameter interpolation class of rational functions -XL^ -*^ jjp-j^ w e rnust r e s t r i c t ourselves to i r r e d u c i b l e rational functions of degrees (n,m) which have no poles i n the approxi-mating i n t e r v a l (the hope that a convergence proof might go through even when "pole positions" are chosen as c r i t i c a l points has not been sub-stantiated even by any numerical attempts). The major dif f i c u l t y a r i s e s when we attempt to have a property analogous to 2) for our interpolation c l a s s . The class of i r r e d u c i b l e rational functions, as a whole, fa i l s not only because a given set may not correspond to a rational function Qm(x)' also, because i f a solution does exist, it may have poles i n the i n t e r v a l , e.g. for interpolation in Slo^\ on C-1, l ] , the unique rational function (with constant t e r m i n denominator = 1) corresponding to:a) (-1,1), (1,1) is non-existent, b) (0, -1), (1, 1) i s ~ — which has a pole at x = 1/2. 1 - 2x i r t i c u l a r c h o i c e of \ e.g. =. z e r o s of TAJX) , i t i s not known T h e r e a r e two o b s t a c l e s c o n c e r n i n g the p o l e s i n £-1, l ] : 1) f o r any \ > fc $ a s u i t a b l y "bad" f can be c o n s t r u c t e d s u c h that the i n i t i a l n o n - l i n e a r s y s t e m has only s o l u t i o n s w i t h p o l e s i n the i n t e r v a l ; 2) i f a g i v e n continuous f u n c t i o n f does i n fact have a best Pn(x) Qm(x) a P P r o x ^ m a t i Q n w i t h n c c r i t i c a l p o i n t s , then t r i v i a l l y , by s e l e c t i o n of the c o r r e c t s o l u t i o n of the n o n - l i n e a r s y s t e m , o u r o v e r a l l p r o c e d u r e c a n p r o d u c e t h i s a p p r o x i m a t i o n f r o m the i n i t i a l s e l e c t i o n : \.*^ " \*i>*\ , E^ 0) = E * . H o w e v e r , c o n v e r s e l y , s t a r t i n g w i t h a pa] f o r what continuous f we w i l l a l w a y s have one p o l e - f r e e s o l u t i o n throughout o u r i t e r a t i v e p r o c e d u r e . In c o n c l u s i o n , a p a r t f r o m the r e a s o n s a s s o c i a t e d w i t h the ( n o n - l i n e a r s y s t e m , f a i l u r e of the R e m e s R a t i o n a l A l g o r i t h m to con-v e r g e i s evident f o r o t h e r than a h i g h l y r e s t r i c t e d , and so f a r unknown i n t e r p o l a t i o n c l a s s . We w i l l now t u r n o u r d i s c u s s i o n to two o t h e r p r o b l e m s ( T i m i n g and S t a b i l i t y ) whose r e l e v a n c e should be c o n s i d e r e d i n the l i g h t of m u c h m o r e e n c o u r a g i n g r e s u l t s i n the a l g o r i t h m ' s p r a c t i c a l i m p l e m e n t a t i o n (see next s e c t i o n ) than i s o t h e r w i s e evident f r o m t h i s s e c t i o n . C) O t h e r P r o b l e m s - T i m i n g It i s the p u r p o s e of t h i s d i s c u s s i o n to make a c o m p a r i s o n of the w o r k r e q u i r e d to o b t a i n r a t i o n a l a p p r o x i m a t i o n s , as c o m p a r e d to p o l y n o m i a l a p p r o x i m a t i o n s . A s the d e t a i l e d e x p e n d i t u r e of t i m e (work) to o b t a i n an a p p r o x i -m a t i o n i s d i r e c t l y dependent upon the s p e c i f i c type of d i g i t a l c o m p u t e r use d , t h i s p r o b l e m ca n m o r e p r o f i t a b l y be p h r a s e d i n t e r m s of - 27 -machine operations (multiplications and divisions), and as a separate category, function evaluations. The number of machine operations is determined as follows: Pn*(x) if in the course of determining a best approximation — to f, Qm v(x) nm moves of the critical points are required, each taking an average of iterations on the non-linear system, and the maximum number of steps being allowed in the moving procedure is n g (see page 18), then: 1 -1) Approximately "n^ncpij^ machine operations are required for the solution of the non-linear systems . 2) The approximate minimum/maximum number of machine operations for moving the critical points are respectively 3nc nm and n s n c ^ n m ; we will denote average by h&^t^v^ 3) The number of function evaluations required for setting up the non-linear systems is approximately n c n(jn m . 4) The approximate minimum/maximum number of function evaluations needed in moving the critical points are respectively: 3 n c n m and n s n c n m (average denoted ^s^c^ ). It should be understood that the above figures are realistically crude, as an actual individual element (n c , n m , n )^ may for various reasons differ by 1 or 2, thus making the above values more nearly correct for larger n, m values, where more useful approximations are obtained. Suppose further that a function evaluation can be considered as requiring k (constant) machine operations. The total number of machine operations required is then given approximately by: NOP = ^ ^ [ v ^ U ^ d 4 K}M+SB\] ..-23) - 28 -The following conclusions are arrived at from 23): 1) Except for extremely low degree approximations, So that k needs to be at least comparable to n c (where n c is typical of an approximation having practical utility) for the function evaluations to have any significant lien on the total computing time (see Table II). 2) As a consequence of 1), if k is small, there is considerable advantage in keeping n<j small (and, if necessary, increasing ^ s ) . This advantage is lost if k is large. 3) is a function only of n+- m and not of n or m individually. If n m were independent of m (the degree of Qm(x)), approxi-mations lying along lines of constant n + m (see Numerical Section) could be obtained with equal work. However as n m increases somewhat with m, approximations with small m are always most easily obtained. Other Problems - Stability We will speak of the Rational Algorithm as being stable (Maehly T l 5 ] ) for particular n, m, wordlength L and particular move k, if up to this move, the mean absolute error at the kth approximate critical points has strictly increased. Moreover, in a practical sense, we will speak of it as being convergent (for a particular n s value) if on some move, no critical points x^ can be moved with this value of n s . If for particular f, m, n, n s the algorithm converges, a basic and difficult unsolved problem is to determine a pr ior i tke. mini-mum wordlength required in order that it is stable for all moves up Table. H Co vmpAr! sov\ of K i h t •for e>* •> (see Hxf p^t 19) r'U&WiAe. oper*"V;o/\s fcre, el&Hrr*;h.eJ * s s * « i i * ^ c&/\vV*»>H Series arc sWe^. (= V-z) bo A n d *V\tAi«*W>«« 0 3 3 . 1 &7AW>° f H >T\(o X|o"' 4-5" . 8?3xtox & " f . xio1* 5* 7 5 0 ^ZWxiS4 7 «* 7 • W x l o * 8 10 * 8 M "* . 2 J o * l o 7 7 1* \o 10 II n e x c l u s i o n k fit ^c. for tAse-U ^PproXmyHoviS °F «^ (=ws (»*!^ ) ( s"«^ • M- 7 • 155" to* 7 ip 9 .135" lo1 0 «Z eve*. We-fter ^pproxi^^ohS K < ^ c - 29 -to and i n c l u d i n g the one on w h i c h i t does c o n v e r g e . C o n s i d e r a p a r t i c u l a r l i m i t i n g c r i t i c a l point x* and the e r r o r c u r v e e(x) i n the neighbourhood of t h i s p o i n t . If: ~ ~ !>'> a —T- i s the a p p r o x i m a t e m i n i m u m step s i z e , and b i s the c o m p u t e r base, then i n s t a b i l i t y can be e x p e c t e d . T h i s c o n d i t i o n i s of c o u r s e t r i v i a l i f h i s s u f f i c i e n t l y s m a l l and E''^ < b , but i t can r e a d i l y o c c u r f o r much l a r g e r E * f . We have e(x) = f(x) - • so that, a s s u m i n g C and t a k i n g : L H > X*X* (which i s not n e c e s s a r i l y t r u e f o r x5,i an endpoint of [-1, we o b t a i n the f o l l o w i n g a p p r o x i m a t e c o n d i t i o n f o r s t a b i l i t y : w here i t i s to be u n d e r s t o o d that P,Q a r e r e s p e c t i v e l y P n * ( x ) , Qm*(x), and the f u n c t i o n s a r e e v a l u a t e d at x* . L i t t l e c an be d e t e r m i n e d f r o m 24) although i t w i l l be noted that S v a r i e s d i r e c t l y w i t h n s ( e v e r y t h i n g e l s e r e m a i n i n g the same) - the l a r g e r n s i s the g r e a t e r the p o s s i b i l i t y of i n s t a b i l i t y (though the g r e a t e r the p o t e n t i a l a c c u r a c y of the a p p r o x i -m a t i o n ) . The p r o b l e m of the dependence of S on n c , L i s m u c h m o r e c o m p l i c a t e d . The d i f f i c u l t y of c o m p l e t e l y r e s o l v i n g t h i s p r o b l e m i s evident even i n the r e l a t i v e l y s i m p l e m= o ( p o l y n o m i a l ) case . C o n d i -t i o n 24) i n the case m = o i s : I f'V> - ?*\+>\ > b" L U n f o r t u n a t e l y , to t h i s author's knowledge, the nature of the second d e r i v a t i v e of a C h e b y s h e v p o l y n o m i a l a p p r o x i m a t i o n has not been i n v e s t i g a t e d . - 30 -The p a r t i c u l a r case of e x, x € [-1, l] , n§ = 60 i s i l l u s t r a t e d i n Graph.I, the isopleth L bounding those points (n,m) which are stable for wordlength L,, from those which are unstable. i i -3 o - 31 -N u m e r i c a l R e s u l t s w i t h R e mes R a t i o n a l A l g o r i t h m H a v i n g d i s c u s s e d the a l g o r i t h m i n a " t h e o r e t i c a l " s e nse, we w i l l now t u r n to some p r a c t i c a l r e s u l t s . In p r a c t i c e , we note i n i t i a l l y , the a l g o r i t h m i s not n e a r l y as bad as might be thought. M o r e o v e r , i f i t w e r e a l w a y s p o s s i b l e f o r g i v e n f,n,m, to r e a d i l y s e l e c t ^ , c. s u c h that no p o l e s w e re g e n e r a t e d — see p r e v i o u s d i s c u s s i o n — the a l g o r i t h m c o u l d be h i g h l y r e c o m m e n d e d . The next 4 g r a p h s ( G r a p h s II-V) o u t l i n e the stages i n a t y p i c a l a p p l i c a t i o n of the R e m e s R a t i o n a l A l g o r i t h m . The case i n point i s that P ? * ( x ) of f i n d i n g the Qg*(x) a p p r o x i m a t i o n to e x on [-1, l ] c a r r y i n g w o r d l e n g t h 12. A s u m m a r y of v a r i o u s a s p e c t s of t h i s s a mple r u n p r e c e d e s the g r a p h s . In p a r t i c u l a r , i t w i l l be noted, the a l g o r i t h m i s stable u n t i l , i t " c o n v e r g e s " . The f o l l o w i n g g r a p h s ( G r a p h s V I - V I I I ) show r e s u l t s of the a l g o r i t h m ' s use i n a m o r e s u c c i n c t f o r m ; i . e . f o r v a r i o u s f u n c t i o n s g r a p h s of E * vs (n,m) have been c o n s t r u c t e d . A l t h o u g h E*n,m i s a d i s c r e t e - v a l u e d f u n c t i o n , i s o p l e t h s of equal error''" have been d r a w n as i f continuous f o r c l a r i t y . The f o l l o w i n g s i g n i f i c a n t f e a t u r e s of these g r a p h s shoul d be noted: 1) V a r i a t i o n of e r r o r * along a l i n e of constant n + m ( i n t h i s way we a r e c o m p a r i n g the e r r o r t e r m s of a p p r o x i m a t i o n s w h i c h can be e v a l u a t e d , f o r a p a r t i c u l a r a rgument, w i t h a p p r o x i m a t e l y equal w o r k ) . 2) Instances of d i f f i c u l t y w i t h the a l g o r i t h m : a) S i n g u l a r s y s t e m s (denoted by S) b) P o l e s p r o d u c e d i n the i n t e r v a l (denoted by*) - 32 -In the case of the last-mentioned d i f f i c u l t y , the following simple s u f f i c i e n c y condition, together with D e s c a r t e s Rule of Signs, was sufficient to demonstrate i n almost a l l cases that a p a r t i c u l a r " a p p r o x i m a t i o n " had a pole i n C-1, l ] , without actually c a l c u l a t i n g the roots of Qm(x). T h e o r e m : Qm(x) = I + ft4X + 0.3X* + , . . + <W,X has no z e r o s i n [-1, l ] if <L I M < I but ) O^X + <X% *x * .. .+fli**iX*l i\<<$ M«V»U-*|v*|f < I O i l * J? a 5* * ~ ^ • £ is J~ ^ w ~ 2 "2 2 5- ^- - 2 x < X X * * 3 ,9 o -o o _ — ff- ft J— i-O a S~ f^- to cc C> CT" 0— « -^ C1 tO " *. X. * X rt or oo « • _ *- |-» K r* > eo O-vS ~9 ^ j , <r- O O A t, fcj V> In p 0° •o r ~» o tl ui -»• + X c x — * J o 4-O a -si * •4 I k z < > O al 3 erf, a— o 3 to o d »/. «< 0O cr *-o «0 o -a o 3" va o r t i l 1 L v •> ^ 5 0_ <± 4 4. CO cr o o c r In fl" I £ - 33 -C o n c l u s i o n s H a v i n g d i s c u s s e d the Remes R a t i o n a l A l g o r i t h m i n some d e t a i l , and h a v ing found i t c o n s i d e r a b l y l a c k i n g , i t i s now evident that t h e r e i s need f o r s i m i l a r s t u d i e s of other r a t i o n a l C h e b y s h e v a l g o r i t h m s . In th i s way, r e a l i s t i c , c o m p a r a t i v e c o n c l u s i o n s c o u l d be f o r m e d . A s f o r the Remes R a t i o n a l A l g o r i t h m i t s e l f , the f o l l o w i n g m a j o r p r o b l e m s r e m a i n : 1) U s e f u l e r r o r bounds f o r r a t i o n a l a p p r o x i m a t i o n (e.g. i f p o s s i b l e i n t e r m s of h i g h o r d e r d e r i v a t i v e s of f ) . 2) D e t e r m i n a t i o n of whether o r not a r e s t r i c t e d c l a s s of fun c t i o n s e x i s t s f o r w h i c h we have o v e r a l l c o n v e r g e n c e . 3) T i m i n g : to study the dependence of n m on m, the degree o f Q m ( x ) . 4) S t a b i l i t y : the b a s i c p r o b l e m of that s e c t i o n . In p r a c t i c e , f o r those continuous f u n c t i o n s (see g r a p h s ) f o r w h i c h the z e r o s of T n c ( x ) s e r v e d as "good" i n i t i a l s ets > a d i s t i n c t c o n c a v i t y was o b s e r v e d i n the e r r o r c u r v e s — j u s t i f y i n g to some extent the i n t e r e s t i n r a t i o n a l a p p r o x i m a t i o n . It i s o ur f i n a l c o n c l u s i o n that the i n h e r e n t d i f f i c u l t i e s i n the use of the R emes R a t i o n a l A l g o r i t h m a r e e x c e s s i v e f o r i t s s t a n d a r d ( i . e . s u b r o u t i n e ) use — to such an extent that t h e r e w o u l d be few t i m e s i n p r a c t i c e when the s l i g h t g a i n i n the degree of a p p r o x i m a t i o n c o u l d w a r r a n t the use of t h i s a l g o r i t h m , r a t h e r than the R emes P o l y n o m i a l A l g o r i t h m . - 34 -Bibliography N.I. A c h i e s e r , Theory of Approximation (English Translation) Ungar, New York, 1956. W. Barth, E i n Iterationsverfahren zur Approximation durch Polynome, Z. angrew. Math, und Mech. 38 (1958) pp. 258-260. P.L. Chebyshev, Collected Papers (in Russian) , French Translation, Chelsea, New York, 1962. E.W. Cheney and H.L. Loeb, On Rational Chebyshev Approxi- mation Num. Math, 4 (1962) pp. 124-127. E.W. Cheney and H.L. Loeb, Two Algorithms for Rational Approximation, Num. Math, 3 (1961) pp. 72-75. W. Cheney and A. A. Goldstein, Note on a Paper by Zuhovickii Concerning the Tchebycheff P r o b l e m for L i n e a r Equations, S.I.A.M. Journal, 6 (1958) pp. 233-239. W.' F r a z e r and J . F. Hart, On the Computation of Rational Approximations to Continuous Functions, unpublished. A. A. Goldstein and W . Cheney, A Finite A l g o r i t h m for the Solution of Inconsistent L i n e a r Equations and Inequalities and the Tchebycheff Approximation of Inconsistent L i n e a r Equations, P a c i f i c J . Math, 8 (1958) pp. 415-427. C. Hastings, Approximations for D i g i t a l Computers, Princeton Un i v e r s i t y P r e s s , 1955. D. Jackson, On Functions of Closest Approximation, Trans. Amer. Math. S o c , 22 (1921) pp. 117-128. L. Kantorovitch, The Method of Successive Approximations for Functional Equations, Acta Math., 71 (1939) pp. 63-97. R.E. Langer (Ed.), On Num e r i c a l Approximation, University of Wisconsin P r e s s , Madison, 1959. C. Lanczos, T r i g o m e t r i c Interpolation of E m p i r i c a l and Analytic Functions, J . Math. Phys . , 16 ( 1138 ) pp. 123-199. H.L. Loeb, Algorithms for Chebyshev Approximation Using the Ratio of L i n e a r Forms, S.I.A.M. Journal, 8 (1960) pp. 458-465. - 35 -15. H.J. Maehly, Rational Approximation for Trancendental Functions, Research Report RC-86 Jan. 16, 1959, I.B.M. Corporation, Yorktown Heights, New York. 16. P. Montel, Lecons sur les Recurrences et l e u r s Applications, P a r i s , G a u t h i e r - V i l l a r s , 1957. 17. F.D. Murnaghan and J . W . Wrench, J r . , The Determination of the Chebyshev Approximating Polynomial for a Differentiable Function, Math. Tables, A i d . Comp., 13 (1959) pp. 185-193. 18. E.N. Novodvorskii and I. P i n s k e r , On a P r o c e s s of Equalization of Maxima (English Translation), New Y o r k U n i v e r s i t y . 19. G. Polya, Sur un Algorithme toujours Convergent pour Obtenir les Polynomes de M e i l l e u r e Approximation de Tchebychef pour une Fonction Continue quelconque, C.R. Accd. S c i . P a r i s , 157 (1913) pp. 840-843. 20. C. de l a Vallee Poussin, Lecon sur 1'Approximation des Fonctions d'une Var i a b l e Reele, Gauthier V i l l a r s , P a r i s , 1952. 21. E . Re me s, Sur le ca l c u l E f f e c t i f des Polynomes d 1 Approximation de Tchebycheff, C.R. Acad. S c i . P a r i s , 199 (1934) pp. 337-340. 22. J.R. Rice, On the Convergence of an A l g o r i t h m for Best Tchebycheff Approximations, S.I.A.M. Journal, 7 (1957) pp. 133-142. 23. , The Approximation of Functions, Mathematics Group, General Motors Research L a b o r a t o r i e s . 24. R.C. Selfridge, Approximation with Least Maximum E r r o r , P a c i f i c J . Math., 3 (1953) pp. 247-255. 25. J . Shohat, The Best Polynomial Approximation of Functions Possessing D e r i v a t i v e s , Duke Math. J . , 8 (1941) pp. 376-385. 26. E. S t i e f e l , Note on Jordon E l i m i n a t i o n , L i n e a r Programming and Tchebycheff Approximation, Num. Math. , 2 (I960) pp . 1 - 17 . 27. L. Veidinger, On the N u m e r i c a l Determination of the Best Approxi-mations i n the Chebyshev Sense, Num. Math., 2 (I960)-pp. 99-105. 28. S.I. Z u h o v i c k i i , An A l g o r i t h m for the Solution of the Chebyshev Approximation P r o b l e m i n the Case of a Finite System of Inconsistent L i n e a r Equations, P a c i f i c J . Math., 8 (1958) pp. 415-427.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Direct Chebyshev approximation
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Direct Chebyshev approximation Henderson, John Robert 1963
pdf
Page Metadata
Item Metadata
Title | Direct Chebyshev approximation |
Creator |
Henderson, John Robert |
Publisher | University of British Columbia |
Date Issued | 1963 |
Description | The Approximation Problem and specifically, "direct" rational Chebyshev approximation is discussed. A brief summary is made of "direct" Chebyshev approximation. The remainder of the thesis is devoted to various aspects of a "Remes-type" Algorithm for rational Chebyshev approximation, as proposed by Fraser and Hart. It is finally concluded that the inherent difficulties of the method would generally outweigh the advantages of the rational approximation which it obtains. |
Subject |
Chebyshev polynomials |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-11-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0080568 |
URI | http://hdl.handle.net/2429/38879 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1963_A8 H3 D4.pdf [ 2.43MB ]
- Metadata
- JSON: 831-1.0080568.json
- JSON-LD: 831-1.0080568-ld.json
- RDF/XML (Pretty): 831-1.0080568-rdf.xml
- RDF/JSON: 831-1.0080568-rdf.json
- Turtle: 831-1.0080568-turtle.txt
- N-Triples: 831-1.0080568-rdf-ntriples.txt
- Original Record: 831-1.0080568-source.json
- Full Text
- 831-1.0080568-fulltext.txt
- Citation
- 831-1.0080568.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080568/manifest