TOPICS
Search

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)^Nc_kF_k(x)
(1)

and

F_(n+1)(x)=alpha(n,x)F_n(x)+beta(n,x)F_(n-1)(x),
(2)

where the c_ks are known, then define

y_(N+2)=y_(N+1)=0
(3)
y_k=alpha(k,x)y_(k+1)+beta(k+1,x)y_(k+2)+c_k
(4)

for k=N,N-1,... 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)
(5)
f(x)=sum_(k=0)^(N)c_kF_k(x)
(6)
=c_0F_0(x)+[y_1-alpha(1,x)y_2-beta(2,x)y_3]F_1(x)+[y_2-alpha(2,x)y_3-beta(3,x)y_4]F_2(x)+[y_3-alpha(3,x)y_4-beta(4,x)y_5]F_3(x)+[y_4-alpha(4,x)y_5-beta(5,x)y_6]F_4(x)+...
(7)
=c_0F_0(x)+y_1F_1(x)+y_2[F_2(x)-alpha(1,x)F_1(x)]+y_3[F_3(x)-alpha(2,x)F_2(x)-F_1(x)beta(2,x)]+y_4[F_4(x)-alpha(3,x)F_3(x)-F_2(x)beta(3,x)]+...
(8)
=c_0F_0(x)+y_2[{alpha(1,x)F_1(x)+beta(1,x)F_0(x)}-alpha(1,x)F_1(x)]+y_1F_1(x)
(9)
=c_0F_0(x)+y_1F_1(x)+beta(1,x)F_0(x)y_2.
(10)

The upward Clenshaw recurrence formula is

y_(-2)=y_(-1)=0
(11)
y_k=1/(beta(k+1,x))[y_(k-2)-alpha(k,x)y_(k-1)-c_k]
(12)

for k=0,1,...,N-1.

f(x)=c_NF_N(x)-beta(N,x)F_(N-1)(x)y_(N-1)-F_N(x)y_(N-2).
(13)

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Clenshaw Recurrence Formula

Cite this as:

Weisstein, Eric W. "Clenshaw Recurrence Formula." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ClenshawRecurrenceFormula.html

Subject classifications