1 Introductory Concepts and Calculus Review 1
1.1 Basic Tools of Calculus 1
1.2 Error, Approximate Equality, and Asymptotic Order Notation 12
1.3 A Primer on Computer Arithmetic 15
1.4 A Word on Computer Languages and Software 19
1.5 Simple Approximations 19
1.6 Application: Approximating the Natural Logarithm 22
1.7 A Brief History of Computing 25
2 A Survey of Simple Methods and Tools 27
2.1 Horner’s Rule and Nested Multiplication 27
2.2 Difference Approximations to the Derivative 30
2.3 Application: Euler’s Method for Initial Value Problems 40
2.4 Linear Interpolation 44
2.5 Application— The Trapezoid Rule 48
2.6 Solution of Tridiagonal Linear Systems 56
2.7 Application: Simple Two-Point Boundary Value Problems 61
3 Root-Finding 65
3.1 The Bisection Method 65
3.2 Newton’s Method: Derivation and Examples 69
3.3 How to Stop Newton’s Method 73
3.4 Application: Division Using Newton’s Method 77
3.5 The Newton Error Formula 81
3.6 Newton’s Method: Theory and Convergence 84
3.7 Application: Computation of the Square Root 88
3.8 The Secant Method: Derivation and Examples 92
3.9 Fixed Point Iteration 96
3.10 Roots of Polynomials (Part 1) 99
3.11 Special Topics in Root-finding Methods 102
3.12 Very High-order Methods and the Efficiency Index 114
4 Interpolation and Approximation 117
4.1 Lagrange Interpolation 117
4.2 Newton Interpolation and Divided Differences 120
4.3 Interpolation Error 132
4.4 Application: Muller’s Method and Inverse Quadratic Interpolation 139
4.5 Application: More Approximations to the Derivative 141
4.6 Hermite Interpolation 142
4.7 Piecewise Polynomial Interpolation 145
4.8 An Introduction to Splines 149
4.9 Application: Solution of Boundary Value Problems 156
4.10 Tension Splines 159
4.11 Least Squares Concepts in Approximation 160
4.12 Advanced Topics in Interpolation Error 166
5 Numerical Integration 171
5.1 A Review of the Definite Integral 171
5.2 Improving the Trapezoid Rule 173
5.3 Simpson’s Rule and Degree of Precision 177
5.4 The Midpoint Rule 187
5.5 Application: Stirling’s Formula 190
5.6 Gaussian Quadrature 192
5.7 Extrapolation Methods 199
5.8 Special Topics in Numerical Integration 203
6 Numerical Methods for Ordinary Differential Equations 211
6.1 The Initial Value Problem — Background 211
6.2 Euler’s Method 213
6.3 Analysis of Euler’s Method 216
6.4 Variants of Euler’s Method 217
6.5 Single Step Methods— Runge-Kutta 225
6.6 Multistep Methods 228
6.7 Stability Issues 234
6.8 Application to Systems of Equations 235
6.9 Adaptive Solvers 240
6.10 Boundary Value Problems 243
7 Numerical Methods for the Solution of Systems of Equations 247
7.1 Linear Algebra Review 247
7.2 Linear Systems and Gaussian Elimination 248
7.3 Operation Counts 254
7.4 The LU Factorization 256
7.5 Perturbation, Conditioning and Stability 262
7.6 SPD Matrices and the Cholesky Decomposition 269
7.7 Iterative Methods for Linear Systems – A Brief Survey 271
7.8 Nonlinear Systems: Newton’s Method and Related Ideas 273
7.9 Application: Numerical Solution of Nonlinear BVP’s 275
8 Approximate Solution of the Algebraic Eigenvalue Problem 277
8.1 Eigenvalue Review 277
8.2 Reduction to Hessenberg Form 280
8.3 Power Methods 281
8.4 An Overview of the QR Iteration 284
8.5 Application: Roots of Polynomials, II 288
9 A Survey of Numerical Methods for Partial Differential Equations 289
9.1 Difference Methods for the Diffusion Equation 289
9.2 Finite Element Methods for the Diffusion Equation 293
9.3 Difference Methods for Poisson Equations 294
10 An Introduction to Spectral Methods 299
10.1 Spectral Methods for Two-Point Boundary Value Problems 299
10.2 Spectral Methods for Time-Dependent Problems 301
10.3 Clenshaw-Curtis Quadrature 303
