Numerical Methods

Preface xiiiChapter 1: MATHEMATICAL MODELING 11.1 Modeling in Computer Animation 21.1.1 A Model Robe 21.2 Modeling in Physics: Radiation Transport 41.3 Modeling in Sports 61.4 Ecological Models 81.5 Modeling a Web Surfer and Google 111.5.1 The Vector Space Model 111.5.2 Google's PageRank 131.6 Chapter 1 Exercises 14Chapter 2: BASIC OPERATIONS WITH MATLAB 192.1 Launching MATLAB 192.2 Vectors 202.3 Getting Help 222.4 Matrices 232.5 Creating and Running .m Files 242.6 Comments 252.7 Plotting 252.8 Creating Your Own Functions 272.9 Printing 282.10 More Loops and Conditionals 292.11 Clearing Variables 312.12 Logging Your Session 312.13 More Advanced Commands 312.14 Chapter 2 Exercises 32Chapter 3: MONTE CARLO METHODS 413.1 A Mathematical Game of Cards 413.1.1 The Odds in Texas Holdem 423.2 Basic Statistics 463.2.1 Discrete Random Variables 483.2.2 Continuous Random Variables 513.2.3 The Central Limit Theorem 533.3 Monte Carlo Integration 563.3.1 Buffon's Needle 563.3.2 Estimating Ï 583.3.3 Another Example of Monte Carlo Integration 603.4 Monte Carlo Simulation of Web Surfing 643.5 Chapter 3 Exercises 67Chapter 4: SOLUTION OF A SINGLE NONLINEAR EQUATION IN ONE UNKNOWN 714.1 Bisection 754.2 Taylor's Theorem 804.3 Newton's Method 834.4 Quasi-Newton Methods 894.4.1 Avoiding Derivatives 894.4.2 Constant Slope Method 894.4.3 Secant Method 904.5 Analysis of Fixed Point Methods 934.6 Fractals, Julia Sets, and Mandelbrot Sets 984.7 Chapter 4 Exercises 102Chapter 5: FLOATING-POINT ARITHMETIC 1075.1 Costly Disasters Caused by Rounding Errors 1085.2 Binary Representation and Base 2 Arithmetic 1105.3 Floating-Point Representation 1125.4 IEEE Floating-Point Arithmetic 1145.5 Rounding 1165.6 Correctly Rounded Floating-Point Operations 1185.7 Exceptions 1195.8 Chapter 5 Exercises 120Chapter 6: CONDITIONING OF PROBLEMS; STABILITY OF ALGORITHMS 1246.1 Conditioning of Problems 1256.2 Stability of Algorithms 1266.3 Chapter 6 Exercises 129Chapter 7: DIRECT METHODS FOR SOLVING LINEAR SYSTEMS AND LEAST SQUARES PROBLEMS 1317.1 Review of Matrix Multiplication 1327.2 Gaussian Elimination 1337.2.1 Operation Counts 1377.2.2 LU Factorization 1397.2.3 Pivoting 1417.2.4 Banded Matrices and Matrices for Which Pivoting Is Not Required 1447.2.5 Implementation Considerations for High Performance 1487.3 Other Methods for Solving Ax = b 1517.4 Conditioning of Linear Systems 1547.4.1 Norms 1547.4.2 Sensitivity of Solutions of Linear Systems 1587.5 Stability of Gaussian Elimination with Partial Pivoting 1647.6 Least Squares Problems 1667.6.1 The Normal Equations 1677.6.2 QR Decomposition 1687.6.3 Fitting Polynomials to Data 1717.7 Chapter 7 Exercises 175Chapter 8: POLYNOMIAL AND PIECEWISE POLYNOMIAL INTERPOLATION 1818.1 The Vandermonde System 1818.2 The Lagrange Form of the Interpolation Polynomial 1818.3 The Newton Form of the Interpolation Polynomial 1858.3.1 Divided Differences 1878.4 The Error in Polynomial Interpolation 1908.5 Interpolation at Chebyshev Points and chebfun 1928.6 Piecewise Polynomial Interpolation 1978.6.1 Piecewise Cubic Hermite Interpolation 2008.6.2 Cubic Spline Interpolation 2018.7 Some Applications 2048.8 Chapter 8 Exercises 206Chapter 9: NUMERICAL DIFFERENTIATION AND RICHARDSON EXTRAPOLATION 2129.1 Numerical Differentiation 2139.2 Richardson Extrapolation 2219.3 Chapter 9 Exercises 225Chapter 10: NUMERICAL INTEGRATION 22710.1 Newton-Cotes Formulas 22710.2 Formulas Based on Piecewise Polynomial Interpolation 23210.3 Gauss Quadrature 23410.3.1 Orthogonal Polynomials 23610.4 Clenshaw-Curtis Quadrature 24010.5 Romberg Integration 24210.6 Periodic Functions and the Euler-Maclaurin Formula 24310.7 Singularities 24710.8 Chapter 10 Exercises 248Chapter 11: NUMERICAL SOLUTION OF THE INITIAL VALUE PROBLEM FOR ORDINARY DIFFERENTIAL EQUATIONS 25111.1 Existence and Uniqueness of Solutions 25311.2 One-Step Methods 25711.2.1 Euler's Method 25711.2.2 Higher-Order Methods Based on Taylor Series 26211.2.3 Midpoint Method 26211.2.4 Methods Based on Quadrature Formulas 26411.2.5 Classical Fourth-Order Runge-Kutta and Runge-Kutta-Fehlberg Methods 26511.2.6 An Example Using MATLAB's ODE Solver 26711.2.7 Analysis of One-Step Methods 27011.2.8 Practical Implementation Considerations 27211.2.9 Systems of Equations 27411.3 Multistep Methods 27511.3.1 Adams-Bashforth and Adams-Moulton Methods 27511.3.2 General Linear m-Step Methods 27711.3.3 Linear Difference Equations 28011.3.4 The Dahlquist Equivalence Theorem 28311.4 Stiff Equations 28411.4.1 Absolute Stability 28511.4.2 Backward Differentiation Formulas (BDF Methods) 28911.4.3 Implicit Runge-Kutta (IRK) Methods 29011.5 Solving Systems of Nonlinear Equations in Implicit Methods 29111.5.1 Fixed Point Iteration 29211.5.2 Newton's Method 29311.6 Chapter 11 Exercises 295Chapter 12: MORE NUMERICAL LINEAR ALGEBRA: EIGENVALUES AND ITERATIVE METHODS FOR SOLVING LINEAR SYSTEMS 30012.1 Eigenvalue Problems 30012.1.1 The Power Method for Computing the Largest Eigenpair 31012.1.2 Inverse Iteration 31312.1.3 Rayleigh Quotient Iteration 31512.1.4 The QR Algorithm 31612.1.5 Google's PageRank 32012.2 Iterative Methods for Solving Linear Systems 32712.2.1 Basic Iterative Methods for Solving Linear Systems 32712.2.2 Simple Iteration 32812.2.3 Analysis of Convergence 33212.2.4 The Conjugate Gradient Algorithm 33612.2.5 Methods for Nonsymmetric Linear Systems 33412.3 Chapter 12 Exercises 345Chapter 13: NUMERICAL SOLUTION OF TWO-POINT BOUNDARY VALUE PROBLEMS 35013.1 An Application: Steady-State Temperature Distribution 35013.2 Finite Difference Methods 35213.2.1 Accuracy 35413.2.2 More General Equations and Boundary Conditions 36013.3 Finite Element Methods 36513.3.1 Accuracy 37213.4 Spectral Methods 37413.5 Chapter 13 Exercises 376Chapter 14: NUMERICAL SOLUTION OF PARTIAL DIFFERENTIAL EQUATIONS 37914.1 Elliptic Equations 38114.1.1 Finite Difference Methods 38114.1.2 Finite Element Methods 38614.2 Parabolic Equations 38814.2.1 Semidiscretization and the Method of Lines 38914.2.2 Discretization in Time 38914.3 Separation of Variables 39614.3.1 Separation of Variables for Difference Equations 40014.4 Hyperbolic Equations 40214.4.1 Characteristics 40214.4.2 Systems of Hyperbolic Equations 40314.4.3 Boundary Conditions 40414.4.4 Finite Difference Methods 40414.5 Fast Methods for Poisson's Equation 40914.5.1 The Fast Fourier Transform 41114.6 Multigrid Methods 41414.7 Chapter 14 Exercises 418APPENDIX A REVIEW OF LINEAR ALGEBRA 421A.1 Vectors and Vector Spaces 421A.2 Linear Independence and Dependence 422A.3 Span of a Set of Vectors; Bases and Coordinates; Dimension of a Vector Space 423A.4 The Dot Product; Orthogonal and Orthonormal Sets; the Gram-Schmidt Algorithm 423A.5 Matrices and Linear Equations 425A.6 Existence and Uniqueness of Solutions; the Inverse; Conditions for Invertibility 427A.7 Linear Transformations; the Matrix of a Linear Transformation 431A.8 Similarity Transformations; Eigenvalues and Eigenvectors 432APPENDIX B TAYLOR'S THEOREM IN MULTIDIMENSIONS 436References 439Index 445