Algorytm Clenshawa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

W analizie numerycznej, algorytm Clenshawa[1] 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[2].


Algorytm Clenshawa[edytuj | edytuj kod]

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}(x)\,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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]


Przypisy

  1. C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Tab. Wash. 9 (1955) pp 118--120.
  2. W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery. Numerical Recipes: The Art of Scientific Computing. , 2007. Cambridge University Press.