Round-off Error due to Arithmetic Operations

Addition – due to equaling the exponent.

Examples:

Summation:

Chopped:

1
Round-off Error due to Arithmetic Operations

Subtractive Cancellation (subtracting numbers of

almost equal size) – too few significant figures
left.

Examples:

2
Round-off Error due to Arithmetic Operations
Smearing
Occurs when individual terms are larger than summation
itself. Consider the exponential series with x = -10

Consider formulas such as:

2 3 4 5
x x x x
ex  1  x     
2! 3! 4! 5!
With 7-decimal-digit accuracy:
exact answer = 4.54 10-05
computed answer = – 6.26 10-05
(45 terms) wrong sign !
Largest intermediate terms are:
9th = –2,755.732 & 10th = 2,755.732
3
 Approximations and Rounding Errors
• Precautions:
– Sums of large and small numbers: due to equaling the
exponent. They are common in sums of infinite series
where the individual terms are very small when
compared with the accumulated sum. This error can be
reduced by summing first the small terms and using
double precision.
– Cancellation of the subtraction: The subtraction of very
similar numbers.
– Smearing: The individual terms are larger than the total
sum.
– Inner products: They are prone to rounding errors. Thus,
it is convenient to use double precision in this type of
calculations. n
 xi y i  x1y1  x2y 2    xnyn
i 1
4
 Chapter 4

Truncation Errors and the

Taylor Series

5
 Truncation Error
Error caused by the nature of the numerical technique
employed to approximate the solution.
Example:
Maclaurin series expansion of ex

2 3 4 5
x x x x
ex  1  x     
2! 3! 4! 5!
x2
If we use a truncated version of the series: e  1  x 
x
2!
x3 x 4 x5
Then the Truncation Error is:   
3! 4! 5!

6
 Taylor Series Expansion

Basic Idea:
Predict the value of a function, ƒ, at a point xi+1
based on the value of the function and all of its
derivatives, ƒ, ƒ', ƒ",… at a neighboring point xi

Given xi, ƒ(xi), ƒ'(xi), ƒ"(xi), ... ƒn+1(xi),

we can predict or approximate ƒ(xi+1)

7
 Taylor Series Expansion
General Form:

h2 h3 hn n
f (x i1 )  f (x i ) hf (x i )  f (x i )  f (x i )   f (x i )  R n
2! 3! n!

h = "step size" = xi+1 – xi

Rn = remainder to account for all other terms
h n 1 n 1
 f () with xi    xi+1
(n  1)!

= O (hn+1) with x not exactly known "on the order of hn+1

"
Note: f(x) must be a function with n+1 continuous derivatives

8
 Taylor Series Expansion

h2 hn n
f (x i1 )  f (x i )  h f (x i )  f (x i )   f (x i )  O(h n 1)
2! n!

 0th order T.S. approx. (n = 0): f(xi+1) = f(xi) + O (h1)

 1st order T.S. approx. (n = 1): f(xi+1) = f(xi) + hf '(xi) + O (h2)

2
h
 2nd order T.S. approx. (n = 2):f (x i1 )  f (x i )  h f (x i )  f (x i )  O (h n 1)
2!

 nth order T.S. approximation will be exact for an nth order

polynomial

9
 Taylor Series Expansion
f(x )
f(xi ) Zero order
f(xi+1 ) f(xi )

f(xi+1 ) f(xi )+f '(xi )h

f(xi+1 ) f(xi )+f '(xi )h+ )+f "(xi )h2/2!

f(xi+1 )

x
xi xi+1
h
10
 Taylor Series Expansion
General Form:

h2 h3 hn n
f (x i1 )  f (x i ) hf (x i )  f (x i )  f (x i )   f (x i )  R n
2! 3! n!

h = "step size" = xi+1 – xi

Rn = remainder to account for all other terms
h n 1 n 1
 f () with xi    xi+1
(n  1)!

= O (hn+1) with x not exactly known "on the order of hn+1

"
Note: f(x) must be a function with n+1 continuous derivatives

11
 Taylor Series Expansion
