Numerical Mathematics

"In truth, it is not knowledge, but learning, not possessing, but production, not being there, but travelling there, which provides the greatest pleasure. When I have completely understood something, then I turn away and move on into the dark; indeed, so curious is the insatiable man, that when he has completed one house, rather than living in it peacefully, he starts to build another. " Letter from C. F. Gauss to W. Bolyai on Sept. 2, 1808 This textbook adds a book devoted to applied mathematics to the series "Grundwissen Mathematik. " Our goals, like those of the other books in the series, are to explain connections and common viewpoints between various mathematical areas, to emphasize the motivation for studying certain prob­ lem areas, and to present the historical development of our subject. Our aim in this book is to discuss some of the central problems which arise in applications of mathematics, to develop constructive methods for the numerical solution of these problems, and to study the associated questions of accuracy. In doing so, we also present some theoretical results needed for our development, especially when they involve material which is beyond the scope of the usual beginning courses in calculus and linear algebra. This book is based on lectures given over many years at the Universities of Freiburg, Munich, Berlin and Augsburg.

Contenu

1 Computing.- 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.- 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.- 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.- 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.- 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.- 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.- 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.- 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.- Error Bounds.- 5.1 Condition of a matrix.- 5.2 An error bound for perturbed matrices.- 5.3 Acceptability of solutions.- 5.4 Problems.- 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.- 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.- The Jacobi Rotation and Eigenvalue Estimates.- 2.1 The Jacobi method.- 2.2 Estimating eigenvalues.- 2.3 Problems.- The Power Method.- 3.1 An iterative method.- 3.2 Computation of eigenvectors and further eigenvalues.- 3.3 The Rayleigh quotient.- 3.4 Problems.- The QR Algorithm.- 4.1 Convergence of the QR algorithm.- 4.2 Remarks on the LR algorithm.- 4.3 Problems.- 4. Approximation.- 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.- 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.- 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.- 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.- 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.- 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.- 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.- 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.- Equidistant Interpolation Points.- 3.1 The difference table.- 3.2 Representations of interpolating polynomials.- 3.3 Numerical differentiation.- 3.4 Problems.- Convergence of Interpolating Polynomials.- 4.1 Best interpolation.- 4.2 Convergence problems.- 4.3 Convergence results.- 4.4 Problems.- 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.- Multidimensional Interpolation.- 6.1 Various interpolation problems.- 6.2 Interpolation on rectangular grids.- 6.3 Bounding the interpolation error.- 6.4 Problems.- 6. Splines.- Polynomial Splines.- 1.1 Spline spaces.- 1.2 A basis for the spline space.- 1.3 Best approximation in spline spaces.- 1.4 Problems.- 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.- 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.- Computing Interpolating Splines.- 4.1 Cubic splines.- 4.2 Quadratic splines.- 4.3 A general interpolation problem.- 4.4 Problems.- 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.- Multidimensional Splines.- 6.1 Bilinear splines.- 6.2 Bicubic splines.- 6.3 Spline-blended functions.- 6.4 Problems.- 7. Integration.- 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.- Extrapolation.- 2.1 The Romberg method.- 2.2 Err…