An Introduction to Numerical Methods and Analysis

ISBN-13: 9781119604693 / Angielski / Twarda / 2021 / 672 str.

James F. Epperson

Spis treści

Preface xiii1 Introductory Concepts and Calculus Review 11.1 Basic Tools of Calculus 21.1.1 Taylor's Theorem 21.1.2 Mean Value and Extreme Value Theorems 91.2 Error, Approximate Equality, and Asymptotic Order Notation 141.2.1 Error 141.2.2 Notation: Approximate Equality 151.2.3 Notation: Asymptotic Order 161.3 A Primer on Computer Arithmetic 201.4 A Word on Computer Languages and Software 291.5 A Brief History of Scientific Computing 321.6 Literature Review 36References 362 A Survey of Simple Methods and Tools 392.1 Horner's Rule and Nested Multiplication 392.2 Difference Approximations to the Derivative 442.3 Application: Euler's Method for Initial Value Problems 522.4 Linear Interpolation 582.5 Application--The Trapezoid Rule 642.6 Solution of Tridiagonal Linear Systems 752.7 Application: Simple Two-Point Boundary Value Problems 813 Root-Finding 873.1 The Bisection Method 883.2 Newton's Method: Derivation and Examples 953.3 How to Stop Newton's Method 1013.4 Application: Division Using Newton's Method 1043.5 The Newton Error Formula 1083.6 Newton's Method: Theory and Convergence 1133.7 Application: Computation of the Square Root 1173.8 The Secant Method: Derivation and Examples 1203.9 Fixed-Point Iteration 1243.10 Roots of Polynomials, Part 1 1333.11 Special Topics in Root-finding Methods 1413.11.1 Extrapolation and Acceleration 1413.11.2 Variants of Newton's Method 1453.11.3 The Secant Method: Theory and Convergence 1493.11.4 Multiple Roots 1533.11.5 In Search of Fast Global Convergence: Hybrid Algorithms 1573.12 Very High-order Methods and the Efficiency Index 1623.13 Literature and Software Discussion 166References 1664 Interpolation and Approximation 1694.1 Lagrange Interpolation 1694.2 Newton Interpolation and Divided Differences 1754.3 Interpolation Error 1854.4 Application: Muller's Method and Inverse Quadratic Interpolation 1904.5 Application: More Approximations to the Derivative 1944.6 Hermite Interpolation 1964.7 Piecewise Polynomial Interpolation 2004.8 An Introduction to Splines 2074.8.1 Definition of the Problem 2074.8.2 Cubic B-Splines 2084.9 Tension Splines 2234.10 Least Squares Concepts in Approximation 2294.10.1 An Introduction to Data Fitting 2294.10.2 Least Squares Approximation and Orthogonal Polynomials 2334.11 Advanced Topics in Interpolation and Approximation 2464.11.1 Stability of Polynomial Interpolation 2474.11.2 The Runge Example 2494.11.3 The Chebyshev Nodes 2534.11.4 Spectral Interpolation 2574.12 Literature and Software Discussion 265References 2665 Numerical Integration 2695.1 A Review of the Definite Integral 2705.2 Improving the Trapezoid Rule 2725.3 Simpson's Rule and Degree of Precision 2775.4 The Midpoint Rule 2885.5 Application: Stirling's Formula 2925.6 Gaussian Quadrature 2945.7 Extrapolation Methods 3065.8 Special Topics in Numerical Integration 3135.8.1 Romberg Integration 3135.8.2 Quadrature with Non-smooth Integrands 3185.8.3 Adaptive Integration 3235.8.4 Peano Estimates for the Trapezoid Rule 3295.9 Literature and Software Discussion 335References 3356 Numerical Methods for Ordinary Differential Equations 3376.1 The Initial Value Problem: Background 3386.2 Euler's Method 3436.3 Analysis of Euler's Method 3466.4 Variants of Euler's Method 3506.4.1 The Residual and Truncation Error 3526.4.2 Implicit Methods and Predictor-Corrector Schemes 3556.4.3 Starting Values and Multistep Methods 3606.4.4 The Midpoint Method and Weak Stability 3626.5 Single-Step Methods: Runge-Kutta 3676.6 Multistep Methods 3746.6.1 The Adams Families 3746.6.2 The BDF Family 3786.7 Stability Issues 3806.7.1 Stability Theory for Multistep Methods 3806.7.2 Stability Regions 3846.8 Application to Systems of Equations 3856.8.1 Implementation Issues and Examples 3856.8.2 Stiff Equations 3896.8.3 A-Stability 3906.9 Adaptive Solvers 3946.10 Boundary Value Problems 4076.10.1 Simple Difference Methods 4076.10.2 Shooting Methods 4146.10.3 Higher Order Difference Methods for BVPs 4176.10.4 Finite Element Methods for BVPs 4246.11 Literature and Software Discussion 432References 4337 Numerical Methods for the Solution of Systems of Equations 4357.1 Linear Algebra Review 4367.2 Linear Systems and Gaussian Elimination 4387.3 Operation Counts 4457.4 The LU Factorization 4477.5 Perturbation, Conditioning, and Stability 4597.5.1 Vector and Matrix Norms 4597.5.2 The Condition Number and Perturbations 4617.5.3 Estimating the Condition Number 4687.5.4 Iterative Refinement 4717.6 SPD Matrices and the Cholesky Decomposition 4757.7 Application: Numerical Solution of Linear Least Squares Problems 4787.8 Sparse and Structured Matrices 4847.9 Iterative Methods for Linear Systems: A Brief Survey 4857.10 Nonlinear Systems: Newton's Method and Related Ideas 4937.10.1 Newton's Method 4947.10.2 Fixed-Point Methods 4977.11 Application: Numerical Solution of Nonlinear Boundary Value Problems 4997.12 Literature and Software Discussion 501References 5028 Approximate Solution of the Algebraic Eigenvalue Problem 5038.1 Eigenvalue Review 5038.2 Reduction to Hessenberg Form 5098.3 Power Methods 5158.4 Bisection and Inertia to Compute Eigenvalues of Symmetric Matrices 5338.5 An Overview of the QR Iteration 5398.6 Application: Roots of Polynomials, Part II 5488.7 Application: Computation of Gaussian Quadrature Rules 5498.8 Literature and Software Discussion 557References 5579 A Survey of Numerical Methods for Partial Differential Equations 5599.1 Difference Methods for the Diffusion Equation 5599.1.1 The Basic Problem 5599.1.2 The Explicit Method and Stability 5609.1.3 Implicit Methods and the Crank-Nicolson Method 5659.2 Finite Element Methods for the Diffusion Equation 5749.3 Difference Methods for Poisson Equations 5789.3.1 Discretization and Examples 5789.3.2 Higher Order Methods 5889.3.3 Iteration and the Method of Conjugate Gradients 5939.4 Literature and Software Discussion 605References 60510 More on Spectral Methods 60710.1 Spectral Methods for Two-Point Boundary Value Problems 60810.2 Spectral Methods in Two Dimensions 62110.3 Spectral Methods for Time-Dependent Problems 63110.4 Clenshaw-Curtis Quadrature 63510.5 Literature and Software Discussion 637References 637Appendix A: Proofs of Selected Theorems, and Additional Material 639A.1 Proofs of the Interpolation Error Theorems 639A.2 Proof of the Stability Result for ODEs 641A.3 Stiff Systems of Differential Equations and Eigenvalues 642A.4 The Matrix Perturbation Theorem 644Index 646

O autorze

JAMES F. EPPERSON, PHD, has been Associate Editor of Mathematical Reviews, published by the American Mathematical Society, since 2001, and will be retiring from this position in July 2021. He was previously Associate Professor in the Department of Mathematical Sciences at the University of Alabama in Huntsville. Dr. Epperson is the author of the previous editions of An Introduction to Numerical Methods and Analysis and their accompanying solutions manuals.