Remainder Term: What is ξ ?
If Zero- order approximation: f ( x i 1 )  f ( x i )  Ro Ro
f ' ( ) 
h

12
 Taylor Series Example
Use zero-order to fourth-order Taylor series expansions to
approximate the function.
f(x)= -0.1x4 – 0.15x3 – 0.5x2 – 0.25x +1.2
From xi = 0 with h =1. Predict the function’s value at xi+1 =1.

Solution
 f(xi)= f(0)= 1.2 , f(xi+1)= f(1) = 0.2 ………exact solution
• Zero- order approx. (n=0)  f(xi+1)=1.2 f ( x i 1 )  f ( x i )
Et = 0.2 – 1.2 = -1.0
• First- order approx. (n=1)  f(xi+1)= 0.95 f ( xi 1 )  f ( xi )  f ' ( xi )h
f(x)= -0.4x3 – 0.45x2 – x – 0.25, f’(0)= -0.25
f( xi+1)= 1.2- 0.25h = 0.95
Et = 0.2 - 0.95 = -0.75
13
 Taylor Series Example
• Second- order approximation (n=2)  f(xi+1)= 0.45
f ' ' ( x i )h 2
f ( x i 1 )  f ( x i )  f ( x i )h 
'

2!
f’’(x) = -1.2 x2 – 0.9x -1 , f’’(0)= -1
f( xi+1)= 1.2 - 0.25h - 0.5 h2 = 0.45
Et = 0.2 – 0.45 = -0.25
• Third-order approximation (n=3)  f(xi+1)= 0.3
f ' ' ( x i ) h 2 f ( 3) ( x i ) h 3
f ( x )  f ( x i )  f ( x i )h 
'

2! 3!
i 1

f( xi+1)= 1.2 - 0.25h - 0.5 h2 – 0.15h3 = 0.3

Et = 0.2 – 0.3 = -0.1

14
 Maclaurin Series
 Maclaurin series is a special case of Taylor series
with the center of expansion a = 0.
The Maclauri n series expansion of f ( x ) :
( 2) ( 3)
f ( 0 ) f ( 0) 3
f ( 0)  f ( 0) x 
'
x 
2
x  ...
2! 3!
If the series converge, we can write :
∞
1 (k )
f ( x)  ∑ k!
f ( 0) x k
k 0
2 3 4 5
x x x x
ex  1  x     
2! 3! 4! 5!

15
 Maclaurin Series – Example 1

Obtain Maclauri n series expansion of f ( x )  e x

f ( x)  e x f ( 0)  1
f ' ( x)  e x f ' ( 0)  1
f ( 2) ( x )  e x f ( 2 ) ( 0)  1
f (k ) ( x)  e x f ( k ) (0)  1 for k  1
∞ ∞
1 (k ) xk x2 x3
ex  ∑ k!
f ( 0) x  ∑
k
k!
 1 x 
2!

3!
 ...
k 0 k 0
The series converges for x  ∞.
16
 3
Taylor Series
Example 1
2.5
exp(x)
1+x+0.5x 2
2

1+x

1.5

1
1

0.5

0
-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

17
 Maclaurin Series – Example 2

Obtain Maclauri n series expansion of f ( x )  sin( x ) :

f ( x )  sin( x ) f ( 0)  0
f ' ( x )  cos( x ) f ' ( 0)  1
f ( 2 ) ( x )   sin( x ) f ( 2 ) ( 0)  0
f ( 3) ( x )   cos( x ) f ( 3) (0)  1
∞
f ( k ) ( 0) k x3 x5 x7
sin( x )  ∑ x  x     ....
k 0
k! 3! 5! 7!
The series converges for x  ∞.
18
4

3
x

1 x-x 3/3!+x 5/5!

0 sin(x)

-1
x-x 3/3!

-2

-3

-4
-4 -3 -2 -1 0 1 2 3 4

