Lagrange Interpolation

The Vandermonde approach requires inverting a matrix — expensive and numerically fragile for large systems. Lagrange interpolation sidesteps this entirely. Instead of solving for coefficients, it constructs a set of clever basis polynomials $L_k(x)$ that each equal 1 at exactly one node and 0 at all others. The interpolating polynomial is then a straightforward weighted sum of these basis polynomials.

The Lagrange Formula

Given $n+1$ nodes $(x_0, f(x_0)),\;\ldots,\;(x_n, f(x_n))$ , the Lagrange interpolating polynomial is:

$P_n(x) = \sum_{k=0}^{n} f(x_k)\, L_k(x)$

where each Lagrange basis polynomial $L_k(x)$ is defined as:

$L_k(x) = \prod_{\substack{j=0 \\ j \neq k}}^{n} \frac{x - x_j}{x_k - x_j}$

The Kronecker Delta Property

The basis polynomials are engineered to satisfy:

$L_k(x_j) = \delta_{kj} = \begin{cases} 1 & \text{if } k = j \\ 0 & \text{if } k \neq j \end{cases}$

This is what guarantees $P_n(x_i) = f(x_i)$ for every node — each $L_k$ activates (equals 1) at its own node $x_k$ and is silent (equals 0) at every other node.

Example: Verifying $L_2(x)$ for 3 nodes

To see this in action, let’s look at a system with three nodes: $x_0, x_1,$ and $x_2$ . By definition, the basis polynomial $L_2(x)$ is constructed by including $x_0$ and $x_1$ in the product, but omitting $x_2$ :

$L_2(x) = \frac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)}$

Let’s calculate the multiplication when we evaluate this polynomial at each specific node:

At $x = x_0$ (where $k \neq j$ ): $L_2(x_0) = \frac{(x_0 - x_0)(x_0 - x_1)}{(x_2 - x_0)(x_2 - x_1)} = \frac{0 \cdot (x_0 - x_1)}{(x_2 - x_0)(x_2 - x_1)} = 0$

Why it is 0: Substituting $x_0$ creates an $(x_0 - x_0)$ term. This turns the numerator into zero, making the whole expression 0.
At $x = x_1$ (where $k \neq j$ ): $L_2(x_1) = \frac{(x_1 - x_0)(x_1 - x_1)}{(x_2 - x_0)(x_2 - x_1)} = \frac{(x_1 - x_0) \cdot 0}{(x_2 - x_0)(x_2 - x_1)} = 0$

Why it is 0: Substituting $x_1$ creates an $(x_1 - x_1)$ term, turning the numerator and the final result to zero.
At $x = x_2$ (where $k = j$ ): $L_2(x_2) = \frac{(x_2 - x_0)(x_2 - x_1)}{(x_2 - x_0)(x_2 - x_1)} = 1$

Why it is 1: Substituting $x_2$ makes the numerator exactly identical to the denominator. Any non-zero value divided by itself equals 1.

The Basis Sums to 1

A companion property is that the basis polynomials add up to 1 at every $x$ :

$\sum_{k=0}^{n} L_k(x) = 1$

Deriving $l_k(x)$ from First Principles

We can use the Kronecker delta property to mathematically build a specific basis polynomial from scratch. Let’s find $l_2(x)$ for a system with 4 nodes where $n=3$ .

Here $n=3$ , meaning our nodes are $x_0, x_1, x_2, x_3$ . We are looking for $l_k(x)$ where $k=2$ .

Based on the rule $l_k(x_j) = 1$ when $k=j$ and $0$ when $k \neq j$ , we know the following must be true:

$l_2(x_0) = 0$
$l_2(x_1) = 0$
$l_2(x_3) = 0$
$l_2(x_2) = 1$

Because $l_2(x)$ evaluates to zero at $x_0, x_1$ , and $x_3$ , these three points are the roots of the polynomial.

Knowing the roots, we can write the polynomial with an unknown constant $C$ : $l_2(x) = C(x-x_0)(x-x_1)(x-x_3)$

