A fast algorithm for linear complex Chebyshev approximations

Tang, Ping Tak Peter

doi:10.1090/S0025-5718-1988-0935074-5

A fast algorithm for linear complex Chebyshev approximations
HTML articles powered by AMS MathViewer

by Ping Tak Peter Tang PDF

Math. Comp. 51 (1988), 721-739 Request permission

Abstract:

We propose a new algorithm for finding best minimax polynomial approximations in the complex plane. The algorithm is the first satisfactory generalization of the well-known Remez algorithm for real approximations. Among all available algorithms, ours is the only quadratically convergent one. Numerical examples are presented to illustrate rapid convergence.

References

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
Hans-Peter Blatt, On strong uniqueness in linear complex Chebyshev approximation, J. Approx. Theory 41 (1984), no. 2, 159–169. MR 747399, DOI 10.1016/0021-9045(84)90109-6
E. W. Cheney, Introduction to approximation theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150
C. B. Dunham and Jack Williams, Rate of convergence of discretization in Chebyshev approximation, Math. Comp. 37 (1981), no. 155, 135–139. MR 616366, DOI 10.1090/S0025-5718-1981-0616366-X
S. Ellacott and Jack Williams, Linear Chebyshev approximation in the complex plane using Lawson’s algorithm, Math. Comput. 30 (1976), no. 133, 35–44. MR 0400652, DOI 10.1090/S0025-5718-1976-0400652-0
Howard C. Elman and Roy L. Streit, Polynomial iteration for nonsymmetric indefinite linear systems, Numerical analysis (Guanajuato, 1984) Lecture Notes in Math., vol. 1230, Springer, Berlin, 1986, pp. 103–117. MR 893620, DOI 10.1007/BFb0072674
Bruce A. Francis, J. William Helton, and George Zames, ${\cal H}^{\infty }$-optimal feedback controllers for linear multivariable systems, IEEE Trans. Automat. Control 29 (1984), no. 10, 888–900. MR 760527, DOI 10.1109/TAC.1984.1103387
Walter Gautschi, Efficient computation of the complex error function, SIAM J. Numer. Anal. 7 (1970), 187–198. MR 293813, DOI 10.1137/0707012
K. Glashoff and K. Roleff, A new method for Chebyshev approximation of complex-valued functions, Math. Comp. 36 (1981), no. 153, 233–239. MR 595055, DOI 10.1090/S0025-5718-1981-0595055-4
Martin H. Gutknecht, Nonstrong uniqueness in real and complex Chebyshev approximation, J. Approx. Theory 23 (1978), no. 3, 204–213. MR 505745, DOI 10.1016/0021-9045(78)90110-7
M. Hartmann and G. Opfer, Uniform approximation as a numerical tool for constructing conformal maps, J. Comput. Appl. Math. 14 (1986), no. 1-2, 193–206. Special issue on numerical conformal mapping. MR 829038, DOI 10.1016/0377-0427(86)90138-X
J. William Helton, Worst case analysis in the frequency domain: the $H^\infty$ approach to control, IEEE Trans. Automat. Control 30 (1985), no. 12, 1154–1170. MR 811936, DOI 10.1109/TAC.1985.1103860

J. Quant. Spectrosc. Radiat. Transfer

Lecture Notes on Superlinear Convergence of a Remes Algorithm

P. J. Laurent and C. Carasso, An algorithm of successive minimization in convex programming, RAIRO Anal. Numér. 12 (1978), no. 4, 377–400, vi (English, with French summary). MR 519019, DOI 10.1051/m2an/1978120403771

Contributions to the Theory of Linear Least Maximum Approximations

Linear and Nonlinear Programming

Gerhard Opfer, An algorithm for the construction of best approximations based on Kolmogorov’s criterion, J. Approx. Theory 23 (1978), no. 4, 299–317 (English, with German summary). MR 509560, DOI 10.1016/0021-9045(78)90082-5
Gerhard Opfer, New extremal properties for constructing conformal mappings, Numer. Math. 32 (1979), no. 4, 423–429. MR 542204, DOI 10.1007/BF01401045
M. J. D. Powell, Approximation theory and methods, Cambridge University Press, Cambridge-New York, 1981. MR 604014
Lothar Reichel, On polynomial approximation in the complex plane with application to conformal mapping, Math. Comp. 44 (1985), no. 170, 425–433. MR 777274, DOI 10.1090/S0025-5718-1985-0777274-0
T. J. Rivlin and H. S. Shapiro, A unified approach to certain problems of approximation and minimization, J. Soc. Indust. Appl. Math. 9 (1961), 670–699. MR 133636
R. L. Streit and A. H. Nuttall, A general Chebyshev complex function approximation procedure and an application to beamforming, J. Acoust. Soc. Amer. 72 (1982), no. 1, 181–190. MR 668082, DOI 10.1121/1.388002

Chebyshev Approximation on the Complex Plane

Lloyd N. Trefethen, Near-circularity of the error curve in complex Chebyshev approximation, J. Approx. Theory 31 (1981), no. 4, 344–367. MR 628517, DOI 10.1016/0021-9045(81)90102-7
L. Veidinger, On the numerical determination of the best approximations in the Chebyshev sense, Numer. Math. 2 (1960), 99–105. MR 139889, DOI 10.1007/BF01386215
Jack Williams, Numerical Chebyshev approximation in the complex plane, SIAM J. Numer. Anal. 9 (1972), 638–649. MR 314232, DOI 10.1137/0709053