A Chebychev-Vandermonde solver (Q1194520)

The representation of an interpolating polynomial in terms of Chebyshev polynomials can be computed in \(O(n^ 2)\) operations. \textit{Å. Björck} and \textit{V. Pereyra} [Math. Comput. 24, 893-903 (1971; Zbl 0221.65054)] have proposed to determine first the interpolating polynomial by the Newton scheme and to bring it into the desired form in a second step. The accuracy of the result depends on the ordering of the nodes \(x_ j\). Therefore, the authors propose another procedure. First the Lagrangian form of the polynomial is determined. Having this, the polynomial may be evaluated at the extremal points of \(T_ n\). Finally, the coefficients are computed by a recursion formula which applies to the interpolation problem for the special nodes.