Clenshaw algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).

In the mathematical subfield of numerical analysis the Clenshaw algorithm 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 T_n 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

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

Retrieved from "http://en.wikipedia.org../../../c/l/e/Clenshaw_algorithm.html"

Category: Numerical analysis

Views

Search