# Compute the correction of a Chebyshev approximation using the Clenshaw summation formula

Assume you have a Chebyshev approximation of a function $$f(x)$$ evaluated using the Clenshaw summation method, up to polynomial order $$N$$:

$$f(x) = \sum_{k=0}^{N-1} a_k T_k(x) = (a_0 - y_2)T_0(x) + y_1 T_1(x)$$

where

$$T_N = 2x \cdot T_{N-1} - T_{N-2}$$

and

\begin{aligned} y_{N+1} &= 0\\ y_{N} &= 0 \\ y_{N-1} &= a_{N-1} - y_{N+1} + 2x \cdot y_N \\ \vdots \\ y_1 &= a_1 - y_3 + 2x \cdot y_2 \end{aligned}

I would like add higher order terms to $$f(x)$$, for example by computing a correction up to an order $$\tilde{N} > N$$ given by an expression

$$\tilde{f}(x) = \sum_{k=N}^{\tilde{N}-1}a_k T_k(x) = (a_N - y_{N+2})T_N + y_{N+1} T_{N+1}.$$

The magnitudes $$y_{N+2}$$ and $$y_{N+1}$$ can be computed with the Clenshaw recurrence using just the $$a_k$$ for $$k=N+1, \ldots, \tilde{N}-1$$, but the polynomials $$T_N$$ and $$T_{N+1}$$ would have to be evaluated using the recurrence relation from $$T_0$$ and $$T_1$$. For my use case, I can only evaluate linear combinations of $$x$$ so I cannot use the analytical expression $$T_N(x) = \cos(N \arccos(x))$$.

I wonder if I could rewrite this expression using the previous solution $$f(x)$$, such as in terms of $$T_0, T_1$$, the old $$y_k$$, and the new $$a_k$$ for $$k = N, \ldots, \tilde{N}-1$$.

I have tried solving the recurrence relation by hand as

\begin{aligned} \tilde{f}(x) &= (a_N - y_{N+2})T_N + y_{N+1}T_{N+1} \\ &= (a_N - y_{N+2} + 2x\cdot y_{N+1})T_N - y_{N+1}T_{N-1} \\ &= y_N(2x\cdot T_{N-1} - T_{N-2}) - y_{N+1} T_{N-1} \\ &= (2x \cdot y_N - y_{N+1}) T_{N-1} - y_N T_{N-2} \\ &= \left[ (a_{N-2} - y_N)T_{N-2} + y_{N-1} T_{N-1}\right] - (a_{N-2}T_{N-2} + a_{N-1}T_{N-1}) \end{aligned}

but in the end I am unable to reduce $$T_N$$ and $$T_{N+1}$$ as I get as a remainder precisely the original approximation $$\sum_{k=0}^{N-1}c_k T_k$$.

I am confused because this is very straightforward to do using the polynomial evaluation, as conserving the previously computed $$T_{N-1}(x)$$ allows you to compute $$\tilde{f}(x)$$ for higher order terms without having to re-evaluate the whole series. Given that the terms $$y_k$$ are constructed iteratively from the polynomials up to $$T_{N-1}$$, I would expect that they could be used to compute $$T_N$$.

Any hint (or solution) would be appreciated.

Use $$y_{N+1} = a_{N+1} - y_{N+3} + 2x y_{N+2}$$ instead of substituting $$y_{N+2}$$ in the first term. Because you need to get larger $$N$$ after expansion.
Then \begin{aligned} \tilde f &= a_N T_N - y_{N+2} T_N + a_{N+1} T_{N+1} - y_{N+3} T_{N+1} + 2x y_{N+2} T_{N+1} \\&= a_N T_N +a_{N+1}T_{N+1} + (a_{N+1}- y_{N+3})T_{N+1} + y_{N+2} T_{N+2} \end{aligned}