An Introduction to Numerical Methods and Analysis

Praise for the First Edition

". . . outstandingly appealing with regard to its style, contents, considerations of requirements of practice, choice of examples, and exercises."—Zentralblatt MATH

". . . carefully structured with many detailed worked examples."—The Mathematical Gazette

The Second Edition of the highly regarded An Introduction to Numerical Methods and Analysis provides a fully revised guide to numerical approximation. The book continues to be accessible and expertly guides readers through the many available techniques of numerical methods and analysis.

An Introduction to Numerical Methods and Analysis, Second Edition reflects the latest trends in the field, includes new material and revised exercises, and offers a unique emphasis on applications. The author clearly explains how to both construct and evaluate approximations for accuracy and performance, which are key skills in a variety of fields. A wide range of higher-level methods and solutions, including new topics such as the roots of polynomials, spectral collocation, finite element ideas, and Clenshaw-Curtis quadrature, are presented from an introductory perspective, and the Second Edition also features:

• Chapters and sections that begin with basic, elementary material followed by gradual coverage of more advanced material
• Exercises ranging from simple hand computations to challenging derivations and minor proofs to programming exercises
• Widespread exposure and utilization of MATLAB
• An appendix that contains proofs of various theorems and other material

The book is an ideal textbook for students in advanced undergraduate mathematics and engineering courses who are interested in gaining an understanding of numerical methods and numerical analysis.

JAMES F. EPPERSON, PhD, is Associate Editor of Mathematical Reviews for the American Mathematical Society. He was previously associate professor in the Department of Mathematics at The University of Alabama in Huntsville and assistant professor at the University of Georgia in Athens. He earned his doctorate at Carnegie Mellon University in Pittsburgh and his undergraduate degree from the College of Engineering at the University of Michigan, Ann Arbor.

Preface xiii

1 Introductory Concepts and Calculus Review 1

1.1 Basic Tools of Calculus 2

1.2 Error, Approximate Equality, and Asymptotic Order Notation 14

1.3 A Primer on Computer Arithmetic 20

1.4 A Word on Computer Languages and Software 29

1.5 Simple Approximations 30

1.6 Application: Approximating the Natural Logarithm 35

1.7 A Brief History of Computing 37

References 41

2 A Survey of Simple Methods and Tools 43

2.1 Horner’s Rule and Nested Multiplication 43

2.2 Difference Approximations to the Derivative 48

2.3 Application: Euler’s Method for Initial Value Problems 56

2.4 Linear Interpolation 62

2.5 Application—The Trapezoid Rule 68

2.6 Solution of Tridiagonal Linear Systems 78

2.7 Application: Simple TwoPoint Boundary Value Problems 85

3 RootFinding 91

3.1 The Bisection Method 92

3.2 Newton’s Method: Derivation and Examples 99

3.3 How to Stop Newton’s Method 105

3.4 Application: Division Using Newton’s Method 108

3.5 The Newton Error Formula 112

3.6 Newton’s Method: Theory and Convergence 117

3.7 Application: Computation of the Square Root 121

3.8 The Secant Method: Derivation and Examples 124

3.9 Fixed Point Iteration 128

3.10 Roots of Polynomials (Part 1) 138

3.11 Special Topics in Rootfinding Methods 145

3.12 Very Highorder Methods and the Efficiency Index 167

3.13 Literature and Software Discussion 170

References 173

4 Interpolation and Approximation 175

4.1 Lagrange Interpolation 175

4.2 Newton Interpolation and Divided Differences 181

4.3 Interpolation Error 191

4.4 Application: Muller’s Method and Inverse Quadratic Interpolation 196

4.5 Application: More Approximations to the Derivative 199

4.6 Hermite Interpolation 202

4.7 Piecewise Polynomial Interpolation 206

4.8 An Introduction to Splines 214

4.9 Application: Solution of Boundary Value Problems 227

4.10 Tension Splines 232

4.11 Least Squares Concepts in Approximation 237

4.12 Advanced Topics in Interpolation Error 254

4.13 Literature and Software Discussion 265

References 267

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 289

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.9 Literature and Software Discussion 334

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 347

6.4 Variants of Euler’s Method 350

6.5 Single Step Methods—Runge–Kutta 367

6.6 Multistep Methods 374

6.7 Stability Issues 380

6.8 Application to Systems of Equations 386

6.9 Adaptive Solvers 394

6.10 Boundary Value Problems 407

6.11 Literature and Software Discussion 422

References 425

7 Numerical Methods for the Solution of Systems of Equations 427

7.1 Linear Algebra Review 428

7.2 Linear Systems and Gaussian Elimination 430

7.3 Operation Counts 437

7.4 The LU Factorization 440

7.5 Perturbation, Conditioning, and Stability 451

7.6 SPD Matrices and the Cholesky Decomposition 467

7.7 Iterative Methods for Linear Systems—A Brief Survey 470

7.8 Nonlinear Systems: Newton’s Method and Related Ideas 479

7.9 Application: Numerical Solution of Nonlinear Boundary Value Problems 484

7.10 Literature and Software Discussion 487

References 489

8 Approximate Solution of the Algebraic Eigenvalue Problem 491

8.1 Eigenvalue Review 491

8.2 Reduction to Hessenberg Form 498

8.3 Power Methods 503

8.4 An Overview of the QR Iteration 521

8.5 Application: Roots of Polynomials, II 530

8.6 Literature and Software Discussion 531

References 533

9 A Survey of Numerical Methods for Partial Differential Equations 535

9.1 Difference Methods for the Diffusion Equation 535

9.2 Finite Element Methods for the Diffusion Equation 550

9.3 Difference Methods for Poisson Equations 553

9.4 Literature and Software Discussion 567

References 569

10 An Introduction to Spectral Methods 571

10.1 Spectral Methods for TwoPoint Boundary Value Problems 572

10.2 Spectral Methods for TimeDependent Problems 584

10.3 ClenshawCurtis Quadrature 593

10.4 Literature and Software Discussion 596

References 597

Appendix A: Proofs of Selected Theorems, and Other Additional Material 599

A.1 Proofs of the Interpolation Error Theorems 599

A.2 Proof of the Stability Result for ODEs 601

A.3 Stiff Systems of Differential Equations and Eigenvalues 602

A.4 The Matrix Perturbation Theorem 604

Index 605

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.