Interpolation
Open in the Padhaiko app3.1 Polynomial Interpolation
Given a discrete table of data points where , polynomial interpolation constructs a unique polynomial of degree at most passing through every data point ( for ) in order to estimate at intermediate points.
3.1.1 Finite differences (Forward, backward, central and divided differences)
For equally spaced nodes with constant step size , three finite-difference operators are defined:
Forward, Backward, and Central Difference Operators
Let for :
- Forward Difference ():
- Backward Difference ():
- Central Difference ():
(Notice that , , and compute the same numerical differences in a difference table; they differ only in how each entry is indexed!)
For unequally spaced nodes , finite differences depend on the varying intervals and are replaced by divided differences:
Newton's Divided Differences
- Zeroth-order:
- First-order:
- -th order:
Divided differences are symmetric in their arguments (independent of point ordering), and the -th divided difference of a degree- polynomial is constant.
3.1.2 Interpolation with equally spaced intervals: Newton’s forward and backward difference interpolation, Stirling’s and Bessel’s central difference interpolation
Let and define the dimensionless shift parameter (or ) relative to the reference node.
Newton's Forward and Backward Difference Formulas
- Newton's Forward Difference Formula (best near the beginning of the table, close to , with ):
- Newton's Backward Difference Formula (best near the end of the table, close to , with ):
When interpolating near the middle of an equally spaced table, central difference formulas average adjacent differences around (the central node) for better accuracy and symmetry:
Stirling's and Bessel's Central Difference Formulas
Let .
- Stirling's Formula (best when , or centered at ):
- Bessel's Formula (best when , centered around ):
3.1.3 Interpolation with unequally spaced intervals: Newton’s divided difference interpolation, Lagrange interpolation
When data points are unequally spaced, two standard formulations yield the exact same unique degree- interpolating polynomial:
Newton's Divided Difference and Lagrange Formulas
- Newton's Divided Difference Polynomial:
- Lagrange Interpolation Polynomial:
Each Lagrange basis polynomial satisfies and for .
| Aspect | Newton's Divided Difference | Lagrange Interpolation |
|---|---|---|
| Adding a New Data Point | Incremental: simply adds one extra term without recomputing earlier terms | Non-incremental: every basis polynomial must be recomputed |
| Computational Cost | Builds a difference table once; fast to evaluate at multiple values | No table needed; convenient for one-off evaluation or symbolic proofs |
| Error / Degree Check | Next higher divided difference directly estimates truncation error | Degree reduction is not immediately visible from individual terms |
3.2 Least square method of curve fitting
Experimental data () often contain measurement noise, so passing a high-degree polynomial through every point causes wild oscillations. Least-squares curve fitting finds a smooth approximating curve (with ) that minimizes the sum of squared residuals:
Setting for each parameter produces the normal equations.
3.2.1 Linear form and forms reducible to linear form
For a straight line , minimizing gives the linear normal equations:
Many non-linear two-parameter models are reducible to linear form via logarithms or reciprocals:
| Model | Linearized Form | Substitutions | Parameter Recovery |
|---|---|---|---|
| Exponential: | |||
| Exponential base-: | |||
| Power law: | |||
| Hyperbolic: | |||
| Saturation growth: |
3.2.2 Quadratic form and forms reducible to quadratic form
For a parabola , minimizing gives three quadratic normal equations:
Forms reducible to quadratic form apply an algebraic transformation to map three-parameter models onto :
- Gaussian / Exponential-quadratic: (with ).
- Log-quadratic power model: (with ).
- Reciprocal quadratic: (with ).
3.2.3 Higher degree polynomials
Generalizing to an -th degree polynomial (), setting () yields an symmetric linear system:
In practice, degrees or are used because higher-degree normal matrices (Hilbert-type matrices) become ill-conditioned.
3.3 Cubic spline interpolation
Instead of fitting a single high-degree polynomial across all nodes (which suffers from Runge's oscillation phenomenon), cubic spline interpolation fits a separate cubic polynomial on each sub-interval () such that the piecewise curve is smooth up to the second derivative:
- Interpolation: and .
- First-derivative continuity: at all interior knots .
- Second-derivative continuity: at all interior knots .
- Boundary conditions (for a natural cubic spline): and .
3.3.1 Equally spaced interval
When step size is constant for all , the tridiagonal system for the second derivatives simplifies cleanly:
Natural Cubic Spline (Equally Spaced Interval)
With uniform spacing :
- Tridiagonal system for interior knots ():
- Cubic piece on :
3.3.2 Unequally spaced interval
When sub-interval widths vary from segment to segment, the general tridiagonal relation weights each equation by and :
Natural Cubic Spline (Unequally Spaced Interval)
Let for .
- Tridiagonal system for interior knots ():
- Cubic piece on :
Worked Out Examples
3.1
Given the equally spaced data below, construct the finite difference table and estimate at using Stirling's central difference interpolation formula:
Constructing the central/forward difference table: Taking (closest to ) with , we have (valid for Stirling's formula since ):
| — | ||||||
| — | — | |||||
| — | — | — | ||||
| — | — | — | — |
Reading along the central horizontal band around :
Applying Stirling's interpolation formula at :
Using Stirling's central difference formula, .
3.2
Find the interpolating polynomial and estimate from the following unequally spaced data using Newton's divided difference formula:
Constructing the divided difference table:
- First divided differences:
- Second divided differences:
- Third divided difference:
| DD | DD | DD | ||
|---|---|---|---|---|
| — | ||||
| — | — | |||
| — | — | — |
Forming and evaluating at :
Substituting :
The interpolating polynomial is , and .
3.3
Fit a second-degree (quadratic) polynomial by the method of least squares to the following data:
Tabulating the required sums ():
Notice and by symmetry.
Solving the normal equations: Substituting the sums into the three quadratic normal equations:
Multiplying the first equation by gives . Subtracting from the third equation:
Substituting back into :
The least-squares quadratic curve is .
Exercises
Exercise — Interpolation
Compare Newton's divided difference interpolation and Lagrange interpolation for unequally spaced data. Why is cubic spline interpolation preferred over a single high-degree polynomial, and what boundary conditions define a natural cubic spline?
Comparing Newton's divided difference and Lagrange interpolation:
- Both formulas produce the exact same unique degree- interpolating polynomial for distinct points.
- Newton's divided difference builds a tabular hierarchy incrementally: adding a new data point requires only one new diagonal of differences and one extra term, leaving earlier terms unchanged.
- Lagrange interpolation expresses directly as a linear combination without a difference table, which is convenient for a single evaluation or analytical derivation, but adding a new data point forces every basis polynomial to be recomputed from scratch.
Why cubic splines are preferred and natural boundary conditions:
- Fitting one high-degree polynomial through many equally spaced points causes severe boundary oscillations (Runge's phenomenon), whereas a cubic spline pieces together smooth low-degree (cubic) polynomials over sub-intervals while enforcing continuity of , , and at every interior knot.
- A natural cubic spline imposes zero curvature (zero second derivative) at both endpoints:
Newton's divided difference is incremental when adding points and reveals degree/error via higher differences, while Lagrange needs no difference table but must be rebuilt if points are added. Cubic splines avoid high-degree polynomial oscillations by joining piecewise cubics with continuous , and a natural cubic spline sets .
Using the data from Example 3.1 ( and ), estimate using Newton's backward difference interpolation formula.
Reading the backward differences at : Since is near the end of the table, take , , and
From the bottom upward-sloping diagonal of the finite difference table:
Substituting into Newton's backward difference formula:
Using Newton's backward difference formula, .
Find using Lagrange interpolation from the following unequally spaced data:
Computing the Lagrange basis polynomials at : With nodes :
Evaluating :
By Lagrange interpolation, .
Fit an exponential curve of the form by the method of least squares to the data:
Linearizing : Taking the natural logarithm of both sides:
Computing the transformed sums ():
| — |
Solving the linear normal equations:
Using Cramer's rule / elimination:
Recovering :
The fitted exponential curve is .
Construct the natural cubic spline for the unequally spaced data points , , and , and estimate and .
Setting up interval widths and the spline equation for : Here and , so:
For a natural cubic spline, and . The single interior knot equation at is:
Substituting , , :
Writing the piecewise cubics on and on :
- On ():
- On ():
Evaluating at and :
The natural cubic spline pieces are on and on , giving and .