A comparison of algorithms for rational approximation

Authors:
C. M. Lee and F. D. K. Roberts

Journal:
Math. Comp. **27** (1973), 111-121

MSC:
Primary 65D15

DOI:
https://doi.org/10.1090/S0025-5718-1973-0331719-0

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

Corrigendum:
Math. Comp. **33** (1979), 847.

MathSciNet review:
0331719

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Results are reported of a numerical study to compare eight algorithms for obtaining rational 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.

**[1]**I. Barrodale,*Best Rational Approximation and Strict Quasi-Convexity*, M.R.C. Report 1157, University of Wisconsin, Madison, Wis., 1971.**[2]**I. Barrodale & J. C. Mason, "Two simple algorithms for discrete rational approximation,"*Math. Comp.*, v. 24, 1970, pp. 877-891. MR**0301894 (46:1049)****[3]**I. Barrodale, M. J. D. Powell & F. D. K. Roberts,*The Differential Correction Algorithm for Rational**Approximation*, Math. Report No. 54, University of Victoria, Victoria, British Columbia, 1971.**[4]**E. W. Cheney,*Introduction to Approximation Theory*, McGraw-Hill, New York, 1966. MR**36**#5568. MR**0222517 (36:5568)****[5]**E. W. Cheney & H. L. Loeb, "Two new algorithms for rational approximation,"*Numer. Math.*, v. 3, 1961, pp. 72-75. MR**22**#12692. MR**0121965 (22:12692)****[6]**E. W. Cheney & H. L. Loeb, "On rational Chebyschev approximation,"*Numer. Math.*, v. 4, 1962, pp. 124-127. MR**27**#2088. MR**0152108 (27:2088)****[7]**E. W. Cheney & T. H. Southard, "A survey of methods for rational approximation, with particular reference to a new method based on a formula of Darboux,"*SIAM Rev.*, v. 5, 1963, pp. 219-231. MR**28**#1754. MR**0158531 (28:1754)****[8]**C. B. Dunham, "Convergence problems in Maehly's second method,"*J. Assoc. Comput. Mach.*, v. 12, 1965, pp. 181-186. MR**31**#5312. MR**0181083 (31:5312)****[9]**C. B. Dunham, "Convergence problems in Maehly's second method. II,"*J. Assoc. Comput. Mach.*,v. 13, 1966, pp. 108-113. MR**32**#6116. MR**0188680 (32:6116)****[10]**G. Forsythe & C. B. Moler,*Computer Solution of Linear Algebraic Systems*, Prentice-Hall, Englewood Cliffs, N.J., 1967. MR**36**#2306. MR**0219223 (36:2306)****[11]**W. Fraser & J. F. Hart, "On the computation of rational approximations to continuous functions,"*Comm. Assoc. Comput. Mach.*, v. 5, 1962, pp. 401-403.**[12]**S. I. Gass,*Linear Programming. Methods and Applications*, 3rd ed., McGraw-Hill, New York, 1969. MR**42**#1509. MR**0266606 (42:1509)****[13]**H. L. Loeb,*On Rational Fraction Approximations at Discrete Points*, Convair Astronautics, Math. Preprint No. 9, 1957.**[14]**H. L. Loeb, "Algorithms for Chebyshev approximations using the ratio of linear forms,"*J. Soc. Indust. Appl. Math.*, v. 8, 1960, pp. 458-465. MR**22**#10147. MR**0119383 (22:10147)****[15]**H. J. Maehly & C. Witzgall, "Methods for fitting rational approximations. II, III,"*J. Assoc. Comput. Mach.*, v. 10, 1963, pp. 257-277. MR**28**#707. MR**0157474 (28:707)****[16]**M. R. Osborne & G. A. Watson, "An algorithm for minimax approximation in the nonlinear case,"*Comput. J.*, v. 12, 1969/70, pp. 63-68. MR**39**#6625. MR**0245314 (39:6625)****[17]**A. Ralston,*A First Course in Numerical Analysis*, McGraw-Hill, New York, 1965. MR**32**#8479. MR**0191070 (32:8479)****[18]**J. R. Rice,*The Approximation of Functions*. Vol. 2:*Nonlinear and Multivariate Theory*, Addison-Wesley, Reading, Mass., 1969. MR**39**#5989. MR**0244675 (39:5989)****[19]**T. J. Rivlin,*An Introduction to the Approximation of Functions*, Blaisdell, Waltham, Mass., 1969. MR**40**#3126. MR**0249885 (40:3126)****[20]**G. A. Watson, "On an algorithm for nonlinear minimax approximation,"*Comm. Assoc. Comput. Mach.*, v. 13, 1970, pp. 160-162. MR**0286485 (44:3694)****[21]**H. Werner, "Tschebyscheff-Approximation im Bereich der rationalen Funktionen bei Vorliegen einer guten Ausgangsnäherung,"*Arch. Rational Mech. Anal.*, v. 10, 1962, pp. 205-219. MR**26**#1993. MR**0144448 (26:1993)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65D15

Retrieve articles in all journals with MSC: 65D15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1973-0331719-0

Keywords:
Rational approximation,
linear programming

Article copyright:
© Copyright 1973
American Mathematical Society