Solution Manual for Numerical Analysis, 3rd Edition, Timothy Sauer Latest Update

Table of Contents Chapter 0: Fundamentals 0.1 Evaluating a Polynomial 1 0.2 Binary Numbers 2 0.3 Floating Point Representation of Real Numbers 8 0.4 Loss of Significance 13 0.5 Review of Calculus 15 Chapter 1: Solving Equations 1.1 The Bisection Method 17 1.2 Fixed-Point Iteration 19 1.3 Limits of Accuracy 24 1.4 Newton’s Method 25 1.5 Root-Finding without Derivatives 28 Chapter 2: Systems of Equations 2.1 Gaussian Elimination 31 2.2 The LU Factorization 32 2.3 Sources of Error 35 2.4 The PA=LU Factorization 40 2.5 Iterative Methods 45 2.6 Methods for Symmetric Positive-Definite Matrices 49 2.7 Nonlinear Systems of Equations 57 Chapter 3: Interpolation 3.1 Data and Interpolating Functions 63 3.2 Interpolation Error 67 3.3 Chebyshev Interpolation 71 3.4 Cubic Splines 75 3.5 Bézier Curves 85 Chapter 4: Least Squares 4.1 Least Squares and the Normal Equations 91 4.2 A Survey of Models 98 4.3 QR Factorization 105 4.4 GMRES Method 115 4.5 Nonlinear Least Squares 121 Chapter 5: Numerical Differentiation and Integration 5.1 Numerical Differentiation 127 5.2 Newton-Cotes Formulas for Numerical Integration 136 5.3 Romberg Integration 146 5.4 Adaptive Quadrature 150 5.5 Gaussian Quadrature 155 Chapter 6: Ordinary Differential Equations 6.1 Initial Value Problems 159 6.2 Analysis of IVP Solvers 168 6.3 Systems of Ordinary Differential Equations 176 6.4 Runge-Kutta Methods and Applications 182 6.5 Variable Step-Size Methods 192 6.6 Implicit Methods and Stiff Equations 193 6.7 Multistep Methods 195 Chapter 7: Boundary Value Problems 7.1 Shooting Method 207 7.2 Finite Difference Methods 211 7.3 Collocation and the Finite Element Method 220 Chapter 8: Partial Differential Equations 8.1 Parabolic Equations 225 8.2 Hyperbolic Equations 228 8.3 Elliptic Equations 230 8.4 Nonlinear Partial Differential Equations 237 Chapter 9: Random Numbers and Applications 9.1 Random Numbers 239 9.2 Monte Carlo Simulation 242 9.3 Discrete and Continuous Brownian Motion 243 9.4 Stochastic Differential Equations 245 Chapter 10: Trigonometric Interpolation and the FFT 10.1 The Fourier Transform 253 10.2 Trigonometric Interpolation 256 10.3 The FFT and Signal Processing 265 Chapter 11: Compression 11.1 The Discrete Cosine Transform 271 11.2 Two-Dimensional DCT and Image Compression 276 11.3 Huffman Coding 280 11.4 Modified DCT and Audio Compression 284 Chapter 12: Eigenvalues and Singular Values 12.1 Power Iteration Methods 293 12.2 QR Algorithm 297 12.3 Singular Value Decomposition 301 12.4 Applications of the SVD 305 Chapter 13: Optimization 13.1 Unconstrained Optimization without Derivatives 307 13.2 Unconstrained Optimization with Derivatives 309 CHAPTER 1 Solving Equations EXERCISES 1.1 The Bisection Method 1 (a) Check that f(x) = x 3 9 satisfies f(2) = 1 and f(3) = 279 = 18. By the Intermediate Value Theorem, f(2)f(3) < 0 implies the existence of a root between x = 2 and x = 3. 1 (b) Define f(x) = 3x 3 2 + x x 5. Check that f(1) = 2 and f(2) = 21, so there is a root in [1; 2]. 1 (c) Define f(x) = cos 2 x x + 6. Check that f(6) > 0 and f(7) < 0. There is a root in [6; 7]. 2 (a) [0; 1] 2 (b) [1; 0] 2 (c) [1; 2] 3 (a) Start with f(x) = x 3 + 9 on [2; 3], where f(2) < 0 and f(3) > 0. The first step is to evaluate f( 5 2 ) = > 0, which implies the new interval is [2; 53 8 5 2 ]. The second step is to evaluate f( 9 4 ) = 9 > 0, giving the interval [2; 729 64 9 4 ]. The best estimate is the midpoint xc = 17 8 . 3 (b) Start with f(x) = 3x 3 2 +x x5 on [1; 2], where f(1) > 0 and f(2) < 0. Since f( 3 2 ) > 0, the second interval is [1; ]. Since f( 3 2 ) > 0, the third interval is [1; 5 4 5 4 ]. The best estimate is the endpoint xc = 9 8 . 3 (c) Start with f(x) = cos 2 x + 6 x on [6; 7], where f(6) > 0 and f(7) < 0. Since f(6:5) > 0, the second interval is [6:5; 7]. Since f(6:75) > 0, the third interval is [6:75; 7]. The best estimate is the midpoint xc = 6:875. 4 (a) 0:875 4 (b) 0:875 4 (c) 1:625 5 (a) Setting f(x) = x 4 3 x 10, check that f(2) = 2 and f(3) = 44, so there is a root in [2; 3]. 5 (b) According to (1.1), the error after n steps is less than (32)=2 n+1 . Ensuring that the error is less than 10 10 requires 1 2
n+1 10 < 10 , or 2 n+1 10 > 10 , which yields n > 10= log10 (2)1  32:2. Therefore 33 steps are required. 6 Bisection Method converges to 0, but 0 is not a root. COMPUTER PROBLEMS 1.1 1 (a) There is a root in [2; 3] (see Exercise 1.1.1). In MATLAB , use the textbook’s Program 1.1, bisect.m. Six correct decimal places corresponds to error tolerances 5  10 7 , according to Def. 1.3. The calling sequence >> f=@(x) xˆ3-9; >> xc=bisect(f,2,3,5e-7) returns the approximate root 2:080083. 1 (b) Similar to (a), on interval [1; 2]. The command >> xc=bisect(@(x) 3*xˆ3+xˆ2-x-5,1,2,5e-7) returns the approximate root 1:169726. 1 (c) Similar to (a), on interval [6; 7]. The command >> xc=bisect(@(x) cos(x)ˆ2+6-x,6,7,5e-7) returns the approximate root 6:776092. 2 (a) 0:75487767 2 (b) 0:97089892 2 (c) 1:59214294 3 (a) Plots for parts (a) - (c) are: 4 3 2 1 −2 −1 1 2 −1 −2 −3 −4 (a) 2 1 −2 −1 1 2 −1 −2 (b) 2 1 −2 −1 1 2 −1 −2 (c) In part (a), it is clear from the graph that there is a root in each of the three intervals [2; 1], [1; 0], and [1; 2]. The command >> bisect(@(x) 2*xˆ3-6*x-1,-2,-1,5e-7) yields the first approximate root 1:641783. Repeating for the next two intervals gives the approximate roots 0:168254 and 1:810038. (b) There are roots in [2; 1], [0:5; 0:5], and [0:5; 1:5]. Using bisect as in part (a) yields the approximate roots 1:023482, 0:163823, and 0:788942. (c) There are roots in [1:7; 0:7], [0:7; 0:3], and [0:3; 1:3]. Using bisect as in part (a) yields the approximate roots 0:818094, 0, and 0:506308. 4 (a) [1; 2], 27 steps, 1:41421356 4 (b) [1; 2], 27 steps, 1:73205081 4 (c) [2; 3], 27 steps, 2:23606798 5 (a) There is a root in the interval [1; 2]. Eight decimal place accuracy implies an error tolerance of 5  10 9 . The command >> bisect(@(x) xˆ3-2,1,2,5e-9) yields the approximate cube root 1:25992105 in 27 steps. 5 (b) There is a root in the interval [1; 2]. Using bisect as in (a) gives the approximate cube root 1:44224957 in 27 steps. 5 (c) There is a root in the interval [1; 2]. Using bisect as in (a) gives the approximate cube root 1:70997595 in 27 steps. 6 0:785398 7 Trial and error, or a plot of f(x) = det(A) 1000, shows that f(18)f(17) < 0 and f(9)f(10) < 0. Applying bisect to f(x) yields the roots 17:188498 and 9:708299. The backward errors of the roots are jf(17:188498)j = 0:0018 and jf(9:708299)j = 0:00014. 8 2:948011 9 The desired height is the root of the function f(H) = H 2 (1 H) 1. Using 1 3 >> bisect(@(H) pi*Hˆ2*(1-H/3)-1,0,1,0.001) gives the solution 636 mm. EXERCISES 1.2 Fixed-Point Iteration 1 (a) 3 x = x ) x 2 = 3 ) x =  p 3 1 (b) x 2 3x + 2 = 0 ) x = 1; 2 1 (c) x 2x + 2 = x ) x 2 p 17 5  2 4x + 2 = x ) x 2 5x + 2 = 0 ) x = 2 2 (a) 1; 2 2 (b) 2 2 (c) 1; 0; 1 3 1 3 (a) Check by substitution. For example, + 1 6 6(1) 10 = 1. 3 (b) Check by substitution.