Transcript Error Analysis

Error Analysis
Part 1
The Basics
1
Key Concepts
•
•
•
•
Analytical vs. numerical Methods
Representation of floating-point numbers
Concept of significant digits
Distinguishing different kinds of errors
– Round-off / chopping / truncation errors
– True/approximate absolute and relative errors
– Acceptable errors
2
Analytical vs. Numerical Methods
• Find the intersection of
y1 = 2x + 3
y2 = x + 2
• Find the intersection of
y1 = x
y2 = cos(x)
3
Analytical vs. Numerical Methods
• Analytical Methods
– Accurate solution
– Difficult and not always possible
• Numerical Methods
– Approximation of true solution
– What method to use?
• How good is our approximation? (Error Analysis)
• How efficient is our method? (Algorithm design, Convergence
rate)
• Does our methods always work? (Convergence)
4
Number Representation
• Do machines represent integers and
floating-point numbers using the same
representation?
• How does computer represent integers?
• How does computer represent floatingpoint numbers?
5
Representation of Integers
13 as 8-bit unsigned integers (no negative #)
1310 = 000011012
= 0 x 27 + 1 x 26 + 0 x 25 + 0 x 24 +
1 x 23 + 1 x 22 + 0 x 21 + 1 x 20
=8+4+0+1
6
Exercise
What is the equivalent decimal number
represented by the following binary
number?
1101012 = ?
7
Representation of Floating-point Numbers
+
3
15678
156.78 = 0.15678 x 103
in an "imaginary" base-10 floating-point system
8
Normalized Representation
(and notations used in this course)
z    (0.a1a2 a3 ...)    e
  m  e
• σ is the sign
• β is the base, e is the exponent
– binary : β =2
– decimal : β =10
• 1/β ≤ m < 1
(i.e., a1 ≠ 0)
– binary: 0.5 ≤ m < 1
– decimal: 0.1 ≤ m < 1
9
Representation of Floating-point Numbers
13.625  1  23  1  22  0  21  1  20
 1  2 1  0  2 2  1  2 3
 (1101.101) 2
 (  )  (0.1101101) 2  2 4
Sign Signed exponent (e)
( Normalized form)
Mantissa (a)
10
Exercise
• What is the normalized floating-point
representation of 12.7510 (for β = 2)?
• What is the normalized floating-point
representation of 2.210 (for β = 2)?
• What is the equivalent decimal value of
(0.110111)2 x 23 ?
11
There are discrete points
on the number lines that
can be represented by our
computer.
How about the space
between ?
12
Implication of floating-point representations
• Only limited range of quantities may be
represented
– Number too larger  overflow
– Number too small (too close to 0)  underflow
• Only a finite number of quantities may be
represented
– round-off or chopping errors
13
Exercise
• Consider the following floating-point
representation
z    (0.a1a2a3 )2  2e
– The mantissa has only 3 bits
– Exponent, e, ranges from -4 to 4
• Can you give an integer that cannot be
represented by this representation?
• Can you give an integer between 0 and 14 that
cannot be represented by this representation?
14
IEEE 754 Floating-point
Representation
Size in
bits
Sign
(0=+ve,
1 = -ve)
Exponent
Bias of the Mantissa
exponent
Single
precision
(float)
32 bits
1 bit
8 bits
(-126 to
+127)
127
23 bits
double
precision
(double)
64 bits
1 bit
11 bits
(-1022 to
+1023)
1023
52 bits
Larger exponent  Wider range of numbers
Longer mantissa  Higher precision
15
Note on IEEE 754 Representation
• Exponents of all 0's and 1's are reserved for
special numbers.
• Zero is a special value denoted with an
exponent field of zero and a mantissa field of
zero, and we could have +0 and -0.
• +∞ an -∞ are denoted with an exponent of all 1's
and a mantissa field of all 0's.
• NaN (Not-a-number) is denoted with an
exponent of all 1's and a non-zero mantissa
field.
16
Errors and Significant Digits
• I paid $10 for 7 oranges. What is unit price
of each orange?
• $1.428571429 (that is the exact output
from my computer !!)
• Is there any difference between
$1.427571429 and $1.4?
• Is there any difference between $1.4 and
$1.40?
17
Significant figures, or digits
• The significant digits of a number are
those that can be used with confidence.
• They correspond to the number of certain
digits plus one estimated digits.
• x = 3.5 (2 significant digits)  3.45 ≤ x < 3.55
• x = 0.51234 (5 significant digits)
 0.512335 ≤ x < 0.512345
18
Excercise
• Suppose x = 3.141592658979323
– Show the value of x up to 4 significant digits.
– Show the value of x up to 10 significant digits.
• Calculate 22/7 up to 5 significant digits.
19
Concepts of Significant Digits
Suppose x = 0.739085 is the true solution
Which of the following calculated values is/are
accurate to 3 significant digits with respect to x?
a = 0.739505
b = 0.739626
c = 0.739379
d = 0.738999
20
Concepts of Significant Digits
xA (approximate value) has m significant digits
(with respect to xT, the true value) if the absolute
error | xT - xA | has magnitude less than or equal to
5 in the (m + 1)st digit of xT counting to the right
from the first non-zero digit in xT.
e.g. 1:
xT  1 / 3  0.3333333...,
xT  x A  0.0003333...
x A  0.333
 3 significant digits
21
e.g. 2:
xT
xT  x A
 23.496,
 00.002
x A  23.494
 4 significant digits
e.g. 3:
xT
xT  x A
 0.02138,
 0.00006
x A  0.02144
 2 significant digits
22
Excercise
Suppose x = 0.739085 is the true solution
Which of the following calculated values is/are
accurate to 3 significant digits with respect to x?
a = 0.739505
b = 0.739626
c = 0.739379
d = 0.738999
(| x - a | = 0.000420)
(| x - b | = 0.000541)
(| x - c | = 0.000294)
(| x - d | = 0.000086)
23
Scientific Notation
How do we express the number 45,300
meaningfully?
• 4.53 x 104 to denote the number is known to 3 significant
figures.
• 4.530 x 104 to denote the number is known to 4
significant figures.
• 4.5300 x 104 to denote the number is known to 5
significant figures.
24
Implications
As numerical methods yield approximate
results, we must therefore develop criteria to
specify how confidence we are in our
approximate result.
Usually, in terms of
1) Significant digits, or
2) Absolute/relative error bounds
25
Error Definition (True Error)
xT – true value
xA – approximate value
True Error in xA (exact value of the error) = E x  xT  x A
xT  x A
( xT  0)
True Relative Error in xA =  x 
xT
xT  x A
 100%
