Abstract
Given samples of a real or complex-valued function on a set of distinct nodes, the traditional linear Chebyshev approximation is to compute the minimax approximation on a prescribed linear functional space. Lawson’s iteration is a classical and well-known method for the task. However, Lawson’s iteration converges only linearly and in many cases, the convergence is very slow. In this paper, relying upon the Lagrange duality, we establish an \(L_q\)-weighted dual programming for the discrete linear Chebyshev approximation. In this framework of dual problem, we revisit the convergence of Lawson’s iteration and provide a new and self-contained proof for the well-known Alternation Theorem in the real case; moreover, we propose a Newton type iteration, the interior-point method, to solve the \(L_2\)-weighted dual programming. Numerical experiments are reported to demonstrate its fast convergence and its capability in finding the reference points that characterize the unique minimax approximation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)
Brubeck, P.D., Nakatsukasa, Y., Trefethen, L.N.: Vandermonde with Arnoldi. SIAM Rev. 63, 405–415 (2021)
Cheney, E.W.: Introduction to Approximation Theory, 2nd edn. Chelsea Publishing Company, New York (1982)
Cline, A.K.: Rate of convergence of Lawson’s algorithm. Math. Comp. 26, 167–176 (1972)
Driscoll, T. A., Hale, N., Trefethen, L. N.: Chebfun User’s Guide. Pafnuty Publications, Oxford (2014). See also www.chebfun.org
Ellacott, S., Williams, J.: Linear Chebyshev approximation in the complex plane using Lawson’s algorithm. Math. Comp. 30, 35–44 (1976)
Filip, S.-I., Nakatsukasa, Y., Trefethen, L.N., Beckermann, B.: Rational minimax approximation via adaptive barycentric representations. SIAM J. Sci. Comput. 40, A2427–A2455 (2018)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore, Maryland (2013)
Lawson, C. L.: Contributions to the Theory of Linear Least Maximum Approximations. PhD thesis, UCLA, USA (1961)
Lorentz, G.G.: Approximation of Functions. Holt, Rinehart and Winston, New York (1966)
Nakatsukasa, Y., Sète, O., Trefethen, L.N.: The AAA algorithm for rational approximation. SIAM J. Sci. Comput. 40, A1494–A1522 (2018)
Nakatsukasa, Y., Trefethen, L.N.: An algorithm for real and complex rational minimax approximation. SIAM J. Sci. Comput. 42, A3157–A3179 (2020)
Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer, New York (2006)
Poussin, C. D. L. V.: Sur la méthode de lápproximation minimum. Soc. Sci. de Bruxelles, Annales, Seconde Partie, Mémoires. 35, 1–16 (1911)
Rice, J. R.: The Approximation of Functions. Addison-Wesley publishing Company (1969)
Rice, J.R., Usow, K.H.: The Lawson algorithm and extensions. Math. Comp. 22, 118–127 (1968)
Rivlin, T.J., Shapiro, H.S.: A unified approach to certain problems of approximation and minimization. J. Soc. Indust. Appl. Math. 9, 670–699 (1961)
Trefethen, L. N.: Approximation Theory and Approximation Practice, Extended Edition SIAM (2019)
Williams, J.: Numerical Chebyshev approximation in the complex plane. SIAM J. Numer. Anal. 9, 638–649 (1972)
Zhang, L.-H., Su, Y., Li, R.-C.: Accurate polynomial fitting and evaluation via Arnoldi. Numerical Algebra, Control and Optimization, to appear. https://doi.org/10.3934/naco.2023002
Acknowledgements
The authors would like to thank the anonymous referees for their useful comments and suggestions to improve the presentation of the paper.
Funding
The first author Linyi Yang was supported by the Postgraduate Research & Practice Innovation Program of Jiangsu Province (KYCX23_3226), and China Scholarship Council program (Project ID: 202306920044). The second author Lei-Hong Zhang was supported in part by the National Natural Science Foundation of China NSFC-12071332, NSFC-12371380, Jiangsu Shuangchuang Project (JSSCTD202209), and Academic Degree and Postgraduate Education Reform Project of Jiangsu Province.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
The authors declare that they have no conflict of interest.
Additional information
Communicated by: Tobin Driscoll
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Linyi, Y., Lei-Hong, Z. & Ya-Nan, Z. The \(L_q\)-weighted dual programming of the linear Chebyshev approximation and an interior-point method. Adv Comput Math 50, 80 (2024). https://doi.org/10.1007/s10444-024-10177-w
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-024-10177-w