The new edition of the popular introductory textbook on numerical approximation methods and mathematical analysis, with a unique emphasis on real-world application
An Introduction to Numerical Methods and Analysis helps students gain a solid understanding of a wide range of numerical approximation methods for solving problems of mathematical analysis. Designed for entry-level courses on the subject, this popular textbook maximizes teaching flexibility by first covering basic topics before gradually moving to more advanced material in each chapter and section. Throughout the text, students are provided clear and accessible guidance on a wide range of numerical methods and analysis techniques, including root-finding, numerical integration, interpolation, solution of systems of equations, and many others.
This fully revised third edition contains new sections on higher-order difference methods, the bisection and inertia method for computing eigenvalues of a symmetric matrix, a completely re-written section on different methods for Poisson equations, and spectral methods for higher-dimensional problems. New problem sets - ranging in difficulty from simple computations to challenging derivations and proofs - are complemented by computer programming exercises, illustrative examples, and sample code. This acclaimed textbook:
- Explains how to both construct and evaluate approximations for accuracy and performance
- Covers both elementary concepts and tools and higher-level methods and solutions
- Features new and updated material reflecting new trends and applications in the field
- Contains an introduction to key concepts, a calculus review, an updated primer on computer arithmetic, a brief history of scientific computing, a survey of computer languages and software, and a revised literature review
- Includes an appendix of proofs of selected theorems and a companion website with additional exercises, application models, and supplemental resources
An Introduction to Numerical Methods and Analysis, Third Edition is the perfect textbook for upper-level undergraduate students in mathematics, science, and engineering courses, as well as for courses in the social sciences, medicine, and business with numerical methods and analysis components.
Table of Contents
Preface xiii
1 Introductory Concepts and Calculus Review 1
1.1 Basic Tools of Calculus 2
1.1.1 Taylor’s Theorem 2
1.1.2 Mean Value and Extreme Value Theorems 9
1.2 Error, Approximate Equality, and Asymptotic Order Notation 14
1.2.1 Error 14
1.2.2 Notation: Approximate Equality 15
1.2.3 Notation: Asymptotic Order 16
1.3 A Primer on Computer Arithmetic 20
1.4 A Word on Computer Languages and Software 29
1.5 A Brief History of Scientific Computing 32
1.6 Literature Review 36
References 36
2 A Survey of Simple Methods and Tools 39
2.1 Horner’s Rule and Nested Multiplication 39
2.2 Difference Approximations to the Derivative 44
2.3 Application: Euler’s Method for Initial Value Problems 52
2.4 Linear Interpolation 58
2.5 Application - The Trapezoid Rule 64
2.6 Solution of Tridiagonal Linear Systems 75
2.7 Application: Simple Two-Point Boundary Value Problems 81
3 Root-Finding 87
3.1 The Bisection Method 88
3.2 Newton’s Method: Derivation and Examples 95
3.3 How to Stop Newton’s Method 101
3.4 Application: Division Using Newton’s Method 104
3.5 The Newton Error Formula 108
3.6 Newton’s Method: Theory and Convergence 113
3.7 Application: Computation of the Square Root 117
3.8 The Secant Method: Derivation and Examples 120
3.9 Fixed-Point Iteration 124
3.10 Roots of Polynomials, Part 1 133
3.11 Special Topics in Root-finding Methods 141
3.11.1 Extrapolation and Acceleration 141
3.11.2 Variants of Newton’s Method 145
3.11.3 The Secant Method: Theory and Convergence 149
3.11.4 Multiple Roots 153
3.11.5 In Search of Fast Global Convergence: Hybrid Algorithms 157
3.12 Very High-order Methods and the Efficiency Index 162
3.13 Literature and Software Discussion 166
References 166
4 Interpolation and Approximation 169
4.1 Lagrange Interpolation 169
4.2 Newton Interpolation and Divided Differences 175
4.3 Interpolation Error 185
4.4 Application: Muller’s Method and Inverse Quadratic Interpolation 190
4.5 Application: More Approximations to the Derivative 194
4.6 Hermite Interpolation 196
4.7 Piecewise Polynomial Interpolation 200
4.8 An Introduction to Splines 207
4.8.1 Definition of the Problem 207
4.8.2 Cubic B-Splines 208
4.9 Tension Splines 223
4.10 Least Squares Concepts in Approximation 229
4.10.1 An Introduction to Data Fitting 229
4.10.2 Least Squares Approximation and Orthogonal Polynomials 233
4.11 Advanced Topics in Interpolation and Approximation 246
4.11.1 Stability of Polynomial Interpolation 247
4.11.2 The Runge Example 249
4.11.3 The Chebyshev Nodes 253
4.11.4 Spectral Interpolation 257
4.12 Literature and Software Discussion 265
References 266
5 Numerical Integration 269
5.1 A Review of the Definite Integral 270
5.2 Improving the Trapezoid Rule 272
5.3 Simpson’s Rule and Degree of Precision 277
5.4 The Midpoint Rule 288
5.5 Application: Stirling’s Formula 292
5.6 Gaussian Quadrature 294
5.7 Extrapolation Methods 306
5.8 Special Topics in Numerical Integration 313
5.8.1 Romberg Integration 313
5.8.2 Quadrature with Non-smooth Integrands 318
5.8.3 Adaptive Integration 323
5.8.4 Peano Estimates for the Trapezoid Rule 329
5.9 Literature and Software Discussion 335
References 335
6 Numerical Methods for Ordinary Differential Equations 337
6.1 The Initial Value Problem: Background 338
6.2 Euler’s Method 343
6.3 Analysis of Euler’s Method 346
6.4 Variants of Euler’s Method 350
6.4.1 The Residual and Truncation Error 352
6.4.2 Implicit Methods and Predictor-Corrector Schemes 355
6.4.3 Starting Values and Multistep Methods 360
6.4.4 The Midpoint Method and Weak Stability 362
6.5 Single-Step Methods: Runge-Kutta 367
6.6 Multistep Methods 374
6.6.1 The Adams Families 374
6.6.2 The BDF Family 378
6.7 Stability Issues 380
6.7.1 Stability Theory for Multistep Methods 380
6.7.2 Stability Regions 384
6.8 Application to Systems of Equations 385
6.8.1 Implementation Issues and Examples 385
6.8.2 Stiff Equations 389
6.8.3 A-Stability 390
6.9 Adaptive Solvers 394
6.10 Boundary Value Problems 407
6.10.1 Simple Difference Methods 407
6.10.2 Shooting Methods 414
6.10.3 Higher Order Difference Methods for BVPs 417
6.10.4 Finite Element Methods for BVPs 424
6.11 Literature and Software Discussion 432
References 433
7 Numerical Methods for the Solution of Systems of Equations 435
7.1 Linear Algebra Review 436
7.2 Linear Systems and Gaussian Elimination 438
7.3 Operation Counts 445
7.4 The LU Factorization 447
7.5 Perturbation, Conditioning, and Stability 459
7.5.1 Vector and Matrix Norms 459
7.5.2 The Condition Number and Perturbations 461
7.5.3 Estimating the Condition Number 468
7.5.4 Iterative Refinement 471
7.6 SPD Matrices and the Cholesky Decomposition 475
7.7 Application: Numerical Solution of Linear Least Squares Problems 478
7.8 Sparse and Structured Matrices 484
7.9 Iterative Methods for Linear Systems: A Brief Survey 485
7.10 Nonlinear Systems: Newton’s Method and Related Ideas 493
7.10.1 Newton’s Method 494
7.10.2 Fixed-Point Methods 497
7.11 Application: Numerical Solution of Nonlinear Boundary Value Problems 499
7.12 Literature and Software Discussion 501
References 502
8 Approximate Solution of the Algebraic Eigenvalue Problem 503
8.1 Eigenvalue Review 503
8.2 Reduction to Hessenberg Form 509
8.3 Power Methods 515
8.4 Bisection and Inertia to Compute Eigenvalues of Symmetric Matrices 533
8.5 An Overview of the QR Iteration 539
8.6 Application: Roots of Polynomials, Part II 548
8.7 Application: Computation of Gaussian Quadrature Rules 549
8.8 Literature and Software Discussion 557
References 557
9 A Survey of Numerical Methods for Partial Differential Equations 559
9.1 Difference Methods for the Diffusion Equation 559
9.1.1 The Basic Problem 559
9.1.2 The Explicit Method and Stability 560
9.1.3 Implicit Methods and the Crank-Nicolson Method 565
9.2 Finite Element Methods for the Diffusion Equation 574
9.3 Difference Methods for Poisson Equations 578
9.3.1 Discretization and Examples 578
9.3.2 Higher Order Methods 588
9.3.3 Iteration and the Method of Conjugate Gradients 593
9.4 Literature and Software Discussion 605
References 605
10 More on Spectral Methods 607
10.1 Spectral Methods for Two-Point Boundary Value Problems 608
10.2 Spectral Methods in Two Dimensions 621
10.3 Spectral Methods for Time-Dependent Problems 631
10.4 Clenshaw-Curtis Quadrature 635
10.5 Literature and Software Discussion 637
References 637
Appendix A: Proofs of Selected Theorems, and Additional Material 639
A.1 Proofs of the Interpolation Error Theorems 639
A.2 Proof of the Stability Result for ODEs 641
A.3 Stiff Systems of Differential Equations and Eigenvalues 642
A.4 The Matrix Perturbation Theorem 644
Index 646
