Solution Manual for Numerical Analysis, 2nd Edition

Preview (16 of 309 Pages)

100%

Purchase to unlock

Loading page image...

’SSOLUTIONSMANUALNUMERICALANALYSISSECONDEDITIONTimothy SauerGeorge Mason University

Loading page image...

iTable of ContentsChapter 0Fundamentals0.1Evaluating a Polynomial10.2Binary Numbers20.3Floating Point Representation of Real Numbers80.4Loss of Significance130.5Review of Calculus15Chapter 1Solving Equations1.1The Bisection Method171.2Fixed-Point Iteration191.3Limits of Accuracy241.4Newton’s Method251.5Root-Finding without Derivatives28Chapter 2Systems of Equations2.1Gaussian Elimination312.2The LU Factorization322.3Sources of Error352.4The PA = LU factorization402.5Iterative Methods452.6Methods for Symmetric Positive-Definite Matrices492.7Nonlinear Systems of Equations57Chapter 3Interpolation3.1Data and Interpolating Functions613.2Interpolation Error653.3Chebyshev Interpolation693.4Cubic Splines733.5Bézier Curves83Chapter 4Least Squares4.1Least Squares and the Normal Equations894.2A Survey of Models964.3QR Factorization1034.4Generalized Minimum Residual (GMRES) Method1124.5Nonlinear Least Squares118

Loading page image...

iiChapter 5Numerical Differentiation and Integration5.1Numerical Differentiation1235.2Newton-Cotes Formulas for Numerical Integration1325.3Romberg Integration1425.4Adaptive Quadrature1465.5Gaussian Quadrature150Chapter 6Ordinary Differential Equations6.1Initial Value Problems1536.2Analysis of IVP Solvers1626.3Systems of Ordinary Differential Equations1706.4Runge-Kutta Methods and Applications1766.5Variable Step-Size Methods1876.6Implicit Methods and Stiff Equations1876.7Multistep Methods190Chapter 7Boundary Value Problems7.1Shooting Method2037.2Finite Difference Methods2077.3Collocation and the Finite Element Method216Chapter 8Partial Differential Equations8.1Parabolic Equations2218.2Hyperbolic Equations2248.3Elliptic Equations2268.4Nonlinear partial differential equations233Chapter 9Random Numbers and Applications9.1Random Numbers2359.2Monte Carlo Simulation2389.3Discrete and Continuous Brownian Motion2399.4Stochastic Differential Equations241Chapter 10 Trigonometric Interpolation and the FFT10.1The Fourier Transform24910.2Trigonometric Interpolation25210.3The FFT and Signal Processing261

Loading page image...

iiiChapter 11 Compression11.1The Discrete Cosine Transform26711.2Two-Dimensional DCT and Image Compression27211.3Huffman Coding27611.4Modified DCT and Audio Compression280Chapter 12 Eigenvalues and Singular Values12.1Power Iteration Methods28912.2QR Algorithm29312.3Singular Value Decomposition29712.4Applications of the SVD300Chapter 13 Optimization13.1Unconstrained Optimization without Derivatives30313.2Unconstrained Optimization with Derivatives305

Loading page image...

