Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Clenshaw algorithm
Summary
In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials. 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.
In full generality, the Clenshaw algorithm computes the weighted sum of a finite series of functions :
where is a sequence of functions that satisfy the linear recurrence relation
where the coefficients and are known in advance.
The algorithm is most useful when are functions that are complicated to compute directly, but and are particularly simple. In the most common applications, does not depend on , and is a constant that depends on neither nor .
To perform the summation for given series of coefficients , compute the values by the "reverse" recurrence formula:
Note that this computation makes no direct reference to the functions . After computing and ,
the desired sum can be expressed in terms of them and the simplest functions and :
See Fox and Parker for more information and stability analyses.
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.
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
Clenshaw summation is extensively used in geodetic applications. A simple application is summing the trigonometric series to compute
the meridian arc distance on the surface of an ellipsoid.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.