A fast algorithm for linear complex Chebyshev approximations

Author:
Ping Tak Peter Tang

Journal:
Math. Comp. **51** (1988), 721-739

MSC:
Primary 30E10; Secondary 65D15, 65E05

DOI:
https://doi.org/10.1090/S0025-5718-1988-0935074-5

MathSciNet review:
935074

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**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**0483298**, https://doi.org/10.1090/S0025-5718-1978-0483298-X**[2]**Hans-Peter Blatt,*On strong uniqueness in linear complex Chebyshev approximation*, J. Approx. Theory**41**(1984), no. 2, 159–169. MR**747399**, https://doi.org/10.1016/0021-9045(84)90109-6**[3]**E. W. Cheney,*Introduction to approximation theory*, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR**1656150****[4]**C. B. Dunham and Jack Williams,*Rate of convergence of discretization in Chebyshev approximation*, Math. Comp.**37**(1981), no. 155, 135–139. MR**616366**, https://doi.org/10.1090/S0025-5718-1981-0616366-X**[5]**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**, https://doi.org/10.1090/S0025-5718-1976-0400652-0**[6]**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**, https://doi.org/10.1007/BFb0072674**[7]**Bruce A. Francis, J. William Helton, and George Zames,*\cal𝐻^{∞}-optimal feedback controllers for linear multivariable systems*, IEEE Trans. Automat. Control**29**(1984), no. 10, 888–900. MR**760527**, https://doi.org/10.1109/TAC.1984.1103387**[8]**Walter Gautschi,*Efficient computation of the complex error function*, SIAM J. Numer. Anal.**7**(1970), 187–198. MR**0293813**, https://doi.org/10.1137/0707012**[9]**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**, https://doi.org/10.1090/S0025-5718-1981-0595055-4**[10]**Martin H. Gutknecht,*Nonstrong uniqueness in real and complex Chebyshev approximation*, J. Approx. Theory**23**(1978), no. 3, 204–213. MR**505745**, https://doi.org/10.1016/0021-9045(78)90110-7**[11]**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**, https://doi.org/10.1016/0377-0427(86)90138-X**[12]**J. William Helton,*Worst case analysis in the frequency domain: the 𝐻^{∞} approach to control*, IEEE Trans. Automat. Control**30**(1985), no. 12, 1154–1170. MR**811936**, https://doi.org/10.1109/TAC.1985.1103860**[13]**A. K. Hui, B. H. Armstrong & A. A. Wray, "Rapid computation of the Voigt and complex error functions,"*J. Quant. Spectrosc. Radiat. Transfer*, v. 19, 1978, pp. 509-516.**[14]**J. Humlíček, "Optimized computation of the Voigt and complex probability functions,"*J. Quant. Spectrosc. Radiat. Transfer*, v. 27, 1982, pp. 437-444.**[15]**W. Kahan,*Lecture Notes on Superlinear Convergence of a Remes Algorithm*, Class Notes for Computer Science 274, University of California at Berkeley, April 1981.**[16]**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****[17]**C. L. Lawson,*Contributions to the Theory of Linear Least Maximum Approximations*, Ph.D. thesis, University of California at Los Angeles, 1961.**[18]**D. G. Luenberger,*Linear and Nonlinear Programming*, 2nd ed., Addison-Wesley, Reading, Mass., 1984.**[19]**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**, https://doi.org/10.1016/0021-9045(78)90082-5**[20]**Gerhard Opfer,*New extremal properties for constructing conformal mappings*, Numer. Math.**32**(1979), no. 4, 423–429. MR**542204**, https://doi.org/10.1007/BF01401045**[21]**M. J. D. Powell,*Approximation theory and methods*, Cambridge University Press, Cambridge-New York, 1981. MR**604014****[22]**Lothar Reichel,*On polynomial approximation in the complex plane with application to conformal mapping*, Math. Comp.**44**(1985), no. 170, 425–433. MR**777274**, https://doi.org/10.1090/S0025-5718-1985-0777274-0**[23]**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**0133636****[24]**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**, https://doi.org/10.1121/1.388002**[25]**P. T. P. Tang,*Chebyshev Approximation on the Complex Plane*, Ph.D. thesis, Department of Mathematics, University of California at Berkeley, May 1987.**[26]**Lloyd N. Trefethen,*Near-circularity of the curve in complex Chebyshev approximation*, J. Approx. Theory**31**(1981), no. 4, 344–367. MR**628517**, https://doi.org/10.1016/0021-9045(81)90102-7**[27]**L. Veidinger,*On the numerical determination of the best approximations in the Chebyshev sense*, Numer. Math.**2**(1960), 99–105. MR**0139889**, https://doi.org/10.1007/BF01386215**[28]**Jack Williams,*Numerical Chebyshev approximation in the complex plane*, SIAM J. Numer. Anal.**9**(1972), 638–649. MR**0314232**, https://doi.org/10.1137/0709053

Retrieve articles in *Mathematics of Computation*
with MSC:
30E10,
65D15,
65E05

Retrieve articles in all journals with MSC: 30E10, 65D15, 65E05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0935074-5

Article copyright:
© Copyright 1988
American Mathematical Society