# Interpolation with the roots of orthogonal polynomials & Spectral expansion

I'm a bit confused about the relationships between these two approximation methods mentioned in the title.

• Does this kind of interpolation also belongs to the field of spectral methods?
• Are the Lagrange interpolants we get from using the roots of orthogonal polynomials also orthogonal?
• It's likely to get mixed with these two methods, could someone please clarify their differences?

Edit:
Let me use the Chebyshev polynomials as an example:
(1) Using the Chebyshev polynomials as basis functions, then $f(x)$ is approximated as \begin{equation} f(x)\simeq\sum\limits_{n=0}^Na_nT_n (x) \end{equation}

(2) Interpolating at the $(N+1)$ roots, $x_0, x_1, ..., x_k,...,x_N$, of the Chebyshev polynomial $T_{N+1}(x)$, then the interpolation of $f(x)$ is
\begin{equation} f(x)\simeq P_N(x)=\sum\limits_{k=0}^N f(x_k)L_k(x) \end{equation} where $L_k(x)$ is the interpolant function at $x=x_k$.

I hope I understood the question correctly. They try to compute exactly the same thing, so they really are equivalent. I'll use Chebyshev polynomials because they are easy to analyze.

Given a function $f(x)$ on $[-1,1]$, the spectral interpolant is the truncation of \begin{aligned} f(x) &= \sum_{n\geq0} \bar a_n T_n(x), \\ \bar a_n &= \frac{1+[n>0]}{\pi}\int_{-1}^1 f(x)T_n(x)\frac{dx}{\sqrt{1-x^2}} \\&= \frac{1+[n>0]}{\pi} \int_{0}^\pi f(\cos\theta)\cos(n\theta)\,\mathrm{d}\theta. \end{aligned} The $N$-th degree Lagrange interpolant, using the roots of $T_{N+1}(x)$ is given by $$a_n = \frac{1+[n>0]}{N+1}\sum_{k=0}^N f(x_k) T_n(x_k), \qquad x_k = \cos\frac{\pi (k+\frac12)}{N+1}.$$ This uses the fact that $\sum_{k=0}^N T_m(x_k)T_n(x_k)$ is zero when $m\neq n$, $m,n\leq N$.

The formula for $a_n$ is nothing but the discrete cosine transform (type-II) applied to the function values at $x_k$, due to $T_n(x_k) = \cos \pi n(k+\frac12)/(N+1)$.

These are not, strictly speaking, the same, though.

The formula for $a_n$ is a trapezoidal rule approximation to the Fourier cosine integral in the formula for the exact coefficients $\bar a_n$. The trapezoidal rule is known to be exponentially accurate for smooth periodic functions (Trefethen-Weideman 2014), which $f(\cos\theta)$ is. Since for a spectral interpolant you would still have to evaluate the integral somehow, the Lagrange interpolant with the roots as nodes is just a way of evaluating that integral.

I tried to compute the exact difference between $a_n$ and $\bar a_n$, by expanding the sum for $a_n$ using the full series for $f$, and using the identity $$\sum_{k=0}^{N} \cos(j\theta_k)\cos(n\theta_k) = \frac{N+1}{2}\big( [N+1\setminus j-n](-1)^{(j-n)N/(N+1)} + [N+1\setminus j+n](-1)^{(j+n)N/(N+1)}\big),$$ and for a complex-differentiable function $g(\theta)=f(\cos\theta)$ that is holomorphic in the region of the complex plane $|\Im \theta|<\alpha$, heuristically the error appears to be something on the order $$a_n - \bar a_n \sim |\bar a_{N+1-n}| \lesssim e^{-\alpha(N+1-n)}.$$ So for smooth functions this error decays very quickly and becomes negligible, so the Lagrange and the spectral interpolants can be considered identical.

Edit. What is the relationship between $\sum a_nT_n(x)$ and $\sum f(x_k) \ell_k(x)$?

Let $a_n$ be defined as above, let $f_1(x) = \sum_{n=0}^{N} a_n T_n(x)$, and let $f_2(x) = \sum_{k=0}^N f(x_k) \ell_k(x)$, where $\ell_k(x) = \prod_{j\neq k} (x-x_j)/(x_k-x_j)$.

Both $f_1(x)$ and $f_2(x)$ are polynomials in $x$ of degree $N$, by construction.

Using the above definition of $a_n$, together with $$T_n(x_k) = \cos(n\theta_k), \qquad \theta_k = \pi(k+\tfrac12)/(N+1)$$ we can check that $f_1(x_k) = f(x_k)$, using the identity $$\sum_{n=0}^{N} \frac{1+[n>0]}{N+1} \cos(n\theta_j)\cos(n\theta_k) = [j=k].$$

Therefore $f_1(x)$ and $f_2(x)$ are (non-identically-zero) polynomials of degree $N$ that pass through the same $N+1$ points, and therefore are the same polynomial.

Using the form of the interpolating polynomial in terms of $a_n$ makes the relationship with the Chebyshev series of the function $f(x)$ clearer than the Lagrange interpolation form.

