The Clenshaw algorithm is useful to evaluate the sum $ S(x) = \sum_{k=0}^n a_k\phi_k(x), $ where the $\phi_k$ can be computed through a three-term recurrence of the form $ \phi_{k+1} = \alpha_k(x)\phi_k(x) + \beta_k(x)\phi_{k-1}(x). $ The Clenshaw algorithm proceeds as follows. - Set $b_{n+1} = b_{n+2} = 0$. - For $k=n,\dots, 1$ compute $b_{k}(x) = a_k + \alpha_k(x)b_{k+1}(x) + \beta_{k+1}(x)b_{k+2}(x).$ - Finally, $S(x) = \phi_0(x)a_0 + \phi_1(x)b_1(x) + \beta_1(x)\phi_0(x)b_2(x)$. ## References - [Wikipedia entry](https://en.wikipedia.org/wiki/Clenshaw_algorithm) - A. Smoktunowicz, *Backward Stability of Clenshaw's algorithm*, Bit Numerical Computing 42, pp. 600-610 (2002), [doi:](https://doi.org/10.1023/A:1022001931526)