CHAPTER 0FundamentalsEXERCISES 0.1Evaluating a Polynomial1 (a)P(x) = 1 +x(1 +x(5 +x(1 +x(6)))).P(13) = 6(13)4+ (13)3+ 5(13)2+13+ 1 = 1 +13(1 +13(5 +13(1 +13(6)))) = 2.1 (b)P(x) = 1 +x(−5 +x(5 +x(4 +x(−3))))P(13) =−3(13)4+ 4(13)3+ 5(13)2−5(13) + 1 = 1 +13(−5 +13(5 +13(4 +13(−3)))) = 01 (c)P(x) = 1 +x(0 +x(−1 +x(1 +x(2))))P(13) = 2(13)4+ (13)3−(13)2+ 1 = 1 +13(0 +13(−1 +13(1 +13(2)))) = 77/81.2 (a)P(x) = 7+x(−3+x(−2+x(6)));P(−12) = 7+(−12)(−3+(−12)(−2+(−12)(6))) = 29/4.2 (b)P(x) = 1 +x(−3 +x(1 +x(−3 +x(−1 +x(8)))));P(−12) = 1 + (−12)(−3 + (−12)(1 + (−12)(−3 + (−12)(−1 + (−12)(8))))) = 45/16.2 (c)P(x) = 4 +x(−2 +x(0 +x(0 +x(−2 +x(0 +x(4))))));P(−12) = 4 + (−12)(−2 + (−12)(0 + (−12)(0 + (−12)(−2 + (−12)(0 + (−12)(4)))))) = 79/16.3P(12) = 1 + (12)2(2 + (12)2(−4 + (12)2(1))) = 81/64.4 (a)P(5) = 1 + 5(12+ (5−2)(12+ (5−3)(−12))) =−44 (b)P(−1) = 1 + (−1)(12+ (−1−2)(12+ (−1−3)(−12))) = 85 (a)P(12) = 4 +12(4 + (12−1)(1 + (12−2)(3 + (12−3)(2)))) = 55 (b)P(−12) = 4−12(4 + (−12−1)(1 + (−12−2)(3 + (−12−3)(2)))) = 41/46 (a)P(x) =a0+x5(a5+x5(a10+x5a15)).The three multiplicationsx2=x·x, x4=x2·x2, x5=x4·xare needed, together with 3 multiplications and 3 additions from the nestedmultiplication. Total of 6 multiplications and 3 additions.6 (b)P(x) =x7(a7+x5(a12+x5(a17+x5(a22+x5a27)))). The four multiplicationsx2=x·x, x4=x2·x2, x5=x4·x, x7=x5·x2are needed, together with 5 multiplications and 4additions from the nested multiplication. Total of 9 multiplications and 4 additions.7The degreenpolynomial with base points isP(x) =c1+ (x−r1)(c2+ (x−r2)(c3+ (x−r3)(c4+. . .+ (x−rn)cn+1))). The operations needed arenmultiplications and2nadditions.COMPUTER PROBLEMS 0.11The MATLABcommandnest(50,ones(51,1),1.00001)gives51.01275208274999,differing from(x51−1)/(x−1)withx= 1.00001by4.76×10−12.

Loading page image...

2CHAPTER0FUNDAMENTALS2The commandnest(99,(-1).ˆ(0:99),1.00001)gives−0.00050024507964763. Theequivalent expression(1−x100)/(1 +x)forx= 1.00001differs by1.713×10−16.EXERCISES 0.2Binary Numbers1 (a)(64)10= (26)10= (1000000)21 (b)(17)10= (16 + 1)10= (10001)21 (c)79÷2=39R139÷2=19R119÷2=9R19÷2=4R14÷2=2R02÷2=1R01÷2=0R1Therefore(79)10= (1001111)2.1 (d)227÷2=113R1113÷2=56R156÷2=28R028÷2=14R014÷2=7R07÷2=3R13÷2=1R11÷2=0R1Therefore(227)10= (11100011)2.2 (a)(1/8)10= (2−3)10= (0.001)22 (b)(7/8)10= (2−1+ 2−2+ 2−3)10= (0.111)22 (c)(35/16)10= (2 + 3/16)10= (2 + 1/8 + 1/16)10= (10.0011)2

Loading page image...

SECTION0.2BINARYNUMBERS32 (d)31/64×2=31/32 + 031/32×2=15/16 + 115/16×2=7/8 + 17/8×2=3/4 + 13/4×2=1/2 + 11/2×2=0 + 1Therefore(31/64)10= (0.011111)2.3 (a)10.5 = 10 + 0.5. Integer part:(10)10= (8 + 2)10= (1010)2. Fractional part:(0.5)10=(0.1)2, so(10.5)10= (1010.1)2.3 (b)13×2=23 + 023×2=13 + 113×2=23 + 0...Therefore(13)10= (0.01)2.3 (c)57×2=37 + 137×2=67 + 067×2=57 + 157×2=37 + 137×2=67 + 0...Therefore(57)10= (0.101)2.

