Finite differences and interpolation · Lecture 16

Newton's Forward and Backward Interpolation

Estimating values between the entries of an equally spaced table: Newton's forward formula from $E^p = (1+\Delta)^p$ , the backward formula from $(1-\nabla)^{-p}$ , how to choose between them, how big the error is, and when interpolation goes wrong.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: the census is every ten years

A town's population (thousands) was counted every ten years. A planner needs the values for 1895 and 1925, when no count was taken.

The data are equally spaced ( $h = 10$ years) but there is no formula
1895 is near the start of the table; 1925 is near the end
Straight-line interpolation ignores the curvature that the differences show
We need a formula that uses the whole table, and an idea of its error

year $x$	population $y$
1891	46
1901	66
1911	81
1921	93
1931	101

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

2 / 21

Today's goals

Derive Newton's forward formula from $E^p = (1+\Delta)^p$ and the backward formula from $(1-\nabla)^{-p}$
Compute $p$ and evaluate the formulas from a difference table
Choose forward or backward according to where $x$ lies
Estimate the interpolation error and recognise the danger of extrapolation
Compare Newton's formulas with linear interpolation and with Lagrange

Last time

Difference tables, operators, $E = 1 + \Delta = e^{hD}$ .

Today

Expand $E^p$ to get values between the table entries.

Finite differences and interpolation · you are here

L15 · Finite Differences and Operators→L16 · Newton's Forward and Backward Interpolation→L17 · Lagrange and Divided-Difference Interpolation→L18 · Spline Interpolation and the Runge Phenomenon

Builds on: L15

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

3 / 21

Start here

The idea in one picture

We measured y only at five equally spaced x values.What is y between the dots, for example at x = 0.5?Draw one smooth polynomial through all five dots.Read the value off the curve. That is interpolation.Near the top of the table, build the curve from the first row of differences.Near the bottom, build it from the last row. Same curve, smaller error.

In plain words

We know a function only at a few points and need it in between
Pass one polynomial through all the points and read off the value
Newton's formulas build that polynomial from the difference table

New words today

interpolation: estimating between known points
extrapolation: estimating outside them (risky)
p = (x − x₀)/h: position measured in steps
forward / backward: start from the top or the bottom of the table

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

4 / 21

Deriving Newton's forward formula

Write x in steps from x₀

x = x_0 + ph \;\Longrightarrow\; p = \frac{x - x_0}{h}, \qquad y(x) = E^{p}y_0 = (1 + \Delta)^{p}y_0

Binomial series (any real p)

\begin{aligned} y(x_0 + ph) = {} & y_0 + p\,\Delta y_0 + \frac{p(p-1)}{2!}\Delta^2 y_0 \\ & + \frac{p(p-1)(p-2)}{3!}\Delta^3 y_0 + \cdots \end{aligned}

Uses the top diagonal $y_0, \Delta y_0, \Delta^2 y_0, \dots$
For integer $p$ it reproduces the table exactly
With $n + 1$ points: stops after $\Delta^n$ ; it is the degree- $n$ polynomial through all of them
Best when $x$ is near the start ( $0 < p < 1$ )

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

5 / 21

The method, step by step

Newton's forward interpolation, step by step

Check the $x$ values are equally spaced; note $h$
Build the forward difference table
Take $x_0$ as the table entry just below $x$ (near the start); compute $p = (x - x_0)/h$
Add terms $\dfrac{p(p-1)\cdots(p-k+1)}{k!}\,\Delta^k y_0$ for $k = 0, 1, 2, \dots$
Stop when the terms become negligible (or the table ends); the last term used estimates the error

Pseudocode

input x[0..n], y[0..n] (equal steps), X
h ← x[1] − x[0];  p ← (X − x[0]) / h
d ← copy of y          # top diagonal
sum ← d[0];  c ← 1
for k = 1 … n:
    for i = 0 … n−k:
        d[i] ← d[i+1] − d[i]
    c ← c·(p − k + 1) / k
    sum ← sum + c·d[0]
return sum

Each pass makes the next column of differences in place; only $d_0$ is used.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

6 / 21

Problem 1: the population in 1895 (forward)

Use the census table to estimate the population in 1895.

1

Differences:

\Delta y_0 = 20

,

\Delta^2 y_0 = -5

,

\Delta^3 y_0 = 2

,

\Delta^4 y_0 = -3

(top diagonal);

p = (1895 - 1891)/10 = 0.4

2

y = 46 + 0.4(20) + \dfrac{0.4(-0.6)}{2}(-5) + \dfrac{0.4(-0.6)(-1.6)}{6}(2) + \dfrac{0.4(-0.6)(-1.6)(-2.6)}{24}(-3)

3

= 46 + 8 + 0.6 + 0.128 + 0.1248

y(1895) \approx 54.85

thousand. The terms shrink fast (8, 0.6, 0.13, 0.12), so the estimate is reliable to about 0.1.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

7 / 21

Newton's backward formula

Measure from the last entry

x = x_n + ph \;(p < 0), \qquad y(x) = E^{p}y_n = (1 - \nabla)^{-p}y_n

