Definition 10.1.1.
-
The interval \([a,b]\) is called the interpolation interval.
-
A polynomial \(p_n(x)\) satisfying (10.1.2) is called an interpolation polynomial or interpolating polynomial.
Section 10.1 Polynomial Interpolation
Subsection 10.1.1 The Interpolation Problem
Let \(f(x)\) be a real-valued function on \([a,b]\text{,}\) and let \(x_0, x_1, \ldots, x_n\) be \(n+1\) distinct points in \([a,b]\text{,}\) with corresponding function values \(f_0, f_1, \ldots, f_n\text{,}\) that is,
\begin{equation}
f(x_i) = f_i, \quad i = 0, 1, \ldots, n\tag{10.1.1}
\end{equation}
The problem is to find a polynomial \(p_n(x)\) of degree at most \(n\) that satisfies
\begin{equation}
p_n(x_i) = f_i, \quad i = 0, 1, \ldots, n\tag{10.1.2}
\end{equation}
The geometric meaning of polynomial interpolation is to find a polynomial \(p_n(x)\) of degree at most \(n\) whose graph passes through the given \(n+1\) data points \((x_i, f_i)\) (\(i = 0, 1, \ldots, n\)), as shown in the figure below.
Subsection 10.1.2 Existence and Uniqueness
We will prove that an interpolating polynomial of degree at most \(n\) satisfying the interpolation condition (10.1.1) exists and is unique. However, the form of its expression can vary depending on the choice of basis functions.
Theorem 10.1.3. Existence and Uniqueness of Interpolating Polynomial.
Let \(P_n[x]\) denote the space of all polynomials of degree at most \(n\text{.}\) There exists a unique polynomial \(p_n(x) \in P_n[x]\) satisfying the interpolation condition (10.1.2).
Proof.
Take the standard basis \(\{1, x, \ldots, x^n\}\) for \(P_n[x]\text{.}\) Then \(p_n(x) \in P_n[x]\) can be written as
\begin{equation*}
p_n(x) = a_0 + a_1 x + \cdots + a_n x^n
\end{equation*}
If \(p_n(x)\) is the interpolating polynomial, then it must satisfy condition (10.1.2), so the coefficients \(a_0, a_1, \ldots, a_n\) must satisfy the system of equations:
\begin{equation}
\begin{cases}
a_0 + a_1 x_0 + \cdots + a_n x_0^n = f_0 \\
a_0 + a_1 x_1 + \cdots + a_n x_1^n = f_1 \\
\quad \vdots \\
a_0 + a_1 x_n + \cdots + a_n x_n^n = f_n
\end{cases}\tag{10.1.3}
\end{equation}
This is a linear system, and its coefficient matrix determinant is the Vandermonde determinant:
\begin{equation*}
V_n(x_0, x_1, \ldots, x_n) = \begin{vmatrix}
1 \amp x_0 \amp \cdots \amp x_0^n \\
1 \amp x_1 \amp \cdots \amp x_1^n \\
\vdots \amp \vdots \amp \amp \vdots \\
1 \amp x_n \amp \cdots \amp x_n^n
\end{vmatrix} = \prod_{i=1}^n \prod_{j=0}^{i-1} (x_i - x_j)
\end{equation*}
Example 10.1.4. Interpolation Using the Vandermonde System.
Given the following data:
| \(x_i\) | \(-1\) | \(1\) | \(2\) | \(5\) |
|---|---|---|---|---|
| \(f_i\) | \(-7\) | \(7\) | \(-4\) | \(35\) |
Find an interpolating polynomial \(p_3(x)\) of degree at most 3.
Solution.
Using equation (10.1.3), we get:
\begin{equation*}
\begin{bmatrix}
1 \amp -1 \amp 1 \amp -1 \\
1 \amp 1 \amp 1 \amp 1 \\
1 \amp 2 \amp 4 \amp 8 \\
1 \amp 5 \amp 25 \amp 125
\end{bmatrix}
\begin{bmatrix}
a_0 \\ a_1 \\ a_2 \\ a_3
\end{bmatrix}
=
\begin{bmatrix}
-7 \\ 7 \\ -4 \\ 35
\end{bmatrix}
\end{equation*}
Solving this system of equations, we obtain:
\begin{equation*}
a_0 = 10, \quad a_1 = 5, \quad a_2 = -10, \quad a_3 = 2
\end{equation*}
Therefore, the interpolating polynomial is:
\begin{equation*}
p_3(x) = 10 + 5x - 10x^2 + 2x^3
\end{equation*}
Remark 10.1.5.
Solving the interpolation problem by solving the linear system (10.1.3) has serious drawbacks:
-
The computational workload is large.
-
The Vandermonde matrix typically has a very large condition number, resulting in poor numerical accuracy of the computed solution.
For example, in Example 10.1.4, the condition number of the coefficient matrix is approximately 215. Therefore, this approach is not recommended in practice.
More convenient methods for finding interpolating polynomials involve choosing appropriate basis functions so that the interpolating polynomial has a special form, and the unknown coefficients in these forms can be determined directly from the interpolation conditions. We will study two such methods: Lagrange interpolation and Newton interpolation.
