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 & J. C. Mason, "Linear Chebyshev approximation of complex-valued functions,"*Math. Comp.*, v. 32, 1978, pp. 853-863. MR**0483298 (58:3313)****[2]**H.-P. Blatt, "On strong uniqueness in linear complex Chebyshev approximation,"*J. Approx. Theory*, v. 41, 1984, pp. 159-169. MR**747399 (85j:41051)****[3]**E. W. Cheney,*Introduction to Approximation Theory*, 2nd ed., Chelsea, New York, 1986. MR**1656150 (99f:41001)****[4]**C. B. Dunham & J. Williams, "Rate of convergence of discretization in Chebyshev approximation,"*Math. Comp.*, v. 37, 1981, pp. 135-139. MR**616366 (82f:41024)****[5]**S. W. Ellacott & J. Williams, "Linear Chebyshev approximation in the complex plane using Lawson's algorithm,"*Math. Comp.*, v. 30, 1976, pp. 35-44. MR**0400652 (53:4483)****[6]**H. C. Elman &. R. L. Streit,*Polynomial Iteration for Nonsymmetric Indefinite Linear Systems*, Research report YALEU/DCS/RR-380, Department of Computer Science, Yale University, New Haven, Conn., March 1985. MR**893620****[7]**B. Francis, J. W. Helton & G. Zamez, " -optimal feedback controllers for linear multivariable systems,"*IEEE Trans. Automat. Control*, v. 29, 1984, pp. 888-900. MR**760527 (85j:93023)****[8]**W. Gautschi, "Efficient computation of the complex error function,"*SIAM J. Numer. Anal.*, v. 7, 1970, pp. 187-198. MR**0293813 (45:2889)****[9]**K. Glashoff & K. Roleff, "A new method for Chebyshev approximation of complex-valued functions,"*Math. Comp.*, v. 36, 1981, pp. 233-239. MR**595055 (82c:65011)****[10]**M. H. Gutknecht, "Non-strong uniqueness in real and complex Chebyshev approximation,"*J. Approx. Theory*, v. 23, 1978, pp. 204-213. MR**505745 (80j:41044)****[11]**M. Hartmann & G. Opfer, "Uniform approximation as a numerical tool for constructing conformal maps,"*J. Comput. Appl. Math.*, v. 14, 1986, pp. 193-206. MR**829038 (87g:30006)****[12]**J. W. Helton, "Worst case analysis in the frequency domain: An approach for control,"*IEEE Trans. Automat. Control*, v. AC-30, 1985, pp. 1192-1201. MR**811936 (87e:93037)****[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. Laurent & C. Carasso, "An algorithm of successive minimization in convex programming,"*RAIRO Anal. Numér.*, v. 12, 1978, pp. 377-400. MR**519019 (80d:90067)****[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]**G. Opfer, "An algorithm for the construction of best approximation based on Kolmogorov's criterion,"*J. Approx. Theory*, v. 23, 1978, pp. 299-317. MR**509560 (80i:65019)****[20]**G. Opfer, "New extremal properties for constructing conformal mappings,"*Numer. Math.*, v. 32, 1979, pp. 423-429. MR**542204 (80h:30009)****[21]**M. J. D. Powell,*Approximation Theory and Methods*, Cambridge Univ. Press, Cambridge, 1981. MR**604014 (82f:41001)****[22]**L. Reichel, "On polynomial approximation in the complex plane with application to conformal mapping,"*Math. Comp.*, v. 44, 1985, pp. 425-433. MR**777274 (86c:30080)****[23]**T. J. Rivlin & H. S. Shapiro, "A unified approach to certain problems of approximation and minimization,"*J. Soc. Indust. Appl. Math.*, v. 9, 1961, pp. 670-699. MR**0133636 (24:A3462)****[24]**R. L. Streit & A. H. Nuttall, "A general Chebyshev complex function approximation procedure and an application to beamforming,"*J. Acoust. Soc. Amer.*, v. 72, 1982, pp. 181-190. MR**668082 (83g:78024)****[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]**L. N. Trefethen, "Near circularity of the error curve in complex Chebyshev approximation,"*J. Approx. Theory*, v. 31, 1981, pp. 344-366. MR**628517 (83e:41011)****[27]**L. Veidinger, "On the numerical determination of the best approximation in the Chebyshev sense,"*Numer. Math.*, v. 2, 1960, pp. 99-105. MR**0139889 (25:3316)****[28]**J. Williams, "Numerical Chebyshev approximation in the complex plane,"*SIAM J. Numer. Anal.*, v. 9, 1972, pp. 638-649. MR**0314232 (47:2784)**

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