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.

Er stammt von Charles William Clenshaw.

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,\dotsc \}$

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

$z_{n}:=c_{n}$

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

for $k\in \{n-2,n-3,\dotsc ,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}$

Literatur

• 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