19
Numerical Differentiation from Taylor Series Expansion
Objective:
Evaluate the derivatives of function, ƒ(xi), without
doing it analytically.
When would we want to do this?
1. function is too complicated to differentiate
analytically:
2  cos(1  x ) 0.5x
e
1  0.5x
2. function is not defined by an equation,
i.e., given a set of data points (xi, ƒ(xi)), i=1,…,n
i 0 1 2 3 4
xi 1.0 3.0 5.0 7.0 9.0
ƒ(xi) 2.3 4.1 5.5 5.7 5.9
20
 Numerical Differentiation from Taylor Series Expansion

Taylor series:
h2 h3 hn n
f (x i1 )  f (x i ) hf (x i )  f (x i )  f (x i )   f (x i )  R n
2! 3! n!

h = "step size" = xi+1 – xi

Taylor series expanded backward:

21
 First Derivatives: Backward Difference

– First derivative with backward difference.

f ( xi 1 )  f ( xi )  f ' ( xi )( xi  xi 1 )

f ( xi )  f ( xi 1 )
f ' ( xi ) 
( xi  xi 1 )

22
 First Derivatives: Backward Difference

Backward Difference Approx.:

First Derivative:

h2
f (x i1 )  f (x i )  (x i 1  x i )f '(x i )  f "( )
2
Letting h = xi - xi-1
h2
f (x i1 )  f (x i )  hf '(x i )  f "()
2
h2
hf '(x i )  f (x i )  f (x i 1 )  f "()
2
f (x i )  f (x i1 )
f '(x)   O(h) 1st order error
h
first backward difference
23
 Example of 1st Backward FDD

Using data below calculate ƒ'(x1) :

i 0 1 2 3 4
xi 1.0 3.0 5.0 7.0 9.0
ƒ(xi) 2.3 4.1 5.5 5.7 5.9
First Backward Finite-Divided-Difference at x1:

f (x1 )  f (x 0 )
f '(x)   O(h)
h
4.1  2.3
f '(x1 )   O(h)
2

f ' (x1)  0.9 { + O (h) }

24
 First Derivatives: Forward Difference

Forward Difference Approx.:

First Derivative:
Use of the Taylor series
f ( xi 1 )  f ( xi )  f ' ( xi )( xi 1  xi )

f ( x i 1 )  f ( x i )
f ' ( xi ) 
( x i 1  x i )

1st order error

25
 First Derivatives: Central Difference

Central Difference Approx.:

First Derivative:
f '' ( xi ) 2 Substraction
f ( xi 1 )  f ( xi )  f ' ( xi )h  h 
2! f ( 3) ( xi ) 3
f ( xi 1 )  f ( xi 1 )  2f ' ( xi )h  h 
f '' ( xi ) 2 3!
f ( xi 1 )  f ( xi )  f ' ( xi )h  h 
2!

f ( xi 1 )  f ( xi 1 )
f ' ( xi ) 
2h

2nd order error

26
 Second Derivatives: Backward Difference
Second Derivative:
 x i2  x i  2
f (x i 2 )  f (x i )   x i 2  x i  f '(x)  f "(x i )
2!
+ O([xi-2– xi]3)

with h = xi– xi-1 and 2h = xi – xi-2

The 2nd order approximation to ƒ(xi-2) becomes:

ƒ(xi-2) = ƒ(xi) – 2hƒ'(xi) + 2h2 ƒ"(xi) +O (h3) [1]
2nd order approximation to ƒ(xi-1):
h2
f (x i1 )  f (x i )  hf '(x)  f "(x i )  O(h 3 ) [2]
2!
27
Second Derivatives: Backward Difference

Subtracting 2*[2] from [1] yields:

f(xi-2) – 2f(xi-1) = –f(xi) + h2f"(xi) + O (h3)
Rearranging:
h2ƒ"(xi) = f(xi) – 2f(xi-1) + f(xi-2) + O (h3)

f (x i )  2f (x i 1 )  f (x i 2 )  O(h 3 )
f "(x i )  1st order
h2 error
Second backward difference

28
 Example of 2nd Backward FDD

Using data below calculate ƒ"(x2) :

