Finite differences and interpolation · Lecture 15

Finite Differences and Operators

Data in a table, no formula in sight: difference tables, the operators Δ, ∇, δ, E, μ and D, where each one comes from, how they are related, and why E = e^{hD} is the key to every interpolation, differentiation and integration formula that follows.

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: a table with no formula

A machine logs one reading per second. We have only the numbers.

Is there a polynomial behind the data? Of which degree?
What was the value at $t = 2.5$ s, between two readings?
One entry looks odd. Is it a recording error? Which one?
All three questions are answered by one tool: repeated subtraction of neighbouring values

$t$ (s)	0	1	2	3	4	5	6
$y$	1	0	5	22	57	116	205

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

2 / 21

Today's goals

Build a forward difference table and read the forward and backward diagonals
Use the fact that the $n$ -th differences of a degree- $n$ polynomial are constant
Define the operators $\Delta, \nabla, \delta, E, \mu, D$ and derive the relations between them
Show why $E = e^{hD}$ connects differences with derivatives
Find missing entries and locate errors in a table

Last time

Module 3: linear systems. Interpolation will need them (splines, Lecture 18).

Today

A new kind of data: values at equally spaced points. A small algebra of operators makes them easy to handle.

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

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

3 / 21

Start here

The idea in one picture

A table of values: here y = x³ at equally spaced x.Subtract each value from the one below it: first differences Δy.Each difference sits between the two numbers it came from.Do the same to the Δy column: second differences.The arrows always point from a pair to its difference.Once more: third differences.For a cubic the third differences are constant. The table reveals the pattern in the data.

In plain words

Data often come as a table at equally spaced x
Subtracting neighbours, again and again, shows the pattern in the table
These differences are the building blocks of the next lectures

New words today

forward difference Δ: next value − this value
difference table: the triangle of repeated differences
operator: a rule applied to a whole column (Δ, ∇, E)
equally spaced: the same step h between x values

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

4 / 21

The forward difference table

Equally spaced points and their values

x_i = x_0 + ih, \qquad y_i = f(x_i)

Forward differences, applied again and again

\begin{aligned} \Delta y_i &= y_{i+1} - y_i, \qquad \Delta^2 y_i = \Delta y_{i+1} - \Delta y_i \\ \Delta^{k} y_i &= \Delta^{k-1}y_{i+1} - \Delta^{k-1}y_i \end{aligned}

Write each difference between the two numbers it came from
Each column is one entry shorter than the one before
The top diagonal $y_0, \Delta y_0, \Delta^2 y_0, \dots$ feeds the forward formula (Lecture 16)
The bottom diagonal feeds the backward formula

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

5 / 21

Explore: the difference table

Type any equally spaced data
Orange cells: the diagonal a formula would use
The tool reports when a column becomes constant
Try $2^x$ : the differences never become constant

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

6 / 21

Problem 1: the difference table of the opening data

Build the forward difference table for

y = 1, 0, 5, 22, 57, 116, 205

at

t = 0, 1, \dots, 6

.

$t$	$y$	$\Delta y$	$\Delta^2 y$	$\Delta^3 y$	$\Delta^4 y$
0	1	−1	6	6	0
1	0	5	12	6	0
2	5	17	18	6	0
3	22	35	24	6	—
4	57	59	30	—	—
5	116	89	—	—	—
6	205	—	—	—	—

Shown in "row" layout: row $i$ holds $\Delta^k y_i$ . Third differences are all 6 and fourth differences are 0: the data come from a cubic.

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

7 / 21

Differences of a polynomial

For a polynomial of degree n with leading coefficient a

\Delta^{n}\big(a x^n + \cdots\big) = a\,n!\,h^n \;(\text{a constant}), \qquad \Delta^{n+1} = 0

Why: each Δ lowers the degree by one

\Delta x^n = (x+h)^n - x^n = n h\,x^{n-1} + \cdots

Opening data: $\Delta^3 y = 6 = a \cdot 3! \cdot 1^3$ , so $a = 1$ : a cubic $t^3 + \cdots$
This is how we "see" the degree in a table
Real data: differences become small and noisy rather than exactly zero
Example: with $h = 1$ , $\Delta x^3 = 3x^2 + 3x + 1$ and $\Delta^2 x^3 = 6x + 6$

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

