Clenshaw-Algorithmus

Der Clenshaw-Algorithmus ist ein Algorithmus der numerischen Mathematik, mit dem Linearkombinationen von Orthogonalpolynomen wie beispielsweise den Tschebyschow-Polynomen ausgewertet werden können. Dabei wird ausgenutzt, dass sich diese Polynome rekursiv berechnen lassen.

Algorithmus

Sei $(p_{k}) \in C [a, b]^{n}$ eine Folge von Funktionen, die einer Dreiterm-Rekursionsbedingung genügen:

p_{0} (x)

sei gegeben,

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

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

für

k \in {2, 3, \dots}

Dann lässt sich $f_{n} (x) : = \sum_{k = 0}^{n} c_{k} p_{k} (x)$ wie folgt berechnen^[1]:

z_{n} : = c_{n}

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

for

k \in {n - 2, n - 3, \dots, 0}

{

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

}

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

C. W. Clenshaw: A note on the summation of Chebyshev series, Mathematical Tables and Other Aids to Computation, Band 9, 1955, S. 118.
W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery: Section 5.4.2. Clenshaw's Recurrence Formula, in: Press, Teukolsky, Vetterling, Flannery, Numerical Recipes: The Art of Scientific Computing, 3. Auflage, Cambridge University Press, 2007
Leslie Fox, Ian B. Parker: Chebyshev Polynomials in Numerical Analysis, Oxford University Press, 1968