Algorytm Clenshawa

Algorytm Clenshawa^[1] – rekurencyjna metoda obliczania liniowej kombinacji wielomianów Czebyszewa. Stosuje się go do dowolnej klasy funkcji definiowalnych za pomocą trójtermowego równania rekurencyjnego^[2].

Niech ciąg ${\displaystyle \phi _{k},\;k=0,1,\dots }$ spełnia liniową relację rekurencyjną

${\displaystyle \phi _{k+1}(x)+\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x)=0,}$

gdzie współczynniki ${\displaystyle \alpha _{k}}$ i ${\displaystyle \beta _{k}}$ są znane. Dla dowolnego, skończonego ciągu ${\displaystyle c_{0},\dots ,c_{n},}$ definiujemy funkcje ${\displaystyle b_{k}}$ przez „odwrócony” wzór rekurencyjny:

${\displaystyle {\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\[.5em]b_{k}(x)&=c_{k}-\alpha _{k}(x)\,b_{k+1}(x)-\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}}$

Kombinacja liniowa ${\displaystyle \phi _{k}}$ spełnia:

${\displaystyle \sum _{k=0}^{n}c_{k}\phi _{k}(x)=b_{0}(x)\phi _{0}(x)+b_{1}(x)\left[\phi _{1}(x)+\alpha _{0}(x)\phi _{0}(x)\right].}$

Rozważmy kombinację liniową wielomianów Czebyszewa

${\displaystyle p_{n}(x)={\frac {a_{0}}{2}}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\ldots +a_{n}T_{n}(x).}$

Współczynniki w postaci rekurencyjnej dla wielomianów Czebyszewa to

${\displaystyle \alpha _{k}(x)=-2x,\quad \beta _{k}=1.}$

Korzystając z zależności

${\displaystyle {\begin{aligned}T_{0}(x)&=1,\quad T_{1}(x)=xT_{0}(x),\\[.5em]b_{0}(x)&=a_{0}+2xb_{1}(x)-b_{2}(x),\end{aligned}}}$

algorytm Clenshawa redukuje się do:

${\displaystyle p_{n}(x)={\frac {1}{2}}\left[b_{0}(x)-b_{2}(x)\right].}$

• schemat Hornera do obliczania wielomianów w postaci potęgowej
• algorytm de Casteljau do obliczania wielomianów w postaci Beziera