Vandermonde Matrix Interpolation

Given a set of data points called nodes, we want to find a polynomial that passes through all of them exactly. The most direct approach is to treat this as a system of linear equations. The Vandermonde matrix is the coefficient matrix of that system: it encodes the relationship between the unknown polynomial coefficients and the given function values at the nodes.

---

The Setup

Suppose we have $n+1$ nodes: $(x_0, f(x_0)),\; (x_1, f(x_1)),\; \ldots,\; (x_n, f(x_n))$.

We want to find a polynomial:

$P_n(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$

that satisfies $P_n(x_i) = f(x_i)$ for every node. This gives $n+1$ equations, one per node which form the linear system:

$\begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \\ 1 & x_1 & x_1^2 & \cdots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{bmatrix} = \begin{bmatrix} f(x_0) \\ f(x_1) \\ \vdots \\ f(x_n) \end{bmatrix}$

The left-hand matrix is the Vandermonde matrix. The number of nodes directly determines the degree of the polynomial:

$\text{Degree} = \text{(number of nodes)} - 1$

---

Worked Example: Degree 1

Problem: A rocket’s velocity was measured at two time points. Find the interpolating polynomial $P_1(t)$.

Time $t$	Velocity $v$
15	362.8
20	517.3

Step 1: Write the linear system:

$\begin{bmatrix} 1 & 15 \\ 1 & 20 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} 362.8 \\ 517.3 \end{bmatrix}$

Step 2: Solve by matrix inversion:

$\begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} 1 & 15 \\ 1 & 20 \end{bmatrix}^{-1} \begin{bmatrix} 362.8 \\ 517.3 \end{bmatrix}$

Recall that the inverse of a $2 \times 2$ matrix $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ is $\dfrac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$:

$\begin{bmatrix} 1 & 15 \\ 1 & 20 \end{bmatrix}^{-1} = \frac{1}{(1)(20)-(1)(15)}\begin{bmatrix} 20 & -15 \\ -1 & 1 \end{bmatrix} = \frac{1}{5}\begin{bmatrix} 20 & -15 \\ -1 & 1 \end{bmatrix}$

Step 3: Compute the coefficients:

$a_0 = \frac{1}{5}\bigl(20 \times 362.8 + (-15) \times 517.3\bigr) = \frac{1}{5}(7256 - 7759.5) = \frac{-503.5}{5} = -100.7$

$a_1 = \frac{1}{5}\bigl((-1) \times 362.8 + 1 \times 517.3\bigr) = \frac{154.5}{5} = 30.9$

$\boxed{P_1(t) = -100.85 + 30.91\,t}$

---

Worked Example: Degree 2

Problem: Velocity was measured at three time points. Find $P_2(t)$ and estimate the acceleration at $t = 7$.

Time $t$	Velocity $v$
3	44
5	24
7	26

Step 1: Set up the $3 \times 3$ system:

$\begin{bmatrix} 1 & 3 & 9 \\ 1 & 5 & 25 \\ 1 & 7 & 49 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 44 \\ 24 \\ 26 \end{bmatrix}$

Step 2: Solve the system:

Solving (by row reduction or computer) yields:

$a_0 = 115.25, \qquad a_1 = -32, \qquad a_2 = 2.75$

$\boxed{P_2(t) = 115.25 - 32\,t + 2.75\,t^2}$

Step 3: Estimate acceleration at $t = 7$:

Acceleration is the derivative of velocity:

$P_2'(t) = -32 + 5.5\,t$

$P_2'(7) = -32 + 5.5 \times 7 = -32 + 38.5 = \mathbf{6.5 \text{ ms}^{-2}}$

---

Limitation: Computational Cost

The Vandermonde approach works, but it requires computing a matrix inverse. For an $(n+1) \times (n+1)$ system, this has time complexity $O(n^3)$ — it becomes prohibitively expensive for large $n$.

Degree	Matrix Size	Feasibility
1	$2 \times 2$	Fast, trivial
2	$3 \times 3$	Manageable
$n \gg 1$	$(n+1) \times (n+1)$	Expensive in both time and memory

Caution

Practical rule: The Vandermonde matrix is only used directly for degree 1 in practice. For higher-degree interpolation, the Lagrange and Newton forms avoid matrix inversion entirely — and are covered in the next two sections.