Numerical Analysis: Mathematics of Scientific Computing (The Sally Series; Pure and Applied Undergraduate Texts, Vol. 2)

This Book Introduces Students With Diverse Backgrounds To Various Types Of Mathematical Analysis That Are Commonly Needed In Scientific Computing. The Subject Of Numerical Analysis Is Treated From A Mathematical Point Of View, Offering A Complete Analysis Of Methods For Scientific Computing With Appropriate Motivations And Careful Proofs. In An Engaging And Informal Style, The Authors Demonstrate That Many Computational Procedures And Intriguing Questions Of Computer Science Arise From Theorems And Proofs. Algorithms Are Presented In Pseudocode, So That Students Can Immediately Write Computer Programs In Standard Languages Or Use Interactive Mathematical Software Packages. This Book Occasionally Touches Upon More Advanced Topics That Are Not Usually Contained In Standard Textbooks At This Level.--book Jacket. 1. Mathematical Preliminaries -- 2. Computer Arithmetic -- 3. Solution Of Nonlinear Equations -- 4. Solving Systems Of Linear Equations -- 5. Selected Topics In Numerical Linear Algebra -- 6. Approximating Functions -- 7. Numerical Differentiation And Integration -- 8. Numerical Solution Of Ordinary Differential Equations -- 9. Numerical Solution Of Partial Differential Equations -- 10. Linear Programming And Related Topics -- 11. Optimization -- Appendix A. Overview Of Mathematical Software. David Kincaid, Ward Cheney. Originally Published: 3rd Ed. Pacific Grove, Ca : Brooks/cole, C2002. Includes Bibliographical References (p. 745-769) And Index. Cover......Page 1 Title......Page 2 Copyright......Page 3 Contents......Page 6 Preface......Page 10 Numerical Analysis: What Is It?......Page 16 1.1 Basic Concepts and Taylor's Theorem......Page 18 1.2 Orders of Convergence and Additional Basic Concepts......Page 30 1.3 Difference Equations......Page 43 2.1 Floating-Point Numbers and Roundoff Errors......Page 52 2.2 Absolute and Relative Errors: Loss of Significance......Page 70 2.3 Stable and Unstable Computations: Conditioning......Page 79 3.0 Introduction......Page 88 3.1 Bisection (Interval Halving) Method......Page 89 3.2 Newton's Method......Page 96 3.3 Secant Method......Page 108 3.4 Fixed Points and Functional Iteration......Page 115 3.5 Computing Roots of Polynomials......Page 124 3.6 Homotopy and Continuation Methods......Page 145 4.0 Introduction......Page 154 4.1 Matrix Algebra......Page 155 4.2 LU and Cholesky Factorizations......Page 164 4.3 Pivoting and Constructing an Algorithm......Page 178 4.4 Norms and the Analysis of Errors......Page 201 4.5 Neumann Series and Iterative Refinement......Page 212 4.6 Solution of Equations by Iterative Methods......Page 222 4.7 Steepest Descent and Conjugate Gradient Methods......Page 247 4.8 Analysis of Roundoff Error in the Gaussian Algorithm......Page 260 5.0 Review of Basic Concepts......Page 269 5.1 Martix Eigenvalue Problem: Power Method......Page 272 5.2 Schur's and Gershgorin's Theorems......Page 280 5.3 Orthogonal Factorizations and Least-Squares Problems......Page 288 5.4 Singular-Value Decomposition and Pseudo inverses......Page 302 5.5 QR-Algorithm of Francis for the Eigenvalue Problem......Page 313 6.1 Polynomial Interpolation......Page 323 6.2 Divided Differences......Page 342 6.3 Hermite Interpolation......Page 353 6.4 Spline Interpolation......Page 364 6.5 B-Splines: Basic Theory......Page 381 6.6 B-Splines: Applications......Page 392 6.7 Taylor Series......Page 403 6.8 Best Approximation: Least-Squares Theory......Page 407 6.9 Best Approximation: Chebyshev Theory......Page 420 6.10 Interpolation in Higher Dimensions......Page 435 6.11 Continued Fractions......Page 453 6.12 Trigonometric Interpolation......Page 460 6.13 Fast Fourier Transform......Page 466 6.14 Adaptive Approximation......Page 475 7.1 Numerical Differentiation and Richardson Extrapolation......Page 480 7.2 Numerical Integration Based on Interpolation......Page 493 7.3 Gaussian Quadrature......Page 507 7.4 Romberg Integration......Page 517 7.5 Adaptive Quadrature......Page 522 7.6 Sard's Theory of Approximating Functionals......Page 528 7.7 Bernoulli Polynomials and the Euler-Maclaurin Formula......Page 534 8.1 The Existence and Uniqueness of Solutions......Page 539 8.2 Taylor-Series Method......Page 545 8.3 Runge-Kutta Methods......Page 554 8.4 Multistep Methods......Page 564 8.5 Local and Global Errors: Stability......Page 572 8.6 Systems and Higher-Order Ordinary Differential Equations......Page 580 8.7 Boundary-Value Problems......Page 587 8.8 Boundary-Value Problems: Shooting Methods......Page 596 8.9 Boundary-Value Problems: Finite-Differences......Page 604 8.10 Boundary-Value Problems: Collocation......Page 608 8.11 Linear Differential Equations......Page 612 8.12 Stiff Equations......Page 623 9.1 Parabolic Equations: Explicit Methods......Page 630 9.2 Parabolic Equations: Implicit Methods......Page 638 9.3 Problems Without Time Dependence: Finite-Differences......Page 644 9.4 Problems Without Time Dependence: Galerkin Methods......Page 649 9.5 First-Order Partial Differential Equations: Characteristics......Page 657 9.6 Quasilinear Second-Order Equations: Characteristics......Page 665 9.7 Other Methods for Hyperbolic Problems......Page 675 9.8 Multigrid Method......Page 682 9.9 Fast Method s for Poisson's Equation......Page 691 10.1 Convexity and Linear Inequalities......Page 696 10.2 Linear Inequalities......Page 704 10.3 Linear Programming......Page 710 10.4 The Simplex Algorithm......Page 715 11.0 Introduction......Page 726 11.1 One-Variable Case......Page 727 11.2 Descent Methods......Page 731 11.3 Analysis of Quadratic Objective Functions......Page 734 11.4 Quadratic-Fitting Algorithms......Page 736 11.5 Nelder-Mead Algorithm......Page 737 11.6 Simulated Annealing......Page 738 11.7 Genetic Algorithms......Page 739 11.8 Convex Programming......Page 740 11.9 Constrained Minimization......Page 741 11.10 Pareto Optimization......Page 742 Appendix A: An Overview of Mathematical Software......Page 746 Bibliography......Page 760 B......Page 786 C......Page 787 D......Page 788 E......Page 789 G......Page 790 I......Page 791 L......Page 792 N......Page 794 O......Page 795 P......Page 796 R......Page 797 S......Page 798 T......Page 800 U......Page 802 Z......Page 803 Back Cover......Page 804 Numerical Analysis: What Is It? 1 1 Mathematical Preliminaries 3 1.0 Introduction 3 1.1 Basic Concepts and Taylor’s Theorem 3 1.2 Orders of Convergence and Additional Basic Concepts 15 1.3 Difference Equations 28 2 Computer Arithmetic 37 2.0 Introduction 37 2.1 Floating-Point Numbers and Roundoff Errors 37 2.2 Absolute and Relative Errors: Loss of Significance 55 2.3 Stable and Unstable Computations: Conditioning 64 3 Solution of Nonlinear Equations 73 3.0 Introduction 73 3.1 Bisection (Interval Halving) Method 74 3.2 Newton’s Method 81 3.3 Secant Method 93 3.4 Fixed Points and Functional Iteration 100 3.5 Computing Roots of Polynomials 109 3.6 Homotopy and Continuation Methods 130 4 Solving Systems of Linear Equations 139 4.0 Introduction 139 4.1 Matrix Algebra 140 4.2 LU and Cholesky Factorizations 149 4.3 Pivoting and Constructing an Algorithm 163 4.4 Norms and the Analysis of Errors 186 4.5 Neumann Series and Iterative Refinement 197 4.6 Solution of Equations by Iterative Methods 207 4.7 Steepest Descent and Conjugate Gradient Methods 232 4.8 Analysis of Roundoff Error in the Gaussian Algorithm 245 5 Selected Topics in Numerical Linear Algebra 254 5.0 Review of Basic Concepts 254 5.1 Matrix Elgenvalue Problem: Power Method 257 5.2 Schur’s and Gershgorin’s Theorems 265 5.3 Orthogonal Factorizations and Least-Squares Problems 273 5.4 Singular-Value Decomposition and Pseudoinverses 287 5.5 QR-Algorithm of Francis for the Elgenvalue Problem 298 6 Approximating Functions 308 6.0 Introduction 308 6.1 Polynomial Interpolation 308 6.2 Divided Differences 327 6.3 Hermlte Interpolation 338 6.4 Spline Interpolation 349 6.5 B-Splines: Basic Theory 366 6.6 B-Splines: Applications 377 6.7 Taylor Series 388 6.8 Best Approximation: Least-Squares Theory 392 6.9 Best Approximation: Chebyshev Theory 405 6.10 Interpolation in Higher Dimensions 420 6.11 Continued Fractions 438 6.12 Trigonometric Interpolation 445 6.13 Fast Fourier Transform 451 6.14 Adaptive Approximation 460 7 Numerical Differentiation and Integration 465 7.1 Numerical Differentiation and Richardson Extrapolation 465 7.2 Numerical Integration Based on Interpolation 478 7.3 Gaussian Quadrature 492 7.4 Romberg Integration 502 7.5 Adaptive Quadrature 507 7.6 Sard’s Theory of Approximating Functionals 513 77 Bernoulli Polynomials and the Euler-Maclaurin Formula 519 8 Numerical Solution of Ordinary Differential Equations 524 8.0 Introduction 524 8.1 The Existence and Uniqueness of Solutions 524 8.2 Taylor-Series Method 530 8.3 Runge-Kutta Methods 539 8.4 Multistep Methods 549 8.5 Local and Global Errors: Stability 557 8.6 Systems and Higher-Order Ordinary Differential Equations 565 8.7 Boundary-Value Problems 572 8.8 Boundary-Value Problems: Shooting Methods 581 8.9 Boundary-Value Problems: Finite-Differences 589 8.10 Boundary-Value Problems: Collocation 593 8.11 Linear Differential Equations 597 8.12 Stiff Equations 608 9 Numerical Solution of Partial Differential Equations 615 9.0 Introduction 615 9.1 Parabolic Equations: Explicit Methods 615 9.2 Parabolic Equations: Implicit Methods 623 9.3 Problems Without Time Dependence: Finite-Differences 629 9.4 Problems Without Time Dependence: Galerkin Methods 634 9.5 First-Order Partial Differential Equations: Characteristics 642 9.6 Quasillnear Second-Order Equations: Characteristics 650 9.7 Other Methods for Hyperbolic Problems 660 9.8 Multigrid Method 667 9.9 Fast Methods for Poisson’s Equation 676 10 Linear Programming and Related Topics 681 10.1 Convexity and Linear Inequalities 681 10.2 Linear Inequalities 689 10.3 Unear Programming 695 10.4 The Simplex Algorithm 700 11 Optimization 711 11.0 Introduction 711 11.1 One-Variable Case 712 11.2 Descent Methods 716 11.3 Analysis of Quadratic Objective Functions 719 11.4 Quadratic-Fitting Algorithms 721 11.5 Nelder-Mead Algorithm 722 11.6 Simulated Annealing 723 11.7 Genetic Algorithms 724 11.8 Convex Programming 725 11.9 Constrained Minimization 726 11.10 Pareto Optimization 727 Appendix A An Overview of Mathematical Software 731 Bibliography 745