3
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user123 Mar 19 '16 at 14:57
  • $\begingroup$ @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. $\endgroup$ – Kirill Mar 19 '16 at 15:26
  • $\begingroup$ @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. $\endgroup$ – Kirill Mar 19 '16 at 15:28
  • $\begingroup$ 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. $\endgroup$ – user123 Mar 19 '16 at 16:48
  • $\begingroup$ @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. $\endgroup$ – Kirill Mar 19 '16 at 17:23
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.