Numerical Mathematics

1 Computing.- 1. Numbers and Their Representation.- 1.1 Representing numbers in arbitrary bases.- 1.2 Analog and digital computing machines.- 1.3 Binary arithmetic.- 1.4 Fixed-point arithmetic.- 1.5 Floating-point arithmetic.- 1.6 Problems.- 2. Floating Point Arithmetic.- 2.1 The roundoff rule.- 2.2 Combining floating point numbers.- 2.3 Numerically stable vs. unstable evaluation of formulae.- 2.4 Problems.- 3. Error Analysis.- 3.1 The condition of a problem.- 3.2 Forward error analysis.- 3.3 Backward error analysis.- 3.4 Interval arithmetic.- 3.5 Problems.- 4. Algorithms.- 4.1 The Euclidean algorithm.- 4.2 Evaluation of algorithms.- 4.3 Complexity of algorithms.- 4.4 The complexity of some algorithms.- 4.5 Divide and conquer.- 4.6 Fast matrix multiplication.- 4.7 Problems.- 2. Linear Systems of Equations.- 1. Gauss Elimination.- 1.1 Notation and statement of the problem.- 1.2 The elimination method.- 1.3 Triangular decomposition by Gauss elimination.- 1.4 Some special matrices.- 1.5 On pivoting.- 1.6 Complexity of Gauss elimination.- 1.7 Problems.- 2. The Cholesky Decomposition.- 2.1 Review of positive definite matrices.- 2.2 The Cholesky decomposition.- 2.3 Complexity of the Cholesky decomposition.- 2.4 Problems.- 3. The QR Decomposition of Householder.- 3.1 Householder matrices.- 3.2 The basic problem.- 3.3 The Householder algorithm.- 3.4 Complexity of the QR decomposition.- 3.5 Problems.- 4. Vector Norms and Norms of Matrices.- 4.1 Norms on vector spaces.- 4.2 The natural norm of a matrix.- 4.3 Special norms of matrices.- 4.4 Problems.- 5. Error Bounds.- 5.1 Condition of a matrix.- 5.2 An error bound for perturbed matrices.- 5.3 Acceptability of solutions.- 5.4 Problems.- 6. III-Conditioned Problems.- 6.1 The singular-value decomposion of a matrix.- 6.2 Pseudo-normal solutions of linear systems of equations.- 6.3 The pseudo-inverse of a matrix.- 6.4 More on linear systems of equations.- 6.5 Improving the condition and regularization of a linear system of equations.- 6.6 Problems.- 3. Eigenvalues.- 1. Reduction to Tridiagonal or Hessenberg Form.- 1.1 The Householder method.- 1.2 Computation of the eigenvalues of tridiagonal matrices.- 1.3 Computation of the eigenvalues of Hessenberg matrices.- 1.4 Problems.- 2. The Jacobi Rotation and Eigenvalue Estimates.- 2.1 The Jacobi method.- 2.2 Estimating eigenvalues.- 2.3 Problems.- 3. The Power Method.- 3.1 An iterative method.- 3.2 Computation of eigenvectors and further eigenvalues.- 3.3 The Rayleigh quotient.- 3.4 Problems.- 4. The QR Algorithm.- 4.1 Convergence of the QR algorithm.- 4.2 Remarks on the LR algorithm.- 4.3 Problems.- 4. Approximation.- 1. Preliminaries.- 1.1 Normed linear spaces.- 1.2 Banach spaces.- 1.3 Hilbert spaces and pre-Hilbert spaces.- 1.4 The spaces Lp[a, b].- 1.5 Linear operators.- 1.6 Problems.- 2. The Approximation Theorems of Weierstrass.- 2.1 Approximation by polynomials.- 2.2 The approximation theorem for continuous functions.- 2.3 The Korovkin approach.- 2.4 Applications of Theorem 2.3.- 2.5 Approximation error.- 2.6 Problems.- 3. The General Approximation Problem.- 3.1 Best approximations.- 3.2 Existence of a best approximation.- 3.3 Uniqueness of a best approximation.- 3.4 Linear approximation.- 3.5 Uniqueness in finite dimensional linear subspaces.- 3.6 Problems.- 4. Uniform Approximation.- 4.1 Approximation by polynomials.- 4.2 Haar spaces.- 4.3 The alternation theorem.- 4.4 Uniqueness.- 4.5 An error bound.- 4.6 Computation of the best approximation.- 4.7 Chebyshev polynomials of the first kind.- 4.8 Expansions in Chebyshev polynomials.- 4.9 Convergence of best approximations.- 4.10 Nonlinear approximation.- 4.11 Remarks on approximation in (C[a, b], || - ||1).- 4.12 Problems.- 5. Approximation in Pre-Hilbert Spaces.- 5.1 Characterization of the best approximation.- 5.2 The normal equations.- 5.3 Orthonormal systems.- 5.4 The Legendre polynomials.- 5.5 Properties of orthonormal polynomials.- 5.6 Convergence in C[a, b].- 5.7 Approximation of piecewise continuous functions.- 5.8 Trigonometric approximation.- 5.9 Problems.- 6. The Method of Least Squares.- 6.1 Discrete approximation.- 6.2 Solution of the normal equations.- 6.3 Fitting by polynomials.- 6.4 Coalescent data points.- 6.5 Discrete approximation by trigonometric functions.- 6.6 Problems.- 5. Interpolation.- 1. The Interpolation Problem.- 1.1 Interpolation in Haar spaces.- 1.2 Interpolation by polynomials.- 1.3 The remainder term.- 1.4 Error bounds.- 1.5 Problems.- 2. Interpolation Methods and Remainders.- 2.1 The method of Lagrange.- 2.2 The method of Newton.- 2.3 Divided differences.- 2.4 The general Peano remainder formula.- 2.5 A derivative-free error bound.- 2.6 Connection to analysis.- 2.7 Problems.- 3. Equidistant Interpolation Points.- 3.1 The difference table.- 3.2 Representations of interpolating polynomials.- 3.3 Numerical differentiation.- 3.4 Problems.- 4. Convergence of Interpolating Polynomials.- 4.1 Best interpolation.- 4.2 Convergence problems.- 4.3 Convergence results.- 4.4 Problems.- 5. More on Interpolation.- 5.1 Horner's scheme.- 5.2 The Aitken-Neville algorithm.- 5.3 Hermite interpolation.- 5.4 Trigonometric interpolation.- 5.5 Complex interpolation.- 5.6 Problems.- 6. Multidimensional Interpolation.- 6.1 Various interpolation problems.- 6.2 Interpolation on rectangular grids.- 6.3 Bounding the interpolation error.- 6.4 Problems.- 6. Splines.- 1. Polynomial Splines.- 1.1 Spline spaces.- 1.2 A basis for the spline space.- 1.3 Best approximation in spline spaces.- 1.4 Problems.- 2. Interpolating Splines.- 2.1 Splines of odd degree.- 2.2 An extremal property of splines.- 2.3 Quadratic splines.- 2.4 Convergence.- 2.5 Problems.- 3. B-splines.- 3.1 Existence of B-splines.- 3.2 Local bases.- 3.3 Additional properties of B-splines.- 3.4 Linear B-splines.- 3.5 Quadratic B-splines.- 3.6 Cubic B-splines.- 3.7 Problems.- 4. Computing Interpolating Splines.- 4.1 Cubic splines.- 4.2 Quadratic splines.- 4.3 A general interpolation problem.- 4.4 Problems.- 5. Error Bounds and Spline Approximation.- 5.1 Error bounds for linear splines.- 5.2 On uniform approximation by linear splines.- 5.3 Least squares approximation by linear splines.- 5.4 Error bounds for splines of higher degree.- 5.5 Least squares splines of higher degree.- 5.6 Problems.- 6. Multidimensional Splines.- 6.1 Bilinear splines.- 6.2 Bicubic splines.- 6.3 Spline-blended functions.- 6.4 Problems.- 7. Integration.- 1. Interpolatory Quadrature.- 1.1 Rectangle rules.- 1.2 The trapezoidal rule.- 1.3 The Euler-MacLaurin expansion.- 1.4 Simpson's rule.- 1.5 Newton-Cotes formulae.- 1.6 Unsymmetric quadrature formulae.- 1.7 Problems.- 2. Extrapolation.- 2.1 The Romberg method.- 2.2 Error analysis.- 2.3 Extrapolation.- 2.4 Convergence.- 2.5 Problems.- 3. Gauss Quadrature.- 3.1 The method of Gauss.- 3.2 Gauss quadrature as interpolation quadrature.- 3.3 Error formula.- 3.4 Modified Gauss quadrature.- 3.5 Improper integrals.- 3.6 Nodes and coefficients of Gauss quadrature formulae.- 3.7 Problems.- 4. Special Quadrature Methods.- 4.1 Integration over an infinite interval.- 4.2 Singular integrands.- 4.3 Periodic functions.- 4.4 Problems.- 5. Optimality and Convergence.- 5.1 Norm minimization.- 5.2 Minimizing random errors.- 5.3 Optimal quadrature formulae.- 5.4 Convergence of quadrature formulae.- 5.5 Quadrature operators.- 5.6 Problems.- 6. Multidimensional Integration.- 6.1 Tensor products.- 6.2 Integration over standard domains.- 6.3 The Monte-Carlo method.- 6.4 Problems.- 8. Iteration.- 1. The General Iteration Method.- 1.1 Examples of convergent iterations.- 1.2 Convergence of iterative methods.- 1.3 Lipschitz constants.- 1.4 Error bounds.- 1.5 Convergence.- 1.6 Problems.- 2. Newton's Method.- 2.1 Accelerating the convergence of an iterative method.- 2.2 Geometric interpretation.- 2.3 Multiple zeros.- 2.4 The secant method.- 2.5 Newton's method for m > 1..- 2.6 Roots of polynomials.- 2.7 Problems.- 3. Iterative Solution of Linear Systems of Equations.- 3.1 Sequences of iteration matrices.- 3.2 The Jacobi method.- 3.3 The Gauss-Seidel method.- 3.4 The theorem of Stein and Rosenberg.- 3.5 Problems.- 4. More on Convergence.- 4.1 Relaxation for the Jacobi method.- 4.2 Relaxation for the Gauss-Seidel method.- 4.3 Optimal relaxation parameters.- 4.4 Problems.- 9. Linear. Optimization.- 1. Introductory Examples and the General Problem.- 1.1 Optimal production planning.- 1.2 A semi-infinite optimization problem.- 1.3 A linear control problem.- 1.4 The general problem.- 1.5 Problems.- 2. Polyhedra.- 2.1 Characterization of vertices.- 2.2 Existence of vertices.- 2.3 The main result.- 2.4 An algebraic characterization of vertices.- 2.5 Problems.- 3. The Simplex Method.- 3.1 Introduction.- 3.2 The vertex exchange without degeneracy.- 3.3 Finding a starting vertex.- 3.4 Degenerate vertices.- 3.5 The two-phase method.- 3.6 The modified simplex method.- 3.7 Problems.- 4. Complexity Analysis.- 4.1 The examples of Klee and Minty.- 4.2 On the average behavior of the algorithm.- 4.3 Runtime of algorithms.- 4.4 Polynomial algorithms.- 4.5 Problems.- References.- Symbols.