Innumerical analysis, theClenshaw algorithm, also calledClenshaw summation, is arecursive method to evaluate a linear combination ofChebyshev polynomials.^[1][2] The method was published byCharles William Clenshaw in 1955. It is a generalization ofHorner's method for evaluating a linear combination ofmonomials.

It generalizes to more than just Chebyshev polynomials; it applies to any class of functions that can be defined by a three-termrecurrence relation.^[3]

In full generality, the Clenshaw algorithm computes the weighted sum of a finite series of functions${\displaystyle {\varphi }_k(x)}$:$${\displaystyle S(x)=\sum _{k=0}^n{a}_k{\varphi }_k(x)}$$where${\displaystyle {\varphi }_k,k=0,1,\dots }$ is a sequence of functions that satisfy the linear recurrence relation$${\displaystyle {\varphi }_{k+1}(x)={\alpha }_k(x){\varphi }_k(x)+{\beta }_k(x){\varphi }_{k-1}(x),}$$where the coefficients${\displaystyle {\alpha }_k(x)}$ and${\displaystyle {\beta }_k(x)}$ are known in advance.

The algorithm is most useful when${\displaystyle {\varphi }_k(x)}$ are functions that are complicated to compute directly, but${\displaystyle {\alpha }_k(x)}$ and${\displaystyle {\beta }_k(x)}$ are particularly simple. In the most common applications,${\displaystyle \alpha (x)}$ does not depend on${\displaystyle k}$, and${\displaystyle \beta }$ is a constant that depends on neither${\displaystyle x}$ nor${\displaystyle k}$.

To perform the summation for given series of coefficients${\displaystyle a_0,\dots ,a_n}$, compute the values${\displaystyle b_k(x)}$ by the "reverse" recurrence formula:

Note that this computation makes no direct reference to the functions${\displaystyle {\varphi }_k(x)}$. After computing${\displaystyle b_2(x)}$ and${\displaystyle b_1(x)}$,the desired sum can be expressed in terms of them and the simplest functions${\displaystyle {\varphi }_0(x)}$ and${\displaystyle {\varphi }_1(x)}$:$${\displaystyle S(x)={\varphi }_0(x)a_0+{\varphi }_1(x)b_1(x)+{\beta }_1(x){\varphi }_0(x)b_2(x).}$$

See Fox and Parker^[4] for more information and stability analyses.

A particularly simple case occurs when evaluating a polynomial of the form$${\displaystyle S(x)=\sum _{k=0}^n{a}_k{x}^k.}$$The functions are simplyand are produced by the recurrence coefficients${\displaystyle \alpha (x)=x}$ and${\displaystyle \beta =0}$.

In this case, the recurrence formula to compute the sum is$${\displaystyle b_k(x)=a_k+x{b}_{k+1}(x)}$$and, in this case, the sum is simply$${\displaystyle S(x)=a_0+x{b}_1(x)=b_0(x),}$$which is exactly the usualHorner's method.

Consider a truncatedChebyshev series$${\displaystyle p_n(x)=a_0+a_1{T}_1(x)+a_2{T}_2(x)+\cdots +a_n{T}_n(x).}$$

The coefficients in the recursion relation for theChebyshev polynomials are$${\displaystyle \alpha (x)=2x,\beta =-1,}$$with the initial conditions$${\displaystyle T_0(x)=1,T_1(x)=x.}$$

Thus, the recurrence is$${\displaystyle b_k(x)=a_k+2x{b}_{k+1}(x)-b_{k+2}(x)}$$and the final results are$${\displaystyle b_0(x)=a_0+2x{b}_1(x)-b_2(x),}$$$${\displaystyle p_n(x)=\frac{1}{2}\left[a_0+b_0(x)-b_2(x)\right].}$$

An equivalent expression for the sum is given by$${\displaystyle p_n(x)=a_0+x{b}_1(x)-b_2(x).}$$

Clenshaw summation is extensively used ingeodetic applications.^[2] A simple application is summing the trigonometric series to compute themeridian arc distance on the surface of an ellipsoid. These have the form$${\displaystyle m(\theta )=C_0\theta +C_1\sin \theta +C_2\sin 2\theta +\cdots +C_n\sin n\theta .}$$

