Interpolation

3.1 Data and Interpolating Functions

1) Interpolation

Interpolation: The process of constructing a function that passes exactly through a given set of data points.

A function $P$ interpolates

$$(x_1,y_1),\ldots,(x_n,y_n)$$

if

$$P(x_i)=y_i, \qquad i=1,\ldots,n.$$

The nodes $x_1,\ldots,x_n$ must be distinct.

2) Interpolating Polynomial

Interpolating Polynomial: A polynomial that passes through every given data point.

For $n$ data points with distinct nodes, there exists exactly one interpolating polynomial of degree at most $n-1$.

3) Polynomial Interpolation Theorem

Given $n$ points

$$(x_1,y_1),\ldots,(x_n,y_n)$$

with distinct $x_i$, there exists a unique polynomial $P$ satisfying

$$\deg(P)\leq n-1$$

and

$$P(x_i)=y_i, \qquad i=1,\ldots,n.$$

4) Lagrange Basis Polynomial

Lagrange Basis Polynomial: A polynomial $L_k(x)$ that equals $1$ at $x_k$ and $0$ at every other interpolation node.

$$L_k(x) = \prod_{\substack{j=1\\j\neq k}}^n \frac{x-x_j}{x_k-x_j}.$$

It satisfies

$$L_k(x_j) = \begin{cases} 1, & j=k,\\ 0, & j\neq k. \end{cases}$$

5) Lagrange Interpolation

Lagrange Interpolation: An explicit representation of the unique interpolating polynomial.

$$P_{n-1}(x) = \sum_{k=1}^n y_kL_k(x).$$

Equivalently,

$$P_{n-1}(x) = \sum_{k=1}^n y_k \prod_{\substack{j=1\\j\neq k}}^n \frac{x-x_j}{x_k-x_j}.$$

The Lagrange form is easy to derive but inefficient to update when new data points are added.

6) Divided Difference

Divided Difference: A recursively defined quantity used as a coefficient in Newton’s interpolation formula.

The zeroth divided difference is

$$f[x_i]=f(x_i).$$

The first divided difference is

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

Higher-order divided differences are defined by

$$f[x_i,\ldots,x_{i+k}] = \frac{ f[x_{i+1},\ldots,x_{i+k}] - f[x_i,\ldots,x_{i+k-1}] }{ x_{i+k}-x_i }.$$

7) Newton’s Divided-Difference Form

Newton’s Divided-Difference Polynomial: A nested representation of the interpolating polynomial.

$$\begin{aligned} P_{n-1}(x) ={}&f[x_1] +f[x_1,x_2](x-x_1)\\ &+f[x_1,x_2,x_3](x-x_1)(x-x_2)\\ &+\cdots\\ &+f[x_1,\ldots,x_n] \prod_{j=1}^{n-1}(x-x_j). \end{aligned}$$

In summation form,

$$P_{n-1}(x) = \sum_{k=1}^n f[x_1,\ldots,x_k] \prod_{j=1}^{k-1}(x-x_j).$$

The empty product for $k=1$ is defined as $1$.

8) Nested Evaluation

Newton’s polynomial can be written in nested form:

$$\begin{aligned} P_{n-1}(x) ={}&c_1+(x-x_1)\bigl( c_2+(x-x_2)\bigl( c_3+\cdots\\ &+(x-x_{n-1})c_n \bigr)\bigr), \end{aligned}$$

where

$$c_k=f[x_1,\ldots,x_k].$$

This form can be evaluated efficiently using generalized Horner’s method.

9) Updating an Interpolating Polynomial

When a new point $(x_{n+1},y_{n+1})$ is added, Newton’s form can be extended by one term:

$$P_n(x) = P_{n-1}(x) + f[x_1,\ldots,x_{n+1}] \prod_{j=1}^{n}(x-x_j).$$

The existing coefficients do not need to be recomputed.

3.2 Interpolation Error

1) Interpolation Error

Interpolation Error: The difference between the original function and its interpolating polynomial.

$$E(x)=f(x)-P_{n-1}(x).$$

The error is zero at every interpolation node:

$$E(x_i)=0.$$

2) Interpolation Error Formula

Suppose $P_{n-1}$ interpolates $f$ at the distinct nodes

$$x_1,\ldots,x_n.$$

If $f$ has $n$ continuous derivatives, then

$$f(x)-P_{n-1}(x) = \frac{f^{(n)}(c)}{n!} \prod_{i=1}^{n}(x-x_i)$$

for some $c$ between the smallest and largest values among

$$x,x_1,\ldots,x_n.$$

3) Interpolation Error Bound

If