Loading page image...

4CHAPTER0FUNDAMENTALS3 (d)(12.8)10= (12)10+ (0.8)10; (12)10= (1100)2.0.8×2=0.6 + 10.6×2=0.2 + 10.2×2=0.4 + 00.4×2=0.8 + 00.8×2=0.6 + 1...Therefore(12.8)10= (1100.1100)2.3 (e)(55.4)10= (55)10+ (0.4)10; (55)10= (32 + 16 + 4 + 2 + 1)10= (110111)2.0.4×2=0.8 + 00.8×2=0.6 + 10.6×2=0.2 + 10.2×2=0.4 + 00.4×2=0.8 + 0...Therefore(55.4)10= (110111.0110)2.3 (f)0.1×2=0.2 + 00.2×2=0.4 + 00.4×2=0.8 + 00.8×2=0.6 + 10.6×2=0.2 + 10.2×2=0.4 + 0...Therefore(0.1)10= (0.00011)2.4 (a)11.25 = 11 + 0.25. Integer part:(11)10= (8 + 2 + 1)10= (1011)2. Fractional part:(0.25)10= (0.01)2, so(10.25)10= (1011.01)2.

Loading page image...

SECTION0.2BINARYNUMBERS54 (b)23×2=13 + 113×2=23 + 023×2=13 + 1...Therefore(23)10= (0.10)2.4 (c)35×2=15 + 115×2=25 + 025×2=45 + 045×2=35 + 135×2=15 + 1...Therefore(35)10= (0.1001)2.4 (d)(3.2)10= (3)10+ (0.2)10; (3)10= (11)2.0.2×2=0.4 + 00.4×2=0.8 + 00.8×2=0.6 + 10.6×2=0.2 + 10.2×2=0.4 + 0...Therefore(3.2)10= (11.0011)2.

Loading page image...

6CHAPTER0FUNDAMENTALS4 (e)(30.6)10= (30)10+ (0.6)10; (30)10= (16 + 8 + 4 + 2)10= (11110)2.0.6×2=0.2 + 10.2×2=0.4 + 00.4×2=0.8 + 00.8×2=0.6 + 10.6×2=0.2 + 1...Therefore(30.6)10= (11110.1001)2.4 (f)(99.9)10= (99)10+ (0.9)10; (99)10= (64 + 32 + 2 + 1)10= (1100011)2.0.9×2=0.8 + 10.8×2=0.6 + 10.6×2=0.2 + 10.2×2=0.4 + 00.4×2=0.8 + 00.8×2=0.6 + 1...Therefore(99.9)10= (1100011.11100)2.5(π)10= (3)10+ (π−3)100.14159265×2=0.28318531 + 00.28318531×2=0.56637061 + 00.56637061×2=0.13274123 + 10.13274123×2=0.26548246 + 00.26548246×2=0.53096491 + 00.53096491×2=0.06192983 + 10.06192983×2=0.12385966 + 00.12385966×2=0.24771932 + 00.24771932×2=0.49543864 + 00.49543864×2=0.99087728 + 00.99087728×2=0.98175455 + 10.98175455×2=0.96350910 + 10.96350910×2=0.92701821 + 1...

Loading page image...

