An Introduction to Numerical Methods and Analysis

James F. Epperson, PHD, is Associate Editor of Mathematical Reviews. Dr. Epperson received his PhD from Carnegie Mellon University, and his research interests include the numerical solution of nonlinear evolution equations via finite difference methods, the use of kernel functions to solve evolution equations, and numerical methods in mathematical finance.

Preface. 1. Introductory Concepts and Calculus Review. 1.1 Basic Tools of Calculus. 1.1.1 Taylor's Theorem. 1.1.2 Mean Value and Extreme Value Theorems. 1.2 Error, Approximate Equality, and Asymptotic Order Notation. 1.2.1 Error. 1.2.2 Notation: Approximate Equality. 1.2.3 Notation: Asymptotic Order. 1.3 A Primer on Computer Arithmetic. 1.4 A Word on Computer Languages and Software. 1.5 Simple Approximations. 1.6 Application: Approximating the Natural Logarithm. References. 2. A Survey of Simple Methods and Tools. 2.1 Horner's Rule and Nested Multiplication. 2.2 Difference Approximations to the Derivative. 2.3 Application: Euler's Method for Initial Value Problems. 2.4 Linear Interpolation. 2.5 Application - The Trapezoid Rule. 2.6 Solution of Tridiagonal Linear Systems. 2.7 Application: Simple Two-Point Boundary Value Problems. 3. Root-Finding. 3.1 The Bisection Method. 3.2 Newton's Method: Derivation and Examples. 3.3 How to Stop Newton's Method. 3.4 Application: Division Using Newton's Method. 3.5 The Newton Error Formula. 3.6 Newton's Method: Theory and Convergence. 3.7 Application: Computation of the Square Root. 3.8 The Secant Method: Derivation and Examples. 3.9 Fixed Point Iteration. 3.10 Special Topics in Root-finding Methods. 3.10.1 Extrapolation and Acceleration. 3.10.2 Variants of Newton's Method. 3.10.3 The Secant Method: Theory and Convergence. 3.10.4 Multiple Roots. 3.10.5 In Search of Fast Global Convergence: Hybrid Algorithms. 3.11 Literature and Software Discussion 156. References. 4. Interpolation and Approximation. 4.1 Lagrange Interpolation. 4.2 Interpolation and Divided Differences. 4.3 Interpolation Error. 4.4 Application: Muller's Method and Inverse Quadratic Interpolation. 4.5 Application: More Approximations to the Derivative. 4.6 Hermite Interpolation. 4.7 Piecewise Polynomial Interpolation. 4.8 An Introduction to Splines. 4.8.1 Definition of the Problem. 4.8.2 Cubic B-Splines. 4.9 Application: Solution of Boundary Value Problems. 4.10 Least Squares Concepts in Approximation. 4.10.1 An Introduction to Data Fitting. 4.10.2 Least Squares Approximation and Orthogonal Polynomials. 4.11 Advanced Topics in Interpolation Error. 4.11.1 Stability of Polynomial Interpolation. 4.11.2 The Runge Example. 4.11.3 The Chebyshev nodes. 4.12 Literature and Software Discussion. References. 5. Numerical Integration. 5.1 A Review of the Definite Integral. 5.2 Improving the Trapezoid Rule. 5.3 Simpson's Rule and Degree of Precision. 5.4 The Midpoint Rule. 5.5 Application: Stirling's Formula. 5.6 Gaussian Quadrature. 5.7 Extrapolation Methods. 5.8 Special Topics in Numerical Integration. 5.8.1 Romberg Integration. 5.8.2 Quadrature with Non-Smooth Integrands. 5.8.3 Adaptive Integration. 5.8.4 Peano Estimates for the Trapezoid Rule. 5.9 Literature and Software Discussion. References. 6. Numerical Methods for Ordinary Differential Equations. 6.1 The Initial Value Problem - Background. 6.2 Euler's Method. 6.3 Analysis of Euler's Method. 6.4 Variants of Euler's Method. 6.4.1 The Residual and Truncation Error. 6.4.2 Implicit Methods and Predictor-Corrector Schemes. 6.4.3 Starting Values and Multistep Methods. 6.4.4 The Midpoint Method and Weak Stability. 6.5 Single Step Methods? Runge-Kutta. 6.6 Multi-step Methods. 6.6.1 The Adams Families. 6.6.2 The BDF Family. 6.7 Stability Issues. 6.7.1 Stability Theory for Multistep Methods. 6.7.2 Stability Regions. 6.8 Application to Systems of Equations. 6.8.1 Implementation Issues and Examples. 6.8.2 Stiff Equations. 6.8.3 A-Stability. 6.9 Adaptive Solvers. 6.10 Boundary Value Problems. 6.10.1 Simple Difference Methods. 6.10.2 Shooting Methods. 6.11 Literature and Software Discussion. References. 7. Numerical Methods for the Solution of Systems of Equations. 7.1 Linear Algebra Review. 7.2 Linear Systems and Gaussian Elimination. 7.3 Operation Counts. 7.4 The LU Factorization. 7.5 Perturbation, Conditioning and Stability. 7.5.1 Vector and Matrix Norms. 7.5.2 The Condition Number and Perturbations. 7.5.3 Estimating the Condition Number. 7.5.4 Iterative Refinement. 7.6 SPD Matrices and the Cholesky Decomposition. 7.7 Iterative Methods for Linear Systems - A Brief Survey. 7.8 Nonlinear Systems: Newton's Method and Related Ideas. 7.8.1 Newton's Method. 7.8.2 Fixed Point Methods. 7.9 Application: Numerical Solution of Nonlinear BVP's. 7.10 Literature and Software Discussion. References. 8. Approximate Solution of the Algebraic Eigenvalue Problem. 8.1 Eigenvalue Review. 8.2 Reduction to Hessenberg Form. 8.3 Power Methods. 8.4 An Overview of the QR Iteration. 8.5 Literature and Software Discussion. References. 9. A Survey of Finite Difference Methods for Partial Differential Equations. 9.1 Difference Methods for the Diffusion Equation. 9.1.1 The Basic Problem. 9.1.2 The Explicit Method and Stability. 9.1.3 Implicit Methods and the Crank-Nicolson Method. 9.2 Difference Methods for Poisson Equations. 9.2.1 Discretization. 9.2.2 Banded Cholesky Solvers. 9.2.3 Iteration and the Method of Conjugate Gradients. 9.3 Literature and Software Discussion. References. Appendix A: Proofs of Selected Theorems, and Other Additional Material. A.1 Proofs of the Interpolation Error Theorems. A.2 Proof of Stability. A.3 Stiff Systems of Differential Equations and Eigenvalues. A.4 The Matrix Perturbation Theorem. Index.