Numerical Analysis: International Edition

Numerical Analysis, designed to be used in a one-year course for students in engineering, science and mathematics, helps the student gain a deeper understanding of numerical analysis by highlighting the five major ideas of the discipline: Convergence, Complexity, Conditioning, Compression, and Orthogonality and connecting back to them throughout the text. Each chapter contains a Reality Check, an extended foray into a relevant application area that can be used as a springboard for individual or team projects. MATLAB is used throughout to demonstrate and implement numerical methods.

Table of Contents:
CHAPTER 0. Fundamentals 0.1 Evaluating a polynomial 0.2 Binary numbers 0.2.1 Decimal to binary 0.2.2 Binary to decimal 0.3 Floating point representation of real numbers 0.3.1 Floating point formats 0.3.2 Machine representation 0.3.3 Addition of floating point numbers 0.4 Loss of significance 0.5 Review of calculus 0.6 Software and Further Reading CHAPTER 1. Solving Equations 1.1 The Bisection Method 1.1.1 Bracketing a root 1.1.2 How accurate and how fast? 1.2 Fixed point iteration 1.2.1 Fixed points of a function 1.2.2 Geometry of Fixed Point Iteration 1.2.3 Linear Convergence of Fixed Point Iteration 1.2.4 Stopping criteria 1.3 Limits of accuracy 1.3.1 Forward and backward error 1.3.2 The Wilkinson polynomial 1.3.3 Sensitivity and error magnification 1.4 Newton’s Method 1.4.1 Quadratic convergence of Newton’s method 1.4.2 Linear convergence of Newton’s method 1.5 Root-finding without derivatives 1.5.1 Secant method and variants 1.5.2 Brent’s Method REALITY CHECK 1: Kinematics of the Stewart platform 1.6 Software and Further Reading CHAPTER 2. Systems of Equations 2.1 Gaussian elimination 2.1.1 Naive Gaussian elimination 2.1.2 Operation counts 2.2 The LU factorization 2.2.1 Backsolving with the LU factorization 2.2.2 Complexity of the LU factorization 2.3 Sources of error 2.3.1 Error magnification and condition number 2.3.2 Swamping 2.4 The PA=LU factorization 2.4.1 Partial pivoting 2.4.2 Permutation matrices 2.4.3 PA = LU factorization 2.4.4 Matlab commands for linear systems 2.5 Iterative methods 2.5.1 Jacobi Method 2.5.2 Gauss-Seidel Method and SOR 2.5.3 Convergence of iterative methods 2.5.4 Sparse matrix computations REALITY CHECK 2: The Euler-Bernoulli Beam 2.6 Conjugate Gradient Method 2.6.1 Positive-definite matrices 2.6.2 Conjugate Gradient Method 2.7 Nonlinear systems of equations 2.7.1 Multivariate Newton’s method 2.7.2 Broyden’s method 2.8 Software and Further Reading CHAPTER 3. Interpolation 3.1 Data and interpolating functions 3.1.1 Lagrange interpolation 3.1.2 Newton’s divided differences 3.1.3 How many degree d polynomials pass through n points? 3.1.4 Code for interpolation 3.1.5 Representing functions by approximating polynomials 3.2 Interpolation error 3.2.1 Interpolation error formula 3.2.2 Proof of Newton form and error formula 3.2.3 Runge phenomenon 3.3 Chebyshev interpolation 3.3.1 Chebyshev’s Theorem 3.3.2 Chebyshev polynomials 3.3.3 Change of interval 3.4 Cubic splines 3.4.1 Properties of splines 3.4.2 Endpoint conditions 3.5 B´ezier curves REALITY CHECK 3: Constructing fonts from B´ezier splines 3.6 Software and Further Reading CHAPTER 4. Least Squares 4.1 Inconsistent systems of equations 4.2 Linear and nonlinear models 4.2.1 Periodic data 4.2.2 Data linearization 4.3 QR factorization 4.3.1 Gram-Schmidt orthogonalization and least squares 4.3.2 Householder reflectors 4.4 Nonlinear least squares 4.4.1 Gauss-Newton method 4.4.2 Models with nonlinear coefficients REALITY CHECK 4: GPS, conditioning and nonlinear least squares 4.5 Software and Further Reading CHAPTER 5. Numerical Differentiation and Integration 5.1 Numerical differentiation 5.1.1 Finite difference formulas 5.1.2 Rounding error 5.1.3 Extrapolation 5.1.4 Symbolic differentiation and integration 5.2 Newton-Cotes formulas for numerical integration 5.2.1 Three simple integrals for Newton-Cotes Formulas 5.2.2 Trapezoid rule 5.2.3 Simpson’s Rule 5.2.4 Composite Newton-Cotes Formulas 5.2.5 Open Newton-Cotes methods 5.3 Romberg integration 5.4 Adaptive quadrature 5.5 Gaussian quadrature REALITY CHECK 5: Motion control in computer-aided modelling 5.6 Software and Further Reading CHAPTER 6. Ordinary Differential Equations 6.1 Initial value problems 6.1.1 Euler’s method 6.1.2 Existence, uniqueness, and continuity for solutions 6.1.3 First-order linear equations 6.2 Analysis of IVP solvers 6.2.1 Local and global truncation error 6.2.2 The explicit trapezoid method 6.2.3 Taylor methods 6.3 Systems of ordinary differential equations 6.3.1 Higher order equations 6.3.2 The pendulum 6.3.3 Orbital mechanics 6.4 Runge-Kutta methods and applications 6.4.1 Classical examples REALITY CHECK 6: The Tacoma Narrows Bridge 6.5 Variable step-size methods 6.6 Implicit methods and stiff equations 6.7 Multistep methods 6.7.1 Generating multistep methods 6.7.2 Explicit multistep methods 6.7.3 Implicit multistep methods 6.8 Software and Further Reading CHAPTER 7. Boundary Value Problems 7.1 Solutions of boundary value problems 7.1.1 Shooting method REALITY CHECK 7: Buckling of a circular ring 7.2 Finite difference methods 7.2.1 Linear boundary value problems 7.2.2 Nonlinear boundary value problems 7.3 Collocation and the Finite Element Method 7.3.1 Collocation 7.3.2 Finite elements and the Galerkin method 7.4 Software and Further Reading CHAPTER 8. Partial Differential Equations 8.1 Parabolic equations 8.1.1 Forward difference method 8.1.2 Stability analysis of forward difference method 8.1.3 Backward difference method 8.1.4 Crank-Nicolson method 8.2 Hyperbolic equations 8.3 Elliptic equations 8.3.1 Finite difference method for elliptic equations REALITY CHECK 8: Heat distribution on a cooling fin 8.3.2 Finite element method for elliptic equations 8.4 Software and Further Reading CHAPTER 9. Random Numbers and Applications 9.1 Random numbers 9.1.1 Pseudo-random numbers 9.2 Monte-Carlo simulation 9.2.1 Power laws for Monte Carlo estimation 9.2.2 Quasi-random numbers 9.3 Discrete and continuous Brownian motion 9.3.1 Random walks 9.3.2 Continuous Brownian motion 9.4 Stochastic differential equations 9.4.1 Adding noise to ODEs 9.4.2 Numerical methods for SDEs REALITY CHECK 9: The Black-Scholes formula 9.5 Software and Further Reading CHAPTER 10. Trigonometric Interpolation and the FFT 10.1 The Fourier Transform 10.1.1 Complex arithmetic 10.1.2 Discrete Fourier Transform 10.1.3 The Fast Fourier Transform 10.2 Trigonometric interpolation 10.2.1 The DFT Interpolation Theorem 10.2.2 Orthogonality and interpolation 10.2.3 Least squares fitting with trigonometric functions 10.2.4 Sound, noise, and filtering REALITY CHECK 10: The Wiener filter 10.3 Software and Further Reading CHAPTER 11. Compression 11.1 The Discrete Cosine Transform 11.1.1 One-dimensional DCT 11.2 Two-dimensional DCT and image compression 11.2.1 The two-dimensional Discrete Cosine Transform 11.2.2 Image compression 11.2.3 Quantization 11.3 Huffman coding 11.3.1 Information theory and coding 11.3.2 Huffman coding for the JPEG format 11.4 Modified DCT and sound compression 11.4.1 Modified Discrete Cosine Transform 11.4.2 Bit quantization REALITY CHECK 11: A simple audio codec using the MDCT 11.5 Software and Further Reading CHAPTER 12. Eigenvalues and Singular Values 12.1 Power iteration methods 12.1.1 Power iteration 12.1.2 Convergence of power iteration 12.1.3 Inverse power iteration 12.1.4 Rayleigh quotient iteration 12.2 QR algorithm 12.2.1 Simultaneous iteration 12.2.2 Real Schur form and QR 12.2.3 Householder reflectors 12.2.4 Upper Hessenberg form REALITY CHECK 12: How search engines rate page qung the SVD in general 12.3.2 Special case: symmetric matrices 12.4 Applications of the SVD 12.4.1 Properties of the SVD 12.4.2 Dimension reduction 12.4.3 Compression 12.4.4 Calculating the SVD 12.5 Software and Further Reading CHAPTER 13. Optimization 13.1 Unconstrained optimization without derivatives 13.1.1 Golden section search 13.1.2 Successive parabolic interpolation 13.1.3 Nelder-Mead search 13.2 Unconstrained optimization with derivatives 13.2.1 Newton’s method 13.2.2 Steepest descent 13.2.3 Conjugate gradient search 13.2.4 Nonlinear least squares REALITY CHECK 13: Molecular conformation and numerical optimization 13.3 Software and Further Reading APPENDIX Appendix A: Matrix Algebra A.1 Matrix fundamentals A.2 Block multiplication A.3 Eigenvalues and eigenvectors A.4 Symmetric matrices A.5 Vector calculus Appendix B: Introduction to Matlab B.1 Starting Matlab B.2 Matlab graphics B.3 Programming in Matlab B.4 Flow control B.5 Functions B.6 Matrix operations B.7 Animation Answers to Selected Exercises Index Bibliography

About the Author :
Timothy Sauer earned the Ph.D. degree in mathematics at the University of California, Berkeley in 1982, and is currently a professor at George Mason University. He has published articles on a wide range of topics in applied mathematics, including dynamical systems, computational mathematics, and mathematical biology.