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 <math>(p_k) \in C[a, b]^n</math> eine Folge von Funktionen, die einer Dreiterm-Rekursionsbedingung genügen:

<math>p_0(x)</math> sei gegeben, <math>p_1(x) = a_1(x) p_0(x)</math>

<math>p_k(x) = a_k (x) p_{k-1}(x) + b_k(x) p_{k-2} (x)</math> für <math>k \in \{2, 3, \dotsc\}</math>

Dann lässt sich <math>f_n(x) := \sum_{k=0}^n c_k p_k(x)</math> wie folgt berechnen<ref>Spezielle Funktionen - Der Clenshaw Algorithmus. (PDF; 178 kB) Abgerufen am 18. Oktober 2019. </ref>:

<math>z_n := c_n</math>

<math>z_{n-1} := c_{n-1} + a_n(x) z_n</math>

for <math>k \in \{n-2, n-3, \dotsc, 0\}</math> {

<math>z_k := c_k + a_{k+1}(x) z_{k+1} + b_{k+2}(x) z_{k+2}</math>

}

<math>f_n(x) := p_0(x) z_0</math>

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

<references/>