Lagrange interpolation with multiplicities

343 Views Asked by At

I was wondering if it were possible to do Lagrange interpolation with multiplicities. Lagrange interpolation gives us a polynomial that obtains certain values on a given set of points. More precisely, given $k$ pairs $(a_i,y_i)\in \mathbb{F}^2$ such that the $a_i$ are pairwise different, there is a unique polynomial $f$ of degree $\leq k-1$ such that $f(a_i)=y_i$. One can construct it by considering the following polynomials $$ Q_i(x) = \prod_{j=1\\j\not=i}^k \frac{x-a_j}{a_i-a_j} \text{ for } i=1,\ldots,k. $$ Note that $Q_i(a_j)= \delta_{ij}$. Now we can define $f$ as $$ f(x)=\sum_{i=1}^k y_i Q_i(x). $$ The uniqueness of $f$ follows from the fundamental theorem of algebra.

I was wondering if this procedure can be generalized to the case where the $a_i$ are not pairwise distinct. Essentially this means that $f(x)$ ramifies around $a_i$ with some multiplicity at least $m_i\geq1$. This is equivalent to saying $f(a_i)=y_i$ and $f^{(1)}(a_i)=\cdots=f^{(m_i-1)}(a_i)=0$.

So what we want is the following : given $k$ triples $(a_i,y_i,m_i)\in \mathbb{F}^2\times \mathbb{N}_+$ with $a_i$ pairwise distinct, find a polynomial $f(x)$ so that $f(a_i)=y_i$ and $f^{(1)}(a_i)=\cdots=f^{(m_i-1)}(a_i)=0$, or equivalently $f(a_i)-y_i= \psi_i(x)(x-a_i)^{m_i}$ for some polynomial $\psi_i(x)$, and for all $i=1,\ldots,k$.

First thing to note is that this breaks the degree and uniqueness constraints. For example if $k=1$, $(a,y,m)=(0,0,2)$ we need to have a second degree polynomial, and it is not unique - both $x^2$ and $2x^2$ satisfy the constraints.

In my opinion we should always be able to find a polynomial of degree $\leq \sum_1^k m_i$, but I didn't prove this. Also, what are the best results we can get on uniqueness?

PS. I just thought of another question. What if we ask that the multiplcity of $f(x)$ in $a_i$ is exactly $m_i$? Now even the case with all distinct points will require degree higher than $k-1$ as we can see from the following triple $(0,0,1),(1,1,1),(-1,1,1)$ having the unique degree two solution $f(x)=x^2$ that has multiplicity 2 in 0.

1

There are 1 best solutions below

0
On BEST ANSWER

Then you pass from Lagrange interpolation to Hermite interpolation