Binomial series again

\begin{aligned} y(x_n + ph) = {} & y_n + p\,\nabla y_n + \frac{p(p+1)}{2!}\nabla^2 y_n \\ & + \frac{p(p+1)(p+2)}{3!}\nabla^3 y_n + \cdots \end{aligned}

$E = (1 - \nabla)^{-1}$ from $\nabla = 1 - E^{-1}$ (Lecture 15)
Uses the bottom diagonal $y_n, \nabla y_n, \nabla^2 y_n, \dots$
Best when $x$ is near the end ( $-1 < p < 0$ )
Same numbers as the forward table: $\nabla y_i = \Delta y_{i-1}$

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

8 / 21

Problem 2: the population in 1925 (backward)

Estimate the population in 1925.

1

Bottom diagonal:

\nabla y_n = 8

,

\nabla^2 y_n = -4

,

\nabla^3 y_n = -1

,

\nabla^4 y_n = -3

;

\;p = (1925 - 1931)/10 = -0.6

2

y = 101 + (-0.6)(8) + \dfrac{(-0.6)(0.4)}{2}(-4) + \dfrac{(-0.6)(0.4)(1.4)}{6}(-1) + \dfrac{(-0.6)(0.4)(1.4)(2.4)}{24}(-3)

3

= 101 - 4.8 + 0.48 + 0.056 + 0.1008

y(1925) \approx 96.84

thousand.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

9 / 21

How accurate? The interpolation error

Remainder after the term in Δⁿ (forward form); ξ lies in the data range

y(x) - P_n(x) = \frac{p(p-1)\cdots(p-n)}{(n+1)!}\,h^{n+1}f^{(n+1)}(\xi)

Practical estimate: the first neglected term

\text{error} \approx \frac{p(p-1)\cdots(p-n)}{(n+1)!}\,\Delta^{n+1}y_0

Small when $p$ is small: $x$ close to $x_0$
The product $p(p-1)\cdots(p-n)$ grows quickly outside the table: extrapolation is risky
Smooth data (small high differences) interpolate well
Same structure as the Taylor remainder (Lecture 3)

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

10 / 21

Explore: forward, backward and the danger zone

Each table row is one term of the formula
Blue band: the data range
Try 1960: the polynomial bends away; the estimate is meaningless
The sin x preset compares with the true function

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

11 / 21

Classical vs numerical

Same question, two approaches: population in 1895

Algebra

Classical (fit a formula)

Assume $y = a + bx + cx^2 + dx^3 + ex^4$
Solve a 5×5 Vandermonde system with entries up to $1931^4 \approx 1.4\times10^{13}$
Badly conditioned: digits are lost before we start

vs

Algorithm

Numerical (Newton forward)

Difference table: subtractions only
$p = 0.4$ , five short terms
$54.8528$ thousand, with a built-in error estimate

When the classical approach cannot work

Data from experiments and records

Population, rainfall or sensor logs have no formula to find. Even fitting one through the points with $x$ as large as 1931 makes a severely ill-conditioned system (Lecture 11). Newton's formula works in the shifted variable $p$ , where all numbers are small.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

12 / 21

Newton forward and backward in Python and C

Builds the difference table once
Forward: top diagonal, $p = (x - x_0)/h$
Backward: bottom diagonal, $p = (x - x_n)/h$
Prints every term, as in a written solution

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

13 / 21

When interpolation goes wrong

Limitations shown failing

High degree on equal spacing: 11 points of $1/(1 + 25x^2)$ ; near the ends the degree-10 polynomial swings far from the data
Extrapolation: outside the table the error term grows without control
Unequal spacing: the formulas do not apply at all
Noisy data: high differences are mostly noise, so extra terms add error

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

14 / 21

Practice

Practice problem

Problem 3"From the table

x

: 1, 2, 3, 4, 5 and

y

: 1, 8, 27, 64, 125, find

y(1.5)

by Newton's forward formula and

y(4.5)

by Newton's backward formula."

How to write a complete answer

Difference table: $\Delta$ : 7, 19, 37, 61; $\Delta^2$ : 12, 18, 24; $\Delta^3$ : 6, 6; $\Delta^4$ : 0
Forward, $p = 0.5$ : $1 + 0.5(7) + \tfrac{0.5(-0.5)}{2}(12) + \tfrac{0.5(-0.5)(-1.5)}{6}(6) = 3.375$
Backward, $p = -0.5$ : $125 - 0.5(61) + \tfrac{(-0.5)(0.5)}{2}(24) + \tfrac{(-0.5)(0.5)(1.5)}{6}(6) = 91.125$
Both exact ( $1.5^3$ , $4.5^3$ ), because $\Delta^4 = 0$ : say so as your check

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

15 / 21

When to use it

Newton's forward and backward formulas: method profile

Best case

Smooth, equally spaced tables; $x$ close to the start (forward) or end (backward)
Low-degree data: exact once the differences vanish
Hand calculation: the difference table organises all the work

Worst case

