The Remez exchange algorithm for approximation with linear restrictions

Chalmers, Bruce L.

doi:10.1090/S0002-9947-1976-0440868-7

The Remez exchange algorithm for approximation with linear restrictions
HTML articles powered by AMS MathViewer

by Bruce L. Chalmers PDF

Trans. Amer. Math. Soc. 223 (1976), 103-131 Request permission

Abstract:

This paper demonstrates a Remez exchange algorithm applicable to approximation of real-valued continuous functions of a real variable by polynomials of degree smaller than n with various linear restrictions. As special cases are included the notion of restricted derivatives approximation (examples of which are monotone and convex approximation and restricted range approximation) and the notion of approximation with restrictions at poised Birkhoff data (examples of which are bounded coefficients approximation, $\varepsilon$-interpolator approximation, and polynomial approximation with restrictions at Hermite and “Ferguson-Atkinson-Sharma” data and pyramid matrix data). Furthermore the exchange procedure is completely simplified in all the cases of approximation with restrictions at poised Birkhoff data. Also results are obtained in the cases of general linear restrictions where the Haar condition prevails. In the other cases (e.g., monotone approximation) the exchange in general requires essentially a matrix inversion, although insight into the exchange is provided and partial alternation results are obtained which lead to simplifications.

References

Claude Carasso, Convergence de l’algorithme de Rémès, J. Approximation Theory 11 (1974), 149–158 (French). MR 359268, DOI 10.1016/0021-9045(74)90027-6
Bruce L. Chalmers, A unified approach to uniform real approximation by polynomials with linear restrictions, Trans. Amer. Math. Soc. 166 (1972), 309–316. MR 294962, DOI 10.1090/S0002-9947-1972-0294962-0
E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
David Ferguson, The question of uniqueness for G. D. Birkhoff interpolation problems, J. Approximation Theory 2 (1969), 1–28. MR 247331, DOI 10.1016/0021-9045(69)90028-8
Pierre-Jean Laurent, Approximation et optimisation, Collection Enseignement des Sciences, No. 13, Hermann, Paris, 1972 (French). MR 0467080

Approximation with convex constraints

H. L. Loeb, D. G. Moursund, L. L. Schumaker, and G. D. Taylor, Uniform generalized weight function polynomial approximation with interpolation, SIAM J. Numer. Anal. 6 (1969), 284–293. MR 250441, DOI 10.1137/0706026
G. G. Lorentz and K. L. Zeller, Monotone approximation by algebraic polynomials, Trans. Amer. Math. Soc. 149 (1970), 1–18. MR 285843, DOI 10.1090/S0002-9947-1970-0285843-5
R. A. Lorentz, Uniqueness of best approximation by monotone polynomials, J. Approximation Theory 4 (1971), 401–418. MR 291688, DOI 10.1016/0021-9045(71)90006-2
John A. Roulier, Polynomials of best approximation which are monotone, J. Approximation Theory 9 (1973), 212–217. MR 352793, DOI 10.1016/0021-9045(73)90088-9
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
O. Shisha, Monotone approximation, Pacific J. Math. 15 (1965), 667–671. MR 185334, DOI 10.2140/pjm.1965.15.667
G. D. Taylor and M. J. Winter, Calculation of best restricted approximations, SIAM J. Numer. Anal. 7 (1970), 248–255. MR 269082, DOI 10.1137/0707017