$$|f^{(n)}(t)|\leq M$$

throughout the interpolation interval, then

$$|f(x)-P_{n-1}(x)| \leq \frac{M}{n!} \left| \prod_{i=1}^{n}(x-x_i) \right|.$$

The error depends on:

• The size of the derivative $f^{(n)}$.
• The positions of the interpolation nodes.
• The distance between $x$ and the nodes.

4) Node Polynomial

Node Polynomial: The polynomial whose roots are the interpolation nodes.

$$\omega_n(x) = \prod_{i=1}^{n}(x-x_i).$$

The interpolation error can be written as

$$f(x)-P_{n-1}(x) = \frac{f^{(n)}(c)}{n!}\omega_n(x).$$

Choosing nodes that minimize the maximum value of $|\omega_n(x)|$ reduces the worst-case interpolation error.

5) Runge Phenomenon

Runge Phenomenon: Large oscillations near the endpoints of an interval when a high-degree polynomial interpolates data at equally spaced nodes.

Increasing the polynomial degree does not necessarily reduce the error.

The Runge phenomenon is especially severe when:

• The degree is high.
• The nodes are equally spaced.
• The function changes rapidly near the endpoints.

6) Avoiding the Runge Phenomenon

Common approaches include:

• Using Chebyshev nodes.
• Using piecewise low-degree polynomials.
• Using cubic splines instead of one high-degree polynomial.

3.3 Chebyshev Interpolation

1) Chebyshev Polynomial

Chebyshev Polynomial: The degree-$n$ polynomial defined on $[-1,1]$ by

$$T_n(x) = \cos\left(n\arccos x\right).$$

The first Chebyshev polynomials are

$$T_0(x)=1,$$ $$T_1(x)=x,$$ $$T_2(x)=2x^2-1,$$ $$T_3(x)=4x^3-3x.$$

2) Chebyshev Recurrence

Chebyshev polynomials satisfy

$$T_{n+1}(x) = 2xT_n(x)-T_{n-1}(x).$$

This recurrence provides an efficient way to generate higher-degree Chebyshev polynomials.

3) Chebyshev Polynomial Properties

For $x\in[-1,1]$,

$$|T_n(x)|\leq1.$$

The degree and leading coefficient are

$$\deg(T_n)=n$$

and

$$\text{leading coefficient}=2^{n-1}, \qquad n\geq1.$$

The endpoint values are

$$T_n(1)=1$$

and

$$T_n(-1)=(-1)^n.$$

4) Chebyshev Roots

The $n$ roots of $T_n$ are

$$x_i = \cos\left( \frac{(2i-1)\pi}{2n} \right), \qquad i=1,\ldots,n.$$

These roots are called Chebyshev nodes on $[-1,1]$.

They are more closely spaced near the endpoints than near the center.

5) Chebyshev Minimax Property

Among all monic polynomials of degree $n$, the scaled Chebyshev polynomial

$$\frac{T_n(x)}{2^{n-1}}$$

has the smallest possible maximum absolute value on $[-1,1]$.

Therefore,

$$\max_{-1\leq x\leq1} \left| \prod_{i=1}^{n}(x-x_i) \right| = \frac{1}{2^{n-1}}$$

when $x_i$ are the Chebyshev roots.

6) Chebyshev Interpolation

Chebyshev Interpolation: Polynomial interpolation using Chebyshev nodes instead of equally spaced nodes.

Chebyshev nodes reduce the maximum interpolation error and suppress endpoint oscillations.

7) Chebyshev Nodes on a General Interval

To transform Chebyshev nodes from $[-1,1]$ to $[a,b]$, use

$$x_i = \frac{a+b}{2} + \frac{b-a}{2} \cos\left( \frac{(2i-1)\pi}{2n} \right),$$

for

$$i=1,\ldots,n.$$

8) Chebyshev Node-Polynomial Bound

For Chebyshev nodes on $[a,b]$,

$$\left| \prod_{i=1}^{n}(x-x_i) \right| \leq \frac{ \left(\dfrac{b-a}{2}\right)^n }{ 2^{n-1} }.$$

Therefore, if

$$|f^{(n)}(x)|\leq M$$

on $[a,b]$, then

$$|f(x)-P_{n-1}(x)| \leq \frac{M}{n!} \frac{ \left(\dfrac{b-a}{2}\right)^n }{ 2^{n-1} }.$$

3.4 Cubic Splines

1) Piecewise Polynomial

Piecewise Polynomial: A function defined by different polynomial expressions on different subintervals.

The points at which adjacent polynomial pieces meet are called knots.

2) Knot

