Why an Interpolating Polynomial Exists
Polynomial interpolation finds a polynomial that passes exactly through a given set of distinct points. Given points (x₀, y₀), (x₁, y₁), ..., (xₙ, yₙ), we seek coefficients so that the polynomial evaluates to yᵢ at each xᵢ.
Substituting each point into the generic polynomial produces a system of linear equations. In matrix form, this yields the Vandermonde matrix. Because this matrix is invertible whenever the xᵢ values are distinct (see the appendix), a unique solution for the coefficients always exists.
In practice, the Vandermonde matrix is often numerically ill-conditioned, making direct inversion a poor choice for computation. Better methods exist, and the Lagrange formulation is one of the most elegant.
The Lagrange Basis Construction
The Lagrange approach builds an interpolant from basis functions, one per node, each designed to be 1 at its own xᵢ and 0 at all other nodes. Define the Lagrange basis functions ℓᵢ(x) for i = 0, ..., n as:
Each ℓᵢ is forced to 1 at xᵢ and 0 at every other xⱼ. The linear combination
p(x) = Σ yᵢ ℓᵢ(x)
is then a valid interpolating polynomial for the given points: at each node xⱼ, every basis term vanishes except ℓⱼ, leaving exactly yⱼ.
To construct ℓᵢ, start with the product over all k ≠ i:
f(x) = Π_{k≠i} (x − xₖ)
This function is 0 at every xₖ when k ≠ i. Its value at xᵢ is a constant, found by substitution. Normalizing f by that constant yields
ℓᵢ(x) = f(x) / f(xᵢ)
A concrete example with points (1, 1), (2, 4), (3, 9) shows ℓ₀, ℓ₁, and ℓ₂ intersecting the x-axis at the nodes where they must be zero. After normalization, each polynomial equals 1 at its designated node and 0 at the others. Combining them recovers the interpolating polynomial through all three points.
Degree and Uniqueness
Each ℓᵢ has degree n, so the sum has degree at most n. This establishes the first part of the polynomial interpolation theorem: for any (n+1) data points with no repeated xᵢ, there exists a polynomial of degree at most n that interpolates them.
Uniqueness follows by contradiction. Suppose two distinct polynomials p and q, both of degree at most n, interpolate the same points. Their difference r = p − q is also a polynomial of degree at most n and has n+1 roots — one at each node. No non-zero polynomial of degree n can have n+1 roots, so r must be identically zero. Therefore, p = q.
This uniqueness means that inverting the Vandermonde matrix, the Lagrange construction, and any other valid method all produce the same polynomial — whichever is most convenient for the problem at hand.
Lagrange Polynomials as a Vector Space Basis
The set of all real polynomials of degree ≤ n, with polynomial addition and scalar multiplication, forms a vector space. The Lagrange polynomials ℓᵢ form a genuine basis for this space, requiring a proof of both linear independence and spanning.
Linear independence: If a linear combination Σ cᵢ ℓᵢ = 0, evaluate at node x₀. Since ℓ₀(x₀) = 1 and all other ℓᵢ(x₀) = 0, this gives c₀ = 0. Applying the same argument at each node shows every coefficient must be zero.
Span: For any polynomial of degree ≤ n and any n+1 distinct points on it, the interpolation theorem guarantees the Lagrange construction reproduces that polynomial exactly. Thus, every polynomial in the space can be expressed as a linear combination of the ℓᵢ.
The Interpolation Matrix in Lagrange Form
Writing the general polynomial using the standard monomial basis leads to the Vandermonde matrix. The Lagrange basis offers a far simpler matrix representation.
Evaluate the interpolant at each node xⱼ. By construction, ℓₖ(xⱼ) = 0 for k ≠ j and ℓⱼ(xⱼ) = 1. The system reduces to cⱼ = yⱼ for each j — the identity matrix. This directly confirms each coefficient equals its corresponding data value.
Appendix: Why the Vandermonde Matrix Is Invertible
For numbers x₀, ..., xₙ, the Vandermonde matrix has entries xᵢ^j. Its determinant has a known closed form:
det = Π_{0 ≤ i < j ≤ n} (xⱼ − xᵢ)
When all xᵢ are distinct, every factor in the product is non-zero, so the determinant is non-zero and the matrix is invertible.
Small cases illustrate the pattern. For a 2-by-2 Vandermonde matrix, the determinant is simply x₁ − x₀. For 3-by-3, expanding the determinant and factoring yields (x₂ − x₀)(x₂ − x₁)(x₁ − x₀).
For the general proof, use column operations that preserve the determinant. Subtract from each column j the product of the previous column and x₀. This fills the first row with zeros after the first entry. Factoring common terms from each row and erasing the first row and column leaves a smaller Vandermonde matrix for x₁, ..., xₙ. Induction on the matrix size completes the proof, yielding the product formula above.
