An Introduction to Numerical Methods and Analysis (Hardcover, 2, Revised)

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