SC-03

Course 3

Spline Interpolation and Data Fitting

Learn piecewise polynomial interpolation to avoid Runge's phenomenon, construct smooth cubic splines, and apply least squares methods for data fitting.

Learning Objectives

Understand piecewise interpolation and its advantages
Construct cubic spline interpolating functions
Apply different boundary conditions for splines
Formulate and solve least squares fitting problems
Understand orthogonal polynomials and their properties
Compare interpolation versus fitting approaches

1. Piecewise Interpolation

High-degree polynomial interpolation can lead to oscillations (Runge's phenomenon). Piecewise interpolation uses low-degree polynomials on each subinterval.

Definition 3.1: Piecewise Polynomial Interpolation

Given a partition $a = x_0 < x_1 < \cdots < x_n = b$ , a piecewise polynomial of degree k, denoted $S_k(x)$ , is a function such that on each subinterval $[x_{i-1}, x_i]$ , $S_k(x)$ is a polynomial of degree at most $k$ .

Example: Piecewise Linear Interpolation

On each subinterval $[x_{i-1}, x_i]$ :

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

Theorem 3.1: Piecewise Linear Error

If $f \in C^2[a, b]$ , the error in piecewise linear interpolation satisfies:

|f(x) - S_1(x)| \leq \frac{h^2}{8} \max_{a \leq x \leq b} |f''(x)|

where $h = \max_i (x_i - x_{i-1})$ .

Definition 3.2: Piecewise Cubic Hermite Interpolation

On each subinterval $[x_{i-1}, x_i]$ , use a cubic polynomial matching $f(x_{i-1}), f(x_i), f'(x_{i-1}), f'(x_i)$ .

Error: $|f(x) - H(x)| \leq \frac{h^4}{384} \max |f^{(4)}(x)|$

2. Cubic Spline Interpolation

Definition 3.3: Cubic Spline

A cubic spline $s(x)$ on $[a, b]$ with nodes $a = x_0 < x_1 < \cdots < x_n = b$ satisfies:

$s(x_i) = y_i$ for $i = 0, 1, \ldots, n$ (interpolation)
$s(x)$ is a cubic polynomial on each $[x_i, x_{i+1}]$
$s(x) \in C^2[a, b]$ (continuous second derivative)

Definition 3.4: Boundary Conditions

Common boundary conditions for cubic splines:

Natural (Free): $s''(a) = s''(b) = 0$
Clamped: $s'(a) = f'(a), \; s'(b) = f'(b)$
Periodic: $s'(a) = s'(b), \; s''(a) = s''(b)$

Theorem 3.2: Spline System

Let $h_i = x_{i+1} - x_i$ and $m_i = s'(x_i)$ . The spline conditions give a tridiagonal system:

(1 - \alpha_i) m_{i-1} + 2m_i + \alpha_i m_{i+1} = \beta_i, \quad i = 1, \ldots, n-1

where $\alpha_i = \frac{h_{i-1}}{h_{i-1} + h_i}$ and $\beta_i$ depends on the function values.

Note:

The tridiagonal system can be solved efficiently in $O(n)$ time using theThomas algorithm (tridiagonal matrix algorithm).

Remark:

Cubic splines are widely used in computer graphics, CAD systems, and data visualization because they provide smooth curves with minimal oscillation.

3. Least Squares Fitting

Unlike interpolation (which passes through all points), fitting finds a function that best approximates the data in some sense, allowing for measurement errors.

Definition 3.5: Least Squares Problem

Given data $(x_i, y_i)$ for $i = 1, \ldots, n$ , find parameters $(a, b)$ for $\phi(x) = a + bx$ that minimize:

\sum_{i=1}^{n} \delta_i^2 = \sum_{i=1}^{n} (y_i - a - bx_i)^2

Theorem 3.3: Normal Equations

Setting partial derivatives to zero gives the normal equations. In matrix form with $X = (\mathbf{1}, \mathbf{x})$ and $\alpha = (a, b)^T$ :

X^T X \alpha = X^T y

The solution is $\alpha = (X^T X)^{-1} X^T y$ .

Example: Linear Regression

For data $(1, 2), (2, 3), (3, 5), (4, 4)$ :

Design matrix: $X = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & 4 \end{pmatrix}$

Normal equations: $X^T X = \begin{pmatrix} 4 & 10 \\ 10 & 30 \end{pmatrix}$ , $X^T y = \begin{pmatrix} 14 \\ 39 \end{pmatrix}$

Solution: $a = 1.5, b = 0.7$ , so $y = 1.5 + 0.7x$

Definition 3.6: General Least Squares

For fitting $\phi(x) = \sum_{k=0}^{m} a_k P_k(x)$ where $P_k$ are basis functions:

\min_{a_0, \ldots, a_m} \sum_{i=1}^{n} w_i \left( y_i - \sum_{k=0}^{m} a_k P_k(x_i) \right)^2

where $w_i > 0$ are weights.

4. Best Approximation

Definition 3.7: Best Square Approximation

For continuous functions with inner product $(f, g) = \int_a^b \rho(x) f(x) g(x) \, dx$ , find $p_n \in P_n$ minimizing:

\|f - p_n\| = \sqrt{(f - p_n, f - p_n)}

Remark:

The Gram matrix for polynomial approximation on $[0, 1]$ with $\rho(x) = 1$ is theHilbert matrix:

H_{ij} = \frac{1}{i + j - 1}

This matrix is extremely ill-conditioned, making the problem numerically unstable.

5. Orthogonal Polynomials

Using orthogonal polynomials as basis functions eliminates the ill-conditioning problem.

Definition 3.8: Orthogonal Polynomials

Polynomials $\{P_0, P_1, P_2, \ldots\}$ are orthogonal on $[a, b]$ with weight $w(x)$ if:

(P_m, P_n) = \int_a^b w(x) P_m(x) P_n(x) \, dx = 0 \quad \text{for } m \neq n

Legendre Polynomials

Orthogonal on $[-1, 1]$ with $w(x) = 1$ :

P_0 = 1, \; P_1 = x, \; P_2 = \frac{1}{2}(3x^2 - 1), \; P_3 = \frac{1}{2}(5x^3 - 3x)

Recurrence: $(n+1)P_{n+1} = (2n+1)xP_n - nP_{n-1}$

Chebyshev Polynomials

Orthogonal on $[-1, 1]$ with $w(x) = 1/\sqrt{1 - x^2}$ :

T_n(x) = \cos(n \arccos x)

Recurrence: $T_{n+1} = 2xT_n - T_{n-1}$

Laguerre Polynomials

Orthogonal on $[0, \infty)$ with $w(x) = e^{-x}$ :

L_n(x) = e^x \frac{d^n}{dx^n}(x^n e^{-x})

Theorem 3.4: Three-Term Recurrence

Any sequence of orthogonal polynomials satisfies a three-term recurrence relation:

P_{k+1}(x) = (x - \alpha_k) P_k(x) - \beta_{k-1} P_{k-1}(x)

where $\alpha_k = \frac{(xP_k, P_k)}{(P_k, P_k)}$ and $\beta_k = \frac{(P_{k+1}, P_{k+1})}{(P_k, P_k)}$ .

Practice Quiz

Spline and Fitting Quiz

Questions

Correct

Accuracy

A cubic spline

s(x)

[a, b]

with

n+1

nodes must satisfy

s(x) \in

Easy

Not attempted

How many conditions are needed to uniquely determine a cubic spline with

n+1

nodes?

Medium

Not attempted

What is the main advantage of piecewise linear interpolation over high-degree polynomial interpolation?

Easy

Not attempted

In least squares fitting, we minimize:

Easy

Not attempted

The normal equations for linear least squares fitting

y = a + bx

can be written as:

Medium

Not attempted

Natural cubic spline boundary conditions specify:

Medium

Not attempted

Legendre polynomials

P_n(x)

are orthogonal on

[-1,1]

with weight function:

Medium

Not attempted

The error in piecewise linear interpolation is

O(h^k)

where

k

equals:

Hard

Not attempted

The Hilbert matrix

H_{ij} = 1/(i+j-1)

in best approximation is problematic because:

Hard

Not attempted

Chebyshev polynomials

T_n(x)

satisfy the recurrence

T_{n+1}(x) =

Hard

Not attempted

Frequently Asked Questions

What's the difference between interpolation and fitting?

Interpolation passes exactly through all data points, whilefitting finds the best approximation that may not pass through any point.

Use interpolation when data is exact; use fitting when data contains measurement errors.

Why are cubic splines preferred over higher-degree splines?

Cubic splines provide a good balance: they're smooth enough ( $C^2$ continuity) for most applications while avoiding the oscillations of higher-degree polynomials. They also have the minimum curvature property among all interpolating curves.

When should I use clamped vs natural boundary conditions?

Clamped (specified derivatives): When you know the slopes at endpoints, such as from physical constraints or additional measurements.

Natural (zero second derivatives): When no endpoint information is available. The spline behaves like a physical spline that relaxes at the ends.

Why use orthogonal polynomials for fitting?

Orthogonal polynomials diagonalize the Gram matrix, eliminating the ill-conditioning problem. Each coefficient can be computed independently, and adding higher-degree terms doesn't change previously computed coefficients.

How do I choose between different orthogonal polynomial families?

Choose based on the domain and weight function that matches your problem:

Legendre: Uniform weight on finite interval
Chebyshev: Minimizes maximum error, good for uniform approximation
Laguerre: Semi-infinite domain with exponential decay
Hermite: Entire real line with Gaussian weight