多元多项式拉格朗日插值：插值点数的唯一性判定问题

Great question! The connection between univariate and multivariate polynomial interpolation is really intuitive, and your initial thought about fixing one variable is exactly the right way to start. Let's break this down step by step.

• For an n-degree univariate polynomial f(x), we know n+1 distinct interpolation points (x_i, f(x_i)) uniquely determine the polynomial. This works because the system of linear equations for the polynomial's coefficients has a unique solution (the Vandermonde matrix is invertible when all x_i are distinct).

Let's focus on your example: a binary polynomial f(x,y) where the degree of x is at most n, and the degree of y is also at most n.

First, let's count how many free coefficients we're dealing with. The polynomial can be written as:
$$f(x,y) = \sum_{a=0}^n \sum_{b=0}^n c_{a,b} x^a y^b$$
That's (n+1) × (n+1) = (n+1)² coefficients total. To uniquely determine all these coefficients, we need exactly (n+1)² distinct interpolation points—and a grid of points is the simplest way to construct such a set.

Why a grid works (building on your initial idea) #

• Fix x to a distinct value x₀: then f(x₀, y) becomes an n-degree univariate polynomial in y. To pin down this polynomial, we need n+1 distinct y-values: (x₀, y₀), (x₀, y₁), ..., (x₀, yₙ).
• Repeat this for n more distinct x-values: x₁, x₂, ..., xₙ. Each of these gives us another univariate polynomial in y, which also needs n+1 points to define.
• Adding it all up, that's (n+1) × (n+1) grid points: (x_i, y_j) where 0 ≤i,j ≤n, with all x_i distinct and all y_j distinct.

Why this uniquely defines f(x,y) #

For each fixed y_j, the values f(x₀,y_j), f(x₁,y_j), ..., f(xₙ,y_j) define an n-degree univariate polynomial in x (this is the coefficient of y^j in f(x,y)). Since we have n+1 distinct x-points, we can uniquely solve for each coefficient c_{a,j} across all a and j.

Quick note on non-grid points #

We don't have to use a grid, but the points need to form a unisolvent set—meaning no two such polynomials can agree on all the points. The grid is just the most straightforward way to construct such a set, and it directly uses the univariate interpolation result you already know.

If we extend this to a k-variate polynomial where each variable has degree ≤n, the number of required interpolation points is (n+1)^k. The logic stays the same: fix k-1 variables to distinct values, solve for the univariate polynomial in the last variable, and repeat across all combinations of fixed values.

内容的提问来源于stack exchange，提问作者Cryptonaut