True Percentage Relative Error in xA =
xT
26
Error Definition
• e.g.,
xT  e  2.7182818...
19
xA 
 2.7142857...
7
• Error = Ex  2.7182818  2.7142857  0.003996
0.003996
 0.00147
• Relative error =  x 
2.7182818
27
Error Definition (Approximate Error)
• If we do not know the true value xT, we can
replace it by an estimation of the true value.
• The result is, we have the approximate error, and
the approximate relative error instead.
28
Error Definition (Approximate Error)
xA(i) – approximate value in the ith iteration of an iterative
approach
Approximate Error in xA = xA (i)  xA (i 1)
x A (i )  x A (i  1)
Approximate Relative Error in xA =
x A (i )
Approximate Percentage Relative Error in xA
x A (i )  x A (i  1)

100%
x A (i )
29
Example: Maclaurin Series
The exponentia l function is computed by
2
3
4
n
x
x
x
x
e x  1  x     ...   ...
2 3! 4!
n!
When x = 0.5
Terms Result
εt (True percentage relative εa (Approx. percentage
error)
relative error)
1
1
(1.6487-1)/1.6487 = 39.3%
2
1.5
(1.6487-1.5)/1.6487 = 9.02% (1.5-1)/1.5 = 33.3%
3
1.625
1.44%
4
1.645833333 0.175%
1.27%
5
1.648437500 0.0172%
0.158%
6
1.648697917 0.00142%
0.0158%
(1.625-1.5)/1.625 = 7.69%
30
How many terms should we use?
Terms
Result
εt
εa
1
1
39.3%
2
1.5
9.02%
33.3%
3
1.625
1.44%
7.69%
4
1.645833333
0.175%
1.27%
5
1.648437500
0.0172%
0.158%
6
1.648697917
0.00142%
0.0158%
• Computation stops when |εa| < εs
– εs = pre-determined acceptable percentage relative
error
• If we want the result to be correct to at least n significant
digits, it is suggested that we set εs = (0.5 x 102-n)%
31
Summary
• Floating-point number representation and its
implication
– Round-off and chopping errors
• Significant digits
• The definitions of
– True errors, true relative errors, true percentage
errors,
– Approximate errors, approximate relative errors,
approximate percentage relative errors
32
Next
Errors do not occur only in the space
between the discrete values (rounding or
chopping error)
Errors also appear in many stages.
Propagation of round-off errors
Truncation errors
33