Knot: A data node at which two adjacent spline pieces meet.

For ordered nodes,

$$x_1<x_2<\cdots<x_n,$$

the interior knots are

$$x_2,\ldots,x_{n-1}.$$

3) Linear Spline

Linear Spline: A piecewise linear function that joins consecutive data points with straight-line segments.

On $[x_i,x_{i+1}]$,

$$S_i(x) = y_i + \frac{y_{i+1}-y_i}{x_{i+1}-x_i} (x-x_i).$$

Linear splines are continuous but generally do not have continuous first derivatives at the knots.

4) Cubic Spline

Cubic Spline: A piecewise cubic function that interpolates the data and has continuous first and second derivatives.

On each interval $[x_i,x_{i+1}]$,

$$S_i(x) = y_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3.$$

5) Interpolation Conditions

Each spline piece must interpolate its two endpoints:

$$S_i(x_i)=y_i$$

and

$$S_i(x_{i+1})=y_{i+1}.$$

6) First-Derivative Continuity

At every interior knot,

$$S_{i-1}'(x_i) = S_i'(x_i), \qquad i=2,\ldots,n-1.$$

This condition prevents corners at the knots.

7) Second-Derivative Continuity

At every interior knot,

$$S_{i-1}''(x_i) = S_i''(x_i), \qquad i=2,\ldots,n-1.$$

This condition makes the curvature continuous.

8) Endpoint Conditions

The interpolation and continuity conditions leave two degrees of freedom.

Two additional endpoint conditions are required to determine a unique cubic spline.

9) Natural Cubic Spline

Natural Cubic Spline: A cubic spline whose second derivatives vanish at both endpoints.

$$S_1''(x_1)=0$$

and

$$S_{n-1}''(x_n)=0.$$

A unique natural cubic spline exists for any set of data points with distinct, ordered nodes.

10) Curvature-Adjusted Spline

Curvature-Adjusted Spline: A cubic spline with prescribed second derivatives at the endpoints.

$$S_1''(x_1)=v_1$$

and

$$S_{n-1}''(x_n)=v_n.$$

This allows direct control of the endpoint curvatures.

11) Clamped Cubic Spline

Clamped Cubic Spline: A cubic spline with prescribed first derivatives at the endpoints.

$$S_1'(x_1)=v_1$$

and

$$S_{n-1}'(x_n)=v_n.$$

A clamped spline is useful when the endpoint slopes are known.

12) Parabolically Terminated Spline

Parabolically Terminated Spline: A cubic spline whose first and last pieces have degree at most two.

$$d_1=0$$

and

$$d_{n-1}=0.$$

Equivalently,

$$c_1=c_2$$

and

$$c_{n-1}=c_n.$$

13) Not-a-Knot Spline

Not-a-Knot Spline: A cubic spline whose first two pieces form the same cubic polynomial and whose last two pieces form the same cubic polynomial.

$$d_1=d_2$$

and

$$d_{n-2}=d_{n-1}.$$

Equivalently, the third derivative is continuous at $x_2$ and $x_{n-1}$.

These two points are effectively not treated as knots.

14) Spline Interval Differences

Define

$$h_i=x_{i+1}-x_i$$

and

$$\Delta_i=y_{i+1}-y_i.$$

After solving for $c_1,\ldots,c_n$, the remaining coefficients are

$$d_i = \frac{c_{i+1}-c_i}{3h_i}$$

and

$$b_i = \frac{\Delta_i}{h_i} - \frac{h_i}{3} (2c_i+c_{i+1}).$$

15) Natural Spline System

For the interior coefficients,

$$h_{i-1}c_{i-1} + 2(h_{i-1}+h_i)c_i + h_ic_{i+1} = 3\left( \frac{\Delta_i}{h_i} - \frac{\Delta_{i-1}}{h_{i-1}} \right)$$

for

$$i=2,\ldots,n-1.$$

For a natural spline,

$$c_1=0 \qquad\text{and}\qquad c_n=0.$$

The resulting coefficient matrix is tridiagonal and strictly diagonally dominant.

16) Spline Advantages

Compared with one high-degree interpolating polynomial, cubic splines:

• Use low-degree polynomial pieces.
• Avoid severe global oscillations.
• Provide continuous slopes and curvatures.
• Require solving a structured tridiagonal system.
• Change mainly near modified data points.

3.5 Bézier Curves

1) Parametric Curve

Parametric Curve: A curve whose coordinates are functions of a parameter $t$.

$$B(t) = \bigl(x(t),y(t)\bigr), \qquad 0\leq t\leq1.$$

A parametric representation can describe curves that are not functions of $x$.

