Clenshaw algorithm

From Wikipedia, the free encyclopedia

In the mathematical subfield of numerical analysis the Clenshaw algorithm (Invented by Charles William Clenshaw) is a recursive method to evaluate polynomials in Chebyshev form.

[edit] Polynomial in Chebyshev form

A polynomial of degree N in Chebyshev form is a polynomial p(x) of the form

p(x) = \sum_{n=0}^{N} a_n T_n(x)

where Tn is the nth Chebyshev polynomial.

[edit] Clenshaw algorithm

The Clenshaw algorithm can be used to evaluate a polynomial in the Chebyshev form. Given

p(x) = \sum_{n=0}^{N} a_n T_n(x)

we define

b_{N} \,\! := a_{N} \,
b_{N-1} \,\! := 2 x b_{N} + a_{N-1} \,
b_{N-n} \,\! := 2 x b_{N-n+1} + a_{N-n} - b_{N-n+2} \,,\; n=2,\ldots,N-1 \,
b_{0} \,\! := x b_{1} + a_{0} - b_{2} \,

then

p(x) = \sum_{n=0}^{N} a_n T_n(x) = b_{0}.

[edit] See also