Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Roundo↵ error propagation
If roundo↵ error caused by u stayed as big as u ! no problem! Does it?
Example
Multiplication:
(x ⌦ y) ⌦ z ⌘ fl(fl(x ⇥ y) ⇥ z) = [xy(1 + 1)] ⇥ z(1 + 2)
where | i |< u
(x ⌦ y) ⌦ z = xyz(1 + 1)(1 + 2)
| (x⌦y)⌦z xyz |=|(1+ 1)(1+ 2) 1|(1+u)2 1⇡2u xyz
no problem with floating point multiplication!
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
How about addition?
If x,y are machine numbers (contain no roundo↵ error themselves) x y ⌘fl(x+y)=[x+y](1+ 1)
| x y (x + y) |= | 1| u x+y
so no problem.
But what if they have roundo↵ errors from previous computations?
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Floating point addition
fl(x) fl(y) = [x(1+ 1)+y(1+ 2)](1+ 3)
| fl(x) fl(y) (x+y) | x + y
|x| |(1+ 1)(1+ 3) 1| |x + y|
+ |y| |(1+ 2)(1+ 3) 1| |x + y|
|x|+|y|((1+u)2 1) |x + y|
⇠ 2u|x|+|y| |x + y|
but |x|+|y| can be large if x,y are nearly equal and opposite! |x+y|
If 2 nearly equal numbers (with error) are subtracted, the relative error can be greatly magnified!
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Severe cancellation or subtractive cancellation
can greatly magnify the relative error so lose lots of precision in final answer
Remedy? ! change formula/algorithm to avoid subtraction quadratic formula
Example
Estimating the budget surplus/deficit
Example
x = b±pb2 4ac 2a
what if b2 4ac?
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Example
sample variance
1 Xn
s 2 = n 1
( x i x ̄ ) 2
!
xi2 nx ̄2
w h e r e x ̄ = 1 P n
n i=1
Alternative form:
i=1
x i
s2= 1
Xn n 1 i=1
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
=) try to avoid calculations that rely on cancellation ... or use higher precision
Example
quadruple precision (not in MATLAB)
Example
in a symbolic environment
(not possible for big problems)
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Stability of Algorithms
Since some error (roundo↵) is usually present, we must have algorithms where the error doesn’t grow too fast
Some growth is inevitable
Sn = Pnk=1 ak typically has Perror ⇠ n1/2u and is guaranteed to have (absolute) error < (n 1)u k | ak | +O(u2)
but exponential growth ( error ⇠ Knu,K > 1 ) is disastrous!
Example
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
An unstable recurrence relation …
To compute the Rintegral I = R 1 x 100 dx , we can derive the recurrence
relation for In = 1 xn dx 0 x+2
In = 1 2In 1 n
and run for n = 1..100, starting from I0 = log(3/2) • Demo BadRecurrence.m
0 x+2
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Remedy?
run recurrence backwards!
• Demo GoodRecurrence.m
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Roundo↵ vs. truncation error
Sometimes there is a tradeo↵ between truncation error and roundo↵
Example
forward di↵erence approximation to the derivative
Approximate f 0(x) by f (x+h) f (x) h
• Demo ForwardDifference.m
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Explanation
In the absence of roundo↵ error, there is still a truncation error. Use Taylor series for f (x + h), assuming f 2 C 2
! truncation error K1h (K1 depends on f and x)
In the absence of roundo↵ error, approximation becomes exact as h ! 0
Using our model for roundo↵ error, get additional error K2u/h + K3u (K2, K3 depend on f and x)
Use bounds (worst case analysis) ! minimum total (absolute) error at an optimal h ⇡ u1/2, ignoring constants
=) no point using h smaller than this!
Roundo↵ error sets a lower bound to achievable accuracy
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
Summary: main e↵ects of roundo↵ error
after Afternotes on Numerical Analysis (Stewart) Roundo↵ error
1 can accumulate over long computations : inevitable
2 can reveal other errors by cancellation ! try to do the problem another way
3 can grow so fast it swamps the actual answer ! try to do the problem another way
Example
sums
Example
recurrence relations
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
End of Topic
Numerical Methods & Scientific Computing: lecture notes
Errors
Error propagation
End of Lecture 8