In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials.
[1][2] The method was published by Charles William Clenshaw in 1955.
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.
[3] In full generality, the Clenshaw algorithm computes the weighted sum of a finite series of functions
is a sequence of functions that satisfy the linear recurrence relation
are functions that are complicated to compute directly, but
To perform the summation for given series of coefficients
Note that this computation makes no direct reference to the functions
, the desired sum can be expressed in terms of them and the simplest functions
See Fox and Parker[4] for more information and stability analyses.
A particularly simple case occurs when evaluating a polynomial of the form
In this case, the recurrence formula to compute the sum is
which is exactly the usual Horner's method.
The coefficients in the recursion relation for the Chebyshev polynomials are
One way to evaluate this is to continue the recurrence one more step, and compute
Clenshaw summation is extensively used in geodetic applications.
[2] A simple application is summing the trigonometric series to compute the meridian arc distance on the surface of an ellipsoid.
term, the remainder is a summation of the appropriate form.
making the coefficients in the recursion relation
The final step is made particularly simple because
, so the end of the recurrence is simply
term is added separately:
Note that the algorithm requires only the evaluation of two trigonometric quantities
Sometimes it necessary to compute the difference of two meridian arcs in a way that maintains high relative accuracy.
This is accomplished by using trigonometric identities to write
Clenshaw summation can be applied in this case[5] provided we simultaneously compute
and perform a matrix summation,
cos k δ sin k μ
The standard Clenshaw algorithm can now be applied to yield