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}{ccc|c}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}{ccc|c}1&1&1&-6\\4&2&1&2\\16&4&1&12\end{array}}\right)\Rightarrow \left({\begin{array}{ccc|c}1&1&1&-6\\0&-2&-3&26\\0&-12&-15&108\end{array}}\right)\Rightarrow \left({\begin{array}{ccc|c}1&1&1&-6\\0&-2&-3&26\\0&0&3&-48\end{array}}\right)\Rightarrow \left({\begin{array}{ccc|c}1&1&0&10\\0&2&0&-22\\0&0&1&-16\end{array}}\right)\Rightarrow \left({\begin{array}{ccc|c}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}{cccc|c}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}{cccc|c}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}{cccc|c}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}{cccc|c}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}{cccc|c}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}{cccc|c}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}{cccc|c}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$.