Leaving off the initial${\displaystyle C_0\theta }$ term, the remainder is a summation of the appropriate form. There is no leading term because${\displaystyle {\varphi }_0(\theta )=\sin 0\theta =\sin 0=0}$.

Therecurrence relation for${\displaystyle \sin k\theta }$ is$${\displaystyle \sin (k+1)\theta =2\cos \theta \sin k\theta -\sin (k-1)\theta ,}$$making the coefficients in the recursion relation$${\displaystyle {\alpha }_k(\theta )=2\cos \theta ,{\beta }_k=-1.}$$and the evaluation of the series is given byThe final step is made particularly simple because${\displaystyle {\varphi }_0(\theta )=\sin 0=0}$, so the end of the recurrence is simply${\displaystyle b_1(\theta )\sin (\theta )}$; the${\displaystyle C_0\theta }$ term is added separately:$${\displaystyle m(\theta )=C_0\theta +b_1(\theta )\sin \theta .}$$

Note that the algorithm requires only the evaluation of two trigonometric quantities${\displaystyle \cos \theta }$ and${\displaystyle \sin \theta }$.

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$${\displaystyle m({\theta }_1)-m({\theta }_2)=C_0({\theta }_1-{\theta }_2)+\sum _{k=1}^{n}2C_k\sin (\frac{1}{2}k({\theta }_1-{\theta }_2))\cos (\frac{1}{2}k({\theta }_1+{\theta }_2)).}$$Clenshaw summation can be applied in this case^[5]provided we simultaneously compute${\displaystyle m({\theta }_1)+m({\theta }_2)}$and perform a matrix summation,$${\displaystyle \mathsf{M}({\theta }_1,{\theta }_2)=\left[\begin{array}{c}(m({\theta }_1)+m({\theta }_2))/2\\ (m({\theta }_1)-m({\theta }_2))/({\theta }_1-{\theta }_2)\end{array}\right]=C_0\left[\begin{array}{c}\mu \\ 1\end{array}\right]+\sum _{k=1}^n{C}_k{\mathsf{F}}_k({\theta }_1,{\theta }_2),}$$whereThe first element of${\displaystyle \mathsf{M}({\theta }_1,{\theta }_2)}$ is the averagevalue of${\displaystyle m}$ and the second element is the average slope.${\displaystyle {\mathsf{F}}_k({\theta }_1,{\theta }_2)}$ satisfies the recurrencerelation$${\displaystyle {\mathsf{F}}_{k+1}({\theta }_1,{\theta }_2)=\mathsf{A}({\theta }_1,{\theta }_2){\mathsf{F}}_k({\theta }_1,{\theta }_2)-{\mathsf{F}}_{k-1}({\theta }_1,{\theta }_2),}$$wheretakes the place of${\displaystyle \alpha }$ in the recurrence relation, and${\displaystyle \beta =-1}$.The standard Clenshaw algorithm can now be applied to yieldwhere${\displaystyle {\mathsf{B}}_k}$ are 2×2 matrices. Finally we have$${\displaystyle \frac{m({\theta }_1)-m({\theta }_2)}{{\theta }_1-{\theta }_2}={\mathsf{M}}_2({\theta }_1,{\theta }_2).}$$This technique can be used in thelimit${\displaystyle {\theta }_2={\theta }_1=\mu }$ and${\displaystyle \delta =0}$ to simultaneously compute${\displaystyle m(\mu )}$ and thederivative${\displaystyle dm(\mu )/d\mu }$, provided that, in evaluating${\displaystyle {\mathsf{F}}_1}$ and${\displaystyle \mathsf{A}}$, we take${\displaystyle \underset{\delta \to 0}{lim}(\sin k\delta )/\delta =k}$.

• Horner scheme to evaluate polynomials inmonomial form
• De Casteljau's algorithm to evaluate polynomials inBézier form

• Numerical analysis

• CS1 maint: postscript