Numerical Analysis:What Is It? 1
Contents 1
1 Mathematical Preliminaries 3
1.0 Introduction 3
1.1 Basic Concepts and Taylor's Theorem 3
1.2 Orders of Convergence and Additional Basic Concepts 15
1.3 Difference Equations 28
2 Computer Arithmetic 37
2.0 Introduction 37
2.1 Floating-Point Numbers and Roundoff Errors 37
2.2 Absolute and Relative Errors:Loss of Significance 55
2.3 Stable and Unstable Computations:Conditioning 64
3.0 Introduction 73
3 Solution of Nonlinear Equations 73
3.1 Bisection(Interval Halving)Method 74
3.2 Newton's Method 81
3.3 Secant Method 93
3.4 Fixed Points and Functional Iteration 100
3.5 Computing Roots of Polynomials 109
3.6 Homotopy and Continuation Methods 130
4 Solving Systems of Linear Equations 139
4.0 Introduction 139
4.1 Matrix Algebra 140
4.2 LU and Cholesky Factorizations 149
4.3 Pivoting and Constructing an Algorithm 163
4.4 Norms and the Analysis of Errors 186
4.5 Neumann Series and Iterative Refinement 197
4.6 Solution of Equations by Iterative Methods 207
4.7 Steepest Descent and Conjugate Gradient Methods 232
4.8 Analysis of Roundoff Error in the Gaussian Algorithm 245
5 Selected Topics in Numerical Linear Algebra 254
5.0 Review of Basic Concepts 254
5.1 Matrix Eigenvalue Problem:Power Method 257
5.2 Schur's and Gershgorin's Theorems 265
5.3 Orthogonal Factorizations and Least-Squares Problems 273
5.4 Singular-Value Decomposition and Pseudoinverses 287
5.5 QR-Algorithm of Francis for the Eigenvalue Problem 298
6.1 Polynomial Interpolation 308
6.0 Introduction 308
6 Approximating Functions 308
6.2 Divided Differences 327
6.3 Hermite Interpolation 338
6.4 Spline Interpolation 349
6.5 B-Splines:Basic Theory 366
6.6 B-Splines:Applications 377
6.7 Taylor Series 388
6.8 Best Approximation:Least-Squares Theory 392
6.9 Best Approximation:Chebyshev Theory 405
6.10 Interpolation in Higher Dimensions 420
6.11 Continued Fractions 438
6.12 Trigonometric Interpolation 445
6.13 Fast Fourier Transform 451
6.14 Adaptive Approximation 460
7 Numerical Differentiation and Integration 465
7.1 Numerical Differentiation and Richardson Extrapolation 465
7.2 Numerical Integration Based on Interpolation 478
7.3 Gaussian Quadrature 492
7.4 Romberg Integration 502
7.5 Adaptive Quadrature 507
7.6 Sard's Theory of Approximating Functionals 513
7.7 Bernoulli Polynomials and the Euler-Maclaurin Formula 519
8 Numerical Solution of Ordinary Differential Equations 524
8.0 Introduction 524
8.1 The Existence and Uniqueness of Solutions 524
8.2 Taylor-Series Method 530
8.3 Runge-Kutta Methods 539
8.4 Multistep Methods 549
8.5 Local and Global Errors:Stability 557
8.6 Systems and Higher-Order Ordinary Differential Equations 565
8.7 Boundary-Value Problems 572
8.8 Boundary-Value Problems:Shooting Methods 581
8.9 Boundary-Value Problems:Finite-Differences 589
8.10 Boundary-Value Problems:Collocation 593
8.11 Linear Differential Equations 597
8.12 Stiff Equations 608
9 Numerical Solution of Partial Differential Equations 615
9.0 Introduction 615
9.1 Parabolic Equations:Explicit Methods 615
9.2 Parabolic Equations:Implicit Methods 623
9.3 Problems Without Time Dependence:Finite-Differences 629
9.4 Problems Without Time Dependence:Galerkin Methods 634
9.5 First-Order Partial Differential Equations:Characteristics 642
9.6 Quasilinear Second-Order Equations:Characteristics 650
9.7 Other Methods for Hyperbolic Problems 660
9.8 Multigrid Method 667
9.9 Fast Methods for Poisson's Equation 676
10 Linear Programming and Related Topics 681
10.1 Convexity and Linear Inequalities 681
10.2 Linear Inequalities 689
10.3 Linear Programming 695
10.4 The Simplex Algorithm 700
11.0 Introduction 711
11 Optimization 711
11.1 One-Variable Case 712
11.2 Descent Methods 716
11.3 Analysis of Quadratic Objective Functions 719
11.4 Quadratic-Fitting Algorithms 721
11.5 Nelder-Meade Algorithm 722
11.6 Simulated Annealing 723
11.7 Genetic Algorithms 724
11.8 Convex Programming 725
11.9 Constrained Minimization 726
11.10 Pareto Optimization 727
AppendixA An Overview of Mathematical Software 731
Bibliography 745
Index 771