• Hi, @KIrill, Thank you so much for this detailed answer, but I am not quite clear about the second equation of $a_n$ you wrote and I can't see its connection with Lagrange interpolating function. Also I have added some edits to my question, could you please take a look at it and explain a bit? – user123 Mar 19 '16 at 14:57
• @David The Lagrange interpolant is a degree-$N$ polynomial, and so is $\sum_{n=0}^{N} a_n T_n(x)$ using the formula I wrote down in terms of $\sum_k f(x_k) T_n(x_k)$. They both perfectly match the function at $N+1$ points $x_k$, so (as degree-$N$ polynomials) they must be identical. See also Berrut-Trefethen (people.maths.ox.ac.uk/trefethen/barycentric.pdf) Again, I think what you're asking about is two ways of computing the same thing. – Kirill Mar 19 '16 at 15:26
• @David Also, I think you skipped a step: the "true" Chebyshev series would be computed through $\int_{-1}^1 f(x)T_n(x)(1-x^2)^{-1/2}\,\mathrm{d}x$, which is a full integral that needs to be evaluated somehow, which is why I thought your question was about the difference between $a_n$ and $\bar a_n$ (you don't make this distinction in your new edits, both using $a_n$). As I see it, a spectral method would be formulated in terms of the integrals, and then later approximated. I may have misunderstood you. – Kirill Mar 19 '16 at 15:28
• I'm sorry, but I still couldn't figure out where does your $a_n$ come from and what's its relationship with $L_n(x)$, not $T_n(x)&. I hope you still have patience on my dullness. – user123 Mar 19 '16 at 16:48 • @David It is a standard formula for computing Chebyshev series coefficients (e.g., equation 3.55 in siam.org/books/ot99/OT99SampleChapter.pdf and the discussion around it; also people.maths.ox.ac.uk/trefethen/ATAP/ATAPfirst6chapters.pdf). The polynomial it computes interpolates$f$at the$N+1$roots of$T_{N+1}$, so it must match the Lagrange interpolant. The relationship with$L_n$is that it is the same polynomial in$x$, but written in two different ways. I used it because it's much easier to analyze the formula in that form than in the Lagrange form. – Kirill Mar 19 '16 at 17:23 Thanks for Kirill's detailed answer, which clarifies all the confusion in my head. According to Kirill's answer and the materials he provided, now I want to generalize it a bit to common cases. Let us suppose$\{F_n(x)\}$is a set of orthogonal polynomials on$[-1,1]$, i.e., \begin{equation} \int_{-1}^1 F_m(x)F_n(x)w(x)dx=g_m\delta_{mn}, \end{equation} and$f(x)$is a continuous function we want to approximate in [-1,1]. (1) Using$\{F_n(x)\}$as basis functions, we get \begin{equation} f(x)=\sum_{n=0}^\infty a_nF_n(x), \end{equation} we approximate it with a truncated version, \begin{equation} f(x)=\sum_{n=0}^N a_nF_n(x), \end{equation} where$a_n$can be computed from \begin{equation} a_n=\frac{1}{g_n}\int_{-1}^1 f(x)F_n(x)w(x)dx. \end{equation} (2) We use the the$(n+1)$roots of$F_{N+1}(x)$to interpolate it: \begin{equation} f(x)\simeq P_N(x)=\sum_{n=0}^N a_nL_n(x). \end{equation} Here, since$P_N(x)$is an N-th degree polynomial, it can also be expressed using$F_n(x), n=1,2,...,N$, because$\{F_n(x)\}_{n=0}^N$is a base for the polynomial sapce$P_l, l\leq N$, so we get: \begin{equation} f(x)\simeq P_N(x)=\sum_{n=0}^N c_n F_n(x). \end{equation} also,$P_N(x_k)=f(x_k)$at the (N+1) interpolation points, which means \begin{equation} f(x_k)=\sum_{n=0}^N c_n F_n(x_k). \end{equation} multiply this equation by$w_k F_m(x_k)$on both sides and compute the sum on$x_k$, \begin{equation} \sum \limits_{k=0}^N f(x_k)F_m(x_k) w_k=\sum \limits_{k=0}^N w_k F_m(x_k) \sum_{n=0}^N c_n F_n(x_k)=\sum_{n=0}^N c_n \sum \limits_{k=0}^N F_m(x_k) F_n(x_k) w_k. \end{equation} Since$(m+n)\leq 2N$,$F_m(x)F_n(x)$is a polynomial of degree less than or equal to 2N. From the principle of Gauss quadrature, the following equation holds exactly: \begin{equation} \int_{-1}^1 F_m(x)F_n(x)w(x)dx=\sum \limits_{k=0}^N F_m(x_k) F_n(x_k) w_k=g_m\delta_{mn}, \end{equation} Therefore, \begin{equation} \sum \limits_{k=0}^N f(x_k)F_m(x_k) w_k=\sum_{n=0}^N c_n g_m\delta_{mn}=c_n g_n, \end{equation} thus, \begin{equation} c_n=\frac{1}{g_n}\sum \limits_{k=0}^N f(x_k)F_m(x_k) w_k, \end{equation} which, as Kirill has stated in the answer, is just a rectangular rule approximation of the intergral$a_n$listed above. In conclusion, the two forms to approximate$f(x)\$ are almost the same. Again, thanks to Kirill's answer.