find the linear interpolation polynomial $f_{p}$ of degree $m>n$ of a polynomial $p(x)$ of degree $n$

Question

I want to prove, or at least understand, the following statement from our lecture:

If I have a polynomial $p(x)$ of degree $n$, and want to find the linear interpolation polynomial $f_{p}(x)$ of degree $m \ge n$, why is it obvious that $f_{p}=p$?

We constructed the linear interpolation polynomial with the Vandermonde Matrix or Lagrange polynomials.

It is just not so obvious for me. Can somebody explain it?

Would be great. :)

Answer 1

Your question has some unclear points, but I think I know what you mean. This answer will explain the math behind interpolation, which should help to get the intuition what happens when interpolating polynomials.

About the Lagrange multiplicators. You most likely mean Lagrange polynomials, as Lagrange Multiplicators or Lagrange multiplier are something different.

And you probably mean "interpolation polyonmial of degree $m$" and not linear interpolation polynomial of degree $m$.

---

Lets denote the space with polynomials of degree $m$ as $P_m$.

The Lagrange-Interpolation-Problem is the task to find a polynomial $\tilde{p}∈P_m$ to $m+1$ pairwise different nodal points $x_0,…,x_m∈ℝ$, with nodal values $y_0,…,y…m$, such that: $$\tilde{p}(x_k)=y_k,\qquad k=0,…,m.$$

That problem has a unique solution. That is, because the monomial basis $\{1,x,x²,…,x^m\}$ has $m+1$ basis elements (vectors). We know, that this basis allows us to write each polynomial like: $$\tilde{p}=\sum_{j=0}^m a_jx^j$$ So we simply need $m+1$ informations to uniquely determine the $m+1$ coefficients. And these are given by: $$\tilde{p}(x_k)=\sum_{j=0}^m a_jx_k^j=y_k \qquad k=0,…,m \label{*}\tag{*}$$

---

In your case the function values are given by a polynomial $p$ of degree $n≤m$. Let that polynomial be $$p=\sum_{j=1}^ma_ix^i.$$ We can define $$\tilde{p}(x)=\sum_{i=0}^nb_ix^i$$ with $b_i=a_i$ for $i≤n$, and $b_i = 0$ for $n<i≤m$.

This polynomial $\tilde{p}$ is in the space $P_n$ and also fulfils $$\tilde{p}(x_k)=y_k:=p(x_k),\qquad k=0,…,m.$$ Therefore, we just found the unique solution of the Lagrange-Interpolation-Problem.

---

As we know from linear algebra, it is possible to write a vector in one basis or in another basis.

So we can write and solve equation\eqref{*} in two ways: \begin{align*} y_k&=\tilde{p}^M(x_k)=\sum_{j=0}^m a_jx_k^j\qquad &k=0,…,m \\ y_k&=\tilde{p}^L(x_k)=\sum_{j=0}^m α_jL_j(x_k)\qquad &k=0,…,m \end{align*}

The first one is the representation in the monomial Basis, the second one using the Lagrange basis $$L_j(x):=\prod_{0≤k≤m \\ k\neq j} \frac{x-x_k}{x_j-x_k}.$$
If you solve that equation system in the monomial basis, you will get the Vandermonde matrix, as you have done in the lecture. The idea of the Lagrange basis was to be able to easily compute the coefficients. But that means, by "preservation of work", that it is hard to calculate the basis vectors.

Nevertheless, both polynomials are the same object only written in a different basis.

So it holds true, that both polynomials have to be the polynomial $\tilde{p}$ that we created above: $$\tilde{p}^M(x)=\tilde{p}^L(x)=\tilde{p}(x).$$