SECTION0.2BINARYNUMBERS7Therefore(π)10= (11.0010010000111. . .)2.6(e)10= (2)10+ (e−2)100.71828183×2=0.43656366 + 10.43656366×2=0.87312731 + 00.87312731×2=0.74625463 + 10.74625463×2=0.49250926 + 10.49250926×2=0.98501851 + 00.98501851×2=0.97003702 + 10.97003702×2=0.94007404 + 10.94007404×2=0.88014809 + 10.88014809×2=0.76029617 + 10.76029617×2=0.52059234 + 10.52059234×2=0.04118468 + 10.04118468×2=0.08236937 + 00.08236937×2=0.16473874 + 0...Therefore(e)10= (10.1011011111100. . .)2.7 (a)(1010101)2= (20+ 22+ 24+ 26)10= (1 + 4 + 16 + 64)10= (85)107 (b)(1011.101)2= (23+ 21+ 20+ 2−1+ 2−3)10= (11 +12+18)10= (93/8)10.7 (c)(10111.01)2= (24+ 22+ 21+ 20)10+ (0.01)2. Setx= (0.01)2. Then22x−x= (01)2= 1impliesx=13. Therefore(10111.01)2= (23 +13)10= (70/3)10.7 (d)(110.10)2= (22+ 21)10+ (0.10)2. Setx= (0.10)2. Then22x−x= (10)2impliesx=23.Therefore(110.10)2= (6 +23)10= (20/3)10.7 (e)(10.110)2= (2)10+ (0.110)2. Setx= (0.110)2. Then23x−x= (110)2= 6impliesx= 6/7. Therefore(10.110)2= (2 +67)10= (20/7)10.7 (f)(110.1101)2= (6)10+ (12)10+ (0.0101)2= (132+x2)10, wherex= (0.101)2.Since23x−x= (101)2= 5,x= 5/7. Therefore(110.1101)2= (132+5712)10= (48/7)10.7 (g)(10.0101101)2= (2)10+(14)10+18(0.1101)2. Setx= (0.1101)2. Then24x−x= (1101)2=13, implying thatx=1315. Therefore(10.0101101)2= (94+181315)10= (283/120)10.7 (h)(111.1)2= (7)10+ (0.1)2= (7)10+x, wherex= (0.1)2. Since21x−x= (1)2,x= 1,and(111.1)2= (7 + 1)10= (8)10.8 (a)(11011)2= (20+ 21+ 23+ 24)10= (1 + 2 + 8 + 16)10= (27)108 (b)(110111.001)2= (25+ 24+ 22+ 21+ 20+ 2−3)10= (55 +18)10.8 (c)(111.001)2= (22+ 21+ 20)10+ (0.001)2. Setx= (0.001)2. Then23x−x= (001)2= 1impliesx= 1/7. Therefore(111.001)2= (7 + 1/7)10.

Loading page image...

8CHAPTER0FUNDAMENTALS8 (d)(1010.01)2= (23+ 21)10+ (0.01)2. Setx= (0.01)2. Then22x−x= (01)2impliesx=13.Therefore(1010.01)2= (10 +13)10= (10 + 1/3)10.8 (e)(10111.10101)2= (10111.10)2= (24+ 22+ 21+ 20)10+ (0.10)2. Setx= (0.10)2. Then22x−x= (10)2= 2impliesx= 2/3. Therefore(10111.10101)2= (23 +23)10.8 (f)(1111.010001)2= (15)10+ (1/4)10+18(0.001)2= (15 + 1/4 +x8)10, wherex= (0.001)2.Since23x−x= (001)2= 5,x= 1/7. Therefore(1111.010001)2= (15 + 1/4 +1817)10=(15 + 15/56)10.EXERCISES 0.3Floating Point Representation of Real Numbers1 (a)(14)10= (0.01)2; fl(14) = +1.0×2−2.1 (b)(13)10= (0.01)2=+1.01010101010101010101010101010101010101010101010101010101. . .×2−2.The Rounding to Nearest Rule says to round down when the53rd bit is0.fl(13) = +1.0101010101010101010101010101010101010101010101010101×2−2.1 (c)(23)10= (0.10)2=+1.01010101010101010101010101010101010101010101010101010101. . .×2−1.fl(23) = +1.0101010101010101010101010101010101010101010101010101×2−1.1 (d)(0.9)10= (0.11100)2=+1.11001100110011001100110011001100110011001100110011001100. . .×2−1.The Rounding to Nearest Rule says to round up since the53rd bit is nonzero, and further bitsare nonzero.fl(0.9) = +1.1100110011001100110011001100110011001100110011001101×2−1.2 (a)(9.5)10= (1001.1)2; fl(9.5) = 1.0011×23.2 (b)(9.6)10= (1001.1001)2= 1.0011001×23=+1.00110011001100110011001100110011001100110011001100110011. . .×23.fl(9.6) = +1.0011001100110011001100110011001100110011001100110011×23.2 (c)(100.2)10= (1100100.0011)2= 1.1001000011×26=+1.10010000110011001100110011001100110011001100110011001100. . .×26.fl(100.2) = +1.1001000011001100110011001100110011001100110011001101×26.2 (d)(447)10= (6 +27)10= (110.010)2=+1.10010010010010010010010010010010010010010010010010010010. . .×22.fl(447)= +1.1001001001001001001001001001001001001001001001001001×22.3Note that fl(5) = 1.01×22. Adding1as bit3,4, . . . ,52of the mantissa will not incur roundingerror. These correspond to2−kfork= 1,2, . . . ,50.4Note that fl(19) = 1.0011×24. Adding1to bit52of the mantissa, corresponding to19 + 2−48,will not be rounded away, and so48is the largest suchk.

