Lecture notes, lecture Errors and Computer Arithmetic PDF

Preview

Summary

Download Lecture notes, lecture Errors and Computer Arithmetic PDF

Description

ERRORS and COMPUTER ARITHMETIC Types of Error in Numerical Calculations • Initial Data Errors: from experiment, modeling, computer representation; problem dependent but need to know at beginning of calculation. • Truncation Error: from stopping algorithm with infinite number of steps; algorithm dependent, but need to be aware of for algorithm design. • Roundoff error: from finite representation of numbers in computer during arithmetic computations; need to be aware of for algorithm design and interpretation of results. Measures of Error: for exact x and approximation x∗ • Absolute error e = |x − x∗|. • Relative error r = |(x − x∗)/x|.

1

ERRORS and COMPUTER NUMBERS Computer Numbers, Roundoff Error • Floating Point Number Representation: any real number y can be put in floating point form y = ±.d1d2 . . . dk . . . × b±n

for base b, with 0 < d1 < b, 0 ≤ di < b, i > 1. E.g. (.1)10 = +(.1100)2 × 2−3. Conversion from decimal to binary? Integer part: repeatedly divide by 2, saving remainder digits di. Fraction: repeatedly multiply by 2, saving remainder digits di.

E.g. (4.1)10 = +(.1000001100)2 × 23. E.g. (3.1)10 = +(.110001100)2 × 22. • Computer numbers: computers use

y ≈ f l(y) = ±.d1′ d′2 . . . d′k × b±e1e2...em

where b, k, m are machine dependent, 0 ≤ ei < b. Digits d1′ . . . dk′ are mantissa, e1e2 . . . em exponent. Note: “real” computer arithmetic uses only a finite subset of (−∞, ∞). 2

COMPUTER NUMBERS CONTINUED • IEEE Standard for b = 2 number representation: single precision (SP) with ±, (k, m) = (23, 8); double precision (DP) with ±, (k, m) = (52, 11); long double with ±, (k, m) = (64, 15). Normalized IEEE form: f l(y) = ±1.b1b2 . . . bk × 2p. E.g. for DP, 12 = +1.000 . . . 000 × 20, with 52 zeros; next DP number is (51 zeros) (1 + 2−52)2 = +1.000 . . . 001 × 20.

Special representations for ±0, ±∞ and NAN (e.g. 00), using special values for p (= -1023 or 1024 for DP). Overflow occurs if p > largest +e1e2 . . . em; with DP p ≤ 1023, note 21023 ≈ 9 × 10307. Underflow occurs if p < smallest −e1e2 . . . em; with DP p ≥ −1022, note 2−1022 ≈ 2 × 10−308, but p = −1023 allows subnormal numbers ≥ 2−1074.

3

COMPUTER NUMBERS CONTINUED Machine Epsilon: macheps or unit roundoff or ǫmach is the smallest number ǫmach for which f l(1 + ǫmach ) > 1. IEEE SP has ǫmach = 2−23 ≈ 10−7; IEEE DP has ǫmach = 2−52 ≈ 2 × 10−16 (MATLAB). Matlab Checks: format short g, disp([1+2^(-52) 1+2^(-53)]) 1 1 disp([1+2^(-52)-1 1+2^(-53)-1]) 2.2204e-16 0 disp(sprintf(’%20.17f’,[1+2^(-52) 1+2^(-53)])) 1.00000000000000022 1.00000000000000000 disp(sprintf(’%20.17f’,[1+2^(-52)-1 1+2^(-53)-1]) 0.00000000000000022 0.00000000000000000

4

COMPUTER NUMBERS CONTINUED Rounding: if y does not have exact f l(y) representation, we need a method for choosing last digit(s). E.g. SP f l(.1) = +1.1001100110011001100110? × 2−4. • chopping discards all bi, i > k, so that SP f l(.1) = +1.10011001100110011001100 × 2−4; DP f l(.1) = +1.100110011001 . . . 10011001 × 2−4, DP f l(4.1) = +1.000001100110 . . . 01100110 × 22, DP f l(3.1) = +1.100011001100 . . . 11001100 × 21. • rounding (to nearest) adds 1 to bk if bk+1 = 1; so SP f l(.1) = +1.10011001100110011001101 × 2−4. DP f l(.1) = +1.100110011001 . . . 10011010 × 2−4, DP f l(4.1) = +1.000001100110 . . . 01100110 × 22, DP f l(3.1) = +1.100011001100 . . . 11001101 × 21. Special case: if bk+1bk+2bk+3 . . . = 10¯ . . ., then add 1 to bk if and only if bk = 1. • Relative rounding error: rounding to nearest (IEEE, MATLAB)) ensures |f l(y) − y | 1 ≤ ǫmach . |y| 2

