Interpolation Theory
Published:
Let $x_0, x_1, … , x_n$ be distinct real or complex numbers, and let $y_0 , y_1, …, y_n$ be associated function values. We now study the problem of finding a polynomial p (x) that interpolates the given data:
By writing: $p(x) = a_0 + a_1x + … + a_mx^m$
Consider that m = n, then
It can be written that $Xa = y$, with
The matrix X is called a Vandermonde matrix.
Theorem
Given n + 1 distinct points $x_0, … , x_n$ and n + 1 ordinates $y_0, …, y_n$, there is a polynomial p(x) of $degree \le n$ that interpolates $y_i$ at $x_i$, i = 0, 1, … , n. This polynomial p(x) is unique among the set of all polynomials of degree at most n.
Below are three kinds of proofs.
Proof
It can be shown that for the matrix X,
This shows that $det(X) \ne 0$, since the points $x_i$ are distinct. Thus X is nonsingular and the system $Xa = y$ has a unique solution a. This proves the existence and uniqueness of an interpolating polynomial of $degree \le n$.
The system $Xa = y$ has a unique solution iff the homogeneous system $Xb = 0$ has only the trivial solution b = 0. Therefore, assume $Xb = 0$ for some b. Using b, define
From the system $Xb = 0$, we have
The polynomial p(x) has n + 1 zeros and degree $p(x) \le n$. This is not possible unless $p(x) \equiv 0$. But then all coefficients $b = 0, i = 0, 1, … , n$, completing the proof.
Consider a special polynomial
Then the polynomial can be rewritten
Since all $l_i(x)$ have degree n, degree $p(x) \le n$.
To prove uniqueness, suppose q(x) is another polynomial of degree $\le$ n that satisfies (1). Define
Then degree $r(x) \le n$, and
Since r(x) has n + 1 zeros, we must have $r(x) \equiv 0$, which proves $p(x) \equiv q(x)$, completing the proof.
Reference
- Godfrey Harold Hardy, Edward Maitland Wright,E. W. (Edward Maitland) Wright,An Introduction to Numerical Analysis, 131-134. Clarendon Press, 1979.