1 Nonlinear Equations 1
1.1 Bisection and Inverse Linear Interpolation 1
1.2 Newton's Method 11
1.3 The Fixed Point Theorem 21
1.4 Quadratic Convergence of Newton's Method 31
1.5 Variants of Newton's Method 43
1.6 Brent's Method 55
1.7 Effects of Finite Precision Arithmetic 62
1.8 Newton's Method for Systems 73
1.9 Broyden's Method 83
2 Linear Systems 90
2.1 Gaussian Elimination with Partial Pivoting 90
2.2 The LU Decomposition 102
2.3 The LU Decomposition with Pivoting 113
2.4 The Cholesky Decomposition 128
2.5 Condition Numbers 140
2.6 The QR Decomposition 153
2.7 Householder Triangularization and the QR Decomposition 165
2.8 Gram-Schmidt Orthogonalization and the QR Decomposition 177
2.9 The Singular Value Decomposition 190
3 Iterative Methods 196
3.1 Jacobi and Gauss-Seidel Iteration 196
3.2 Sparsity 208
3.3 Iterative Refinement 214
3.4 Preconditioning 219
3.5 Krylov Space Methods 226
3.6 Numerical Eigenproblems 238
4 Polynomial Interpolation 247
4.1 Lagrange Interpolating Polynomials 247
4.2 Piecewise Linear Interpolation 261
4.3 Cubic Splines 274
4.4 Computation of the Cubic Spline Coefficients 284
5 Numerical Integration 298
5.1 Closed Newton-Cotes Formulas 298
5.2 Open Newton-Cotes Formulas and Undetermined Coefficients 316
5.3 Gaussian Quadrature 330
5.4 Gauss-Chebyshev Quadrature 342
5.5 Radau and Lobatto Quadrature 351
5.6 Adaptivity and Automatic Integration 361
5.7 Romberg Integration 371
6 Differential Equations 381
6.1 Numerical Differentiation 381
6.2 Euler's Method 392
6.3 Improved Euler's Method 402
6.4 Analysis of Explicit One-Step Methods 411
6.5 Taylor and Runge-Kutta Methods 419
6.6 Adaptivity and Stiffness 428
6.7 Multi-Step Methods 437
7 Nonlinear Optimization 446
7.1 One-Dimensional Searches 446
7.2 The Method of Steepest Descent 455
7.3 Newton Methods for Nonlinear Optimization 467
7.4 Multiple Random Start Methods 477
7.5 Direct Search Methods 485
7.6 The Nelder-Mead Method 493
7.7 Conjugate Direction Methods 500
8 Approximation Methods 508
8.1 Linear and Nonlinear Least Squares 508
8.2 The Best Approximation Problem 517
8.3 Best Uniform Approximation 525
8.4 Applications of the Chebyshev Polynomials 538
Afterword 545
Answers 549
Bibliography 571
Index 577