Extrapolation far outside the table
Many equally spaced points with a high-degree polynomial (Runge, Lecture 18)
Noisy measurements: high differences amplify noise

Best suited for

Tables of functions, physical properties (steam tables), census-type records
Deriving differentiation and integration formulas (Lectures 19–20)
Resampling equally spaced signals

Avoid when

Unequally spaced data (use Lagrange or divided differences, Lecture 17)
Long tables needing a smooth curve everywhere (use splines, Lecture 18)
Data with errors (use least squares, Lecture 23)

Rule of thumb: forward near the top, backward near the bottom, central formulas in the middle; never far outside the table.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

16 / 21

Comparative analysis: interpolation methods

Method	Spacing	Uses	Cost per $x$	Add a point	Best for
Linear	any	two neighbours	$O(1)$	trivial	quick look-ups, dense tables
Newton forward	equal	top diagonal	$O(n)$ after table	append a term	$x$ near the start
Newton backward	equal	bottom diagonal	$O(n)$ after table	append a term	$x$ near the end
Lagrange (L17)	any	all points	$O(n^2)$	start again	theory, few points
Divided differences (L17)	any	divided-difference table	$O(n)$ after table	append a term	unequal data
Cubic spline (L18)	any	tridiagonal solve	$O(\log n)$ after setup	redo solve	many points, smooth curves

All polynomial methods through the same $n + 1$ points give the same polynomial; they differ in convenience and rounding.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

17 / 21

Roadmap

Limitations, and where we fix them

Newton's formulas are exact for polynomials and simple to use, but they need equal spacing and they misbehave at high degree.

What it does well (keep this)

Difference table organises the work
Forward/backward choice by position
Error estimate from the next term
Basis for differentiation and integration formulas

LimitationHow it is overcomeWhere

Needs equally spaced

x

→

Lagrange and divided differences

Lecture 17 →

High degree oscillates near the ends

→

Piecewise cubics: splines

Lecture 18 →

We want slopes, not values

→

Differentiate the formula

Lecture 19 →

We want areas under the data

→

Integrate the formula: trapezoidal, Simpson

Lecture 20 →

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

18 / 21

Applications

Where this method runs in the real world

Click a card to see table interpolation in use.

$T$ (°C)	100	110	120	130
$p$ (kPa)	101.42	143.38	198.67	270.28

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

19 / 21

Checkpoint

Checkpoint · think, then discuss with your neighbourNewton's forward formula with

x_0 = 2

,

h = 0.5

. What is

p

for

x = 2.3

?

A

0.6

B

0.3

C

1.15

D

4.6

A.

p = (x - x_0)/h = (2.3 - 2)/0.5 = 0.6

.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

20 / 21

Summary

Key points

Forward: $y = y_0 + p\Delta y_0 + \tfrac{p(p-1)}{2!}\Delta^2 y_0 + \cdots$ , $p = (x - x_0)/h$
Backward: $y = y_n + p\nabla y_n + \tfrac{p(p+1)}{2!}\nabla^2 y_n + \cdots$ , $p = (x - x_n)/h$
Forward near the start, backward near the end; the first neglected term estimates the error
Only for equal spacing; extrapolation and high degree are dangerous

Opening problem: solved

Forward with $p = 0.4$ : 54.85 thousand in 1895. Backward with $p = -0.6$ : 96.84 thousand in 1925. Linear interpolation would have said 54.0 and 96.2.

Homework

From $x$ : 0, 1, 2, 3, 4 and $y$ : 1, 7, 23, 55, 109, find $y(0.5)$ and $y(3.5)$ .
The values of $\sin x$ at $x = 0.1, 0.2, 0.3, 0.4, 0.5$ are 0.09983, 0.19867, 0.29552, 0.38942, 0.47943. Find $\sin 0.15$ and $\sin 0.45$ and compare with a calculator.
Derive Newton's backward formula from $E = (1 - \nabla)^{-1}$ .
Use the lab tool to extrapolate the census to 1941 and 1951. Comment.

Next lecture

Lagrange and divided-difference interpolation. The same polynomial when the data are not equally spaced.

Md Mahbub E Noor

Lecture 16: Newton's Forward and Backward Interpolation

University of Barishal

21 / 21

Newton's Forward and Backward Interpolation

The problem: the census is every ten years

Today's goals

The idea in one picture

Deriving Newton's forward formula

Newton's forward interpolation, step by step

Problem 1: the population in 1895 (forward)

Newton's backward formula

Problem 2: the population in 1925 (backward)

How accurate? The interpolation error

Explore: forward, backward and the danger zone

Same question, two approaches: population in 1895

Classical (fit a formula)

Numerical (Newton forward)

Data from experiments and records

Newton forward and backward in Python and C

Limitations shown failing

Practice problem

Newton's forward and backward formulas: method profile

Comparative analysis: interpolation methods

Limitations, and where we fix them

Where this method runs in the real world

🌡️ Engineering property tables

📟 Look-up tables in embedded systems

🔭 Astronomical tables

🎞️ Frames, pixels and samples

Checkpoint

Summary