Loading page image...

SECTION0.3FLOATINGPOINTREPRESENTATION OFREALNUMBERS95 (a)1 + (2−51+ 2−53) =+1.00000000000000000000000000000000000000000000000000101×20.fl(1 + (2−51+ 2−53)) =+1.0000000000000000000000000000000000000000000000000010×20,using the Round-ing to Nearest Rule. Therefore fl((1 + (2−51+ 2−53))−1) =.0000000000000000000000000000000000000000000000000010= 1.0000000000000000000000000000000000000000000000000000×2−51= 2−51.5 (b)1 + (2−51+ 2−52+ 2−53) =+1.00000000000000000000000000000000000000000000000000111×20.fl(1 + (2−51+ 2−52+ 2−53)) =+1.0000000000000000000000000000000000000000000000000100×20,using the Round-ing to Nearest Rule. Therefore fl((1 + (2−51+ 2−52+ 2−53))−1) =.0000000000000000000000000000000000000000000000000100= 1.0000000000000000000000000000000000000000000000000000×2−50= 2−50.6 (a)1 + (2−51+ 2−52+ 2−54)= +1.000000000000000000000000000000000000000000000000001101×20.fl(1 + (2−51+ 2−52+ 2−54)) =+1.0000000000000000000000000000000000000000000000000011×20,using the Round-ing to Nearest Rule. Therefore fl((1 + (2−51+ 2−52+ 2−54))−1) =.0000000000000000000000000000000000000000000000000011=1.1000000000000000000000000000000000000000000000000000×2−51=2−51+ 2−52= 3"mach.6 (b)1 + (2−51+ 2−52+ 2−60) =+1.000000000000000000000000000000000000000000000000001100000001×20.fl(1 + (2−51+ 2−52+ 2−60)) =+1.0000000000000000000000000000000000000000000000000011×20,using the Round-ing to Nearest Rule. Therefore fl((1 + (2−51+ 2−52+ 2−60))−1) =.0000000000000000000000000000000000000000000000000011=1.1000000000000000000000000000000000000000000000000000×2−51= 2−51+ 2−52= 3"mach.7 (a)(8)10= (1000.)2= 1.0×23. The biased exponent is3+1023 = 1026, which is210+2. Thesign is0(positive), so the sign/exponent is represented by the binary string0100 0000 0010.The mantissa is52zeros, so the machine representation is the 64 bits0100 0000 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000or4020000000000000in hex format.7 (b)(21)10= (10101.)2= 1.0101×24. The biased exponent is4 + 1023 = 1027 = 210+ 3,represented by100 0000 0011. The machine representation is0100 0000 0011 0101 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

Loading page image...

