A comparison of algorithms for rational 𝑙_{∞} approximation

Lee, C. M.; Roberts, F. D. K.

doi:10.1090/S0025-5718-1973-0331719-0

A comparison of algorithms for rational $l_{\infty }$ approximation
HTML articles powered by AMS MathViewer

by C. M. Lee and F. D. K. Roberts PDF

Math. Comp. 27 (1973), 111-121 Request permission

Corrigendum: Math. Comp. 33 (1979), 847-848.
Corrigendum: Math. Comp. 33 (1979), 847.

Abstract:

Results are reported of a numerical study to compare eight algorithms for obtaining rational ${l_\infty }$ approximations. The algorithms investigated are Loeb’s algorithm, the linear inequality algorithm, the Osborne-Watson algorithm, the differential correction algorithms I, II and III, the Remes algorithm and Maehly’s algorithm. The results of the study indicate that the Remes algorithm and the differential correction algorithm III are the most satisfactory methods to use in practice.

References

Best Rational Approximation and Strict Quasi-Convexity

I. Barrodale and J. C. Mason, Two simple algorithms for discrete rational approximation, Math. Comp. 24 (1970), 877–891. MR 301894, DOI 10.1090/S0025-5718-1970-0301894-X

The Differential Correction Algorithm for Rational

Approximation

E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
E. W. Cheney and H. L. Loeb, Two new algorithms for rational approximation, Numer. Math. 3 (1961), 72–75. MR 121965, DOI 10.1007/BF01386002
E. W. Cheney and H. L. Loeb, On rational Chebyshev approximation, Numer. Math. 4 (1962), 124–127. MR 152108, DOI 10.1007/BF01386303
E. W. Cheney and T. H. Southard, A survey of methods for rational approximation, with particular reference to a new method based on a forumla of Darboux, SIAM Rev. 5 (1963), 219–231. MR 158531, DOI 10.1137/1005065
Charles B. Dunham, Convergence problems in Maehly’s second method, J. Assoc. Comput. Mach. 12 (1965), 181–186. MR 181083, DOI 10.1145/321264.321268
Charles B. Dunham, Convergence problems in Maehly’s second method. II, J. Assoc. Comput. Mach. 13 (1966), 108–113. MR 188680, DOI 10.1145/321312.321320
George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223

Comm. Assoc. Comput. Mach.

Saul I. Gass, Linear programming. Methods and applications, 3rd ed., McGraw-Hill Book Co., New York-London-Toronto, Ont., 1969. MR 0266606

On Rational Fraction Approximations at Discrete Points

Henry L. Loeb, Algorithms for Chebyshev approximations using the ratio of linear forms, J. Soc. Indust. Appl. Math. 8 (1960), 458–465. MR 119383, DOI 10.1137/0108031
Hans J. Maehly, Methods for fitting rational approximations. II, III, J. Assoc. Comput. Mach. 10 (1963), 257–277. MR 157474, DOI 10.1145/321172.321173
M. R. Osborne and G. A. Watson, An algorithm for minimax approximation in the nonlinear case, Comput. J. 12 (1969/70), 63–68. MR 245314, DOI 10.1093/comjnl/12.1.63
Anthony Ralston, A first course in numerical analysis, McGraw-Hill Book Co., New York-Toronto-London, 1965. MR 0191070
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
Theodore J. Rivlin, An introduction to the approximation of functions, Blaisdell Publishing Co. [Ginn and Co.], Waltham, Mass.-Toronto, Ont.-London, 1969. MR 0249885
G. A. Watson, On an algorithm for nonlinear minimax approximation, Comm. ACM 13 (1970), 160–162. MR 0286485, DOI 10.1145/362052.362056
Helmut Werner, Tschebyscheff-Approximation im Bereich der rationalen Funktionen bei Vorliegen einer guten Ausgangsnäherung, Arch. Rational Mech. Anal. 10 (1962), 205–219 (German). MR 144448, DOI 10.1007/BF00281188