## Applications to Cubic Spline Interpolation

**Cubic spline interpolation** constructs a smooth piecewise cubic polynomial curve passing through a given set of data points. The method reduces to solving a system of linear equations.

### Problem Setup

Given data points (x0, y0), (x1, y1), ..., (xn, yn) with x0 < x1 < ... < xn, find cubic polynomials S_i(x) on each interval [x_i, x_{i+1}] such that:

1. **S_i(x_i) = y_i** and **S_i(x_{i+1}) = y_{i+1}** (interpolation)
2. **S_{i-1}(x_i) = S_i(x_i)** (continuity)
3. **S_prime_{i-1}(x_i) = S_prime_i(x_i)** (first derivative continuity)
4. **S_doubleprime_{i-1}(x_i) = S_doubleprime_i(x_i)** (second derivative continuity)

### The Linear System

Let M_i = S_doubleprime(x_i) be the second derivatives at the knots. The continuity conditions lead to a **tridiagonal system**:

**AM = b**

where A is a tridiagonal matrix with entries based on the spacings h_i = x_{i+1} - x_i.

### Natural Boundary Conditions

For a **natural spline**, we set M_0 = M_n = 0, giving an (n-1) x (n-1) tridiagonal system that can be solved in O(n) time using the Thomas algorithm.

### Why Linear Algebra?

The spline coefficients are determined by solving this tridiagonal band matrix system. This is a direct application of linear algebra:
- The matrix A is sparse, symmetric, and positive definite
- Efficient O(n) algorithms exist specifically because of the tridiagonal structure

### Applications

- Computer graphics (smooth curve design)
- CAD/CAM systems
- Data fitting and smoothing
- Geographic information systems