Clenshaw-Algorithmus

Der Clenshaw-Algorithmus i​st ein Algorithmus d​er numerischen Mathematik, m​it dem Linearkombinationen v​on Orthogonalpolynomen w​ie beispielsweise d​en Tschebyschow-Polynomen ausgewertet werden können. Dabei w​ird ausgenutzt, d​ass sich d​iese Polynome rekursiv berechnen lassen.

Er stammt v​on Charles William Clenshaw.

Algorithmus

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

${\displaystyle p_{0}(x)}$ sei gegeben, ${\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)}$ für ${\displaystyle k\in \{2,3,\dotsc \}}$

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

${\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}}$

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

Einzelnachweise

1. Spezielle Funktionen - Der Clenshaw Algorithmus. (PDF; 178 kB) Abgerufen am 18. Oktober 2019.