8 / 21

Six operators, all defined on $f(x)$

Shift and the three differences

\begin{aligned} E f(x) &= f(x+h) & \Delta f(x) &= f(x+h) - f(x) \\ \nabla f(x) &= f(x) - f(x-h) & \delta f(x) &= f(x+\tfrac h2) - f(x-\tfrac h2) \end{aligned}

Average and derivative

\mu f(x) = \tfrac12\big[f(x+\tfrac h2) + f(x-\tfrac h2)\big], \qquad D f(x) = f'(x)

$E$ : shift one step forward; $E^{-1}$ one step back; $E^{p}$ : shift by $ph$
$\Delta$ forward, $\nabla$ backward, $\delta$ central difference
$\mu$ : mean of the two half-step neighbours
All are linear: $\Delta(af + bg) = a\Delta f + b\Delta g$ , so they can be added, multiplied and inverted like numbers

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

9 / 21

Where the relations come from

Express every operator in terms of

E

, using only the definitions.

1

\Delta f(x) = f(x+h) - f(x) = Ef(x) - f(x)

, so

\boxed{\Delta = E - 1}

, i.e.

E = 1 + \Delta

2

\nabla f(x) = f(x) - f(x-h) = f(x) - E^{-1}f(x)

, so

\boxed{\nabla = 1 - E^{-1}}

3

\delta f(x) = E^{1/2}f(x) - E^{-1/2}f(x)

, so

\boxed{\delta = E^{1/2} - E^{-1/2}}

;

\;

similarly

\boxed{\mu = \tfrac12(E^{1/2} + E^{-1/2})}

4

Taylor:

Ef(x) = f(x+h) = f + hf' + \tfrac{h^2}{2!}f'' + \cdots = \big(1 + hD + \tfrac{(hD)^2}{2!} + \cdots\big)f

, so

\boxed{E = e^{hD}}

Everything is a function of

E

, and

E = e^{hD}

links the differences with derivatives:

hD = \ln E = \ln(1 + \Delta)

.

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

10 / 21

The relations at a glance

	in terms of $E$	in terms of $\Delta$	in terms of $hD$
$E$	$E$	$1 + \Delta$	$e^{hD}$
$\Delta$	$E - 1$	$\Delta$	$e^{hD} - 1$
$\nabla$	$1 - E^{-1}$	$1 - (1+\Delta)^{-1}$	$1 - e^{-hD}$
$\delta$	$E^{1/2} - E^{-1/2}$	$\Delta(1+\Delta)^{-1/2}$	$2\sinh(hD/2)$
$\mu$	$\tfrac12(E^{1/2} + E^{-1/2})$	$(1 + \tfrac12\Delta)(1+\Delta)^{-1/2}$	$\cosh(hD/2)$

Useful identities that follow: $\Delta = E\nabla = \nabla E = \delta E^{1/2}$ ; $\;\Delta - \nabla = \Delta\nabla = \delta^2$ ; $\;\mu^2 = 1 + \tfrac14\delta^2$ ; $\;(1 + \Delta)(1 - \nabla) = 1$ .

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

11 / 21

Problem 2: proving operator identities

Prove (a)

\Delta - \nabla = \Delta\nabla = \delta^2

, (b)

\mu^2 = 1 + \tfrac14\delta^2

, (c)

(1 + \Delta)(1 - \nabla) = 1

.

1

(a)

\Delta - \nabla = (E - 1) - (1 - E^{-1}) = E - 2 + E^{-1}

2

\;\;\Delta\nabla = (E - 1)(1 - E^{-1}) = E - 1 - 1 + E^{-1} = E - 2 + E^{-1}

, and

\delta^2 = (E^{1/2} - E^{-1/2})^2 = E - 2 + E^{-1}

✓

3

(b)

\mu^2 = \tfrac14(E + 2 + E^{-1}) = \tfrac14(E - 2 + E^{-1}) + 1 = \tfrac14\delta^2 + 1

✓

4

(c)

