A comparison of algorithms for rational approximation
Authors:
C. M. Lee and F. D. K. Roberts
Journal:
Math. Comp. 27 (1973), 111121
MSC:
Primary 65D15
Corrigendum:
Math. Comp. 33 (1979), 847848.
Corrigendum:
Math. Comp. 33 (1979), 847.
MathSciNet review:
0331719
Fulltext PDF Free Access
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 OsborneWatson 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 QuasiConvexity, M.R.C. Report 1157, University of Wisconsin, Madison, Wis., 1971.
 [2]
I.
Barrodale and J.
C. Mason, Two simple algorithms for discrete
rational approximation, Math. Comp. 24 (1970), 877–891. MR 0301894
(46 #1049), http://dx.doi.org/10.1090/S0025571819700301894X
 [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, McGrawHill
Book Co., New York, 1966. MR 0222517
(36 #5568)
 [5]
E.
W. Cheney and H.
L. Loeb, Two new algorithms for rational approximation, Numer.
Math. 3 (1961), 72–75. MR 0121965
(22 #12692)
 [6]
E.
W. Cheney and H.
L. Loeb, On rational Chebyshev approximation, Numer. Math.
4 (1962), 124–127. MR 0152108
(27 #2088)
 [7]
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 0158531
(28 #1754)
 [8]
Charles
B. Dunham, Convergence problems in Maehly’s second
method, J. Assoc. Comput. Mach. 12 (1965),
181–186. MR 0181083
(31 #5312)
 [9]
Charles
B. Dunham, Convergence problems in Maehly’s second method.
II, J. Assoc. Comput. Mach. 13 (1966), 108–113.
MR
0188680 (32 #6116)
 [10]
George
E. Forsythe and Cleve
B. Moler, Computer solution of linear algebraic systems,
PrenticeHall Inc., Englewood Cliffs, N.J., 1967. 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. 401403.
 [12]
Saul
I. Gass, Linear programming. Methods and applications, Third
edition, McGrawHill Book Co., New York, 1969. MR 0266606
(42 #1509)
 [13]
H. L. Loeb, On Rational Fraction Approximations at Discrete Points, Convair Astronautics, Math. Preprint No. 9, 1957.
 [14]
Henry
L. Loeb, Algorithms for Chebyshev approximations using the ratio of
linear forms, J. Soc. Indust. Appl. Math. 8 (1960),
458–465. MR 0119383
(22 #10147)
 [15]
Hans
J. Maehly, Methods for fitting rational approximations. II,
III, J. Assoc. Comput. Mach. 10 (1963),
257–277. MR 0157474
(28 #707)
 [16]
M.
R. Osborne and G.
A. Watson, An algorithm for minimax approximation in the nonlinear
case, Comput. J. 12 (1969/1970), 63–68. MR 0245314
(39 #6625)
 [17]
Anthony
Ralston, A first course in numerical analysis, McGrawHill
Book Co., New York, 1965. MR 0191070
(32 #8479)
 [18]
John
R. Rice, The approximation of functions. Vol. 2: Nonlinear and
multivariate theory, AddisonWesley Publishing Co., Reading,
Mass.LondonDon Mills, Ont., 1969. MR 0244675
(39 #5989)
 [19]
Theodore
J. Rivlin, An introduction to the approximation of functions,
Blaisdell Publishing Co. Ginn and Co., Waltham, Mass.Toronto, Ont.London,
1969. MR
0249885 (40 #3126)
 [20]
G.
A. Watson, On an algorithm for nonlinear minimax
approximation, Comm. ACM 13 (1970), 160–162. MR 0286485
(44 #3694)
 [21]
Helmut
Werner, TschebyscheffApproximation im Bereich der rationalen
Funktionen bei Vorliegen einer guten Ausgangsnäherung, Arch.
Rational Mech. Anal. 10 (1962), 205–219 (German). MR 0144448
(26 #1993)
 [1]
 I. Barrodale, Best Rational Approximation and Strict QuasiConvexity, 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. 877891. 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, McGrawHill, 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. 7275. MR 22 #12692. MR 0121965 (22:12692)
 [6]
 E. W. Cheney & H. L. Loeb, "On rational Chebyschev approximation," Numer. Math., v. 4, 1962, pp. 124127. 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. 219231. 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. 181186. 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. 108113. MR 32 #6116. MR 0188680 (32:6116)
 [10]
 G. Forsythe & C. B. Moler, Computer Solution of Linear Algebraic Systems, PrenticeHall, 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. 401403.
 [12]
 S. I. Gass, Linear Programming. Methods and Applications, 3rd ed., McGrawHill, 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. 458465. 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. 257277. 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. 6368. MR 39 #6625. MR 0245314 (39:6625)
 [17]
 A. Ralston, A First Course in Numerical Analysis, McGrawHill, New York, 1965. MR 32 #8479. MR 0191070 (32:8479)
 [18]
 J. R. Rice, The Approximation of Functions. Vol. 2: Nonlinear and Multivariate Theory, AddisonWesley, 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. 160162. MR 0286485 (44:3694)
 [21]
 H. Werner, "TschebyscheffApproximation im Bereich der rationalen Funktionen bei Vorliegen einer guten Ausgangsnäherung," Arch. Rational Mech. Anal., v. 10, 1962, pp. 205219. MR 26 #1993. MR 0144448 (26:1993)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65D15
Retrieve articles in all journals
with MSC:
65D15
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197303317190
PII:
S 00255718(1973)03317190
Keywords:
Rational approximation,
linear programming
Article copyright:
© Copyright 1973 American Mathematical Society
