FINITE DIFFERENCES AND
INTERPOLATION
FINITE DIFFERENCES
• Finite Difference Operators
• Relation between the operators
• Newton’s Forward Difference Interpolation
Formula
• Newton’s Backward Difference Interpolation
Formula
• Lagrange’s Interpolation Formula
• Divided Differences
• Newton’s divided difference formula
Polynomial Interpolation
Using Simple Operators
Shift Operator Ef(x) = f(x + h)
Forward Difference Op. Df(x) = f(x + h) - f(x)
Backward Difference Op. f(x) = f(x) - f(x - h)
Central Difference Op. f(x) = f(x + h/2) - f(x - h/2)
Average Operator f(x) = {f(x + h/2) + f(x - h/2)}/2
Derivative Operator Df(x) = df(x)/dx
Compound Operators
• EDf(x) = E{Df(x)}
= E{f(x+h) - f(x)}
= Ef(x+h) - Ef(x)
= f(x + 2h) - f(x + h)
• Now try DEf(x) and see if the result is the same.
Powers of operators
• EEf(x) = E2f(x) = f(x + 2h)
• EEE ... Ef(x) = Enf(x) = f(x + nh)
E-1f(x) = f(x - h)
E-nf(x) = f(x - nh)
E1/2f(x) = f(x + h/2)
E0f(x) = f(x)
Relationships between operators
Df(x) = f(x + h) - f(x) = Ef(x) - f(x) = (E - 1)f(x)
Therefore, D=E-1
Verify these relationships:
= 1 - E-1 = E1/2 - E-1/2
= (E1/2 + E-1/2)/2 2=D-
Relationship between E and D
• Ef(x) = f(x + h)
= f(x) + hf (x) + h2 f (x)/2! + h3 f (x)/3! + . . .
= f(x) + hD f(x) + h2/2! D2f(x) + h3/3! D3f(x) + . . .
= (1 + hD + h2D2/2! + h3D3/3! + . . .)f(x)
ehD = f(x)
Therefore, E = ehD
• You can try to derive the following:
= 2sinh(hD/2)
= cosh(hD/2)
Definition
• Interpolation is the process of finding equations
to approximate straight lines and curves that best
fit given sets of data.
9
WHAT IS INTERPOLATION?
Given (x0,y0), (x1,y1), …, (xn,yn), finding the value of ‘y’ at a
value of ‘x’ in (x0, xn) is called interpolation.
10
NEWTON GREGORY FORWARD
INTERPOLATION
x-x
For convenience we put p = 0 and f0 = y0. Then we have
h
p(p – 1) 2 p(p - 1)(p - 2) 3
P(x0 + ph) = y o + pDy 0 + D y0 + D y0 + +
2! 3!
p(p - 1)(p - 2) L (p - n + 1) n
D y0
n!
11
NEWTON GREGORY BACKWARD
INTERPOLATION FORMULA
x xn
Taking p = ,
h
we get the interpolation formula as:
P(xn+ph) = y0 + pyn + p(p 1)
2!
2yn + p(p 1)(p 2)
3!
3yn + ….. +
p (p 1) (p 2) (p n 1)
n!
nyn
12
Difference tables: An easy way to compute powers of
either the forward or backward difference operator is to
construct a difference table using a spread sheet. Here is
the forward difference table for the data from the example.
X F(X) D D2 D3 D4
0 0.00 0.21 0.09 0.06 0.04
1 0.21 0.30 0.15 0.10 -0.03
2 0.51 0.45 0.25 0.07 0.01
3 0.96 0.70 0.32 0.08 -0.02
4 1.66 1.02 0.40 0.06 0.02
5 2.68 1.42 0.46 0.08
6 4.10 1.88 0.54
7 5.98 2.42
8 8.40
Example
Estimate f (3.17)from the data using Newton
Forward Interpolation.
x: 3.1 3.2 3.3 3.4 3.5
f(x): 0 0.6 1.0 1.2 1.3
14
Solution
First let us form the difference table
x y Dy D2y D3y D4y
3.1 0
0.6
3.2 0.6 - 0.2
0.4 0
3.3 1.0 - 0.2 0.1
0.2 0.1
3.4 1.2 -0.1
0.1
3.5 1.3
Here x0 = 3.1, x = 3.17, h = 0.1.
15
Example
Estimate f(42) from the following data using newton
backward interpolation.
x: 20 25 30 35 40 45
f(x): 354 332 291 260 231 204
16
Solution
The difference table is:
x f f 2f 3f 4f 5f
20 354
- 22
25 332 - 19
- 41 29
30 291 10 -37
- 31 -8 45
35 260 2 8
- 29 0
40 231 2
- 27
45 204
Here xn = 45, h = 5, x = 42 and p = - 0.6
17
Solution
Newton backward formula is:
p(p + 1) 2 p(p + 1)(p + 2) 3 p(p + 1)(p + 2)(p + 3) 4
P(x) = yn+pyn+ yn+ y n+ yn +
2! 3! 4!
p(p + 1)(p + 2)(p + 3)(p + 4) 5
yn
5!
(-0.6)(0.4) (-0.6)(0.40(1.4) (-0.6)(0.4)(1.4)(2.4)
P(42)=204+(-0.6)(-27)+ 2+ 0+ 8+
2 6 24
(-0.6)(0.4)(1.4)(2.4)(3.4)
45 = 219.1430
120
Thus, f(42) = 219.143
18
NEWTONS DIVIDED DIFFERENCE
• What is divided difference?
f[x1] – f[x0]
f[x0,x1] = x1 – x0
f[x0,x1,x2] = f[x1,x2] – f[x0,x1]
x2 – x1
f[x0, x1, …, xk-1,xk] = f[x1,x 2 - xk ] - f[x 0 ,...,xk-1]
xk - x 0
for k = 3, 4, ….. n.
These Ist, IInd... and kth order differences are denoted
by Df, D2f, …, Dkf.
• The divided difference interpolation polynomial is:
P(x) = f(x0) + (x – x0) f [x0, x1] + (x –x0) (x – x1) f [x0,
x1 , x2] + ……+ (x – x0)…..(x –xn-1) f[x0, x1, …, xn]
19
Example
• For the data
x: –1 0 2 5
f(x) :7 10 22 235
• Find the divided difference polynomial and estimate f(1).
20
Solution
X f Df D 2f D 3f
-1 7
3
0 10 1
6 2
2 22 13
71
5 235
P(x) = f(x0) + (x – x0) f[x0, x1] + (x – x0) ( x – x1) f [x0, x1, x2] +
(x – x0) (x – x1) (x – x2) f [x0, x1, x2, x3]
= 7 + (x +1) 3 + (x +1) (x – 0) 1 + (x +1) (x –0) (x – 2) 2
= 2x3 – x2 + 10
P (1) = 11
21
Use Newton’s divided-difference method to compute
f(2) from the experimental data shown in the
following table:
22
23
Lagrange Interpolation
Lagrange Interpolating takes the following general
formula:
f N (x)
24
Linear Interpolation
25
Example
Use a Lagrange interpolating polynomial of the first
and second order to evaluate f(2) on the basis of the
data:
x0 = 1 f(x0) = 0
x1 = 4 f(x1) = 1.386294
x2 = 6 f(x2) = 1.791760
26
Quadratic Interpolation
For 3 points of data
27
Example – cont.
28
Example – cont.
29
