Clenshaw algorithm

The Clenshaw algorithm, also called Clenshaw summation, is a recursive method in numerical analysis for evaluating a linear combination of Chebyshev polynomials. It was published by Charles William Clenshaw in 1955 and generalizes Horner's method, which does the same job for a linear combination of ordinary monomials. It is not limited to Chebyshev polynomials: it applies to any family of functions that can be defined by a three-term recurrence relation. The method is most useful when the functions themselves are complicated to compute directly but the recurrence coefficients are simple, and it works by running a reverse recurrence over the series coefficients so that the sum never has to evaluate the functions one by one. Horner's method falls out as a special case, and the same scheme handles truncated Chebyshev series. Clenshaw summation is widely used in geodesy, for example to sum the trigonometric series that give the meridian arc length on the surface of an ellipsoid. The source points readers to Fox and Parker for stability analyses.