Clenshaw algorithm

Remarks

Write $a_k = b_k - \alpha_k b_{k+1} - \beta_{k+1} b_{k+2}$ for $1 \le k \le n$ and substitute in $\sum_{k \ge 1} a_k \phi_k$. After collecting terms, the coefficient of $b_j$ for $j \ge 3$ is $\phi_j - \alpha_{j-1}\phi_{j-1} - \beta_{j-1}\phi_{j-2} = 0$, and the coefficient of $b_2$ is $\phi_2 - \alpha_1 \phi_1 = \beta_1 \phi_0$; only the terms in the formula remain. For the Chebyshev polynomials $T_k$ one has $\phi_0 = 1$, $\phi_1 = x$, $\alpha_k = 2x$ and $\beta_k = -1$, so $\sum_{k=0}^n a_k T_k(x) = a_0 + x b_1 - b_2$. Check with $n = 2$: $b_2 = a_2$, $b_1 = a_1 + 2x a_2$, and $a_0 + x(a_1 + 2x a_2) - a_2 = a_0 + a_1 x + a_2(2x^2 - 1)$, which is $a_0 T_0 + a_1 T_1 + a_2 T_2$. For the monomials $\phi_k = x^k$, with $\alpha_k = x$ and $\beta_k = 0$, the algorithm is Horner's method. The cost is $O(n)$ operations, and the values $\phi_k(x)$ for $k \ge 2$ are never formed.

Going deeper

For a student

The algorithm is the standard way to evaluate a truncated Chebyshev series, for instance in function libraries and in Chebyshev spectral methods. It works for any family defined by a three-term recurrence, so for all classical orthogonal polynomials and also for some special functions such as Bessel functions. The backward recurrence is the transpose of the forward one, which explains why only $b_1$ and $b_2$ appear in the result. Its rounding error behaviour is good for Chebyshev series on $[-1, 1]$, though near the endpoints $\pm 1$ the errors can be amplified.