(1 + \Delta)(1 - \nabla) = E \cdot E^{-1} = 1

✓

Method: rewrite both sides in terms of

E

, then compare. It works for every identity of this kind.

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

12 / 21

Problem 3: a missing entry

The table

y = 1, 3, 9, \;?, 81

(at equal steps) comes from a cubic. Find the missing value.

1

A cubic has

\Delta^4 y = 0

, i.e.

(E - 1)^4 y_0 = 0

2

Expand:

(E^4 - 4E^3 + 6E^2 - 4E + 1)\,y_0 = y_4 - 4y_3 + 6y_2 - 4y_1 + y_0 = 0

3

Substitute:

81 - 4y_3 + 6(9) - 4(3) + 1 = 0

, so

4y_3 = 124

y_3 = 31

. (Check: the differences 2, 6, 22, 50; 4, 16, 28; 12, 12 are constant at third order.)

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

13 / 21

Using differences to check data

Finding an error in a table

Add an error $\varepsilon$ to one entry: it spreads through the table
In the $k$ -th differences it appears as $\varepsilon$ times binomial coefficients with alternating signs
Third differences become $6 + \varepsilon(1, -3, 3, -1) = 7, 3, 9, 5$
The pattern points to the wrong entry; subtract $\varepsilon$ to correct it

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

14 / 21

Classical vs numerical

Same question, two approaches: "what is $y$ at $t = 2.5$ ?"

Algebra

Classical (find the formula)

Guess a cubic $y = at^3 + bt^2 + ct + d$ and solve a 4×4 system (Lecture 12)
Get $y = t^3 - 2t + 1$
$y(2.5) = 15.625 - 5 + 1 = 11.625$

vs

Differences

Numerical (operators)

$y(2.5) = E^{2.5}y_0 = (1 + \Delta)^{2.5}y_0$
Expand with the top diagonal $1, -1, 6, 6$ (Lecture 16)
$= 1 + 2.5(-1) + \tfrac{2.5(1.5)}{2}(6) + \tfrac{2.5(1.5)(0.5)}{6}(6) = 11.625$

When the classical approach cannot work

Real measurements: no formula exists

Census counts, temperatures or stock prices are not a polynomial; guessing "the formula" is impossible. The difference table works directly on the numbers, tells us how smooth the data are, and gives interpolation (Lecture 16), derivatives (Lecture 19) and integrals (Lecture 20).

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

15 / 21

The difference table in Python and C

Each column is computed from the previous one
Prints the table in row layout
Reports the first column that is constant
Change the data: try the census or $2^x$

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

16 / 21

Practice

Practice problem

Problem 4"Define the operators

E

,

\Delta

,

\nabla

and

\delta

. Show that

E = e^{hD}

and hence that

hD = \log(1 + \Delta)

. Prove that

\Delta - \nabla = \Delta\nabla

."

How to write a complete answer

Give each definition as a formula acting on $f(x)$ with step $h$
Expand $f(x + h)$ by Taylor's series and factor out $f$ : $Ef = e^{hD}f$
Then $1 + \Delta = E = e^{hD}$ , so $hD = \log(1 + \Delta) = \Delta - \tfrac{\Delta^2}{2} + \tfrac{\Delta^3}{3} - \cdots$
For the identity, write both sides in terms of $E$ : each equals $E - 2 + E^{-1}$

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

17 / 21

Roadmap

What the operators will do for us

Every formula of Module 4 and 5 is an operator identity expanded as a series:

What it does well (keep this)

Difference tables reveal smoothness and degree
Operators obey ordinary algebra
$E = e^{hD}$ links differences and derivatives
Errors in tables leave a recognisable pattern

LimitationHow it is overcomeWhere

Values between table points

→

E^p = (1+\Delta)^p

: Newton forward;

(1-\nabla)^{-p}

: backward

Lecture 16 →

Unequally spaced data

→

Divided differences and Lagrange

Lecture 17 →

Derivatives from a table

→

hD = \ln(1 + \Delta)

, central forms with

\delta

Lecture 19 →

Areas under tabulated data

→

Integrate

E^p

term by term: trapezoidal, Simpson

Lecture 20 →

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

18 / 21

