Unit 2: Polynomial Interpolation, Finite Differences & Approximation Theory

1. The Polynomial Interpolation Problem

Let $f: [a, b] \to \mathbb{R}$ be a continuous function. Suppose we are given $n + 1$ distinct nodes:

along with corresponding function values $y_i = f(x_i)$ for $i = 0, 1, \dots, n$.

The Polynomial Interpolation Problem seeks a polynomial $P_n(x) \in \mathbb{P}_n$ of degree at most $n$:

satisfying the $n + 1$ interpolation conditions:

Theorem 2.1 (Existence and Uniqueness of the Interpolating Polynomial):

Given $n + 1$ distinct points $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$, there exists one and only one polynomial $P_n \in \mathbb{P}_n$ of degree at most $n$ passing through all $n + 1$ points.

Rigorous Proof: Expressing the interpolation conditions in matrix form:

The coefficient matrix $V$ is the Vandermonde Matrix. Its determinant satisfies:

Because the nodes $x_i$ are pairwise distinct, $x_i - x_j \ne 0$ for all $i > j$. Consequently, $\det(V) \ne 0$. By Cramer's Rule, $V$ is non-singular and invertible, which guarantees that the coefficient vector $\vec{c} = V^{-1} \vec{y}$ exists and is strictly unique. $\blacksquare$

2. The Lagrange Basis Formulation

Direct matrix inversion of the Vandermonde matrix is computationally expensive ($\mathcal{O}(n^3)$) and notoriously ill-conditioned. The Lagrange form provides an explicit analytical representation by introducing cardinal basis polynomials.

Definition 2.1 (Cardinal Lagrange Basis Polynomials):

For $n + 1$ distinct nodes $x_0, x_1, \dots, x_n$, the $k$-th Lagrange basis polynomial $L_{n,k}(x)$ of degree $n$ is defined by:

The Lagrange polynomials satisfy the fundamental Kronecker delta property:

The interpolating polynomial is simply the linear combination:

3. Rigorous Error Analysis: The Cauchy Remainder Theorem

Theorem 2.2 (Cauchy Interpolation Remainder Formula):

Let $f \in C^{n+1}[a, b]$ and let $P_n \in \mathbb{P}_n$ interpolate $f$ at $n + 1$ distinct nodes $x_0, x_1, \dots, x_n \in [a, b]$. For any point $x \in [a, b]$:

where $\xi = \xi(x)$ is a number lying strictly in the interior of the interval spanned by $x_0, x_1, \dots, x_n$ and $x$.

Rigorous Proof: If $x = x_i$ for any node, both sides are $0$ and equality holds trivially. Assume $x \ne x_i$ for all $i$. Fix $x$ and define the node product polynomial:

Notice that $w(x) \ne 0$ since $x$ is not a node. Define the auxiliary error function $g: [a, b] \to \mathbb{R}$:

Now inspect the zeros of $g(t)$:

1. For each node $t = x_i$ ($i = 0, \dots, n$):

1. For $t = x$:

Thus, $g(t)$ possesses at least $n + 2$ distinct zeros in $[a, b]$.

Since $f \in C^{n+1}[a, b]$ and $P_n, w$ are polynomials, $g \in C^{n+1}[a, b]$. Applying Rolle's Theorem successively:

• $g'(t)$ has at least $n + 1$ zeros between the $n + 2$ zeros of $g(t)$.
• $g''(t)$ has at least $n$ zeros.
• Repeating this $n+1$ times, the $(n+1)$-th derivative $g^{(n+1)}(t)$ has at least one zero $\xi$ in the interior of the domain.

Now compute $g^{(n+1)}(t)$:

Therefore:

Evaluating at the zero $t = \xi$:

Rearranging terms yields:

1. Motivation for the Divided Difference Formulation

While the Lagrange form is mathematically elegant, adding a new data point $(x_{n+1}, y_{n+1})$ requires completely recalculating all $n + 2$ basis polynomials $L_{n+1, k}(x)$. Newton's Divided Differences overcomes this limitation by expressing $P_n(x)$ in a triangular, incremental hierarchical basis:

Adding a new node requires simply computing one additional leading coefficient $a_{n+1}$.

2. Recursive Definition of Divided Differences

Definition 2.2:

The divided differences of a function $f$ with respect to distinct nodes $x_0, x_1, \dots, x_n$ are defined recursively:

• Zeroth Divided Difference:

• First Divided Difference:

• Second Divided Difference:

• General $k$-th Divided Difference:

The coefficients $a_k$ in the Newton interpolating polynomial are precisely the top-diagonal entries of the divided difference table: $a_k = f[x_0, x_1, \dots, x_k]$.

3. Mean Value Theorem for Divided Differences

Theorem 2.3:

Let $f \in C^k[a, b]$ and let $x_0, x_1, \dots, x_k$ be distinct nodes in $[a, b]$. Then there exists a point $\xi$ in the open interval $(\min x_i, \max x_i)$ such that:

