24 CHAPTER 1- Mathematical Preliminaries and Error Analysis Solution These numbers were chosen to illustrate some problems that can arise with finite- digit arithmetic. Because x and u are nearly the same, their difference is small. The absolute error for xe u is (x-l)-(xeuo)|=|(x-)-(fl(fl(x)-fl(u)) 0714251)-(1(0748×10-071425×10) =10.347143×10-4-f1(000×0)=047143×10-5 This approximation has a small absolute error, but a large relative error 047143×10-5 0347143×10-s0.136 The subsequent division by the small number w or multiplication by the large number u magnifies the absolute error without modifying the relative error. The addition of the large and small numbers u and u produces large absolute error but not large relative error. These calculations are shown in Table 1.3 Table 1.3 Operation Actual value Absolute error Relative error 0.30000×10-4 0.34714×10-4 0471×10-5 0.136 (x eme 0.27000×10 0.31242×101 0.424 (xe)⑧U 0.29629×10 0.34285×10 0.136 0.98765×105 0.98766×105 0.161×101 0.163×10-4 One of the most common error-producing calculations involves the cancelation of significant digits due to the subtraction of nearly equal numbers. Suppose two nearly equal numbers x and y, with x >y, have the k-digit representations fl(x)=0.dd2……dnap+1ap+2…ak×10, fl()=0.dd2…dnBp+1Bp+2….Rk×10 The floating-point form of x-y is fl(f1(x)-fl(y)=0.p+10p+2…k×1000, The floating-point number used to represent x- y has at most k-p digits of significance However, in most calculation devices, x-y will be assigned k digits, with the last p being either zero or randomly assigned. Any further calculations involving x-y retain the problem of having only k-p digits of significance, since a chain of calculations is no more accurate than its weakest portion. f a finite-digit representation or calculation introduces an error, further enlargement of the error occurs when dividing by a number with small magnitude(or, equivalently, whe Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
24 CHAPTER 1 Mathematical Preliminaries and Error Analysis Solution These numbers were chosen to illustrate some problems that can arise with finitedigit arithmetic. Because x and u are nearly the same, their difference is small. The absolute error for x u is |(x − u) − (x u)| = |(x − u) − (f l(f l(x) − f l(u)))| = 5 7 − 0.714251 − f l 0.71428 × 100 − 0.71425 × 100 = 0.347143 × 10−4 − f l 0.00003 × 100 = 0.47143 × 10−5 . This approximation has a small absolute error, but a large relative error 0.47143 × 10−5 0.347143 × 10−4 ≤ 0.136. The subsequent division by the small number w or multiplication by the large number v magnifies the absolute error without modifying the relative error. The addition of the large and small numbers u and v produces large absolute error but not large relative error. These calculations are shown in Table 1.3. Table 1.3 Operation Result Actual value Absolute error Relative error x u 0.30000 × 10−4 0.34714 × 10−4 0.471 × 10−5 0.136 (x u) .. w 0.27000 × 101 0.31242 × 101 0.424 0.136 (x u) ⊗ v 0.29629 × 101 0.34285 × 101 0.465 0.136 u ⊕ v 0.98765 × 105 0.98766 × 105 0.161 × 101 0.163 × 10−4 One of the most common error-producing calculations involves the cancelation of significant digits due to the subtraction of nearly equal numbers. Suppose two nearly equal numbers x and y, with x > y, have the k-digit representations f l(x) = 0.d1d2 ... dpαp+1αp+2 ...αk × 10n , and f l(y) = 0.d1d2 ... dpβp+1βp+2 ...βk × 10n . The floating-point form of x − y is f l(f l(x) − f l(y)) = 0.σp+1σp+2 ...σk × 10n−p , where 0.σp+1σp+2 ...σk = 0.αp+1αp+2 ...αk − 0.βp+1βp+2 ...βk . The floating-point number used to represent x − y has at most k − p digits of significance. However, in most calculation devices, x − y will be assigned k digits, with the last p being either zero or randomly assigned. Any further calculations involving x−y retain the problem of having only k −p digits of significance, since a chain of calculations is no more accurate than its weakest portion. If a finite-digit representation or calculation introduces an error, further enlargement of the error occurs when dividing by a number with small magnitude (or, equivalently, when Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
1.2 Round-off Errors and Computer Arithmetic multiplying by a number with large magnitude). Suppose, for example, that the number z has the finite-digit approximation z +8, where the error 8 is introduced by representation or by previous calculation. Now divide by a=10-, where n>0 Then e≈n(f() e)=(z+)×10 The absolute error in this approximation, 8 x 10, is the original absolute error, 81, mul- tiplied by the factor 10. Example 5 Let p=0.54617 and q=0.54601. Use four-digit arithmetic to approximate p-q and determine the absolute and relative errors using(a) rounding and(b) chopping Solution The exact value of r=p-q is r=0.00016 (a) Suppose the subtraction is performed using four-digit rounding arithmetic. Round ing p and q to four digits gives P*=0.5462 and g*=0.5460, respectively, and r=P-q=0.0002 is the four-digit approximation to r. Since r-r+_100016-0.0002=0.25, 10.00016 the result has only one significant digit, whereas p* and g* were accurate to four and five significant digits, respectivel (b) If chopping is used to obtain the four digits, the four-digit approximations to p, g, and r are p'=0.5461, q=0.5460, and r=P-q=00001. This gives |r-r*|10.00016-0.0001 =0.375 0.00016 which also results in only one significant digit of accuracy The loss of accuracy due to round-off error can often be avoided by a reformulation of the calculations, as illustrated in the next example Illustration The quadratic formula states that the roots of ax+ bx +c=0, when a#0, are -b+√b2-4ac and x2= (1.1) Consider this formula applied to the equation x2+62 10x +1=0, whose roots are 0.01610723andx=-62.08390 The roots I and z of a general We will again use four-digit rounding arithmetic in the calculations to determine the rootIn quadratic equation are related to this equation, b2 is much larger than 4ac, so the nu the coefficients by the fact that the subtraction of nearly equal numbers. Because erator in the calculation for x] involves At √b2-4ac=√(62.10)2-(400010001000 =√3856.-4000=√3852.=6206 -1-t= This is a special case of Vieta's we have Formulas for the coefficients of fl(x1)-6210+62.06-0.04000 0.02000 Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning rese
1.2 Round-off Errors and Computer Arithmetic 25 multiplying by a number with large magnitude). Suppose, for example, that the number z has the finite-digit approximation z + δ, where the error δ is introduced by representation or by previous calculation. Now divide by ε = 10−n, where n > 0. Then z ε ≈ f l f l(z) f l(ε) = (z + δ) × 10n . The absolute error in this approximation, |δ| × 10n, is the original absolute error, |δ|, multiplied by the factor 10n. Example 5 Let p = 0.54617 and q = 0.54601. Use four-digit arithmetic to approximate p − q and determine the absolute and relative errors using (a) rounding and (b) chopping. Solution The exact value of r = p − q is r = 0.00016. (a) Suppose the subtraction is performed using four-digit rounding arithmetic. Rounding p and q to four digits gives p∗ = 0.5462 and q∗ = 0.5460, respectively, and r∗ = p∗ − q∗ = 0.0002 is the four-digit approximation to r. Since |r − r∗| |r| = |0.00016 − 0.0002| |0.00016| = 0.25, the result has only one significant digit, whereas p∗ and q∗ were accurate to four and five significant digits, respectively. (b) If chopping is used to obtain the four digits, the four-digit approximations to p, q, and r are p∗ = 0.5461, q∗ = 0.5460, and r∗ = p∗ − q∗ = 0.0001. This gives |r − r∗| |r| = |0.00016 − 0.0001| |0.00016| = 0.375, which also results in only one significant digit of accuracy. The loss of accuracy due to round-off error can often be avoided by a reformulation of the calculations, as illustrated in the next example. Illustration The quadratic formula states that the roots of ax2 + bx + c = 0, when a = 0, are x1 = −b + √b2 − 4ac 2a and x2 = −b − √b2 − 4ac 2a . (1.1) Consider this formula applied to the equation x2 + 62.10x + 1 = 0, whose roots are The roots x1 and x2 of a general quadratic equation are related to the coefficients by the fact that x1 + x2 = −b a and x1x2 = c a . This is a special case of Vièta’s Formulas for the coefficients of polynomials. approximately x1 = −0.01610723 and x2 = −62.08390. We will again use four-digit rounding arithmetic in the calculations to determine the root. In this equation, b2 is much larger than 4ac, so the numerator in the calculation for x1 involves the subtraction of nearly equal numbers. Because b2 − 4ac = (62.10)2 − (4.000)(1.000)(1.000) = √ 3856. − 4.000 = √ 3852. = 62.06, we have f l(x1) = −62.10 + 62.06 2.000 = −0.04000 2.000 = −0.02000, Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
26 CHAPTER 1 Mathematical Preliminaries and Error Analysis a poor approximation to x=-0.016ll, with the large relative error -0.01611+0.020004 ≈24×10-1 On the other hand, the calculation for x2 involves the addition of the nearly equal numbers -b and -vb2-4ac. This presents no problem since 6210-62.06-124.2 fl(x2) 2.000 -62.10 has the small relative error -62.08+62.10 ≈3.2×10 To obtain a more accurate four-digit rounding approximation for xI, we change the form of the quadratic formula by rationalizing the numerator: b2-(b2-4ac) x √b2-4ac which simplifies to an alternate quadratic formula x Using(1.2) give -2.000 fl(x1) 6210+62061242 0.01610 which has the small relative error 6.2x 10-4 The rationalization technique can also be applied to give the following alternative quadratic //A (1.3) This is the form to use if b is a negative number. In the lllustration however the mistaken use of this formula for x2 would result in not only the subtraction of nearly equal numbers, but also the division by the small result of this subtraction. The inaccuracy that this combination duces 2.000 fl(x2) b-√b2-4ac6210-6206004000 has the large relative error 1.9x 10 The lesson: Think before you compute Nested Arithmetic Accuracy loss due to round-off error can also be reduced by rearranging calculations, as shown in the next example Example 6 Evaluate f(x)=x-61x2+3.2x+1.5 at x=4.71 using three-digit arithmetic. Solution Table 1. 4 gives the intermediate results in the calculations Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning
26 CHAPTER 1 Mathematical Preliminaries and Error Analysis a poor approximation to x1 = −0.01611, with the large relative error | − 0.01611 + 0.02000| | − 0.01611| ≈ 2.4 × 10−1 . On the other hand, the calculation for x2 involves the addition of the nearly equal numbers −b and − √b2 − 4ac. This presents no problem since f l(x2) = −62.10 − 62.06 2.000 = −124.2 2.000 = −62.10 has the small relative error | − 62.08 + 62.10| | − 62.08| ≈ 3.2 × 10−4 . To obtain a more accurate four-digit rounding approximation for x1, we change the form of the quadratic formula by rationalizing the numerator: x1 = −b + √b2 − 4ac 2a −b − √b2 − 4ac −b − √b2 − 4ac = b2 − (b2 − 4ac) 2a(−b − √b2 − 4ac) , which simplifies to an alternate quadratic formula x1 = −2c b + √b2 − 4ac . (1.2) Using (1.2) gives f l(x1) = −2.000 62.10 + 62.06 = −2.000 124.2 = −0.01610, which has the small relative error 6.2 × 10−4. The rationalization technique can also be applied to give the following alternative quadratic formula for x2: x2 = −2c b − √b2 − 4ac . (1.3) This is the form to use if b is a negative number. In the Illustration, however, the mistaken use of this formula for x2 would result in not only the subtraction of nearly equal numbers, but also the division by the small result of this subtraction. The inaccuracy that this combination produces, f l(x2) = −2c b − √b2 − 4ac = −2.000 62.10 − 62.06 = −2.000 0.04000 = −50.00, has the large relative error 1.9 × 10−1. • The lesson: Think before you compute! Nested Arithmetic Accuracy loss due to round-off error can also be reduced by rearranging calculations, as shown in the next example. Example 6 Evaluate f (x) = x3 − 6.1x2 + 3.2x + 1.5 at x = 4.71 using three-digit arithmetic. Solution Table 1.4 gives the intermediate results in the calculations. Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
1.2 Round-off Errors and Computer Arithmetic 27 Table 1.4 3.2x Exac 4.71 22.1841 104.487111 135.32301 15072 Three-digit(chopping) 4.71 22 150 Three-digit(rounding) 15.1 To illustrate the calculations, let us look at those involved with finding x' using three digit rounding arithmetic. First we find x2=4.712=22.1841 which rounds to 22.2 x3=x2.x=222.4.71=104.562 which rounds to105 Als 6.1x2=6.1(22.2)=13542 which rounds to 135, 3.2x=32(4.71)=15.072 which rounds to15.1 The exact result of the evaluation is Exact:f(4.71)=104.48711l-135.32301+15.072+1.=-14.263899 Using finite-digit arithmetic, the way in which we add the results can effect the final result Suppose that we add left to right. Then for chopping arithmetic we have Three-digit( chopping):f(4.71)=(104.-134.)+15.0)+1.5=-13.5, and for rounding arithmetic we have Three-digit( rounding):f(4.71)=((105.-135)+15.1)+1.5=-13.4 ( You should carefully verify these results to be sure that your notion of finite-digit arithmetic is correct. Note that the three-digit chopping values simply retain the leading three digits, with no rounding involved, and differ significantly from the three-digit rounding values The relative errors for the three-digit methods are 14.263899+13.5 14.263899+13.4 Chopping ≈0.06. 14.263899 80.05, and Rounding: 14.263899 Illustration As an alternative approach, the polynomial f(r) in Example 6 can be written in a nested manner as Remember that chopping(or rounding) is performed after each f(x)=x3-6x2+32x+1.5=(x-6.1)x+32)x+1.5 calculation Using three-digit chopping arithmetic now produces f(4.71)=(4.71-6.1)4.71+3.2)4.71+1.5=((-1.39)(4.71)+3.2)4.71+1.5 (-6.54+32)4.71+1.5=(-3.34)4.71+1.5=-15.7+1.5=-14.2 Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning rese
1.2 Round-off Errors and Computer Arithmetic 27 Table 1.4 x x2 x3 6.1x2 3.2x Exact 4.71 22.1841 104.487111 135.32301 15.072 Three-digit (chopping) 4.71 22.1 104. 134. 15.0 Three-digit (rounding) 4.71 22.2 105. 135. 15.1 To illustrate the calculations, let us look at those involved with finding x3 using threedigit rounding arithmetic. First we find x2 = 4.712 = 22.1841 which rounds to 22.2. Then we use this value of x2 to find x3 = x2 · x = 22.2 · 4.71 = 104.562 which rounds to 105. Also, 6.1x2 = 6.1(22.2) = 135.42 which rounds to 135, and 3.2x = 3.2(4.71) = 15.072 which rounds to 15.1. The exact result of the evaluation is Exact: f (4.71) = 104.487111 − 135.32301 + 15.072 + 1.5 = −14.263899. Using finite-digit arithmetic, the way in which we add the results can effect the final result. Suppose that we add left to right. Then for chopping arithmetic we have Three-digit (chopping): f (4.71) = ((104. − 134.) + 15.0) + 1.5 = −13.5, and for rounding arithmetic we have Three-digit (rounding): f (4.71) = ((105. − 135.) + 15.1) + 1.5 = −13.4. (You should carefully verify these results to be sure that your notion of finite-digit arithmetic is correct.) Note that the three-digit chopping values simply retain the leading three digits, with no rounding involved, and differ significantly from the three-digit rounding values. The relative errors for the three-digit methods are Chopping: −14.263899 + 13.5 −14.263899 ≈ 0.05, and Rounding: −14.263899 + 13.4 −14.263899 ≈ 0.06. Illustration As an alternative approach, the polynomial f (x) in Example 6 can be written in a nested manner as Remember that chopping (or rounding) is performed after each calculation. f (x) = x3 − 6.1x2 + 3.2x + 1.5 = ((x − 6.1)x + 3.2)x + 1.5. Using three-digit chopping arithmetic now produces f (4.71) = ((4.71 − 6.1)4.71 + 3.2)4.71 + 1.5 = ((−1.39)(4.71) + 3.2)4.71 + 1.5 = (−6.54 + 3.2)4.71 + 1.5 = (−3.34)4.71 + 1.5 = −15.7 + 1.5 = −14.2. Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
28 CHAPTER 1- Mathematical Preliminaries and Error analys In a similar manner, we now obtain a three-digit rounding answer of. 3. The new relative errors are 14.263899+14. Three-digit(chopping): ≈0.0045 14.263899 -14.263899+14.3 Three-digit(rounding) ≈00025 14.263899 Nesting has reduced the relative error for the chopping approximation to less than 10%0 of that obtained initially For the rounding approximation the improvement has been even more dramatic; the error in this case has been reduced by more than 95%0 Polynomials should always be expressed in nested form before performing an evalu- ation. because this form minimizes the number of arithmetic calculations The decreased error in the Illustration is due to the reduction in computations from four multiplications and three additions to two multiplications and three additions. One way to reduce round-off error is to reduce the number of computations. EXERCISE SET 12 1. Compute the absolute error and relative error in approximations of p by p ,p*=22/7 b.p=丌,p=3.1416 c.p=e,p=2.718 d 2,p*=1.414 e.p=e0,p*=22000 f.p=102,p2=1400 p=8,p*=39900 h.p=9,p=√l8(9/e) 2. Find the largest interval in which p" must lie to approximate p with relative error at most 10-for b 3. Suppose p"must approximate p with relative error at most 10. Find the largest interval in which p must lie for each value of P. b.900 c.1500 4. Perform the following computations (i) exactly, (ii) using three-digit chopping arithmetic, and(iii) using three-digit rounding arithmetic. (iv) Compute the relative errors in parts(ii)and (iii) 3 5. Use three-digit rounding arithmetic to perform the following calculations. Compute the absolute error and relative error with the exact value determined to at least five digits b.133-0.499 C.(121-0.327)-119 d.(121-119)-0.327 是 f.-10+6e~3 号 6. Repeat Exercise 5 using four-digit rounding arithmetic. 7. Repeat Exercise 5 using three-digit chopping arithmetic 8. Repeat Exercise 5 using four-digit chopping arithmetic Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning
28 CHAPTER 1 Mathematical Preliminaries and Error Analysis In a similar manner, we now obtain a three-digit rounding answer of −14.3. The new relative errors are Three-digit (chopping): −14.263899 + 14.2 −14.263899 ≈ 0.0045; Three-digit (rounding): −14.263899 + 14.3 −14.263899 ≈ 0.0025. Nesting has reduced the relative error for the chopping approximation to less than 10% of that obtained initially. For the rounding approximation the improvement has been even more dramatic; the error in this case has been reduced by more than 95%. Polynomials should always be expressed in nested form before performing an evaluation, because this form minimizes the number of arithmetic calculations. The decreased error in the Illustration is due to the reduction in computations from four multiplications and three additions to two multiplications and three additions. One way to reduce round-off error is to reduce the number of computations. E X E R C I S E S E T 1.2 1. Compute the absolute error and relative error in approximations of p by p∗. a. p = π, p∗ = 22/7 b. p = π, p∗ = 3.1416 c. p = e, p∗ = 2.718 d. p = √2, p∗ = 1.414 e. p = e10, p∗ = 22000 f. p = 10π , p∗ = 1400 g. p = 8!, p∗ = 39900 h. p = 9!, p∗ = √18π (9/e)9 2. Find the largest interval in which p∗ must lie to approximate p with relative error at most 10−4 for each value of p. a. π b. e c. √2 d. √3 7 3. Suppose p∗ must approximate p with relative error at most 10−3. Find the largest interval in which p∗ must lie for each value of p. a. 150 b. 900 c. 1500 d. 90 4. Perform the following computations (i) exactly, (ii) using three-digit chopping arithmetic, and (iii) using three-digit rounding arithmetic. (iv) Compute the relative errors in parts (ii) and (iii). a. 4 5 + 1 3 b. 4 5 · 1 3 c. 1 3 − 3 11 + 3 20 d. 1 3 + 3 11 − 3 20 5. Use three-digit rounding arithmetic to perform the following calculations. Compute the absolute error and relative error with the exact value determined to at least five digits. a. 133 + 0.921 b. 133 − 0.499 c. (121 − 0.327) − 119 d. (121 − 119) − 0.327 e. 13 14 − 6 7 2e − 5.4 f. −10π + 6e − 3 62 g. 2 9 · 9 7 h. π − 22 7 1 17 6. Repeat Exercise 5 using four-digit rounding arithmetic. 7. Repeat Exercise 5 using three-digit chopping arithmetic. 8. Repeat Exercise 5 using four-digit chopping arithmetic. Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.