Clenshaw algorithm
In numerical analysis, the Clenshaw algorithm[1] is a recursive method to evaluate a linear combination of Chebyshev polynomials. It is a generalization of Horner's method for evaluating a linear combination of monomials.
It generalizes to more than just Chebyshev polynomials; it applies to any class of functions that can be defined by a three-term recurrence relation.[2]
Clenshaw algorithm
Suppose that is a sequence of functions that satisfy the linear recurrence relation
where the coefficients and are known in advance. Note that in the most common applications, does not depend on , and is a constant that depends on neither nor .
Our goal is to evaluate a weighted sum of these functions
Given the coefficients , compute the values by the "reverse" recurrence formula:
The linear combination of the satisfies:
See Fox and Parker[3] for more information and stability analyses.
Horner as a special case of Clenshaw
A particularly simple case occurs when evaluating a polynomial of the form
- .
The functions are simply
and are produced by the recurrence coefficients and .
In this case, the recurrence formula to compute the sum is
and, in this case, the sum is simply
- ,
which is exactly the usual Horner's method.
Special case for Chebyshev series
Consider a truncated Chebyshev series
The coefficients in the recursion relation for the Chebyshev polynomials are
with the initial conditions
Thus, the recurrence is
and the final sum is
One way to evaluate this is to continue the recurrence one more step, and compute
(note the doubled a0 coefficient) followed by
Geodetic applications
Clenshaw's algorithm is extensively used in geodetic applications where it is usually referred to as Clenshaw summation.[4] A simple application is summing the trigonometric series to compute the meridian arc. These have the form
Leaving off the initial term, the remainder is a summation of the appropriate form. There is no leading term because .
The recurrence relation for is
- ,
making the coefficients in the recursion relation
and the evaluation of the series is given by
The final step is made particularly simple because , so the end of the recurrence is simply ; the term is added separately:
Note that the algorithm requires only the evaluation of two trigonometric quantities and .
See also
- Horner scheme to evaluate polynomials in monomial form
- De Casteljau's algorithm to evaluate polynomials in Bézier form
References
- ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1090/S0025-5718-1955-0071856-0, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1090/S0025-5718-1955-0071856-0
instead. Note that this paper is written in terms of the Shifted Chebyshev polynomials of the first kind . - ^ 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; I. B. Parker (1968), Chebyshev Polynomials in Numerical Analysis, Oxford University Press, ISBN 0-19-859614-6
- ^ Tscherning, C. C.; Poder, K. (1982), "Some Geodetic applications of Clenshaw Summation" (PDF), Bolletino di Geodesia e Scienze Affini, 41 (4): 349–375