Clenshaw-Algorithmus
# 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}$
