Continuous phase modulation

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 ${\varphi }_k,k=0,1,\dots$ is a sequence of functions that satisfy the linear recurrence relation

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

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

$S(x)=\sum _{k=0}^n{a}_k{\varphi }_k(x)$

Given the coefficients $a_0,\dots ,a_n$, compute the values $b_k(x)$ by the "reverse" recurrence formula:

$\begin{array}{rl}{b}_{n+1}(x)& =b_{n+2}(x)=0,\\ b_k(x)& =a_k+{\alpha }_k(x)b_{k+1}(x)+{\beta }_{k+1}(x)b_{k+2}(x).\end{array}$

The linear combination of the ${\varphi }_k$ satisfies:

$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 for more information and stability analyses.

Horner as a special case of Clenshaw

A particularly simple case occurs when evaluating a polynomial of the form

$S(x)=\sum _{k=0}^n{a}_k{x}^k$.

The functions are simply

$\begin{array}{rl}{\varphi }_0(x)& =1,\\ {\varphi }_k(x)& =x^k=x{\varphi }_{k-1}(x)\end{array}$

and are produced by the recurrence coefficients $\alpha (x)=x$ and $\beta =0$.

In this case, the recurrence formula to compute the sum is

$b_k(x)=a_k+x{b}_{k+1}(x)$

and, in this case, the sum is simply

$S(x)=a_0+x{b}_1(x)=b_0(x)$,

which is exactly the usual Horner's method.

Special case for Chebyshev series

Consider a truncated Chebyshev series

$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 the Chebyshev polynomials are

$\alpha (x)=2x,\beta =-1,$

with the initial conditions

$T_0(x)=1,T_1(x)=x.$

Thus, the recurrence is

$b_k(x)=a_k+2x{b}_{k+1}(x)-b_{k+2}(x)$

and the final sum is

$p_n(x)=a_0+x{b}_1(x)-b_2(x).$

One way to evaluate this is to continue the recurrence one more step, and compute

$b_0(x)=2a_0+2x{b}_1(x)-b_2(x),$

(note the doubled a₀ coefficient) followed by

$p_n(x)=b_0(x)-x{b}_1(x)-a_0=\frac{1}{2}[b_0(x)-b_2(x)].$

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 .$

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

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 ,{\beta }_k=-1.$

and the evaluation of the series is given by

$\begin{array}{rl}{b}_{n+1}(\theta )& =b_{n+2}(\theta )=0,\\ b_k(\theta )& =C_k+2b_{k+1}(\theta )\cos \theta -b_{k+2}(\theta )(n\ge k\ge 1).\end{array}$

The final step is made particularly simple because ${\varphi }_0(\theta )=\sin 0=0$, so the end of the recurrence is simply $b_1(\theta )\sin (\theta )$; the $C_0\theta$ term is added separately:

$m(\theta )=C_0\theta +b_1(\theta )\sin \theta .$

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