# .

# Clenshaw algorithm

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

See also

Horner scheme to evaluate polynomials in monomial form

De Casteljau's algorithm to evaluate polynomials in Bézier form

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License