Minimum degree of a polynomial passing through points

Question

If $P(x)$ is a polynomial such that $P(a_{1})=b_{1}, P(a_{2})=b_{2}, \ldots , P(a_{k})=b_{k}$, how can I find the polynomial which has minimum degree and for whom the relations above are true?

Answer 1

Given $k$ distinct points, from the fundamental theorem of algebra, we can find a polynomial of degree at most $k-1$ passing through these $k$ points. This polynomial is called the Lagrange polynomial and this interpolation is known as Lagrange interpolation.

The Lagrange polynomial is found as follows: First compute $$L_j(a)\:=\:\prod_{i \neq j}{a-a_i\over a_j-a_i}\,.$$ Note that $L_j(x)$ is a polynomial in $a$ of degree $k-1$ and has the property that $L_j(a_i) = \delta_{ij}$, where $\delta_{ij}$ is the Kronecker delta. Now, the Lagrange polynomial you are after is given by $$L(a) = \sum_{j=1}^k b_j L_j(a)$$ The degree of this interpolating polynomial is nothing but the rank of the following matrix $$\begin{bmatrix}1 & a_1 & a_1^2 & \cdots a_1^{k-1} & b_1\\ 1 & a_2 & a_2^2 & \cdots a_2^{k-1} & b_2\\ 1 & a_3 & a_3^2 & \cdots a_3^{k-1} & b_3\\ \vdots & \vdots & \vdots & \ddots \vdots & \vdots\\ 1 & a_k & a_k^2 & \cdots a_k^{k-1} & b_k\\\end{bmatrix}$$

Answer 2

Naively, you could construct the interpolating polynomial through the first $t$ points, and see if it passes through the others. If not, increase $t$ by one. By the time $t=k$ you will definitely have one.

Answer 3

You can use Lagrange interpolation to find the polynomial. It will have degree at most $k-1$ It will take some work to see if the degree is less.