PadhaikoAll subjects

Interpolation

Numerical Methods (ENSH 252)

Open in the Padhaiko app

3.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:

Definition

Forward, Backward, and Central Difference Operators

Let for :

  1. Forward Difference ():
  1. Backward Difference ():
  1. 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:

Definition

Newton's Divided Differences

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.

Definition

Newton's Forward and Backward Difference Formulas

  1. Newton's Forward Difference Formula (best near the beginning of the table, close to , with ):
  1. 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:

Definition

Stirling's and Bessel's Central Difference Formulas

Let .

  1. Stirling's Formula (best when , or centered at ):
  1. 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:

Definition

Newton's Divided Difference and Lagrange Formulas

  1. Newton's Divided Difference Polynomial:
  1. Lagrange Interpolation Polynomial:

Each Lagrange basis polynomial satisfies and for .

AspectNewton's Divided DifferenceLagrange Interpolation
Adding a New Data PointIncremental: simply adds one extra term without recomputing earlier termsNon-incremental: every basis polynomial must be recomputed
Computational CostBuilds a difference table once; fast to evaluate at multiple valuesNo table needed; convenient for one-off evaluation or symbolic proofs
Error / Degree CheckNext higher divided difference directly estimates truncation errorDegree 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:

Common Models Reducible to Linear Form (Y = A + BX)
ModelLinearized FormSubstitutionsParameter 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 :

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:

  1. Interpolation: and .
  2. First-derivative continuity: at all interior knots .
  3. Second-derivative continuity: at all interior knots .
  4. 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:

Definition

Natural Cubic Spline (Equally Spaced Interval)

With uniform spacing :

3.3.2 Unequally spaced interval

When sub-interval widths vary from segment to segment, the general tridiagonal relation weights each equation by and :

Definition

Natural Cubic Spline (Unequally Spaced Interval)

Let for .


Worked Out Examples

Example 3.1

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 ):

Finite Difference Table Centered at x0 = 30
—
——
———
————

Reading along the central horizontal band around :

Applying Stirling's interpolation formula at :

Answer:

Using Stirling's central difference formula, .

Example 3.2

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:
Newton Divided Difference Table
DD DD DD
—
——
———

Forming and evaluating at :

Substituting :

Answer:

The interpolating polynomial is , and .

Example 3.3

3.3

Fit a second-degree (quadratic) polynomial by the method of least squares to the following data:

Tabulating the required sums ():

Summation Table for Quadratic Least-Squares Fit

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 :

Answer:

The least-squares quadratic curve is .


Exercises

Exercise — Interpolation

Question 1

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:
Answer:

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 .

Question 2

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:

Answer:

Using Newton's backward difference formula, .

Question 3

Find using Lagrange interpolation from the following unequally spaced data:

Computing the Lagrange basis polynomials at : With nodes :

Evaluating :

Answer:

By Lagrange interpolation, .

Question 4

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 ():

Least-Squares Sums for Exponential Fit
—

Solving the linear normal equations:

Using Cramer's rule / elimination:

Recovering :

Answer:

The fitted exponential curve is .

Question 5

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 :

Answer:

The natural cubic spline pieces are on and on , giving and .

← Solution of System of Linear Algebraic EquationsNumerical Differentiation and Integration →