An algorithm for computing continuous Chebyshev approximations

Authors:
Zhong Qi Jing and Adly T. Fam

Journal:
Math. Comp. **48** (1987), 691-710

MSC:
Primary 65D15; Secondary 41A46, 41A50

DOI:
https://doi.org/10.1090/S0025-5718-1987-0878700-0

MathSciNet review:
878700

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we introduce an algorithm for computing nonlinear continuous Chebyshev approximations. The algorithm is based on successive linearizations within adaptively adjusted neighborhoods. The convergence of the algorithm is proven under some general assumptions such that it is applicable for many Chebyshev approximation problems discussed in the literature. It, like the Remez exchange method, is purely continuous in the sense that it converges to a solution of a continuous Chebyshev approximation problem rather than one on a discretized set. Quadratic convergence is shown in so-called regular cases, including polynomial and nondegenerate rational approximations. We believe the algorithm is also computationally more efficient than some other algorithms. A few numerial examples are given to illustrate the basic features of the algorithm.

**[1]**I. Barrodale, M. J. D. Powell, and F. D. K. Roberts,*The differential correction algorithm for rational \cal𝑙_{∞}-approximation*, SIAM J. Numer. Anal.**9**(1972), 493–504. MR**0312685**, https://doi.org/10.1137/0709044**[2]**I. Barrodale and C. Phillips,*An improved algorithm for discrete Chebyshev linear approximation*, Proceedings of the Fourth Manitoba Conference on Numerical Mathematics (Winnipeg, Man., 1974) Utilitas Math., Winnipeg, Man., 1975, pp. 177–190. Congr. Numer., No. XII. MR**0373585****[3]**I. Barrodale, L. M. Delves, and J. C. Mason,*Linear Chebyshev approximation of complex-valued functions*, Math. Comp.**32**(1978), no. 143, 853–863. MR**0483298**, https://doi.org/10.1090/S0025-5718-1978-0483298-X**[4]**E. W. Cheney,*Introduction to approximation theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR**0222517****[5]**Ludwig Cromme,*Eine Klasse von Verfahren zur Ermittlung bester nichtlinearer Tschebyscheff-Approximationen*, Numer. Math.**25**(1975/76), no. 4, 447–459 (German, with English summary). MR**0443298**, https://doi.org/10.1007/BF01396341**[6]**Charles B. Dunham and Charles R. Crawford,*Minimax approximation by a semicircle*, SIAM J. Numer. Anal.**17**(1980), no. 1, 63–65. MR**559462**, https://doi.org/10.1137/0717008**[7]**W. Fraser & J. F. Hart, "On the computation of rational approximations to continuous functions,"*Comm. ACM*, v. 5, 1962, pp. 401-403.**[8]**Z. Q. Jing,*Chebyshev Design of Digital Filters by a New Minimax Algorithm*, Ph. D. Dissertation, State University of New York at Buffalo, 1983.**[9]**D. W. Kammler & R. J. McGlinn,*A Family of Fortran Programs for Finding Best Chebyshev Approximations with Applications to Exponential Sums*, Research report prepared under AFOSR grant number 74-2653, Southern Illinois University, Carbondale, Ill., September 1, 1975.**[10]**E. H. Kaufman Jr. and G. D. Taylor,*Uniform approximation with rational functions having negative poles*, J. Approx. Theory**23**(1978), no. 4, 364–378. MR**509566**, https://doi.org/10.1016/0021-9045(78)90088-6**[11]**E. H. Kaufman Jr. and G. D. Taylor,*An application of linear programming to rational approximation*, Proceedings of the International Conference on Padé Approximants, Continued Fractions and Related Topics (Univ. Colorado, Boulder, Colo., 1972; dedicated to the memory of H. S. Wall), 1974, pp. 371–373. MR**0339454**, https://doi.org/10.1216/RMJ-1974-4-2-371**[12]**Edwin H. Kaufman Jr., David J. Leeming, and G. D. Taylor,*A combined Remes-differential correction algorithm for rational approximation*, Math. Comp.**32**(1978), no. 141, 233–242. MR**0460989**, https://doi.org/10.1090/S0025-5718-1978-0460989-8**[13]**K. Madsen,*An algorithm for minimax solution of overdetermined systems of non-linear equations*, J. Inst. Math. Appl.**16**(1975), no. 3, 321–328. MR**0443341****[14]**Günter Meinardus,*Approximation of functions: Theory and numerical methods*, Expanded translation of the German edition. Translated by Larry L. Schumaker. Springer Tracts in Natural Philosophy, Vol. 13, Springer-Verlag New York, Inc., New York, 1967. MR**0217482****[15]**M. R. Osborne and G. A. Watson,*A note on singular minimax approximation problems*, J. Math. Anal. Appl.**25**(1969), 692–700. MR**0235699**, https://doi.org/10.1016/0022-247X(69)90266-2**[16]**G. M. Phillips and P. J. Taylor,*Theory and applications of numerical analysis*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1973. MR**0343523****[17]**M. J. D. Powell,*The minimax solution of linear equations subject to bounds on the variables*, Proceedings of the Fourth Manitoba Conference on Numerical Mathematics (Winnipeg, Man., 1974) Utilitas Math., Winnipeg, Man., 1975, pp. 53–107. Congr. Numer., No. XII. MR**0455398****[18]**John R. Rice,*The approximation of functions. Vol. 2: Nonlinear and multivariate theory*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR**0244675****[19]**John A. Roulier and G. D. Taylor,*Uniform approximation by polynomials having bounded coefficients*, Abh. Math. Sem. Univ. Hamburg**36**(1971), 126–135. Collection of articles dedicated to Lothar Collatz on his sixtieth birthday. MR**0336177**, https://doi.org/10.1007/BF02995915**[20]**G. A. Watson,*A method for calculating best non-linear Chebyshev approximations*, J. Inst. Math. Appl.**18**(1976), no. 3, 351–360. MR**0454480****[21]**H. Werner & R. Collinge, "Chebyshev approximation to the gamma function,"*Math. Comp.*v. 15, 1961, pp. 195-197.

Retrieve articles in *Mathematics of Computation*
with MSC:
65D15,
41A46,
41A50

Retrieve articles in all journals with MSC: 65D15, 41A46, 41A50

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0878700-0

Article copyright:
© Copyright 1987
American Mathematical Society