Relation between Chebyshev Interpolation and Expansion

Question

I am seeking connections between pointwise Lagrange interpolation (using Chebyshev-Gauss nodes) and generalized series approximation approach using Chebyshev polynomials.

---

Pointwise Lagrange interpolation

Given a function $f \in C^0([-1,1])$ and a grid of $n+1$ nodes $X = (x_i)_{i = 0}^n$ on $[-1,1]$ we can construct the interpolating polynomial $\Pi^{\ \small{X}}_{\ n} f \in \mathbb{P}_n$ in the following way: $$\Pi^{\ \small{X}}_{\ n} f := \sum_{k = 0}^n f(x_k) L_k(x)$$ with $L_k$ the $k$-th Lagrange polynomial: $L_k(x) := \prod_{j = 0, j \not = k}^n \frac{x - x_j}{x_k - x_j} $

It's easy to check that the operator $\Pi^{\ \small{X}}_{\ n} : C^0([-1,1]) \to \mathbb{P}_n, \ f \mapsto \Pi^{\ \small{X}}_{\ n} f$ is a projection, i.e. $(\Pi^{\ \small{X}}_{\ n})^2 = \Pi^{\ \small{X}}_{\ n}$ and $\Pi^{\ \small{X}}_{\ n}|_{\mathbb{P}_n} = \mathrm{id}_{\mathbb{P}_n}$.

In order to achieve good convergence and to avoid Runge phenomenon, we can choose Chebyshev-Gauss (CG) grid (i.e. zeros of Chebyshev polynomials) getting the interpolating polynomial: $\Pi^{\ \small{CG}}_{\ n} f$. We can make also another choice and take Chebyshev-Gauss-Lobatto grid (CGL or simply GL) obtaining $\Pi^{\ \small{GL}}_{\ n} f$

---

Chebyshev Expansion

In a more abstract framework, we can start by considering the space $L^2_{\small w}([-1,1])$ with the following inner product $(f,g)_w := \int_{-1}^1 f(x)g(x)w(x)dx$. Then , choosing $w(x) = 1/\sqrt{1 - x^2}$, we obtain the Chebyshev orthonogonal basis $\{T_k\}_{k\ge0}$ where $T_k$ is the $k$-th Chebyshev polynomial.

We can write:$$f(x) = \sum_{k=0}^\infty \hat{f}_k T_k(x) \quad \forall x \in [-1,1]$$ with $\hat{f}_k = (f,T_k)_w/(T_k,T_k)_w$

Moreover we can truncate the series at $n$ and obtain a projection of $f$ onto $\mathbb{P}_n$: $$S_{\ n} f := \sum_{k=0}^n \hat{f}_k T_k$$

---

Connections?

My question is this: is possible to find coefficients $\hat{f}_k$ such that: $$ \Pi^{\ \small{CG}}_{\ n} f = S_{\ n} f = \sum_{k=0}^n \hat{f}_k T_k$$ or $$ \Pi^{\ \small{GL}}_{\ n} f = S_{\ n} f = \sum_{k=0}^n \hat{f}_k T_k$$

Furthermore I know that we can approximate coefficients $\hat{f}_k$ using a discrete scalar product i.e. approximating the integral with interpolating polynomial but It seems a closed loop...

Can anyone help me?

Note: I originally posted this question on math.se but didn't receive any answer (also starting a bounty). I hope this question can be appropriate for this site, I'm sorry in advance if this is not "research level" math.

Answer 1

There is an excellent explanation of this in Chapter 4 of L. N. Trefethen's Approximation Theory and Approximation Practice (henceforth ATAP; the first 6 chapters are available for free online). I will try to summarize it in your notation, but I recommend reading his explanation.

Chebyshev interpolation

Interpolation at the Chebyshev points gives your $\Pi^{CG}_n f$, which can also be written in terms of the first $n$ Chebyshev polynomials:

$$\Pi^{CG}_n f = \sum_{k=0}^n c_k T_k(x).$$

The question then becomes:

How are the coefficients $c_k$ of the degree-$n$ Chebyshev interpolant related to the coefficients $\hat{f}_k$ of the infinite Chebyshev series?

Aliasing

It turns out that on the Chebyshev grid with $n+1$ points, the following Chebyshev polynomials all take exactly the same values:

$$T_{2jn\pm m}(x), \ \ \ \ j = 0, 1, 2 \dots$$

The above statement is valid as long as $0\le m \le n$ and where the subscript is positive (of course). See Thm. 4.1 of ATAP. Thus each $T_k$ for $k > n$ is "aliased" to appear like some corresponding $T_k$ with $k\le n$.

Relation between the Chebyshev interpolant and the Chebyshev series

Once you know about aliasing, the connection between the coefficients $c_k$ and $\hat{f}_k$ is immediate. Since the Chebyshev interpolant and the infinite Chebyshev series must be equal at the Chebyshev points, we have

$$ \sum_{k=0}^n c_k T_k(x_j) = \sum_{k=0}^\infty \hat{f}_k T_k(x_j), $$ where $x_j$ is any of the Chebyshev points. But from the aliasing result, we know that each term with $k>n$ in the right-hand-side sum can be rewritten in terms of $T_k(x_j)$ for some $k\le n$. The result is Thm. 4.2 of ATAP, which gives the formulae (for the degree-$n$ interpolant coefficients) \begin{align} c_0 - f_0 & = \sum_{j=1}^\infty f_{2jn} \\ c_n - f_n & = \sum_{j=1}^\infty f_{(2j+1)n} \\ c_k - f_k & = \sum_{j=1}^\infty (f_{2jn+k} + f_{2jn-k}) & 1\le k \le n-1. \end{align} So the difference between the coefficients of the Chebyshev interpolant and the Chebyshev projection is given by certain sums of coefficients of the remainder of the Chebyshev series.

One of the major themes of ATAP is that the Chebyshev interpolant is almost as good as the Chebyshev projection for approximation purposes; see Theorems 7.2, 8.2, and 16.1 therein. The great virtue of the interpolant is that it is much easier to compute.