Clenshaw Recurrence Formula

The downward Clenshaw recurrence formula evaluates a sum of products of indexed Coefficients by functions which obey a recurrence relation. If

$$f(x)=\sum_{k=0}^N c_kF_k(x)$$

and

$$F_{n+1}(x)=\alpha(n,x)F_n(x)+\beta(n,x)F_{n-1}(x),$$

where the $c_k\/$s are known, then define

$$y_{N+2} = y_{N+1} = 0$$

$$y_k = \alpha(k,x)y_{k+1}+\beta(k+1,x)y_{k+2}+c_k$$

for $k=N,N-1,\ldots$ and solve backwards to obtain $y_2$ and $y_1$.

$$c_k=y_k-\alpha(k,x)y_{k+1}-\beta(k+1,x)y_{k+2}$$

$$f(x) = \sum_{k=0}^N c_kF_k(x)$$

$$= c_0F_0(x)+[y_1-\alpha(1,x)y_2-\beta(2,x)y_3]F_1(x)$$

$$\phantom{=} \mathop{+}[y_2-\alpha(2,x)y_3-\beta(3,x)y_4]F_2(x)$$

$$\phantom{=} \mathop{+}[y_3-\alpha(3,x)y_4-\beta(4,x)y_5]F_3(x)$$

$$\phantom{=} \mathop{+}[y_4-\alpha(4,x)y_5-\beta(5,x)y_6]F_4(x)+\ldots$$

$$= c_0F_0(x)+y_1F_1(x)+y_2[F_2(x)-\alpha(1,x)F_1(x)]$$

$$\phantom{=} \mathop{+} y_3[F_3(x)-\alpha(2,x)F_2(x)-\beta(2,x)]$$

$$\phantom{=} \mathop{+}y_4[F_4(x)-\alpha(3,x)F_3(x)-\beta(3,x)]+\ldots$$

$$= c_0F_0(x)+y_2[\{\alpha(1,x)F_1(x)+\beta(1,x)F_0(x)\}$$

$$\phantom{=} -\alpha(1,x)F_1(x)]+y_1F_1(x)$$

$$= c_0F_0(x)+y_1F_1(x)+\beta(1,x)F_0(x)y_2.$$

The upward Clenshaw recurrence formula is

$$y_{-2} = y_{-1} = 0$$

$$y_k = {1\over\beta(k+1,x)} [y_{k-2}-\alpha(k,x)y_{k-1}-c_k]$$

for $k=0,1,\ldots,N-1$.

$$f(x)=c_NF_N(x)-\beta(N,x)F_{N-1}(x)y_{N-1}-F_N(x)y_{N-2}.$$

References

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Recurrence Relations and Clenshaw's Recurrence Formula.'' §5.5 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 172-178, 1992.