Polynomial defined by the points it passes through

Question

Supposing I have a number of points $(x_i, y_i)$ where the $x_i$:s are all different, how would I go about creating a polynomial that passes through those points? Of course, if the $y_i$:s are all 0, I can just use the factor theorem, but I cannot seem to find an easy way for non-zero values of $y$.

Answer 1

One way could be solving a linear system of exation. In fact, if you have $k$ different points $(x_i,y_i)$, with $x_i$ different each other, you can costruct a polynomial: $$P(x)=a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+a_1x+a_0$$ In particular, you have to solve for $(a_{k-1},a_{k-2},\cdots,a_1,a_0)$ in the following system: $$\left\{\begin{matrix} a_{k-1}x_1^{k-1}+a_{k-2}x_1^{k-2}+\cdots+a_1x_{1}+a_0=y_1 \\ \vdots \\a_{k-1}x_k^{k-1}+a_{k-2}x_k^{k-2}+\cdots+a_1x_{k}+a_0=y_k \end{matrix}\right.$$

Answer 2

In theory, you can set up a linear system of equations for the coefficients. If there are $n$ different points, they define a polynomial of degree $n -1$. You end up tangled with Vandermonde's determinant, loads of fun that way.

In practice, you use the Lagrange form of the interpolating polynomial, or it's baricenyric form. Packages like e.g. SciPy, NumPy (Python) or libraries for numerical computation have this built-in.