Transcript x - Electrical and Computer Engineering

ECE 204 Numerical Methods for Computer Engineers
Error Analysis
Douglas Wilhelm Harder
Department of Electrical and Computer Engineering
University of Waterloo
Copyright © 2007 by Douglas Wilhelm Harder. All rights reserved.
Error Analysis
• In this topic, we will look at:
– how fixed-point iteration can be used to solve
certain problems numerically, and
– some of the various limitations of iterative
numerical methods including:
• determining convergence,
• slow convergence, and
• non-convergence
Absolute and Relative Errors
• What are the absolute and relative errors
of 3.14 as an approximation to p?
3.14  p  0.001593
3.14  p
p
 0.0005070
Absolute and Relative Errors
• What is the maximum and minimum
tolerance of this resistor?
• The resistor is labeled as 220 W with a
tolerance (relative error) of 5% (or 0.05)
• Recall that |x| = y implies that either
x = y or –x = y
Absolute and Relative Errors
• Thus, to find the maximum and minimum
possible resistances, we must solve the
following two equations:
220 W  r
 0.05  r  209 W
220 W
r  220 W
 0.05  r  231 W
220 W
• Thus, the actual resistance must lie on the
interval [209 W, 231 W]
Absolute and Relative Errors
• Assume that a digital ammeter has a
three-digit readout which is assumed to be
correct
• What is the largest absolute and relative
error of the reading 24.3 mA?
Absolute and Relative Errors
• If the reading is correct, then the actual
current could be anywhere in the range
[24.25, 24.35]
• Thus, the largest absolute error of the
reading is 0.05 mA or 50 mA
Absolute and Relative Errors
• To determine the maximum relative, we
need only calculate the relative error of
24.3 as an approximation to these two end
points:
24.3  24.25
 0.002062
24.25
24.3  24.35
 0.002053
24.25
• Thus, the relative error is no larger than
0.0021 for this reading
Significant Digits
• Of 3.1415 and 3.1416, which has more
significant digits as an approximation to
p = 3.141592653589793...?
3.1415  p
p
3.1416  p
p
 0.00002949  0.00005  0.5  10
4
 0.000002338  0.000005  0.5  10 5
Convergence
• If a sequence x1, x2, x3, x4, ... converges to
some value x ≠ 0, then both the absolute
and relative errors of xk go to 0 as k → ∞
• That is,
xk  x
0
lim xk  x  0 and lim
k 
k 
x
Convergence
• Also, if the relative error of a sequence
x1, x2, x3, x4, ... goes to 0 then the absolute
error must also go to 0, and
• If the absolute error of a sequence
x1, x2, x3, x4, ... goes to 0, then the relative
error goes to 0 so long as the sequence
does not converge to 0
Convergence
• For example, the sequence
3, 3.1, 3.14, 3.141, 3.1415, 3.14159, 3.141592, 3.1415926, ...
converges to p, and the absolute error of
xk (where k represents the number of
places after the decimal) is less than 10–k
• The relative error of xk must therefore be
less than 0.31831·10–k
Convergence
• While it is always more useful to speak of
relative errors, it is often easier,
mathematically, to show that absolute
errors converge to zero
• We will see this in the 2nd half of this
course (Newton’s method, etc.)