i 0 1 2 3 4
xi 1.0 3.0 5.0 7.0 9.0
ƒ(xi) 2.3 4.1 5.5 5.7 5.9

Second Backward Finite-Divided-Difference at x2:

f (x 2 )  2f (x1 )  f (x 0 )
f "(x 2 )  2
 O(h)
h
5.5  2* 4.1  2.3
f "(x 2 )  2
 O(h)
2

f " (5.0)  - 0.1 { + O (h) }

29
Numerical Differentiation: Second Derivatives
- Higher order divided differences.

f '' ( xi ) 2
f ( xi 1 )  f ( xi )  f ' ( xi )h  h 
2!
f '' ( xi ) 2 addition
f ( xi 1 )  f ( xi )  f ' ( xi )h  h 
2!

- Second finite central divided difference

30
 Other Forms of Numerical Differentiation
Forward:
 (x i1 )   (x i )
f '(x i )   O(h)
h 1st order error
 (x i  2 )  2 (x i 1 )   (x i )
f "(x i )  2
 O(h)
h
- f ( xi  2 )  4 f ( xi 1 ) -3 f ( xi )
f '(x i ) = + O(h 2 ) 2nd order
2h error
Centered:
 (x i1 )   (x i1 )
f '(x i )   O(h 2 )
2h 2nd order error
 (x i 1 )  2 (x i )   (x i 1 )
f "(x i )   O(h 2 )
h2
31
Numerical Differentiation: Second Derivatives
- Higher order divided differences.

f '' ( xi ) 2
f ( xi 1 )  f ( xi )  f ' ( xi )h  h 
2!
f '' ( xi ) 2 addition
f ( xi 1 )  f ( xi )  f ' ( xi )h  h 
2!

- Second finite central divided difference

32
Other Forms of Numerical Differentiation

What points are used for each form?

Backward:
…, ƒ(xi-2), ƒ(xi-1), ƒ(xi), ƒ(xi+1), ƒ(xi+2), …

Forward:
…, ƒ(xi-2), ƒ(xi-1), ƒ(xi), ƒ(xi+1), ƒ(xi+2), …

Centered:
…, ƒ(xi-2), ƒ(xi-1), ƒ(xi), ƒ(xi+1), ƒ(xi+2), …

33
 Taylor Series and Truncation errors
Questions:
• Which is a better approximation?
Forward, Centered, or Backward?

• Why?

• When would you use which?

Note:
We also can get higher order forward, centered, and
backward difference derivative approximations
[C&C Chapter 23, tabulated in Figs. 23.1-3]

34
Example Problem 4.4

35
 Error Propagation
Error Propagation
Errors which appear because we are basing current
calculations on previous calculations which also incurred
some form of error.
Example:

36
 Error Propagation
Stability and Condition Number
Numerically Unstable: Computations which are so
sensitive to round-off errors that errors grow
uncontrollably during calculations.
Condition: sensitivity to such uncertainty; "well
conditioned" vs. "ill conditioned"
Condition Number: measure of the condition; i.e.,
extent to which uncertainty in x is amplified by ƒ(x).

C.N.  1 ===> "well-conditioned"

C.N. >> 1 ===> "ill-conditioned"

37
 Example Combining Roundoff and Truncation Error

Determine h to minimize the total error of a forward finite-

divided difference approximation for:
f (x i1 )  f (x i )
f '(x) 
• Truncation Error: h
f (x i1 )  f (x i ) h xi    xi+1
f '(x)   f "()
h 2
• Round-off Error:
f  x   fˆ  x    f  x  with  = machine epsilon.

ˆ  (x  h).
(1   )   (x i (1  ) h
).
As a result: f ' =
i
  "()
h 2
Roundoff   (x i  h)    (x i )   2  (x i )
Error h h
38
Example Combining Roundoff and Truncation Error

 Total error  = truncation error + roundoff error 

h 2 f (x i )
E = | Total Error |  f "() +
2 h

NOTE: Truncation error decreases as h decreases

Round-off error increases as h decreases

39
Example Combining Roundoff and Truncation Error

40
46