Proof: Let $P_k(x)$ be the polynomial of degree $k$ interpolating $f$ at $x_0, \dots, x_k$. The leading coefficient of $P_k(x)$ is $f[x_0, \dots, x_k]$. By Cauchy's remainder theorem:

Now let $P_{k-1}(x)$ interpolate $f$ at $x_0, \dots, x_{k-1}$. Then $P_k(x) - P_{k-1}(x) = f[x_0, \dots, x_k] \prod_{j=0}^{k-1} (x - x_j)$. Evaluating the error at $x = x_k$ and applying the generalized Rolle's theorem proves $f[x_0, \dots, x_k] = \frac{f^{(k)}(\xi)}{k!}$. $\blacksquare$

1. Equispaced Grid Finite Difference Operators

When nodes are uniformly spaced with constant step size $h$:

divided differences simplify into finite difference operator algebra.

Definitions of Core Operators:

1. Forward Difference Operator ($\Delta$):

Higher powers: $\Delta^n f_k = \Delta(\Delta^{n-1} f_k) = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} f_{k+j}$.

2. Backward Difference Operator ($\nabla$):

Higher powers: $\nabla^n f_k = \sum_{j=0}^n (-1)^j \binom{n}{j} f_{k-j}$.

3. Central Difference Operator ($\delta$):

4. Shift Operator ($E$):

5. Averaging Operator ($\mu$):

Fundamental Operator Identities:

From Taylor series: $E f(x) = f(x + h) = \sum \frac{h^k D^k}{k!} f(x) = e^{hD} f(x)$, where $D = \frac{d}{dx}$.

2. Newton-Gregory Forward and Backward Formulas

Let $x = x_0 + s h$, so $s = \frac{x - x_0}{h}$ is the non-dimensionalized step parameter.

The Newton-Gregory Forward Interpolation Formula:

Suitable for interpolating near the beginning of a tabulated dataset:

The Newton-Gregory Backward Interpolation Formula:

Suitable for interpolating near the end of a dataset (or for extrapolation): Let $x = x_n + s h$, so $s = \frac{x - x_n}{h}$:

3. Central Difference Formulas: Stirling & Bessel

For interpolation near the center of a table, forward and backward formulas exhibit asymmetric error propagation. Central difference formulas provide optimal symmetric precision:

• Stirling's Formula: Averages forward and backward expressions about the central node:

• Bessel's Formula: Best suited for $s$ near $0.5$ (midway between nodes):

1. The Catastrophe of High-Degree Equispaced Interpolation

It is a common intuition that increasing the degree $n$ of an interpolating polynomial on a uniform grid should improve accuracy. In 1901, Carl Runge discovered that this intuition fails catastrophically.

Consider the Runge Function on $[-1, 1]$:

If $P_n(x)$ interpolates $f$ at $n + 1$ equispaced nodes $x_k = -1 + \frac{2k}{n}$, then as $n \to \infty$:

Near the boundaries $x = \pm 1$, the polynomial oscillations explode exponentially.

Mathematical Origin: In Cauchy's remainder formula:

On uniform grids, the node product polynomial $w_n(x)$ is highly non-uniform: it is small near the center $x = 0$, but near the boundaries $x \approx \pm 1$, it attains gigantic peaks of order $\mathcal{O}(n^{-1} e^n)$. Combined with the singularity of $f(z)$ in the complex plane at $z = \pm \frac{i}{5}$ (which lies inside the equispaced convergence ellipse), the error diverges.

2. Chebyshev Polynomials and Optimal Node Clustering

To suppress boundary oscillations, we must choose nodes $x_k$ that minimize the maximum norm of the node product polynomial:

Definition 2.3 (Chebyshev Polynomials of the First Kind):

The Chebyshev polynomials $T_n(x)$ are defined on $[-1, 1]$ by:

They satisfy the three-term recurrence relation:

The leading coefficient of $T_n(x)$ is $2^{n-1}$ for $n \ge 1$.

Theorem 2.4 (The Minimax Property of Chebyshev Polynomials):

Among all monic polynomials of degree $n$ on $[-1, 1]$, the monic Chebyshev polynomial $\tilde{T}_n(x) = \frac{T_n(x)}{2^{n-1}}$ has the strictly smallest maximum absolute value on $[-1, 1]$:

Theorem 2.5 (Chebyshev Optimal Interpolation Nodes):

The roots of $T_{n+1}(x) = 0$ provide the optimal interpolation nodes on $[-1, 1]$:

These nodes are densely clustered near the endpoints $x = \pm 1$ and spread apart near the center $x = 0$. Using Chebyshev nodes, the Lebesgue constant grows only logarithmically ($\Lambda_n \sim \frac{2}{\pi} \ln n$), completely eliminating Runge's phenomenon and guaranteeing uniform convergence for any analytic function!