To find $C$ , substitute $x = x_2$ into the equation: $l_2(x_2) = C(x_2-x_0)(x_2-x_1)(x_2-x_3)$

Since we know $l_2(x_2) = 1$ , we can substitute $1$ on the left side: $1 = C(x_2-x_0)(x_2-x_1)(x_2-x_3)$

Isolating $C$ gives us: $C = \frac{1}{(x_2-x_0)(x_2-x_1)(x_2-x_3)}$

Substitute $C$ back into the general equation to get the completed basis polynomial: $l_2(x) = \frac{(x-x_0)(x-x_1)(x-x_3)}{(x_2-x_0)(x_2-x_1)(x_2-x_3)}$

Worked Example: 3 Nodes

Problem: Find the interpolating polynomial through the following three data points.

$x_k$ $f(x_k)$
1 2
2 3
4 1

$x_k$	$f(x_k)$
1	2
2	3
4	1

Step 1: Compute the Basis Polynomials

$L_0(x)$ : The product omits $j = 0$ , so it includes terms for $j = 1$ and $j = 2$ :

$L_0(x) = \frac{(x - x_1)(x - x_2)}{(x_0 - x_1)(x_0 - x_2)} = \frac{(x-2)(x-4)}{(1-2)(1-4)} = \frac{(x-2)(x-4)}{(-1)(-3)} = \frac{(x-2)(x-4)}{3}$

$L_1(x)$ : Omits $j = 1$ , includes $j = 0$ and $j = 2$ :

$L_1(x) = \frac{(x - x_0)(x - x_2)}{(x_1 - x_0)(x_1 - x_2)} = \frac{(x-1)(x-4)}{(2-1)(2-4)} = \frac{(x-1)(x-4)}{(1)(-2)} = \frac{(x-1)(x-4)}{-2}$

$L_2(x)$ : Omits $j = 2$ , includes $j = 0$ and $j = 1$ :

$L_2(x) = \frac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)} = \frac{(x-1)(x-2)}{(4-1)(4-2)} = \frac{(x-1)(x-2)}{(3)(2)} = \frac{(x-1)(x-2)}{6}$

Step 2: Construct the Polynomial

$P(x) = y_0\,L_0(x) + y_1\,L_1(x) + y_2\,L_2(x) = 2\,L_0(x) + 3\,L_1(x) + 1\cdot L_2(x)$

$P(x) = 2\cdot\frac{(x-2)(x-4)}{3} \;+\; 3\cdot\frac{(x-1)(x-4)}{-2} \;+\; \frac{(x-1)(x-2)}{6}$

After expanding and collecting terms:

$\boxed{P(x) = -\frac{2}{3}x^2 + 3x - \frac{1}{3}}$

Step 3: Verification

Node	Computed $P(x)$	Expected
$x = 1$	$-\tfrac{2}{3} + 3 - \tfrac{1}{3} = 2$	$\checkmark$
$x = 2$	$-\tfrac{8}{3} + 6 - \tfrac{1}{3} = 3$	$\checkmark$
$x = 4$	$-\tfrac{32}{3} + 12 - \tfrac{1}{3} = 1$	$\checkmark$

The Recomputation Problem

Lagrange interpolation has one significant drawback: adding a new node forces a complete rebuild of every basis polynomial.

To see why, consider $L_0(x)$ with the original three nodes:

$L_0(x) = \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$

Now suppose we add a fourth node $x_3$ . The Kronecker delta property requires $L_0(x_3) = 0$ , which means $(x - x_3)$ must appear in the numerator. Similarly, $(x_0 - x_3)$ must appear in the denominator. The basis polynomial becomes:

$L_0^{\,\text{new}}(x) = \frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)}$

This is a different function from the original $L_0(x)$ — every basis polynomial picks up a new factor in both numerator and denominator. $L_1$ , $L_2$ , and any others must all be rebuilt as well. None of the work done for the 3-node case carries forward.