.

In numerical analysis, the Clenshaw algorithm[1] is a recursive method to evaluate a linear combination of Chebyshev polynomials. In general it applies to any class of functions that can be defined by a three-term recurrence relation.[2]

Clenshaw algorithm

Suppose that \( \phi_k,\; k=0, 1, \ldots \) is a sequence of functions that satisfy the linear recurrence relation

\( \phi_{k+1}(x) + \alpha_k(x)\,\phi_k(x) + \beta_k(x)\,\phi_{k-1}(x) = 0, \)

where the coefficients \alpha_k and \beta_k are known in advance. For any finite sequence \(c_0, \ldots, c_n \), define the functions \( b_k \) by the "reverse" recurrence formula:

\( \begin{align} b_{n+1}(x) &= b_{n+2}(x) = 0, \\[.5em] b_{k}(x) &= c_k -\alpha_k(x)\,b_{k+1}(x) - \beta_{k+1}(x)\,b_{k+2}(x). \end{align} \)

The linear combination of the \( \phi_k \) satisfies:

\( \sum_{k=0}^n c_k \phi_k(x) = b_0(x) \phi_0(x) + b_1(x)\left[\phi_1(x) + \alpha_0(x)\phi_0(x)\right]. \)

See Fox and Parker[3] for more information and stability analyses.
Special case for Chebyshev series

Consider a truncated Chebyshev series

\( p_n(x) = \frac{a_0}{2} + a_1T_1(x) + a_2T_2(x) + \cdots + a_nT_n(x). \)

The coefficients in the recursion relation for the Chebyshev polynomials are

\( \alpha_k(x) = -2x, \quad \beta_k = 1. \)

Therefore, using the identities

\( \begin{align} T_0(x) &= 1, \quad T_1(x) = xT_0(x),\\[.5em] b_{0}(x) &= a_0 + 2xb_1(x) - b_2(x), \end{align} \)

Clenshaw's algorithm reduces to:

\( p_n(x) = \frac{1}{2}\left[a_0 + b_0(x) - b_2(x)\right]. \)

References

^ C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Tab. Wash. 9 (1955) pp 118--120.
^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 5.4.2. Clenshaw's Recurrence Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
^ L. Fox and I. B. Parker, Chebyshev Polynomials in Numerical Analysis, Oxford University Press (1968).