Clenshaw algorithm

The Clenshaw algorithm is an algorithm of numerical analysis , the linear combinations of orthogonal polynomials such as the Chebyshev polynomials can be evaluated. This makes use of the fact that these polynomials can be calculated recursively .

algorithm

Let be a sequence of functions that satisfy a three-term recursion condition: ${\ displaystyle (p_ {k}) \ in C [a, b] ^ {n}}$

{\ displaystyle p_ {0} (x)}

be given

{\ displaystyle p_ {1} (x) = a_ {1} (x) p_ {0} (x)}

{\ displaystyle p_ {k} (x) = a_ {k} (x) p_ {k-1} (x) + b_ {k} (x) p_ {k-2} (x)}

For

{\ displaystyle k \ in \ {2,3, \ dotsc \}}

Then it can be calculated as follows: ${\ displaystyle f_ {n} (x): = \ sum _ {k = 0} ^ {n} c_ {k} p_ {k} (x)}$

{\ displaystyle z_ {n}: = c_ {n}}

{\ displaystyle z_ {n-1}: = c_ {n-1} + a_ {n} (x) z_ {n}}

for {

{\ displaystyle k \ in \ {n-2, n-3, \ dotsc, 0 \}}

{\ displaystyle z_ {k}: = c_ {k} + a_ {k + 1} (x) z_ {k + 1} + b_ {k + 2} (x) z_ {k + 2}}

}

{\ displaystyle f_ {n} (x): = p_ {0} (x) z_ {0}}

CW Clenshaw: A note on the summation of Chebyshev series , Mathematical Tables and Other Aids to Computation, Volume 9, 1955, p. 118.
WH Press, SA Teukolsky, WT Vetterling, BP Flannery: Section 5.4.2. Clenshaw's Recurrence Formula , in: Press, Teukolsky, Vetterling, Flannery, Numerical Recipes: The Art of Scientific Computing, 3rd edition, Cambridge University Press, 2007
Leslie Fox, Ian B. Parker: Chebyshev Polynomials in Numerical Analysis , Oxford University Press, 1968