Algorytm Clenshawa

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

Algorytm Clenshawa

Niech ciąg ${\varphi }_k,k=0,1,\dots$ spełnia liniową relację rekurencyjną

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

gdzie współczynniki ${\alpha }_k$ i ${\beta }_k$ są znane. Dla dowolnego, skończonego ciągu $c_0,\dots ,c_n,$ definiujemy funkcje $b_k$ przez „odwrócony” wzór rekurencyjny:

$\begin{array}{cc}{b}_{n+1}(x)& =b_{n+2}(x)=0,\\ b_k(x)& =c_k-{\alpha }_k(x)b_{k+1}(x)-{\beta }_{k+1}(x)b_{k+2}(x).\end{array}$

Kombinacja liniowa ${\varphi }_k$ spełnia:

$\sum _{k=0}^n{c}_k{\varphi }_k(x)=b_0(x){\varphi }_0(x)+b_1(x)[{\varphi }_1(x)+{\alpha }_0(x){\varphi }_0(x)].$

Specjalny przypadek dla ciągu wielomianów Czebyszewa

Rozważmy kombinację liniową wielomianów Czebyszewa

$p_n(x)=\frac{a_0}{2}+a_1{T}_1(x)+a_2{T}_2(x)+\dots +a_n{T}_n(x).$

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

${\alpha }_k(x)=-2x,{\beta }_k=1.$

Korzystając z zależności

$\begin{array}{cc}{T}_0(x)& =1,T_1(x)=x{T}_0(x),\\ b_0(x)& =a_0+2x{b}_1(x)-b_2(x),\end{array}$

algorytm Clenshawa redukuje się do:

$p_n(x)=\frac{1}{2}[b_0(x)-b_2(x)].$

Zobacz też

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