5

COMPUTER NUMBERS CONTINUED Computer Arithmetic : assume ◦ denotes computer implementation of +, −, / or ×.

• Model for sequence of operations: for x ◦ y, computer a) takes stored values f l(x) and f l(y ), b) accurately computes f l(x) ◦ f l(y ), c) then rounds the result to get f l(f l(x) ◦ f l(y )). E.g. Rounded DP for 4.1 − 3.1: f l(4.1) = +1.000001100110 . . . 01100110 × 22 −f l(3.1) = −0.1100011001100 . . . 11001101 × 22 = (2−2 − 2−53) × 22 = 1 − 2−51 = +.1111 . . . 1110 = +1.1111 . . . 11100 × 2−1. Matlab Checks: format long g, disp(4.1-3.1) 1 disp(sprintf(’%20.16g’,4.1-3.1)) 0.9999999999999996 disp( (4.1-3.1)-1 ) -4.440892098500626e-16 disp( 4.1-(3.1+1) ) 0 Computer addition is only approximately associative. IEEE requires |f l(x ◦ y) − (x ◦ y)| ≤ ǫmach , |x ◦ y|

for IEEE standard computer hardware. 6

LOSS of SIGNIFICANT DIGITS Significant Digits : x∗ approximates x to t significant digits if t is the largest nonegative integer with    x − x∗   < 5 × 10−t.   x  Subtractive Cancellation : when significant digits are lost during the subtraction of two ≈= numbers. • Examples in decimal: 123.4567 - 123.4566 √ 4.01 − 2 with 3 digits: √ 4.01 − 2 ≈ 2.0025 − 2 → 2 − 2 = 0;

• Algebraic rearrangment: if is often possible to use algebraically equivalent formulas to avoid LSD calculations. Examples: a) x2 + bx + c√= 0, has x = (−b ± b2 − 4c)/2, with LSD for small |c/b|.

7

LSD EXAMPLES b) 1/(1 + x) − 1/(1 − x) for small x.

c) (1 − sec(x))/tan2(x) for small x.

Matlab Check: for x = 10.^[-2:-2:-8] disp([x (1-sec(x))/tan(x)^2 end 0.01 -0.499987499790956 0.0001 -0.499999993627931 1e-06 -0.500044450290837 1e-08 0

-cos(x)/(1+cos(x))] -0.499987499791664 -0.49999999875 -0.499999999999875 -0.5

d) (ex −1)/x for small x (Taylor series sometimes helps).

8

NUMERICAL SOFTWARE • Numerical algorithms in texbook and written for class will be short algorithms, designed to illustrate primary algorithm features and problems. • Software Libraries: numerical methods described and analyzed in textbook and class have been placed in software libraries. • Software libraries contain carefully documented software for algorithms carefully implemented as language dependent functions and procedures: e.g. CACM, NAG, IMSL, STATLIB, WWW, for standard computer languages, and environments: e.g. MATLAB, MAPLE, MATHEMATICA, R, GAUSS for interactive work; e.g. FORTRAN, C, C++, JAVA, PYTHON for high performance computation.

9...