in numerical analysis, the clenshaw algorithm, note that this paper is written in terms of the shifted chebyshev polynomials of the first kind t^*_n(x) = t_n(2x-1). also called clenshaw summation, is a recursive method to evaluate a linear combination of chebyshev polynomials. it is a generalization of horner's method for evaluating a linear combination of monomials. it generalizes to more than just chebyshev polynomials; it applies to any class of functions that can be defined by a three-term recurrence relation. ==clenshaw algorithm== in full generality, the clenshaw algorithm computes the weighted sum of a finite series of functions \phi_k(x): :s(x) = \sum_{k=0}^n a_k \phi_k(x) where \phi_k,\; k=0, 1, \ldots is a sequence of functions that satisfy the linear recurrence relation :\phi_{k+1}(x) = \alpha_k(x)\,\phi_k(x) + \beta_k(x)\,\phi_{k-1}(x), where the coefficients \alpha_k(x) and \beta_k(x) are known in advance. the algorithm is most useful when \phi_k(x) are complex functions to compute directly, but \alpha_k(x) and \beta_k(x) are particularly simple. in the most common applications, \alpha(x) does not depend on k, and \beta is a constant that depends on neither x nor k. to perform the summation for given series of coefficients a_0, \ldots, a_n, compute the values b_k(x) by the "reverse" recurrence formula: : \begin{align} b_{n+1}(x) &= b_{n+2}(x) = 0, \\ b_k(x) &= a_k + \alpha_k(x)\,b_{k+1}(x) + \beta_{k+1}(x)\,b_{k+2}(x). \end{align} note that this computation makes no direct reference to the functions \phi_k(x). after computing b_2(x) and b_1(x), the desired sum can be expressed in terms of them and the simplest functions \phi_0(x) and \phi_1(x): :s(x) = \phi_0(x)\,a_0 + \phi_1(x)\,b_1(x) + \beta_1(x)\,\phi_0(x)\,b_2(x). see fox and parker for more information and stability analyses. ==examples== ===horner as a special case of clenshaw=== a particularly simple case occurs when evaluating a polynomial of the form :s(x) = \sum_{k=0}^n a_k x^k. the functions are simply : \begin{align} \phi_0(x) &= 1, \\ \phi_k(x) &= x^k = x\phi_{k-1}(x) \end{align} and are produced by the recurrence coefficients \alpha(x) = x and \beta = 0. in this case, the recurrence formula to compute the sum is :b_k(x) = a_k + x b_{k+1}(x) and, in this case, the sum i
Numerical_analysis