# .

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].$$

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).