The three-term recursion for Chebyshev polynomials is mixed forward-backward stable

DOI10.1007/S11075-014-9925-XMaRDI QIDQ494669zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alicja Smoktunowicz, Agata Smoktunowicz, Ewa Pawelec

Publication date 1 September 2015

Published in Numerical Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1312.5677

zbMATH Keywords

Chebyshev polynomialserror analysisfloating point arithmeticmixed forward-backward stabilityroots of polynomialsthree-term recurrence relation

Mathematics Subject Classification ID

Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Computation of special functions and constants, construction of tables (65D20) Roundoff error (65G50) Numerical computation of roots of polynomial equations (65H04) Numerical aspects of recurrence relations (65Q30)

Abstract: This paper provides error analyses of the algorithms most commonly used for the evaluation of the Chebyshev polynomial of the first kind $T_N(x)$. Some of these algorithms are shown to be backward stable. This means that the computed value of $T_N(x)$ in floating point arithmetic by these algorithms can be interpreted as a slightly perturbed value of polynomial $T_N$, for slightly perturbed value of $x$.

Review text

An algorithm \(W\) for computing the Chebyshev polynomial \(T_N(x)\) is called mixed forward-backward stable with respect to the data \(x\) if the value \(\widetilde T_N(x)\) computed by \(W\) in floating point arithmetic satisfies \[ \widetilde T_N(x)= (1 + \delta_N)T_N((1 + \Delta_N)x) + O(\epsilon_M^2), \quad |\delta_N|, |\Delta_N| \leq \epsilon_ML, \] where \(L=L(N)\) is a modestly growing function on \(N\) and \(\epsilon_M\) is the machine precision. The authors prove that the three-term recurrence relation \(T_{n+1}(x)=2xT_n(x) - T_{n-1}(x)\) is mixed forward-backward stable.

Recommendations

• Evaluation of Chebyshev polynomials by a three-term recurrence in floating-point arithmetic
• Accurate evaluation of Chebyshev polynomials in floating-point arithmetic
• Backward stability of Clenshaw's algorithm
• Evaluation of Legendre polynomials by a three-term recurrence in floating-point arithmetic
• Is the recurrence relation for orthogonal polynomials always stable?

Cites work

• A general condition number for polynomials
• A unified rounding error bound for polynomial evaluation
• An error analysis of Goertzel's (Watt's) method for computing Fourier coefficients
• Analysis of a nonlinear system with random characteristics
• Backward stability of Clenshaw's algorithm
• Barycentric Lagrange Interpolation
• Error analysis of an algorithm for summing certain finite series
• scientific article; zbMATH DE number 3146146 (Why is no real title available?)
• scientific article; zbMATH DE number 3658906 (Why is no real title available?)
• scientific article; zbMATH DE number 2107939 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• On algorithms for the summation of certain special functions
• Rounding error bounds for the Clenshaw and Forsythe algorithms for the evaluation of orthogonal polynomial series
• Stability of parallel algorithms to evaluate Chebyshev series

Cited in

(4)

• Evaluation of Chebyshev polynomials by a three-term recurrence in floating-point arithmetic
• Backward stability of Clenshaw's algorithm
• Accurate evaluation of Chebyshev polynomials in floating-point arithmetic
• Faster stochastic trace estimation with a Chebyshev product identity

Describes a project that uses

Uses Software

• mctoolbox
• Chebfun
• OPQ

This page was built for publication: The three-term recursion for Chebyshev polynomials is mixed forward-backward stable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494669)