2) Cubic Bézier Curve

Cubic Bézier Curve: A parametric cubic curve determined by four points:

$$P_0,\ P_1,\ P_2,\ P_3.$$

The curve is

$$B(t) = (1-t)^3P_0 + 3(1-t)^2tP_1 + 3(1-t)t^2P_2 + t^3P_3,$$

where

$$0\leq t\leq1.$$

3) Endpoints

The first and last points are the endpoints of the curve.

$$B(0)=P_0$$

and

$$B(1)=P_3.$$

The curve generally does not pass through the two interior control points.

4) Control Points

Control Points: The points $P_1$ and $P_2$ that determine the shape and endpoint tangent directions of the curve.

The initial tangent is

$$B'(0) = 3(P_1-P_0).$$

The final tangent is

$$B'(1) = 3(P_3-P_2).$$

Thus:

• $P_1-P_0$ determines the starting direction.
• $P_3-P_2$ determines the ending direction.

5) Coordinate Form

Let

$$P_i=(x_i,y_i).$$

Then

$$\begin{aligned} x(t) ={}&(1-t)^3x_0 +3(1-t)^2tx_1\\ &+3(1-t)t^2x_2 +t^3x_3, \end{aligned}$$

and

$$\begin{aligned} y(t) ={}&(1-t)^3y_0 +3(1-t)^2ty_1\\ &+3(1-t)t^2y_2 +t^3y_3. \end{aligned}$$

6) Power-Basis Form

A cubic Bézier coordinate can also be written as

$$x(t)=x_0+b_xt+c_xt^2+d_xt^3,$$

where

$$b_x=3(x_1-x_0),$$ $$c_x=3(x_2-x_1)-b_x,$$

and

$$d_x=x_3-x_0-b_x-c_x.$$

The same formulas apply to $y(t)$.

7) Convex Hull Property

Convex Hull Property: A Bézier curve lies entirely within the convex hull of its control points.

This property makes the curve predictable and useful in geometric design.

8) Bézier Spline

Bézier Spline: A piecewise curve formed by joining multiple Bézier curves.

For positional continuity between two pieces,

$$P_3^{(i)} = P_0^{(i+1)}.$$

For matching tangent directions, the adjacent control points and shared endpoint should be collinear.

Bézier splines are widely used in:

• Computer graphics
• Font outlines
• Vector graphics
• Computer-aided design
• PDF and PostScript paths

Comparison of Interpolation Methods

Method	Representation	Main Advantage	Main Limitation
Lagrange	Single polynomial	Explicit formula	Expensive to update
Newton Divided Differences	Single nested polynomial	Efficient evaluation and updating	High degree may oscillate
Chebyshev Interpolation	Polynomial with optimized nodes	Reduces maximum error	Nodes must be chosen
Linear Spline	Piecewise linear	Simple and local	Not smooth at knots
Cubic Spline	Piecewise cubic	Smooth and stable	Requires endpoint conditions
Bézier Curve	Parametric cubic	Direct shape control	Does not automatically interpolate control points

Essential Concepts

1. Interpolation: Constructs a function that passes through given data points.
2. Interpolating Polynomial: The unique degree-$n-1$ or lower polynomial through $n$ distinct nodes.
3. Lagrange Basis: Equals $1$ at one node and $0$ at every other node.
4. Lagrange Interpolation: Expresses the polynomial as a weighted sum of basis polynomials.
5. Divided Difference: Recursively computes coefficients for Newton’s form.
6. Newton Interpolation: Provides a nested polynomial that is easy to evaluate and update.
7. Interpolation Error: The difference $f(x)-P(x)$.
8. Node Polynomial: The product $\prod_i(x-x_i)$ controlling part of the interpolation error.
9. Runge Phenomenon: Endpoint oscillation caused by high-degree interpolation at equally spaced nodes.
10. Chebyshev Polynomial: The polynomial $T_n(x)=\cos(n\arccos x)$.
11. Chebyshev Nodes: Optimized nodes that reduce the maximum interpolation error.
12. Spline: A piecewise polynomial joined at knots.
13. Cubic Spline: A piecewise cubic function with continuous first and second derivatives.
14. Natural Spline: Has zero second derivative at both endpoints.
15. Clamped Spline: Has specified slopes at both endpoints.
16. Not-a-Knot Spline: Uses the same cubic across the first and last interior knots.
17. Bézier Curve: A parametric cubic controlled by two endpoints and two control points.
18. Control Point: Determines a Bézier curve’s shape and tangent direction.
19. Convex Hull Property: Keeps a Bézier curve within the region formed by its control points.