Numerical Analysis/Vandermonde example

We'll find the interpolating polynomial passing through the three points $(1,-6)$, $(2,2)$, $(4,12)$, using the Vandermonde matrix.

For our polynomial, we'll take $(1,-6)=(x_0,y_0)$, $(2,2)=(x_1,y_1)$, and $(4,12)=(x_2,y_2)$.

Since we have 3 points, we can expect degree 2 polynomial.

So define our interpolating polynomial as:

$p(x)=a_2{x}^2+a_{1}x+a_0$.

So, to find the coefficients of our polynomial, we solve the system $p(x_i)=y_i$, $i\in \{0,1,2\}$.

$\left(\begin{array}{ccc}{x}_0^2& x_0& 1\\ x_1^2& x_1& 1\\ x_2^2& x_2& 1\end{array}\right)*\left(\begin{array}{c}{a}_2\\ a_1\\ a_0\end{array}\right)=\left(\begin{array}{c}{y}_0\\ y_1\\ y_2\end{array}\right)$

In order to solve the system, we will use an augmented matrix based on the Vandermonde matrix, and solve for the coefficients using Gaussian elimination. Substituting in our $x$ and $y$ values, our augmented matrix is:

$\left(\begin{array}{cccc}{1}^2& 1& 1& -6\\ 2^2& 2& 1& 2\\ 4^2& 4& 1& 12\end{array}\right)$

Then, using Gaussian elimination,

$\left(\begin{array}{cccc}1& 1& 1& -6\\ 4& 2& 1& 2\\ 16& 4& 1& 12\end{array}\right)\Rightarrow \left(\begin{array}{cccc}1& 1& 1& -6\\ 0& -2& -3& 26\\ 0& -12& -15& 108\end{array}\right)\Rightarrow \left(\begin{array}{cccc}1& 1& 1& -6\\ 0& -2& -3& 26\\ 0& 0& 3& -48\end{array}\right)\Rightarrow \left(\begin{array}{cccc}1& 1& 0& 10\\ 0& 2& 0& -22\\ 0& 0& 1& -16\end{array}\right)\Rightarrow \left(\begin{array}{cccc}1& 0& 0& -1\\ 0& 1& 0& 11\\ 0& 0& 1& -16\end{array}\right)$

Our coefficients are $a_2=-1$, $a_1=11$, and $a_0=-16$. So, the interpolating polynomial is

$p(x)=-x^2+11x-16$.

Adding a point

Now we add a point, $(3,-10)=(x_3,y_3)$, to our data set and find a new interpolation polynomial with this method.

Since we have 4 points, we will have degree 3 polynomial.

Thus our polynomial is $p(x)=a_3{x}^3+a_2{x}^2+a_{1}x+a_0$,

and we get the coefficients by solving the system $p(x_i)=y_i$.

Constructing our augmented matrix as before and using Gaussian elimination, we get:

$\left(\begin{array}{ccccc}{1}^3& 1^2& 1& 1& -6\\ 2^3& 2^2& 2& 1& 2\\ 4^3& 4^2& 4& 1& 12\\ 3^3& 3^2& 3& 1& -10\end{array}\right)\Rightarrow \left(\begin{array}{ccccc}1& 1& 1& 1& -6\\ 0& -4& -6& -7& 50\\ 0& -48& -60& -63& 396\\ 0& -18& -24& -26& 152\end{array}\right)\Rightarrow \left(\begin{array}{ccccc}1& 1& 1& 1& -6\\ 0& -4& -6& -7& 50\\ 0& 0& 12& 21& -204\\ 0& 0& 3& \frac{11}{12}& -73\end{array}\right)$

$\Rightarrow \left(\begin{array}{ccccc}1& 1& 1& 1& -6\\ 0& -4& -6& -7& 50\\ 0& 0& 12& 21& -204\\ 0& 0& 0& \frac{1}{4}& -22\end{array}\right)\Rightarrow \left(\begin{array}{ccccc}1& 1& 1& 0& 82\\ 0& -4& -6& 0& -566\\ 0& 0& 12& 0& 1644\\ 0& 0& 0& 1& -88\end{array}\right)\Rightarrow \left(\begin{array}{ccccc}1& 1& 0& 0& -55\\ 0& -4& 0& 0& 256\\ 0& 0& 1& 0& 137\\ 0& 0& 0& 1& -88\end{array}\right)$

$\Rightarrow \left(\begin{array}{ccccc}1& 0& 0& 0& 9\\ 0& 1& 0& 0& -64\\ 0& 0& 1& 0& 137\\ 0& 0& 0& 1& -88\end{array}\right)$

Therefore, our polynomial is:

$p(x)=9x^3-64x^2+137x-88$.