Solution Manual for Numerical Analysis, 3rd Edition

Preview (16 of 314 Pages)

100%

Purchase to unlock

Loading page image...

SOLUTIONSMANUALNUMERICALANALYSISTHIRDEDITIONTimothy SauerGeorge Mason University

Loading page image...

iiiTable of ContentsChapter 0: Fundamentals0.1Evaluating a Polynomial10.2Binary Numbers20.3Floating Point Representation of Real Numbers80.4Loss of Significance130.5Review of Calculus15Chapter 1: Solving Equations1.1The Bisection Method171.2Fixed-Point Iteration191.3Limits of Accuracy241.4Newton’s Method251.5Root-Finding without Derivatives28Chapter 2: Systems 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 3: Interpolation3.1Data and Interpolating Functions633.2Interpolation Error673.3Chebyshev Interpolation713.4Cubic Splines753.5Bézier Curves85Chapter 4: Least Squares4.1Least Squares and the Normal Equations914.2A Survey of Models984.3QR Factorization1054.4GMRES Method1154.5Nonlinear Least Squares121

Loading page image...

ivChapter 5: Numerical Differentiation and Integration5.1Numerical Differentiation1275.2Newton-Cotes Formulas for Numerical Integration1365.3Romberg Integration1465.4Adaptive Quadrature1505.5Gaussian Quadrature155Chapter 6: Ordinary Differential Equations6.1Initial Value Problems1596.2Analysis of IVP Solvers1686.3Systems of Ordinary Differential Equations1766.4Runge-Kutta Methods and Applications1826.5Variable Step-Size Methods1926.6Implicit Methods and Stiff Equations1936.7Multistep Methods195Chapter 7: Boundary Value Problems7.1Shooting Method2077.2Finite Difference Methods2117.3Collocation and the Finite Element Method220Chapter 8: Partial Differential Equations8.1Parabolic Equations2258.2Hyperbolic Equations2288.3Elliptic Equations2308.4Nonlinear Partial Differential Equations237Chapter 9: Random Numbers and Applications9.1Random Numbers2399.2Monte Carlo Simulation2429.3Discrete and Continuous Brownian Motion2439.4Stochastic Differential Equations245Chapter 10: Trigonometric Interpolation and the FFT10.1The Fourier Transform25310.2Trigonometric Interpolation25610.3The FFT and Signal Processing265

Loading page image...

vChapter 11: Compression11.1The Discrete Cosine Transform27111.2Two-Dimensional DCT and Image Compression27611.3Huffman Coding28011.4Modified DCT and Audio Compression284Chapter 12: Eigenvalues and Singular Values12.1Power Iteration Methods29312.2QR Algorithm29712.3Singular Value Decomposition30112.4Applications of the SVD305Chapter 13: Optimization13.1Unconstrained Optimization without Derivatives30713.2Unconstrained Optimization with Derivatives309

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.1

Loading page image...

2The 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)22

Loading page image...

2 (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.3

Loading page image...

3 (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.4

Loading page image...

4 (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.5

Loading page image...

4 (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...6

Loading page image...

Therefore(π)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.7

Loading page image...

8 (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.8

Loading page image...

5 (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= 3mach.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= 3mach.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 00009

Loading page image...

or4035000000000000in 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×2110

Preview Mode

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

Report

Study Now!

Document Details

Related Documents

Solution Manual for Numerical Analysis, 2nd 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