{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:53:30Z","timestamp":1776794010050,"version":"3.51.2"},"reference-count":23,"publisher":"American Mathematical Society (AMS)","issue":"276","license":[{"start":{"date-parts":[[2012,3,31]],"date-time":"2012-03-31T00:00:00Z","timestamp":1333152000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Interpolation polynomial\n \n \n \n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n p_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n at the Chebyshev nodes\n \n \n \n \n cos<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \u03c0\n \n <\/mml:mi>\n j<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mrow>\n \\cos \\pi j\/n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (\n \n \n \n \n 0<\/mml:mn>\n \n \u2264\n \n <\/mml:mo>\n j<\/mml:mi>\n \n \u2264\n \n <\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n 0\\le j\\le n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ) for smooth functions is known to converge fast as\n \n \n \n \n n<\/mml:mi>\n \n \u2192\n \n <\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n n\\to \\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The sequence\n \n \n \n \n {<\/mml:mo>\n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{p_n\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is constructed recursively and efficiently in\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n O(n\\log _2n)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n flops for each\n \n \n \n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n p_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n by using the FFT, where\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is increased geometrically,\n \n \n \n \n n<\/mml:mi>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n i<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n n=2^i<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (\n \n \n \n \n i<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n \n \u2026\n \n <\/mml:mo>\n <\/mml:mrow>\n i=2,3,\\dots<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ), until an estimated error is within a given tolerance of\n \n \n \n \n \u03b5\n \n <\/mml:mi>\n \\varepsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This sequence\n \n \n \n \n {<\/mml:mo>\n \n 2<\/mml:mn>\n j<\/mml:mi>\n <\/mml:msup>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{2^j\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , however, grows too fast to get\n \n \n \n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n p_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of proper\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , often a much higher accuracy than\n \n \n \n \n \u03b5\n \n <\/mml:mi>\n \\varepsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n being achieved. To cope with this problem we present quasi-Chebyshev nodes (QCN) at which\n \n \n \n \n {<\/mml:mo>\n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{p_n\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n can be constructed efficiently in the same order of flops as in the Chebyshev nodes by using the FFT, but with\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n increasing at a slower rate. We search for the optimum set in the QCN that minimizes the maximum error of\n \n \n \n \n {<\/mml:mo>\n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{p_n\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Numerical examples illustrate the error behavior of\n \n \n \n \n {<\/mml:mo>\n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{p_n\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with the optimum nodes set obtained.\n <\/p>","DOI":"10.1090\/s0025-5718-2011-02484-1","type":"journal-article","created":{"date-parts":[[2011,3,31]],"date-time":"2011-03-31T13:19:58Z","timestamp":1301577598000},"page":"2169-2184","source":"Crossref","is-referenced-by-count":1,"title":["A polynomial interpolation process at quasi-Chebyshev nodes with the FFT"],"prefix":"10.1090","volume":"80","author":[{"given":"Hiroshi","family":"Sugiura","sequence":"first","affiliation":[]},{"given":"Takemitsu","family":"Hasegawa","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2011,3,31]]},"reference":[{"issue":"5","key":"1","doi-asserted-by":"publisher","first-page":"1743","DOI":"10.1137\/S1064827503430126","article-title":"An extension of MATLAB to continuous functions and operators","volume":"25","author":"Battles, Zachary","year":"2004","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1137\/S0036144502417715","article-title":"Barycentric Lagrange interpolation","volume":"46","author":"Berrut, Jean-Paul","year":"2004","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"5","key":"3","doi-asserted-by":"publisher","first-page":"1666","DOI":"10.1137\/S0036142901398325","article-title":"Computing zeros on a real interval through Chebyshev expansion and polynomial rootfinding","volume":"40","author":"Boyd, John P.","year":"2002","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/j.cam.2006.05.006","article-title":"Numerical experiments on the accuracy of the Chebyshev-Frobenius companion matrix method for finding the zeros of a truncated series of Chebyshev polynomials","volume":"205","author":"Boyd, John P.","year":"2007","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0771-050x(75)90009-1","article-title":"An extension of Clenshaw-Curtis quadrature","volume":"1","author":"Branders, Maria","year":"1975","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"6","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF01386223","article-title":"A method for numerical integration on an automatic computer","volume":"2","author":"Clenshaw, C. W.","year":"1960","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.2307\/2003354","article-title":"An algorithm for the machine calculation of complex Fourier series","volume":"19","author":"Cooley, James W.","year":"1965","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","volume-title":"Interpolation and approximation","author":"Davis, Philip J.","year":"1963"},{"key":"9","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/355602.361310","article-title":"Implementing Clenshaw-Curtis quadrature. I. Methodology and experience","volume":"15","author":"Gentleman, W. Morven","year":"1972","journal-title":"Comm. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"print"},{"issue":"164","key":"10","doi-asserted-by":"publisher","first-page":"537","DOI":"10.2307\/2007691","article-title":"Generalized Chebyshev interpolation and its application to automatic quadrature","volume":"41","author":"Hasegawa, Takemitsu","year":"1983","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"189","key":"11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.2307\/2008690","article-title":"An algorithm based on the FFT for a generalized Chebyshev interpolation","volume":"54","author":"Hasegawa, Takemitsu","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"12","isbn-type":"print","volume-title":"Chebyshev polynomials","author":"Mason, J. C.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0849303559"},{"key":"13","series-title":"Springer Series in Information Sciences","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-00551-4","volume-title":"Fast Fourier transform and convolution algorithms","volume":"2","author":"Nussbaumer, Henri J.","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/3540101594"},{"key":"14","unstructured":"R. B. Platte, L. N. Trefethen, Chebfun: A new kind of numerical computing, Report No. 08\/13, Oxford University Computing Laboratory, October (2008)."},{"issue":"224","key":"15","doi-asserted-by":"publisher","first-page":"1577","DOI":"10.1090\/S0025-5718-98-00975-2","article-title":"Fast algorithms for discrete polynomial transforms","volume":"67","author":"Potts, Daniel","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"5","key":"16","doi-asserted-by":"publisher","first-page":"2176","DOI":"10.1137\/040603280","article-title":"The accuracy of the Chebyshev differencing method for analytic functions","volume":"42","author":"Reddy, S. C.","year":"2005","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"4","key":"17","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF01403676","article-title":"Product integration with the Clenshaw-Curtis points: implementation and error estimates","volume":"34","author":"Sloan, Ian H.","year":"1980","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"193","key":"18","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2008542","article-title":"A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms","volume":"56","author":"Steidl, G.","year":"1991","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"19","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/0729070","article-title":"Polynomial interpolation on quasi-equidistributed nodes on the unit disk","volume":"29","author":"Sugiura, Hiroshi","year":"1992","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"175","key":"20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.2307\/2008098","article-title":"Symmetric FFTs","volume":"47","author":"Swarztrauber, Paul N.","year":"1986","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/060659831","article-title":"Is Gauss quadrature better than Clenshaw-Curtis?","volume":"50","author":"Trefethen, Lloyd N.","year":"2008","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"1","key":"22","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10543-006-0045-4","article-title":"Fast construction of the Fej\u00e9r and Clenshaw-Curtis quadrature rules","volume":"46","author":"Waldvogel, J\u00f6rg","year":"2006","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"issue":"4","key":"23","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s00211-007-0101-2","article-title":"The kink phenomenon in Fej\u00e9r and Clenshaw-Curtis quadrature","volume":"107","author":"Weideman, J. A. C.","year":"2007","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2011-80-276\/S0025-5718-2011-02484-1\/S0025-5718-2011-02484-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-276\/S0025-5718-2011-02484-1\/S0025-5718-2011-02484-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:57:34Z","timestamp":1776790654000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-276\/S0025-5718-2011-02484-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,31]]},"references-count":23,"journal-issue":{"issue":"276","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["S0025-5718-2011-02484-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2011-02484-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2011,3,31]]}}}