An algorithm for fast discrete transformation for Fourier sums over Sobolev orthogonal polynomials generated by Chebyshev polynomials of the first kind

We consider the problem of numerical realization of linear combinations $S_N(x) =\sum\nolimits_{k=0}^{N-1}p_kT_{1,k+1}(x)$, where $T_{1,n}(x)$ $(n=0,1,\ldots)$ are Sobolev orthogonal polynomials generated by Chebyshev polynomials of of the first kind $T_{0} = 1 / \sqrt{2}$, $T_{n}(x)=\cos( n\arccos x)$ ($n \in \mathbb{N}$) as follows $T_{1,0}=1$, $T_{1,n+1}(x) =\int_{-1}^x T_{n}(t)dt$ $(n=1,\ldots)$. To solve this problem on the grid $x_j=\cos\frac{(2j+1)\pi}{2M}$ $(0\le j\le M-1)$ a number transformations of expression $S_N(x)$ are applied, which allows to reduce the problem under consideration to the application of a fast discrete Fourier transform. The corresponding algorithm and program in the language C# have been developed. The numerical experiments with using this program show that algorithm based on fast transform is significantly faster than method based on direct calculation of $S_N(x)$ with using explicit formulas for $T_{1,n}(x)$.