Preface0. Fundamentals0.1 Evaluating a polynomial0.2 Binary numbers 0.2.1 Decimal to binary 0.2.2 Binary to decimal0.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 numbers0.4 Loss of significance0.5 Review of calculus0.6 Software and Further Reading 1. Solving Equations1.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 criteria1.3 Limits of accuracy 1.3.1 Forward and backward error 1.3.2 The Wilkinson polynomial 1.3.3 Sensitivity and error magnification1.4 Newton's Method 1.4.1 Quadratic convergence of Newton's method 1.4.2 Linear convergence of Newton's method1.5 Root-finding without derivatives 1.5.1 Secant method and variants 1.5.2 Brent's MethodREALITY CHECK 1: Kinematics of the Stewart platform1.6 Software and Further Reading 2. Systems of Equations2.1 Gaussian elimination 2.1.1 Naive Gaussian elimination 2.1.2 Operation counts2.2 The LU factorization 2.2.1 Backsolving with the LU factorization 2.2.2 Complexity of the LU factorization2.3 Sources of error 2.3.1 Error magnification and condition number 2.3.2 Swamping2.4 The PA=LU factorization 2.4.1 Partial pivoting 2.4.2 Permutation matrices 2.4.3 PA = LU factorizationREALITY CHECK 2: The Euler-Bernoulli Beam2.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 computations2.6 Methods for symmetric positive-definite matrices 2.6.1 Symmetric positive-definite matrices 2.6.2 Cholesky factorization 2.6.3 Conjugate Gradient Method 2.6.4 Preconditioning2.7 Nonlinear systems of equations 2.7.1 Multivariate Newton's method 2.7.2 Broyden's method2.8 Software and Further Reading 3. Interpolation3.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 polynomials3.2 Interpolation error 3.2.1 Interpolation error formula 3.2.2 Proof of Newton form and error formula 3.2.3 Runge phenomenon3.3 Chebyshev interpolation 3.3.1 Chebyshev's Theorem 3.3.2 Chebyshev polynomials 3.3.3 Change of interval3.4 Cubic splines 3.4.1 Properties of splines 3.4.2 Endpoint conditions3.5 Bezier curvesREALITY CHECK 3: Constructing fonts from Bezier splines3.6 Software and Further Reading 4. Least Squares4.1 Least squares and the normal equations 4.1.1 Inconsistent systems of equations 4.1.2 Fitting models to data4.2 Linear and nonlinear models 4.1.3 Conditioning of least squares4.2 A survey of models 4.2.1 Periodic data 4.2.2 Data linearization4.3 QR factorization 4.3.1 Gram-Schmidt orthogonalization and least squares 4.3.2 Modified Gram-Schmidt orthogonalization 4.3.3 Householder reflectors4.4 Generalized Minimum Residual (GMRES) Method 4.4.1 Krylov methods 4.4.2 Preconditioned GMRES4.5 Nonlinear least squares 4.5.1 Gauss-Newton method 4.5.2 Models with nonlinear parameters 4.5.3 Levenberg-Marquardt methodREALITY CHECK 4: GPS, conditioning and nonlinear least squares4.6 Software and Further Reading 5. Numerical Differentiation and Integration5.1 Numerical differentiation 5.1.1 Finite difference formulas 5.1.2 Rounding error 5.1.3 Extrapolation 5.1.4 Symbolic differentiation and integration5.2 Newton-Cotes formulas for numerical integration 5.2.1 Trapezoid rule 5.2.2 Simpson's Rule 5.2.3 Composite Newton-Cotes Formulas 5.2.4 Open Newton-Cotes methods5.3 Romberg integration5.4 Adaptive quadrature5.5 Gaussian quadratureREALITY CHECK 5: Motion control in computer-aided modelling5.6 Software and Further Reading 6. Ordinary Differential Equations6.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 equations6.2 Analysis of IVP solvers 6.2.1 Local and global truncation error 6.2.2 The explicit trapezoid method 6.2.3 Taylor methods6.3 Systems of ordinary differential equations 6.3.1 Higher order equations 6.3.2 Computer simulation: The pendulum 6.3.3 Computer simulation: Orbital mechanics6.4 Runge-Kutta methods and applications 6.4.1 The Runge-Kutta family 6.4.2 Computer simulation: The Hodgkin-Huxley neuron 6.4.3 Computer simulation: The Lorenz equationsREALITY CHECK 6: The Tacoma Narrows Bridge6.5 Variable step-size methods 6.5.1 Embedded Runge-Kutta pairs 6.5.2 Order 4/5 methods6.6 Implicit methods and stiff equations6.7 Multistep methods 6.7.1 Generating multistep methods 6.7.2 Explicit multistep methods 6.7.3 Implicit multistep methods6.8 Software and Further Reading 7. Boundary Value Problems7.1 Shooting method 7.1.1 Solutions of boundary value problems 7.1.2 Shooting method implementationREALITY CHECK 7: Buckling of a circular ring7.2 Finite difference methods 7.2.1 Linear boundary value problems 7.2.2 Nonlinear boundary value problems7.3 Collocation and the Finite Element Method 7.3.1 Collocation 7.3.2 Finite elements and the Galerkin method7.4 Software and Further Reading 8. Partial Differential Equations8.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 method8.2 Hyperbolic equations 8.2.1 The wave equation 8.2.2 The CFL condition8.3 Elliptic equations 8.3.1 Finite difference method for elliptic equationsREALITY CHECK 8: Heat distribution on a cooling fin 8.3.2 Finite element method for elliptic equations8.4 Nonlinear partial differential equations 8.4.1 Implicit Newton solver 8.4.2 Nonlinear equations in two space dimensions8.5 Software and Further Reading 9. Random Numbers and Applications9.1 Random numbers 9.1.1 Pseudo-random numbers 9.1.2 Exponential and normal random numbers9.2 Monte-Carlo simulation 9.2.1 Power laws for Monte Carlo estimation 9.2.2 Quasi-random numbers9.3 Discrete and continuous Brownian motion 9.3.1 Random walks 9.3.2 Continuous Brownian motion9.4 Stochastic differential equations 9.4.1 Adding noise to differential equations 9.4.2 Numerical methods for SDEsREALITY CHECK 9: The Black-Scholes formula9.5 Software and Further Reading 10. Trigonometric Interpolation and the FFT10.1 The Fourier Transform 10.1.1 Complex arithmetic 10.1.2 Discrete Fourier Transform 10.1.3 The Fast Fourier Transform10.2 Trigonometric interpolation 10.2.1 The DFT Interpolation Theorem 10.2.2 Efficient evaluation of trigonometric functions10.3 The FFT and signal processing 10.3.1 Orthogonality and interpolation 10.3.2 Least squares fitting with trigonometric functions 10.3.3 Sound, noise, and filteringREALITY CHECK 10: The Wiener filter10.4 Software and Further Reading 11. Compression11.1 The Discrete Cosine Transform 11.1.1 One-dimensional DCT 11.1.2 The DCT and least squares approximation11.2 Two-dimensional DCT and image compression 11.2.1 Two-dimensional DCT 11.2.2 Image compression 11.2.3 Quantization11.3 Huffman coding 11.3.1 Information theory and coding 11.3.2 Huffman coding for the JPEG format11.4 Modified DCT and audio compression 11.4.1 Modified Discrete Cosine Transform 11.4.2 Bit quantizationREALITY CHECK 11: A simple audio codec using the MDCT11.5 Software and Further Reading 12. Eigenvalues and Singular Values12.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 iteration12.2 QR algorithm 12.2.1 Simultaneous iteration 12.2.2 Real Schur form and QR 12.2.3 Upper Hessenberg formREALITY CHECK 12: How search engines rate page quality12.3 Singular value decomposition 12.3.1 Finding the SVD in general 12.3.2 Special case: symmetric matrices12.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 SVD12.5 Software and Further Reading 13. Optimization13.1 Unconstrained optimization without derivatives 13.1.1 Golden section search 13.1.2 Successive parabolic interpolation 13.1.3 Nelder-Mead search13.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 squaresREALITY CHECK 13: Molecular conformation and numerical optimization13.3 Software and Further Reading APPENDIXAppendix A: Matrix AlgebraA.1 Matrix fundamentalsA.2 Block multiplicationA.3 Eigenvalues and eigenvectorsA.4 Symmetric matricesA.5 Vector calculus Appendix B: Introduction to MATLABB.1 Starting MATLABB.2 MATLAB graphicsB.3 Programming in MATLABB.4 Flow controlB.5 FunctionsB.6 Matrix operationsB.7 Animation and moviesReferences