Applications

Where this method runs in the real world

Click a card to see differences at work.

month	1	2	3	4	5
sales	120	135	152	171	192
$\Delta y$	—	15	17	19	21
$\Delta^2 y$	—	—	2	2	2

pixel $x$	1	2	3	4	5	6
brightness $I$	20	22	21	180	182	181
$\Delta I$	2	−1	159	2	−1	—

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

19 / 21

Checkpoint

Checkpoint · think, then discuss with your neighbourFor

y = 2, 5, 10, 17

(equal steps), what is

\Delta^2 y_0

?

A

2

B

3

C

5

D

0

A.

\Delta y = 3, 5, 7

;

\Delta^2 y = 2, 2

. Constant second differences: the data come from a quadratic (

y = x^2 + 1

at

x = 1, 2, 3, 4

).

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

20 / 21

Summary

Key points

$\Delta^k y$ of a degree- $n$ polynomial: constant for $k = n$ , zero for $k > n$
$\Delta = E - 1$ , $\nabla = 1 - E^{-1}$ , $\delta = E^{1/2} - E^{-1/2}$ , $\mu = \tfrac12(E^{1/2} + E^{-1/2})$
$E = e^{hD}$ (Taylor), so $hD = \ln(1+\Delta) = -\ln(1-\nabla)$
Prove identities by writing everything in terms of $E$ ; find missing values from $\Delta^{n+1} = 0$

Opening problem: solved

Third differences are constant (6), so the data are a cubic with leading coefficient 1 ( $y = t^3 - 2t + 1$ ); $y(2.5) = 11.625$ ; an error of +1 in 22 shows up as $7, 3, 9, 5$ in the third differences.

Homework

Build the difference table for $y = 2, 9, 28, 65, 126$ ( $x = 1, \dots, 5$ ). What is the degree? Find $y(6)$ by extending the table.
Prove $\nabla = 1 - E^{-1}$ , $\delta = \Delta E^{-1/2}$ and $E\nabla = \Delta$ .
Find the missing term: $y = 2, 4, 8, \;?, 32$ (assume a cubic).
Evaluate $\Delta^2(x^3)$ with $h = 1$ and $\Delta(e^{ax})$ with step $h$ .

Next lecture

Newton's forward and backward interpolation. Expand $E^p$ to find values between the table entries.

Md Mahbub E Noor

Lecture 15: Finite Differences and Operators

University of Barishal

21 / 21

Finite Differences and Operators

The problem: a table with no formula

Today's goals

The idea in one picture

The forward difference table

Explore: the difference table

Problem 1: the difference table of the opening data

Differences of a polynomial

Six operators, all defined on $f(x)$

Where the relations come from

The relations at a glance

Problem 2: proving operator identities

Problem 3: a missing entry

Finding an error in a table

Same question, two approaches: "what is $y$ at $t = 2.5$ ?"

Classical (find the formula)

Numerical (operators)

Real measurements: no formula exists

The difference table in Python and C

Practice problem

What the operators will do for us

Where this method runs in the real world

⚙️ Babbage's difference engine

📉 Time series: differencing to remove a trend

🖼️ Edges in images

🎙️ Speech features: delta coefficients

Checkpoint

Summary

Finite Differences and Operators

The problem: a table with no formula

Today's goals

The idea in one picture

The forward difference table

Explore: the difference table

Problem 1: the difference table of the opening data

Differences of a polynomial

Six operators, all defined on f(x)f(x)f(x)

Where the relations come from

The relations at a glance

Problem 2: proving operator identities

Problem 3: a missing entry

Finding an error in a table

Same question, two approaches: "what is yyy at t=2.5t = 2.5t=2.5?"

Classical (find the formula)

Numerical (operators)

Real measurements: no formula exists

The difference table in Python and C

Practice problem

What the operators will do for us

Where this method runs in the real world

⚙️ Babbage's difference engine

📉 Time series: differencing to remove a trend

🖼️ Edges in images

🎙️ Speech features: delta coefficients

Checkpoint

Summary

Six operators, all defined on $f(x)$

Same question, two approaches: "what is $y$ at $t = 2.5$ ?"