When one has a finite sum of the form

$S=\sum_{k=0}^{n}{c_k F_k(x)}$

where $F_k(x)$ satisfies a two-term recurrence relation

$F_{k+1}(x)=\alpha_k F_k(x)+\beta_k F_{k-1}(x)$

the standard algorithm used for computing $S$ is Clenshaw summation:


$y_k=\alpha_k y_{k+1}+\beta_{k+1}y_{k+2}+c_k\; ; \;k=n\;\mathrm{to}\;1\;\mathrm{step}\;-1$

$S=y_1F_1(x)+(\beta_1 y_2+c_0)F_0(x)$

I am also very familiar with the concept of "minimal" and "dominant" solutions of a two-term recurrence; to review, the dominant solution is the solution most stably propagated when the two-term recurrence is run in the forward direction, while the minimal solution is the solution that is stably computed when the recurrence is run backwards. As an example, for the recurrence relation of the Bessel functions, $J_n(x)$, the function of the first kind, is the minimal solution while $Y_n(x)$, the other solution to the Bessel ODE, is the dominant solution to the two-term recurrence.

Mystifying to me, however, is this remark given in the book "Numerical Recipes" without justification of any sort:

"...Clenshaw's recurrence is always stable, independent of whether the recurrence for the functions... is stable in the upward or downward direction."

My question now, is why would the stability properties of $F_k$ (i.e. its being minimal or dominant) not spoil the recurrence, if this is true? If not, I would be interested in seeing a counterexample.


1 Answer 1


I think the answer is quite technical, but nevertheless contained for the specific case of Chebyshev polynomials in the original paper by Clenshaw: http://www.ams.org/journals/mcom/1955-09-051/S0025-5718-1955-0071856-0/S0025-5718-1955-0071856-0.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.