An algorithm for computing continuous Chebyshev approximations

Jing, Zhong Qi; Fam, Adly T.

doi:10.1090/S0025-5718-1987-0878700-0

An algorithm for computing continuous Chebyshev approximations
HTML articles powered by AMS MathViewer

by Zhong Qi Jing and Adly T. Fam PDF

Math. Comp. 48 (1987), 691-710 Request permission

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.

References

I. Barrodale, M. J. D. Powell, and F. D. K. Roberts, The differential correction algorithm for rational ${\cal l}_{\infty }$-approximation, SIAM J. Numer. Anal. 9 (1972), 493–504. MR 312685, DOI 10.1137/0709044
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) Congr. Numer., No. XII, Utilitas Math., Winnipeg, Man., 1975, pp. 177–190. MR 0373585
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 483298, DOI 10.1090/S0025-5718-1978-0483298-X
E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
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 443298, DOI 10.1007/BF01396341
Charles B. Dunham and Charles R. Crawford, Minimax approximation by a semicircle, SIAM J. Numer. Anal. 17 (1980), no. 1, 63–65. MR 559462, DOI 10.1137/0717008

Comm. ACM

Chebyshev Design of Digital Filters by a New Minimax Algorithm

A Family of Fortran Programs for Finding Best Chebyshev Approximations with Applications to Exponential Sums

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, DOI 10.1016/0021-9045(78)90088-6
E. H. Kaufman Jr. and G. D. Taylor, An application of linear programming to rational approximation, Rocky Mountain J. Math. 4 (1974), 371–373. MR 339454, DOI 10.1216/RMJ-1974-4-2-371
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 460989, DOI 10.1090/S0025-5718-1978-0460989-8
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 443341
Günter Meinardus, Approximation of functions: Theory and numerical methods, Expanded translation of the German edition, Springer Tracts in Natural Philosophy, Vol. 13, Springer-Verlag New York, Inc., New York, 1967. Translated by Larry L. Schumaker. MR 0217482
M. R. Osborne and G. A. Watson, A note on singular minimax approximation problems, J. Math. Anal. Appl. 25 (1969), 692–700. MR 235699, DOI 10.1016/0022-247X(69)90266-2
G. M. Phillips and P. J. Taylor, Theory and applications of numerical analysis, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1973. MR 0343523
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) Congr. Numer., No. XII, Utilitas Math., Winnipeg, Man., 1975, pp. 53–107. MR 0455398
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
John A. Roulier and G. D. Taylor, Uniform approximation by polynomials having bounded coefficients, Abh. Math. Sem. Univ. Hamburg 36 (1971), 126–135. MR 336177, DOI 10.1007/BF02995915
G. A. Watson, A method for calculating best non-linear Chebyshev approximations, J. Inst. Math. Appl. 18 (1976), no. 3, 351–360. MR 454480

Math. Comp.