SC-02

Course 2

Polynomial Interpolation

Learn how to construct polynomials that pass through given data points. Master Lagrange and Newton interpolation methods, understand error bounds, and explore Hermite interpolation for matching derivatives.

Learning Objectives

Understand the polynomial interpolation problem and uniqueness theorem
Construct Lagrange interpolating polynomials using basis functions
Apply Newton's divided difference method for efficient computation
Analyze interpolation error using the error formula
Implement Hermite interpolation for derivative matching
Compare different interpolation methods and their applications

1. The Interpolation Problem

Given a set of data points, we want to find a polynomial that passes through all of them. This is fundamental to many numerical methods including integration and differentiation.

Definition 2.1: Polynomial Interpolation Problem

Given $n + 1$ distinct points $x_0, x_1, \ldots, x_n$ (called interpolation nodes) and corresponding function values $y_i = f(x_i)$ for $i = 0, 1, \ldots, n$ , find a polynomial $P_n(x)$ of degree at most $n$ such that:

P_n(x_i) = y_i, \quad i = 0, 1, \ldots, n

Theorem 2.1: Existence and Uniqueness

The interpolation polynomial $P_n(x)$ satisfying $P_n(x_i) = y_i$ for $i = 0, 1, \ldots, n$ exists and is unique.

Remark:

The uniqueness means that while there are different ways to construct the interpolating polynomial (Lagrange form, Newton form, etc.), they all give the same polynomial.

2. Lagrange Interpolation

Definition 2.2: Lagrange Basis Polynomials

The Lagrange basis polynomials $l_i(x)$ for $i = 0, 1, \ldots, n$ are defined as:

l_i(x) = \prod_{j=0, j \neq i}^{n} \frac{x - x_j}{x_i - x_j} = \frac{(x - x_0) \cdots (x - x_{i-1})(x - x_{i+1}) \cdots (x - x_n)}{(x_i - x_0) \cdots (x_i - x_{i-1})(x_i - x_{i+1}) \cdots (x_i - x_n)}

Each $l_i(x)$ is a polynomial of degree $n$ satisfying $l_i(x_j) = \delta_{ij}$ (Kronecker delta).

Definition 2.3: Lagrange Interpolating Polynomial

The Lagrange interpolating polynomial is:

P_n(x) = \sum_{i=0}^{n} y_i \, l_i(x) = y_0 l_0(x) + y_1 l_1(x) + \cdots + y_n l_n(x)

Example: Lagrange Interpolation with 3 Points

Problem: Find the interpolating polynomial for $(0, 1), (1, 3), (2, 7)$ .

Solution:

First, compute the basis polynomials:

l_0(x) = \frac{(x-1)(x-2)}{(0-1)(0-2)} = \frac{(x-1)(x-2)}{2}

l_1(x) = \frac{(x-0)(x-2)}{(1-0)(1-2)} = \frac{x(x-2)}{-1} = -x(x-2)

l_2(x) = \frac{(x-0)(x-1)}{(2-0)(2-1)} = \frac{x(x-1)}{2}

Then:

P_2(x) = 1 \cdot l_0(x) + 3 \cdot l_1(x) + 7 \cdot l_2(x) = x^2 + x + 1

Theorem 2.2: Interpolation Error

Let $x_0, x_1, \ldots, x_n$ be $n+1$ distinct points in $[a, b]$ , and let $f \in C^{n+1}[a, b]$ . If $P_n(x)$ is the interpolating polynomial, then for each $x \in [a, b]$ , there exists $\xi \in (a, b)$ such that:

f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \omega_{n+1}(x)

where $\omega_{n+1}(x) = (x - x_0)(x - x_1) \cdots (x - x_n)$ .

Note:

The error depends on both the $(n+1)$ -th derivative of $f$ and the product $\omega_{n+1}(x)$ . Choosing good interpolation nodes can minimize $\max|\omega_{n+1}(x)|$ .

3. Newton's Divided Differences

Newton's method provides an alternative form that makes it easy to add new data points without recomputing the entire polynomial.

Definition 2.4: Divided Differences

The divided differences are defined recursively:

Zeroth order: $f[x_i] = f(x_i)$

