Clenshaw algorithm

In numerical analysis, the Clenshaw algorithm 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.

Clenshaw algorithm

Suppose that $\phi _{k},\;k=0,1,\ldots$ is a sequence of functions that satisfy the linear recurrence relation

$\phi _{k+1}(x)+\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x)=0,$

where the coefficients $\alpha _{k}$ and $\beta _{k}$ are known in advance. Note that in the most common applications, $\alpha (x)$ does not depend on $k$, and $\beta$ is a constant that depends on neither $x$ nor $k$.

Our goal is to evaluate a weighted sum of these functions

$\sum _{k=0}^{n}a_{k}\phi _{k}(x)$

Given the coefficients $a_{0},\ldots ,a_{n}$, compute the values $b_{k}(x)$ by the "reverse" recurrence formula:

${\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\[.5em]b_{k}(x)&=a_{k}-\alpha _{k}(x)\,b_{k+1}(\theta )-\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}$

The linear combination of the $\phi _{k}$ satisfies:

$\sum _{k=0}^{n}a_{k}\phi _{k}(x)=b_{0}(x)\phi _{0}(x)+b_{1}(x)\left[\phi _{1}(x)+\alpha _{0}(x)\phi _{0}(x)\right].$

See Fox and Parker for more information and stability analyses. The Horner scheme is a special case of the Clenshaw algorithm ($\phi _{k}(x)=x^{k}$, $\alpha _{k}(x)=-x$, $\beta _{k}(x)=0$).

Special case for Chebyshev series

Consider a truncated Chebyshev series

$p_{n}(x)={\frac {a_{0}}{2}}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\cdots +a_{n}T_{n}(x).$

The coefficients in the recursion relation for the Chebyshev polynomials are

$\alpha _{k}(x)=-2x,\quad \beta _{k}=1.$

Therefore, using the identities

${\begin{aligned}T_{0}(x)&=1,\quad T_{1}(x)=xT_{0}(x),\\[.5em]b_{0}(x)&=a_{0}+2xb_{1}(x)-b_{2}(x),\end{aligned}}$

Clenshaw's algorithm reduces to:

$p_{n}(x)=b_{0}(x)-xb_{1}(x)-{\frac {a_{0}}{2}}={\frac {1}{2}}\left[b_{0}(x)-b_{2}(x)\right].$

Geodetic applications

Clenshaw's algorithm is extensively used in geodetic applications where it is usually referred to as Clenshaw summation. A simple application is summing the trigonometric series to compute the meridian arc. These have the form

$m(\theta )=C_{0}\theta +C_{1}\sin \theta +C_{2}\sin 2\theta +\cdots +C_{n}\sin n\theta .$

The recurrence relation for $\sin k\theta$ is

$\sin k\theta =2\cos \theta \sin(k-1)\theta -\sin(k-2)\theta$,

making the coefficients in the recursion relation

$\alpha _{k}(\theta )=-2\cos \theta ,\quad \beta _{k}=1.$

and the evaluation of the series is given by

${\begin{aligned}b_{n+1}(\theta )&=b_{n+2}(\theta )=0,\\[.5em]b_{k}(\theta )&=C_{k}+2b_{k+1}(\theta )\cos \theta -b_{k+2}(\theta )\quad (n\geq k\geq 1),\\[.5em]m(\theta )&=C_{0}\theta +b_{1}(\theta )\sin \theta ,\end{aligned}}$

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

See also

• Horner scheme to evaluate polynomials in monomial form
• De Casteljau's algorithm to evaluate polynomials in Bézier form