Polynomial Interpolation

Definition

The interpolation of a given bivariate data set by the polynomial of lowest possible degree that passes through the points of the dataset.

Examples

Find the cubic polynomial $f(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3$ passes through the four points $(1,3),(2,-2),(3,-5),(4,0)$.

Set the system equation for the polynomial $\left[\begin{array}{cccc}1& x_1& x_1^2& x_1^3\\ 1& x_2& x_2^2& x_2^3\\ 1& x_3& x_3^2& x_3^3\\ 1& x_4& x_4^2& x_4^3\end{array}\right]=\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\end{array}\right]=\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}\right]$ substitute the given points to the system equation and make the augmented matrix $\left[\begin{array}{cccccc}1& 1& 1& 1& & 3\\ 1& 2& 4& 8& & -2\\ 1& 3& 9& 27& & -5\\ 1& 4& 16& 64& & 0\end{array}\right]$ solve the system of equation using the gauss elimination $\left[\begin{array}{cccccc}1& 1& 1& 1& & 3\\ 1& 2& 4& 8& & -2\\ 1& 3& 9& 27& & -5\\ 1& 4& 16& 64& & 0\end{array}\right]\stackrel{\text{reduced form}}{\to }\left[\begin{array}{cccccc}1& 0& 0& 0& & 4\\ 0& 1& 0& 0& & 3\\ 0& 0& 1& 0& & -5\\ 0& 0& 0& 1& & 1\end{array}\right]$ Then, $a_0=4,a_1=3,a_2=-5,a_3=1$. $\therefore f(x)=4+3x-5x^2+x^3$

Facts

Interpolation theorem

For any $n+1$ bivariate data points $(x_0,y_0),\dots ,(x_n,y_n)\in {\mathbb{R}}^2$, where no two $x_i$ are the same, there exists a unique polynomial $p(x)$ of degree at most $n$ that interpolates these points. $p(x_0)=y_0,\dots ,p(x_n)-y_n$