First order: $f[x_i, x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$

k-th order:

f[x_0, x_1, \ldots, x_k] = \frac{f[x_1, x_2, \ldots, x_k] - f[x_0, x_1, \ldots, x_{k-1}]}{x_k - x_0}

Remark:

Divided differences are symmetric: the value of $f[x_0, x_1, \ldots, x_k]$ does not depend on the order of the nodes.

Definition 2.5: Newton's Interpolating Polynomial

The Newton form of the interpolating polynomial is:

P_n(x) = f[x_0] + f[x_0, x_1](x - x_0) + f[x_0, x_1, x_2](x - x_0)(x - x_1) + \cdots

+ \, f[x_0, x_1, \ldots, x_n](x - x_0)(x - x_1) \cdots (x - x_{n-1})

Example: Divided Difference Table

For data points $(0, 1), (1, 3), (2, 7), (3, 13)$ :

$x_i$	$f[x_i]$	1st diff	2nd diff	3rd diff
0	1
1	3	2
2	7	4	1
3	13	6	1	0

Newton polynomial: $P_3(x) = 1 + 2x + 1 \cdot x(x-1) + 0 = x^2 + x + 1$

Theorem 2.3: Divided Difference and Derivatives

If $f \in C^n[a, b]$ , then there exists $\xi \in (a, b)$ such that:

f[x_0, x_1, \ldots, x_n] = \frac{f^{(n)}(\xi)}{n!}

4. Hermite Interpolation

Hermite interpolation extends polynomial interpolation by also matching derivative values at the interpolation nodes, resulting in higher accuracy.

Definition 2.6: Hermite Interpolation Problem

Given nodes $x_0, x_1, \ldots, x_n$ with function values $f(x_i)$ and derivative values $f'(x_i)$ , find a polynomial $H_{2n+1}(x)$ of degree at most $2n+1$ such that:

H_{2n+1}(x_i) = f(x_i), \quad H'_{2n+1}(x_i) = f'(x_i), \quad i = 0, 1, \ldots, n

Definition 2.7: Two-Point Cubic Hermite Interpolation

For two points $x_0, x_1$ , the cubic Hermite polynomial uses basis functions:

h_0(x) = \left(1 + 2\frac{x - x_0}{x_1 - x_0}\right)\left(\frac{x - x_1}{x_0 - x_1}\right)^2

h_1(x) = \left(1 + 2\frac{x - x_1}{x_0 - x_1}\right)\left(\frac{x - x_0}{x_1 - x_0}\right)^2

H_0(x) = (x - x_0)\left(\frac{x - x_1}{x_0 - x_1}\right)^2, \quad H_1(x) = (x - x_1)\left(\frac{x - x_0}{x_1 - x_0}\right)^2

The Hermite polynomial is:

H(x) = f(x_0)h_0(x) + f(x_1)h_1(x) + f'(x_0)H_0(x) + f'(x_1)H_1(x)

Theorem 2.4: Hermite Interpolation Error

If $f \in C^{2n+2}[a, b]$ , then for the Hermite interpolating polynomial $H_{2n+1}(x)$ , there exists $\xi \in (a, b)$ such that:

f(x) - H_{2n+1}(x) = \frac{f^{(2n+2)}(\xi)}{(2n+2)!} \omega_{n+1}^2(x)

where $\omega_{n+1}(x) = (x - x_0)(x - x_1) \cdots (x - x_n)$ .

Note:

The error for Hermite interpolation involves $\omega_{n+1}^2(x)$ rather than $\omega_{n+1}(x)$ , giving faster convergence as the nodes become denser.

5. Comparison and Applications

Lagrange Form

Conceptually simple and elegant
All basis polynomials must be recomputed when adding points
Good for theoretical analysis

Newton Form

Efficient for adding new data points
Can be evaluated efficiently using Horner's method
Divided difference table provides insight into data behavior

Hermite Interpolation

Higher accuracy when derivative information is available
Smoother interpolant (matching slopes)
Foundation for spline interpolation

Remark:

Warning: Runge's Phenomenon

High-degree polynomial interpolation with equally-spaced nodes can lead to large oscillations near the boundaries. This is called Runge's phenomenon. Solutions include using Chebyshev nodes or piecewise interpolation (splines).

Practice Quiz

Polynomial Interpolation Quiz

Questions

Correct

Accuracy

Given data points

(0, 1), (1, 3), (2, 7)

, what is the Lagrange interpolating polynomial?

Easy

Not attempted

What is the divided difference

f[x_0, x_1]

for

f(x) = x^2

with

x_0 = 1, x_1 = 3

Easy

Not attempted

How many data points are needed to uniquely determine a polynomial of degree

n

Easy

Not attempted

The Lagrange basis polynomial

l_i(x)

satisfies

l_i(x_j) =

Medium

Not attempted

For

f(x) \in C^{n+1}[a,b]

, the interpolation error

f(x) - P_n(x)

is proportional to:

Medium

Not attempted

What is the key advantage of Newton's divided difference form over Lagrange form?

Medium

Not attempted

Hermite interpolation uses which additional information at each node?

Medium

Not attempted

For two-point cubic Hermite interpolation with

x_0, x_1

, the interpolating polynomial has degree at most:

Hard

Not attempted

The divided difference

f[x_0, x_1, \ldots, x_n]

equals

\frac{f^{(n)}(\xi)}{n!}

for some

\xi

in the interval when:

Hard

Not attempted

The interpolation error for Hermite interpolation with

n+1

nodes is

O(h^{2n+2})

because:

Hard

Not attempted

Frequently Asked Questions

What's the difference between Lagrange and Newton interpolation?

Both produce the same polynomial, but in different forms. Lagrange formexpresses the polynomial as a weighted sum of basis polynomials. Newton formuses divided differences and nested products.

Newton's form is more efficient when adding new data points, as only one new term needs to be computed.

How do I choose interpolation nodes to minimize error?

The error depends on $\omega_{n+1}(x) = \prod(x - x_i)$ . To minimize its maximum value on $[-1, 1]$ , use Chebyshev nodes:

x_k = \cos\left(\frac{2k + 1}{2n + 2}\pi\right), \quad k = 0, 1, \ldots, n

When should I use Hermite interpolation instead of Lagrange?

Use Hermite interpolation when you have reliable derivative information at the data points. This often occurs in physics simulations where both position and velocity are known. Hermite interpolation provides smoother curves and higher accuracy with fewer points.

What is Runge's phenomenon and how can I avoid it?

Runge's phenomenon refers to oscillations that appear near the boundaries when using high-degree polynomial interpolation with equally-spaced nodes.

To avoid it:

Use Chebyshev nodes instead of equally-spaced nodes
Use piecewise polynomial interpolation (splines)
Keep the polynomial degree low

How do divided differences relate to derivatives?

For a function $f \in C^n$ , the n-th divided difference $f[x_0, \ldots, x_n]$ equals $f^{(n)}(\xi)/n!$ for some $\xi$ in the interval. This connection is useful for error analysis and shows that divided differences approximate scaled derivatives.