Computational Physics

Lecture 9

Numerical Differentiation
 Taylor’s Expansion

Taylor’s Expansion

1
f ( x + h) = f ( x) + f ¢( x)h + f ¢¢( x)h + O(h )
2 3

2
1
f ¢( x)h = f ( x + h) - f ( x) - f ¢¢( x)h + O(h )
2 3

2
f ( x + h) - f ( x ) 1
f ¢( x) = - f ¢¢( x)h + O(h )
2

h 2
 Forward Difference method

Forward Difference Formula for f ¢(x)

f ( x + h) - f ( x )
f ¢( x) » error = O(h)
h

Geometrically
f (x)

f ¢(x)
f ( x + h) - f ( x )

x x+h
 Numerical Differentiation

Backward Difference Formula for f ¢(x)

Similarly
1
¢ ¢¢
f ( x - h) = f ( x ) - f ( x ) h + f ( x ) h + O ( h )
2 3

2
Geometrically

f ( x ) - f ( x - h) f (x)
f ¢( x) »
h f ( x ) - f ( x - h)
error = O(h) h

x-h x x
5
 Numerical Differentiation

Central Difference Formula for f ¢(x)

1 1 1 ( 4)
¢ ¢¢ ¢¢¢
f ( x + h) = f ( x ) + f ( x ) h + f ( x ) h + f ( x ) h + f ( x ) h + O ( h )
2 3 4 5

2 6 4!
1 1 1 ( 4)
–) f ( x - h) = f ( x) - f ¢( x)h + f ¢¢( x)h - f ¢¢¢( x)h + f ( x)h 4 + O(h 5 )
2 3

2 6 4!
1
f ( x + h) - f ( x - h) = 2hf ¢( x) ¢¢¢
+ f ( x)h 3
+ O(h ) 5
3
1
¢ ¢¢¢
2hf ( x) = f ( x + h) - f ( x - h) - f ( x)h + O(h )
3 5

3
 Numerical Differentiation

Central Difference Formula for f ¢(x)

Geometrically
f ( x + h) - f ( x - h)
f ¢( x) »
2h f (x)

f ¢(x)
error = O(h ) 2
f ( x + h) - f ( x - h)

2h

x-h x x+h x
 Numerical Differentiation

Example
f ( x) = x 3
(\ f ¢( x) = 3 x 2 , f ¢(1) = 3)

Calculate f’(1) using FD, BD, CD

 Numerical Differentiation

Example (cont)
FD:
f (1.1) - f (1) error = 0.31
h=0.1 f ¢(1) = = 3.31
0.1 ! error µ h

h=0.05 f (1.05) - f (1) error = 0.1525

f ¢(1) = = 3.1525
0.05
BD:
f (1) - f (0.9) error = 0.29
h=0.1 f ¢(1) = = 2.71
0.1
f (1) - f (0.95)
h=0.05 ¢
f (1) = = 2.8453 error = 0.1547
0.05
CD: f (1.1) - f (0.9)
h=0.1 f ¢(1) = = 3.01 error = 0.01 ! error µ h 2
0.2
f (1.05) - f (0.95)
h=0.05 ¢
f (1) = = 3.00250 error = 0.00250
0.1
9
 Numerical Differentiation

Example (cont)
• Remarks:
– FD, BD, CD each involves 2 function calls, 1
subtraction, and 1 division: same computation
time
– CD is the most accurate (hence, the most
recommended method)
– However, sometimes, CD cannot be applied

10
 Numerical Differentiation

Forward Difference Formula for f ¢¢(x)

1 1
f ( x + 2h) = f ( x) + f ¢( x)2h + f ¢¢( x)(2h) + f ¢¢¢( x)(2h) 3 + O(h 4 )
2

2 6
1 1
–2´ f ( x + h) = f ( x) + f ¢( x)h + f ¢¢( x ) h 2
+ f ¢¢¢( x ) h 3
+ O ( h 4
)
2 6
1 3 4 1
¢¢ 2
¢¢¢
f ( x + 2h) - 2 f ( x + h) = - f ( x ) + f ( x ) h [ 2 - 2 × ] + f ( x ) h [ - ] + O ( h ) 4

2 3 3
f ¢¢( x)h = f ( x + 2h) - 2 f ( x + h) + f ( x) - f ¢¢¢( x)h + O(h )
2 3 4

f ( x + 2h) - 2 f ( x + h) + f ( x )
f ¢¢( x) » 2
h
error = O(h) 11
 Numerical Differentiation

Backward Difference Formula for f ¢¢(x)

