A fast algorithm for linear complex Chebyshev approximations
Author:
Ping Tak Peter Tang
Journal:
Math. Comp. 51 (1988), 721739
MSC:
Primary 30E10; Secondary 65D15, 65E05
MathSciNet review:
935074
Fulltext 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 wellknown 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
complexvalued functions, Math. Comp.
32 (1978), no. 143, 853–863. MR 0483298
(58 #3313), http://dx.doi.org/10.1090/S0025571819780483298X
 [2]
HansPeter
Blatt, On strong uniqueness in linear complex Chebyshev
approximation, J. Approx. Theory 41 (1984),
no. 2, 159–169. MR 747399
(85j:41051), http://dx.doi.org/10.1016/00219045(84)901096
 [3]
E.
W. Cheney, Introduction to approximation theory, AMS Chelsea
Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150
(99f:41001)
 [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
(82f:41024), http://dx.doi.org/10.1090/S0025571819810616366X
 [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
(53 #4483), http://dx.doi.org/10.1090/S00255718197604006520
 [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, http://dx.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
(85j:93023), http://dx.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
(45 #2889)
 [9]
K.
Glashoff and K.
Roleff, A new method for Chebyshev
approximation of complexvalued functions, Math. Comp. 36 (1981), no. 153, 233–239. MR 595055
(82c:65011), http://dx.doi.org/10.1090/S00255718198105950554
 [10]
Martin
H. Gutknecht, Nonstrong uniqueness in real and complex Chebyshev
approximation, J. Approx. Theory 23 (1978),
no. 3, 204–213. MR 505745
(80j:41044), http://dx.doi.org/10.1016/00219045(78)901107
 [11]
M.
Hartmann and G.
Opfer, Uniform approximation as a numerical tool for constructing
conformal maps, J. Comput. Appl. Math. 14 (1986),
no. 12, 193–206. Special issue on numerical conformal mapping.
MR 829038
(87g:30006), http://dx.doi.org/10.1016/03770427(86)90138X
 [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
(87e:93037), http://dx.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. 509516.
 [14]
J. Humlíček, "Optimized computation of the Voigt and complex probability functions," J. Quant. Spectrosc. Radiat. Transfer, v. 27, 1982, pp. 437444.
 [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
(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., AddisonWesley, 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 (80i:65019), http://dx.doi.org/10.1016/00219045(78)900825
 [20]
Gerhard
Opfer, New extremal properties for constructing conformal
mappings, Numer. Math. 32 (1979), no. 4,
423–429. MR
542204 (80h:30009), http://dx.doi.org/10.1007/BF01401045
 [21]
M.
J. D. Powell, Approximation theory and methods, Cambridge
University Press, CambridgeNew York, 1981. MR 604014
(82f:41001)
 [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
(86c:30080), http://dx.doi.org/10.1090/S00255718198507772740
 [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 #A3462)
 [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
(83g:78024), http://dx.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, Nearcircularity of the curve in complex Chebyshev
approximation, J. Approx. Theory 31 (1981),
no. 4, 344–367. MR 628517
(83e:41011), http://dx.doi.org/10.1016/00219045(81)901027
 [27]
L.
Veidinger, On the numerical determination of the best
approximations in the Chebyshev sense, Numer. Math. 2
(1960), 99–105. MR 0139889
(25 #3316)
 [28]
Jack
Williams, Numerical Chebyshev approximation in the complex
plane, SIAM J. Numer. Anal. 9 (1972), 638–649.
MR
0314232 (47 #2784)
 [1]
 I. Barrodale, L. M. Delves & J. C. Mason, "Linear Chebyshev approximation of complexvalued functions," Math. Comp., v. 32, 1978, pp. 853863. MR 0483298 (58:3313)
 [2]
 H.P. Blatt, "On strong uniqueness in linear complex Chebyshev approximation," J. Approx. Theory, v. 41, 1984, pp. 159169. 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. 135139. 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. 3544. MR 0400652 (53:4483)
 [6]
 H. C. Elman &. R. L. Streit, Polynomial Iteration for Nonsymmetric Indefinite Linear Systems, Research report YALEU/DCS/RR380, 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. 888900. MR 760527 (85j:93023)
 [8]
 W. Gautschi, "Efficient computation of the complex error function," SIAM J. Numer. Anal., v. 7, 1970, pp. 187198. MR 0293813 (45:2889)
 [9]
 K. Glashoff & K. Roleff, "A new method for Chebyshev approximation of complexvalued functions," Math. Comp., v. 36, 1981, pp. 233239. MR 595055 (82c:65011)
 [10]
 M. H. Gutknecht, "Nonstrong uniqueness in real and complex Chebyshev approximation," J. Approx. Theory, v. 23, 1978, pp. 204213. 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. 193206. MR 829038 (87g:30006)
 [12]
 J. W. Helton, "Worst case analysis in the frequency domain: An approach for control," IEEE Trans. Automat. Control, v. AC30, 1985, pp. 11921201. 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. 509516.
 [14]
 J. Humlíček, "Optimized computation of the Voigt and complex probability functions," J. Quant. Spectrosc. Radiat. Transfer, v. 27, 1982, pp. 437444.
 [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. 377400. 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., AddisonWesley, 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. 299317. MR 509560 (80i:65019)
 [20]
 G. Opfer, "New extremal properties for constructing conformal mappings," Numer. Math., v. 32, 1979, pp. 423429. 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. 425433. 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. 670699. 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. 181190. 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. 344366. 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. 99105. MR 0139889 (25:3316)
 [28]
 J. Williams, "Numerical Chebyshev approximation in the complex plane," SIAM J. Numer. Anal., v. 9, 1972, pp. 638649. 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:
http://dx.doi.org/10.1090/S00255718198809350745
PII:
S 00255718(1988)09350745
Article copyright:
© Copyright 1988
American Mathematical Society