10CHAPTER0FUNDAMENTALSor4035000000000000in hex format.7 (c)(1/8)10= 1.0×2−3. The biased exponent is−3 + 1023 = 1020 = 210−4, represented by011 1111 1100. The machine representation is0011 1111 1100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000or3fc0000000000000in hex format.7 (d)(1/3)10= 1.01×2−2, and after rounding down, fl(1/3) = 1.0101. . .0101×2−2. Thebiased exponent is−2 + 1023 = 1021 = 210−3, represented by011 1111 1101. The machinerepresentation is0011 1111 1101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101or3fd5555555555555in hex format.7 (e)(2/3)10= 1.01×2−1, and after rounding down, fl(1/3) = 1.0101. . .0101×2−1. Thebiased exponent is−1 + 1023 = 1022 = 210−2, represented by011 1111 1110. The machinerepresentation is0011 1111 1110 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101or3fe5555555555555in hex format.7 (f)(0.1)10= 1.1001×2−4, and after rounding up, fl(0.1) = 1.1001. . .1001 1010×2−4. Thebiased exponent is−4 + 1023 = 1019 = 210−5, represented by011 1111 1011. The machinerepresentation is0011 1111 1011 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1010or3fb999999999999ain hex format.7 (g)(−0.1)10=−1.1001×2−4, and after rounding, fl(−0.1) =−1.1001. . .1001 1010×2−4.The biased exponent is−4 + 1023 = 1019 = 210−5, represented by011 1111 1011. Themachine representation is1011 1111 1011 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1010orbfb999999999999ain hex format.7 (h)(−0.2)10=−1.1001×2−3, and after rounding, fl(−0.2) =−1.1001. . .1001 1010×2−3.The biased exponent is−3 + 1023 = 1020 = 210−4, represented by011 1111 1100. Themachine representation is1011 1111 1100 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1010orbfc999999999999ain hex format.8Yes. Yes. No, under chopping,1/3 + 2/3 = 1−"mach.9 (a)(7/3)10= 1.0010×21, and after rounding, fl(7/3) = 1.0010. . .1010 1011×21.(4/3)10=1.01×20, and after rounding, fl(4/3) = 1.01. . .0101 0101×20. Subtracting gives1.00101010101010101010101010101010101010101010101010110×21−0.10101010101010101010101010101010101010101010101010101×21=0.10000000000000000000000000000000000000000000000000001×21

Loading page image...

SECTION0.3FLOATINGPOINTREPRESENTATION OFREALNUMBERS11that is normalized to=1.0000000000000000000000000000000000000000000000000001×20,which is1 +"mach. After subtracting1, the result is that the double precision floating pointversion of(7/3−4/3)−1is"mach.9 (b)(4/3)10= 1.01×20, and after rounding, fl(4/3) = 1.01. . .0101 0101×20.(1/3)10=1.01×2−2, and after rounding, fl(1/3) = 1.01. . .0101 0101×2−2. Subtracting gives1.010101010101010101010101010101010101010101010101010100×20−0.010101010101010101010101010101010101010101010101010101×20=0.111111111111111111111111111111111111111111111111111111×20that normalizes to=1.11111111111111111111111111111111111111111111111111111×2−1and rounds to=10.0000000000000000000000000000000000000000000000000000×2−1which is1.0×20. After subtracting1, the result is machine zero, not"mach.10 (a)No.10 (b)Yes.11The associative law of addition fails for floating point addition with the Rounding to NearestRule, for example, because1 + ("mach/2 +"mach/2) = 1 +"mach>1, while(1 +"mach/2) +"mach/2 = 1, because1 +"mach/2 = 1.12 (a)fl(1/3) = 1.0101. . .01×2−2, with relative rounding error of2−54<"mach/2 = 2−53.12 (b)fl(3.3) = 1.101001100110. . .0110×21,3.3−fl(3.3) = 0.4×2−51with relative roundingerror of8"mach/33.12 (c)fl(9/7) = 1.010010. . .0100101×20, fl(9/7)−9/7 = 3"mach/7, with relative roundingerror of"mach/3.13(a)2, represented by010. . .0(b)2−511, represented by0010. . .0(c)0, represented by10. . .0.When bit4through12is the nonzero bit, the floating point number is positive but less than2−511. When bit13through64is the nonzero bit, the number is positive and subnormal, soless than2−511.14(a)0(b)2−51(c)2−51

Preview Mode

This document has 309 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

Solution Manual for Numerical Analysis, 3rd Edition

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

Company

Explore

Study Tools