1 1
f ( x - 2h) = f ( x) - f ¢( x)2h + f ( x)(2h) - f ¢¢¢( x)(2h) 3 + O(h 4 )
¢¢ 2

2 6
1 1
–2´ f ( x - h ) = f ( x ) - f ¢( x ) h + f ¢¢ ( x ) h 2
- f ¢¢¢( x ) h 3
+ O ( h 4
)
2 6
1 3 4 1
f ( x - 2h) - 2 f ( x - h) = - f ( x) + f ¢¢( x)h [2 - 2 × ] - f ¢¢¢( x)h [ - ] + O(h 4 )
2

2 3 3
f ¢¢( x)h 2 = f ( x - 2h) - 2 f ( x - h) + f ( x) - f ¢¢¢( x)h 3 + O(h 4 )

f ( x ) - 2 f ( x - h) + f ( x - 2h)
f ¢¢( x) » 2
h
error = O(h) 12
 Numerical Differentiation

Central Difference Formula for f ¢¢(x)

1 1 1 ( 4)
f ( x + h) = f ( x) + f ¢( x)h + ¢¢ ¢¢¢
f ( x)h + f ( x)h + f ( x)h 4 + O(h 5 )
2 3

2 6 4!
1 1 1 ( 4)
+) f ( x - h) = f ( x) - f ¢( x)h + f ¢¢( x)h - f ¢¢¢( x)h + f ( x)h 4 + O(h 5 )
2 3

2 6 4!
1 ( 4)
f ( x + h) + f ( x - h) = 2 f ( x ) + f ¢¢( x)h 2
+ f ( x)h 4 + O(h 6 )
12

f ( x + h) + f ( x - h) - 2 f ( x )
¢¢
f ( x) = 2
+ O(h )
2

Similar remark on the selection of FD|BD|CD applies for f”(x)

13
 Numerical Differentiation

More Accurate FD Formula for f ¢(x)

1
f ( x + h) = f ( x) + f ¢( x)h + f ¢¢( x)h 2 + O(h 3 )
2
1 2 f ( x + 2h) - 2 f ( x + h) + f ( x )
¢
f ( x + h) = f ( x ) + f ( x ) h + h [ 2
+ O ( h )] + O ( h 3
)
2 h
1 1
= f ( x) + f ¢( x)h + f ( x + 2h) - f ( x + h) + f ( x ) + O ( h 3 )
2 2
1 3
- f ( x + 2h) + 2 f ( x + h) - f ( x )
f ¢( x) = 2 2 + O(h 2 )
h

- f ( x + 2h) + 4 f ( x + h) - 3 f ( x )
f ¢( x) = + O(h 2 )
2h
 Numerical Differentiation

More Accurate FD Formula (cont)

• Better accuracy can be achieved using this formula

• But, it involves more computations:
– 3 function calls, two +/–, one division
• Trade-off:
– More computation is the price you paid for better
accuracy
• Similar idea applies to more accurate BD formula
 Numerical Differentiation

Richardson Extrapolation
Idea:
• exact • Use different h to
= computed+ error estimate the truncation
error
• The truncation error is • Use extrapolation to
of the form: chk get more accurate
– where c is some result
constant

16
 Numerical Differentiation

Richardson Extrapolation (cont)

• Example: CD for f’(x)
f ( x + h) - f ( x - h)
¢
f ( x) = + O(h )
2

2h

• Using Different h (h1, h2)

exact = R1 + c h 1 1
2

= R2 + c h 2 2
2

• c1 and c2 could be different

17
 Numerical Differentiation

Richardson Extrapolation (cont)

• If c1 » c2 º c
R1 + ch = R2 + ch = exact
1
2 2
2
R2 - R1
c(h - h ) = R2 - R1
2 2
Þc= 2
1 2
h1 - h22
R2 - R1 2 R2 - R1
exact = R2 + 2 × h2 = R2 + × h2
2

h1 - h22
2 æ h1
2
ö
h2 çç 2 - 1÷÷
è h2 ø
R2 - R1
Þ exact » R2 +
( ) -1
h1 2
h2
18
 Numerical Differentiation

Example
• f(x) = 3
x.
Use CD with Richardson
extrapolation to compute f’(1)
h1 = 0.1 f ¢(1) = 3.01 ® R1
h2 = 0.05 f ¢(1) = 3.0025 ® R2

3.0025 - 3.01 Magic?

exact » 3.0025 + 2
= 3.0000 Coincidence?
æ 0.1 ö
ç ÷ -1
è 0.05 ø
19
Formula’s
Formula’s