Clenshaw algorithm

From Freepedia

In the mathematical subfield of numerical analysis the Clenshaw algorithm is a recursive method to evaluate polynomials in Chebyshev form.

Polynomial in Chebyshev form

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

<math>p(x) = \sum_{n=0}^{N} a_n T_n(x)</math>

where T_n is the nth Chebyshev polynomial.

Clenshaw algorithm

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

<math>p(x) = \sum_{n=0}^{N} a_n T_n(x)</math>

we define

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

then

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

See also

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