Algorytm Clenshawa

W analizie numerycznej, algorytm Clenshawa jest rekurencyjną metodą obliczania liniowej kombinacji wielomianów Czebyszewa. W ogólności stosuje się go do dowolnej klasy funkcji definiowalnych za pomocą trójtermowego równania rekurencyjnego.

Algorytm Clenshawa

Niech ciąg $\phi_k,\; k = 0, 1, \ldots$ spełnia liniową relację rekurencyjną

$\phi_{k+1}(x) + \alpha_k(x)\,\phi_k(x) + \beta_k(x)\,\phi_{k-1}(x) = 0,$

gdzie współczynniki $\alpha_k$ i $\beta_k$ są znane. Dla dowolnego, skończonego ciągu $c_0, \ldots, c_n$, definiujemy funkcje $b_k$ przez "odwrócony" wzór rekurencyjny:

$\begin{align} 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}\,b_{k+2}(x). \end{align}$

Kombinacja liniowa $\phi_k$ spełnia:

$\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].$

Specjany przypadek dla ciągu wielomianów Czebyszewa

Rozważmy kombinację liniową wielomianów Czebyszewa

$p_n(x) = \frac{a_0}{2} + a_1T_1(x) + a_2T_2(x) + \cdots + a_nT_n(x).$

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

$\alpha_k(x) = -2x, \quad \beta_k = 1.$

Korzystając z zależności

$\begin{align} T_0(x) &= 1, \quad T_1(x) = xT_0(x),\\[.5em] b_{0}(x) &= a_0 + 2xb_1(x) - b_2(x), \end{align}$

Algorytm Clenshawa redukuje się do:

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

Zobacz też

• Schemat Hornera do obliczania wielomianów w postaci potęgowej
• Algorytm de Casteljau do obliczania wielomianów w postaci Beziera