Thursday, 16 June 2011

algorithms - On Clenshaw's summation formula

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_{n+2}=y_{n+1}=0$



$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.

No comments:

Post a Comment