Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [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, " $ {H^\infty }$-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 $ {H^\infty }$ 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)

Similar Articles

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

American Mathematical Society