- 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]
Contents
Clenshaw algorithm
Suppose that is a sequence of functions that satisfy the linear recurrence relation
where the coefficients αk and βk are known in advance. For any finite sequence , define the functions bk by the "reverse" recurrence formula:
The linear combination of the φk satisfies:
See Fox and Parker[3] for more information and stability analyses.
Special case for Chebyshev series
Consider a truncated Chebyshev series
The coefficients in the recursion relation for the Chebyshev polynomials are
Therefore, using the identities
Clenshaw's algorithm reduces to:
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, http://apps.nrbook.com/empanel/index.html?pg=222
- ^ 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
Categories:
Wikimedia Foundation. 2010.