Clenshaw algorithm

In numerical analysis, the Clenshaw algorithm 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.

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 α_k and β_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 φ_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 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].$

See also

• Horner scheme to evaluate polynomials in monomial form
• De Casteljau's algorithm to evaluate polynomials in Bézier form