Numerical Mathematics and Computing, Sixth Edition

Authors Ward Cheney And David Kincaid Show Students Of Science And Engineering The Potential Computers Have For Solving Numerical Problems And Give Them Ample Opportunities To Hone Their Skills In Programming And Problem Solving. The Text Also Helps Students Learn About Errors That Inevitably Accompany Scientific Computations And Arms Them With Methods For Detecting, Predicting, And Controlling These Errors. A More Theoretical Text With A Different Menu Of Topics Is The Authors' Highly Regarded Numerical Analysis: Mathematics Of Scientific Computing, Third Edition.--publisher's Website. Introduction -- Floating-point Representation And Errors -- Locating Roots Of Equations -- Interpolation And Numerical Differentiation -- Numerical Integration -- Additional Topics On Numerical Integration -- Systems Of Linear Equations -- Additional Topics Concerning Systems Of Linear Equations -- Approximation By Spline Functions -- Ordinary Differential Equations -- Systems Of Ordinary Differential Equations -- Smoothing Of Data And The Method Of Least Squares -- Monte Carlo Methods And Simulation -- Boundary-value Problems For Ordinary Differential Equations -- Partial Differential Equations -- Minimization Of Functions -- Linear Programming. Ward Cheney, David Kincaid. Includes Bibliographical References (p. 745-753) And Index. Front Cover......Page 1 Title Page......Page 4 Copyright......Page 5 Contents......Page 10 1.1 Preliminary Remarks......Page 24 Significant Digits of Precision: Examples......Page 26 Accuracy and Precision......Page 28 Rounding and Chopping......Page 29 Nested Multiplication......Page 30 First Programming Experiment......Page 32 Mathematical Software......Page 33 Additional References......Page 34 Problems 1.1......Page 35 Computer Problems 1.1......Page 37 Taylor Series......Page 43 Complete Horner’s Algorithm......Page 46 Taylor’s Theorem in Terms of (x – c)......Page 47 Taylor’s Theorem in Terms of h......Page 49 Alternating Series......Page 51 Summary......Page 53 Problems 1.2......Page 54 Computer Problems 1.2......Page 59 2.1 Floating-Point Representation......Page 66 Normalized Floating-Point Representation......Page 67 Single-Precision Floating-Point Form......Page 69 Double-Precision Floating-Point Form......Page 71 Computer Errors in Representing Numbers......Page 73 Notation fl(x) and Backward Error Analysis......Page 74 Summary......Page 77 Problems 2.1......Page 78 Computer Problems 2.1......Page 82 Significant Digits......Page 84 Computer-Caused Loss of Significance......Page 85 Theorem on Loss of Precision......Page 86 Avoiding Loss of Significance in Subtraction......Page 87 Range Reduction......Page 90 Problems 2.2......Page 91 Computer Problems 2.2......Page 94 Introduction......Page 99 Bisection Algorithm and Pseudocode......Page 101 Examples......Page 102 Convergence Analysis......Page 104 False Position (Regula Falsi) Method and Modifications......Page 106 Problems 3.1......Page 108 Computer Problems 3.1......Page 110 3.2 Newton’s Method......Page 112 Interpretations of Newton’s Method......Page 113 Illustration......Page 115 Convergence Analysis......Page 116 Systems of Nonlinear Equations......Page 119 Fractal Basins of Attraction......Page 122 Additional References......Page 123 Problems 3.2......Page 124 Computer Problems 3.2......Page 128 3.3 Secant Method......Page 134 Secant Algorithm......Page 135 Convergence Analysis......Page 137 Fixed-Point Iteration......Page 140 Summary......Page 141 Problems 3.3......Page 142 Computer Problems 3.3......Page 144 Preliminary Remarks......Page 147 Polynomial Interpolation......Page 148 Interpolating Polynomial: Lagrange Form......Page 149 Interpolating Polynomial: Newton Form......Page 151 Nested Form......Page 153 Calculating Coefficients a[sub(i)] Using Divided Differences......Page 154 Algorithms and Pseudocode......Page 159 Vandermonde Matrix......Page 162 Inverse Interpolation......Page 164 Polynomial Interpolation by Neville’s Algorithm......Page 165 Interpolation of Bivariate Functions......Page 167 Summary......Page 168 Problems 4.1......Page 169 Computer Problems 4.1......Page 175 4.2 Errors in Polynomial Interpolation......Page 176 Runge Function......Page 177 Theorems on Interpolation Errors......Page 179 Summary......Page 183 Problems 4.2......Page 184 Computer Problems 4.2......Page 186 First-Derivative Formulas via Taylor Series......Page 187 Richardson Extrapolation......Page 189 First-Derivative Formulas via Interpolation Polynomials......Page 193 Second-Derivative Formulas via Taylor Series......Page 196 Summary......Page 197 Problems 4.3......Page 198 Computer Problems 4.3......Page 201 Definite and Indefinite Integrals......Page 203 Lower and Upper Sums......Page 204 Riemann-Integrable Functions......Page 206 Examples and Pseudocode......Page 207 Problems 5.1......Page 210 Computer Problems 5.1......Page 211 5.2 Trapezoid Rule......Page 213 Uniform Spacing......Page 214 Error Analysis......Page 215 Applying the Error Formula......Page 218 Recursive Trapezoid Formula for Equal Subintervals......Page 219 Multidimensional Integration......Page 221 Summary......Page 222 Problems 5.2......Page 223 Computer Problems 5.2......Page 226 Description......Page 227 Pseudocode......Page 228 Euler-Maclaurin Formula......Page 229 General Extrapolation......Page 232 Additional References......Page 234 Problems 5.3......Page 235 Computer Problems 5.3......Page 237 Basic Simpson’s Rule......Page 239 Simpson’s Rule......Page 242 Composite Simpson’s Rule......Page 243 An Adaptive Simpson’s Scheme......Page 244 Example Using Adaptive Simpson Procedure......Page 247 Newton-Cotes Rules......Page 248 Summary......Page 249 Problems 6.1......Page 250 Computer Problems 6.1......Page 252 Description......Page 253 Change of Intervals......Page 254 Gaussian Nodes and Weights......Page 255 Legendre Polynomials......Page 257 Summary......Page 260 Problems 6.2......Page 262 Computer Problems 6.2......Page 264 7.1 Naive Gaussian Elimination......Page 268 A Larger Numerical Example......Page 270 Algorithm......Page 271 Pseudocode......Page 273 Testing the Pseudocode......Page 276 Residual and Error Vectors......Page 277 Problems 7.1......Page 278 Computer Problems 7.1......Page 280 Naive Gaussian Elimination Can Fail......Page 282 Partial Pivoting and Complete Partial Pivoting......Page 284 Gaussian Elimination with Scaled Partial Pivoting......Page 285 A Larger Numerical Example......Page 288 Pseudocode......Page 289 Long Operation Count......Page 292 Summary......Page 294 Problems 7.2......Page 295 Computer Problems 7.2......Page 299 7.3 Tridiagonal and Banded Systems......Page 303 Tridiagonal Systems......Page 304 Strictly Diagonal Dominance......Page 305 Pentadiagonal Systems......Page 306 Block Pentadiagonal Systems......Page 308 Summary......Page 309 Problems 7.3......Page 310 Computer Problems 7.3......Page 311 8.1 Matrix Factorizations......Page 316 Numerical Example......Page 317 Formal Derivation......Page 319 Solving Linear Systems Using LU Factorization......Page 323 LDL[sup(T)] Factorization......Page 325 Cholesky Factorization......Page 328 Multiple Right-Hand Sides......Page 329 Example Using Software Packages......Page 330 Summary......Page 332 Problems 8.1......Page 334 Computer Problems 8.1......Page 339 Vector and Matrix Norms......Page 342 Condition Number and Ill-Conditioning......Page 344 Basic Iterative Methods......Page 345 Pseudocode......Page 350 Convergence Theorems......Page 351 Matrix Formulation......Page 354 Conjugate Gradient Method......Page 355 Summary......Page 358 Problems 8.2......Page 360 Computer Problems 8.2......Page 362 8.3 Eigenvalues and Eigenvectors......Page 365 Calculating Eigenvalues and Eigenvectors......Page 366 Mathematical Software......Page 367 Properties of Eigenvalues......Page 368 Gershgorin’s Theorem......Page 370 Singular Value Decomposition......Page 371 Numerical Examples of Singular Value Decomposition......Page 374 Application: Linear Differential Equations......Page 376 Application: A Vibration Problem......Page 377 Summary......Page 378 Problems 8.3......Page 379 Computer Problems 8.3......Page 381 8.4 Power Method......Page 383 Power Method Algorithms......Page 384 Aitken Acceleration......Page 386 Inverse Power Method......Page 387 Shifted (Inverse) Power Method......Page 388 Summary......Page 389 Problems 8.4......Page 390 Computer Problems 8.4......Page 391 9.1 First-Degree and Second-Degree Splines......Page 394 First-Degree Spline......Page 395 Modulus of Continuity......Page 397 Interpolating Quadratic Spline Q(x)......Page 399 Subbotin Quadratic Spline......Page 401 Summary......Page 403 Problems 9.1......Page 404 Computer Problems 9.1......Page 407 Introduction......Page 408 Natural Cubic Spline......Page 409 Algorithm for Natural Cubic Spline......Page 411 Pseudocode for Natural Cubic Splines......Page 415 Using Pseudocode for Interpolating and Curve Fitting......Page 416 Space Curves......Page 417 Smoothness Property......Page 419 Summary......Page 421 Problems 9.2......Page 422 Computer Problems 9.2......Page 426 9.3 B Splines: Interpolation and Approximation......Page 427 Interpolation and Approximation by B Splines......Page 433 Pseudocode and a Curve-Fitting Example......Page 435 Pseudocode......Page 437 Bézier Curves......Page 439 Summary......Page 441 Additional References......Page 442 Problems 9.3......Page 443 Computer Problems 9.3......Page 446 Initial-Value Problem: Analytical versus Numerical Solution......Page 449 Solving Differential Equations and Integration......Page 451 Vector Fields......Page 452 Taylor Series Methods......Page 454 Euler’s Method Pseudocode......Page 455 Taylor Series Method of Higher Order......Page 456 Summary......Page 458 Problems 10.1......Page 459 Computer Problems 10.1......Page 461 10.2 Runge-Kutta Methods......Page 462 Taylor Series for f (x, y)......Page 463 Runge-Kutta Method of Order 2......Page 464 Runge-Kutta Method of Order 4......Page 465 Pseudocode......Page 466 Summary......Page 467 Problems 10.2......Page 468 Computer Problems 10.2......Page 470 An Adaptive Runge-Kutta-Fehlberg Method......Page 473 An Industrial Example......Page 477 Adams-Bashforth-Moulton Formulas......Page 478 Stability Analysis......Page 479 Summary......Page 482 Problems 10.3......Page 483 Computer Problems 10.3......Page 484 Uncoupled and Coupled Systems......Page 488 Taylor Series Method......Page 489 Vector Notation......Page 490 Taylor Series Method: Vector Notation......Page 491 Runge-Kutta Method......Page 492 Autonomous ODE......Page 494 Summary......Page 496 Problems 11.1......Page 497 Computer Problems 11.1......Page 498 Higher-Order Differential Equations......Page 500 Autonomous ODE Systems......Page 502 Problems 11.2......Page 503 Computer Problems 11.2......Page 505 A Predictor-Corrector Scheme......Page 506 Pseudocode......Page 507 An Engineering Example......Page 511 Some Remarks about Stiff Equations......Page 512 Summary......Page 514 Computer Problems 11.3......Page 515 Linear Least Squares......Page 518 Linear Example......Page 521 Nonpolynomial Example......Page 522 Basis Functions {g[sub(0)], g[sub(1)], . . . , g[sub(n)]}......Page 523 Summary......Page 524 Problems 12.1......Page 525 Orthonormal Basis Functions {g[sub(0)], g[sub(1)], . . . , g[sub(n)]}......Page 528 Outline of Algorithm......Page 531 Smoothing Data: Polynomial Regression......Page 533 Summary......Page 538 Problems 12.2......Page 539 Computer Problems 12.2......Page 540 12.3 Other Examples of the Least-Squares Principle......Page 541 Use of a Weight Function w (x)......Page 542 Nonlinear Example......Page 543 Linear and Nonlinear Example......Page 544 Additional Details on SVD......Page 545 Using the Singular Value Decomposition......Page 547 Problems 12.3......Page 550 Computer Problems 12.3......Page 553 13.1 Random Numbers......Page 555 Random-Number Algorithms and Generators......Page 556 Examples......Page 558 Uses of Pseudocode Random......Page 560 Problems 13.1......Page 564 Computer Problems 13.1......Page 565 Numerical Integration......Page 567 Example and Pseudocode......Page 568 Computing Volumes......Page 570 Ice Cream Cone Example......Page 571 Computer Problems 13.2......Page 572 Loaded Die Problem......Page 575 Birthday Problem......Page 576 Buffon’s Needle Problem......Page 578 Two Dice Problem......Page 579 Neutron Shielding......Page 580 Additional References......Page 581 Computer Problems 13.3......Page 582 14.1 Shooting Method......Page 586 Shooting Method Algorithm......Page 588 Summary......Page 590 Problems 14.1......Page 591 Finite-Difference Approximations......Page 593 The Linear Case......Page 594 Pseudocode and Numerical Example......Page 595 Shooting Method in the Linear Case......Page 597 Pseudocode and Numerical Example......Page 598 Summary......Page 600 Problems 14.2......Page 601 Computer Problems 14.2......Page 603 Some Partial Differential Equations from Applied Problems......Page 605 Finite-Difference Method......Page 608 Pseudocode for Explicit Method......Page 610 Crank-Nicolson Method......Page 611 Pseudocode for the Crank-Nicolson Method......Page 612 Alternative Version of the Crank-Nicolson Method......Page 613 Stability......Page 614 Summary......Page 616 Problems 15.1......Page 617 Wave Equation Model Problem......Page 619 Analytic Solution......Page 620 Numerical Solution......Page 621 Pseudocode......Page 623 Advection Equation......Page 624 Lax-Wendroff Method......Page 625 Summary......Page 626 Computer Problems 15.2......Page 627 Helmholtz Equation Model Problem......Page 628 Finite-Difference Method......Page 629 Numerical Example and Pseudocode......Page 633 Finite-Element Methods......Page 636 More on Finite Elements......Page 640 Summary......Page 642 Problems 15.3......Page 643 Computer Problems 15.3......Page 645 Unconstrained and Constrained Minimization Problems......Page 648 One-Variable Case......Page 649 Unimodal Functions F......Page 650 Fibonacci Search Algorithm......Page 651 Golden Section Search Algorithm......Page 654 Quadratic Interpolation Algorithm......Page 656 Problems 16.1......Page 658 Computer Problems 16.1......Page 660 16.2 Multivariate Case......Page 662 Taylor Series for F: Gradient Vector and Hessian Matrix......Page 663 Alternative Form of Taylor Series......Page 664 Steepest Descent Procedure......Page 666 More Advanced Algorithms......Page 667 Minimum, Maximum, and Saddle Points......Page 669 Nelder-Mead Algorithm......Page 670 Method of Simulated Annealing......Page 671 Summary......Page 673 Problems 16.2......Page 674 Computer Problems 16.2......Page 677 First Primal Form......Page 680 Numerical Example......Page 681 Transforming Problems into First Primal Form......Page 683 Dual Problem......Page 684 Second Primal Form......Page 686 Summary......Page 687 Problems 17.1......Page 688 Computer Problems 17.1......Page 692 17.2 Simplex Method......Page 693 Vertices in K and Linearly Independent Columns of A......Page 694 Simplex Method......Page 695 Problems 17.2......Page 697 17.3 Approximate Solution of Inconsistent Linear Systems......Page 698 l[sub(1)] Problem......Page 699 l[sub(∞)] Problem......Page 701 Summary......Page 703 Computer Problems 17.3......Page 705 A.1 Programming Suggestions......Page 707 Case Studies......Page 710 On Developing Mathematical Software......Page 714 B.1 Representation of Numbers in Different Bases......Page 715 Conversion of Integer Parts......Page 716 Conversion of Fractional Parts......Page 718 Base Conversion 10 ↔ 8 ↔ 2......Page 719 More Examples......Page 721 Problems B.1......Page 722 Computer Problems B.1......Page 724 C.1 More on IEEE Standard Floating-Point Arithmetic......Page 726 Vectors......Page 729 Matrices......Page 731 Matrix Product......Page 734 Other Concepts......Page 736 Cramer’s Rule......Page 738 D.2 Abstract Vector Spaces......Page 739 Linear Independence......Page 740 Linear Transformations......Page 741 Change of Basis and Similarity......Page 742 Orthogonal Matrices and Spectral Theorem......Page 743 Norms......Page 744 Gram-Schmidt Process......Page 745 Answers for Selected Problems......Page 747 Bibliography......Page 768 Index......Page 777