8
$\begingroup$

The naive summation of a Chebyshev series \begin{align*} f(x) = \frac{c_0}{2} + \sum_{k=1}^{n-1} c_{k}T_{k}(x) \end{align*} which employs the three-term recurrence for evaluation of the Chebyshev polynomials is known to be numerically unstable near $x=\pm 1$. For this reason, Clenshaw presented an algorithm which avoids this instability; see Clenshaw's original work and an exposition in Algorithm 3.1 of Numerical Methods for Special Functions.

Is there literature which presents a numerically stable method for evaluating the derivative of a Chebyshev series, perhaps using an analogy to the Clenshaw recurrence presented above? Or is the naive method stable?

$\endgroup$
1
  • $\begingroup$ A useful alternative to the answer you got is to derive the Chebyshev coefficients of the derivative from the coefficients of the original function. $\endgroup$
    – J. M.
    Sep 18, 2017 at 7:50

1 Answer 1

13
$\begingroup$

You can just take Clenshaw's recurrence $$ u_k(x) = 2xu_{k+1}(x)-u_{k+2}(x)+\color{red}{a_k},\\ f(x) = x u_1(x)-u_2(x)+\color{red}{a_0} $$ and differentiate it directly: $$ u_k'(x) = 2xu_{k+1}'(x)-u_{k+2}'(x) + \color{blue}{2u_{k+1}(x)},\\ f'(x) = x u_1'(x)-u_2'(x) + \color{blue}{u_1(x)}. $$ Note that now the derivatives of partial sums, $u_k'(x)$ satisfy exactly the same recurrence, except that the coefficients $a_k$ are replaced by $2u_{k+1}(x)$. This means that the series for the derivative can be written as the Chebyshev series $$ f'(x) = \tfrac12 u_1(x) + \sum_{k\geq1} 2u_{k+1}(x)T_k(x). $$

Since Clenshaw's recurrence evaluates Chebyshev series accurately, it will evaluate the Chebyshev series with coefficients $2u_{k+1}(x)$ accurately too, and it doesn't need to be analyzed separately. A very similar thing happens when differentiating polynomials using Horner's rule.

$\endgroup$
3
  • $\begingroup$ This is effectively a manual application of automatic differentiation on the loop for Clenshaw's recurrence. It should be noted that this method is easily extensible if one wants second, third, ... $n$-th order derivatives. $\endgroup$
    – J. M.
    Sep 18, 2017 at 7:51
  • $\begingroup$ @J.M. Sure, but manual application of automatic differentiation is just plain old "differentiation" ;-) $\endgroup$
    – Kirill
    Sep 18, 2017 at 15:24
  • $\begingroup$ This answer is so good; I keep coming back to it for insights. As with most things, everything is trivial after you know it, but how many people know this? It definitely deserves to be more widely known. $\endgroup$
    – user14717
    Jan 11, 2022 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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