Lectures on Numerical Mathematics

The present book is an edition of the manuscripts to the courses "Numerical Methods I" and "Numerical Mathematics I and II" which Professor H. Rutishauser held at the E.T.H. in Zurich. The first-named course was newly conceived in the spring semester of 1970, and intended for beginners, while the two others were given repeatedly as elective courses in the sixties. For an understanding of most chapters the funda­ mentals of linear algebra and calculus suffice. In some places a little complex variable theory is used in addition. However, the reader can get by without any knowledge of functional analysis. The first seven chapters discuss the direct solution of systems of linear equations, the solution of nonlinear systems, least squares prob­ lems, interpolation by polynomials, numerical quadrature, and approxima­ tion by Chebyshev series and by Remez' algorithm. The remaining chapters include the treatment of ordinary and partial differential equa­ tions, the iterative solution of linear equations, and a discussion of eigen­ value problems. In addition, there is an appendix dealing with the qd­ algorithm and with an axiomatic treatment of computer arithmetic.

1. An Outline of the Problems.- § 1.1. Reliability of programs.- § 1.2. The evolution of a program.- § 1.3. Difficulties.- Notes to Chapter 1.- 2. Linear Equations and Inequalities.- § 2.1. The classical algorithm of Gauss.- § 2.2. The triangular decomposition.- § 2.3. Iterative refinement.- § 2.4. Pivoting strategies.- § 2.5. Questions of programming.- § 2.6. The exchange algorithm.- § 2.7. Questions of programming.- § 2.8. Linear inequalities (optimization).- Notes to Chapter 2.- 3. Systems of Equations With Positive Definite Symmetric Coefficient Matrix.- § 3.1. Positive definite matrices.- § 3.2. Criteria for positive definiteness.- § 3.3. The Cholesky decomposition.- § 3.4. Programming the Cholesky decomposition.- § 3.5. Solution of a linear system.- § 3.6. Influence of rounding errors.- § 3.7. Linear systems of equations as a minimum problem.- Notes to Chapter 3.- 4. Nonlinear Equations.- § 4.1. The basic idea of linearization.- § 4.2. Newton’s method.- § 4.3. The regula falsi.- § 4.4. Algebraic equations.- § 4.5. Root squaring (Dandelin-Graeffe).- § 4.6. Application of Newton’s method to algebraic equations.- Notes to Chapter 4.- 5. Least Squares Problems.- § 5.1. Nonlinear least squares problems.- § 5.2. Linear least squares problems and their classical solution.- § 5.3. Unconstrained least squares approximation through orthogonalization.- § 5.4. Computational implementation of the orthogonalization.- § 5.5. Constrained least squares approximation through orthogonalization.- Notes to Chapter 5.- 6. Interpolation.- § 6.1. The interpolation polynomial.- § 6.2. The barycentric formula.- § 6.3. Divided differences.- § 6.4. Newton’s interpolation formula.- § 6.5. Specialization to equidistant xi.- § 6.6. The problematic nature of Newton interpolation.- § 6.7. Hermite interpolation.- § 6.8. Spline interpolation.- § 6.9. Smoothing.- § 6.10.Approximate quadrature.- Notes to Chapter 6.- 7. Approximation.- § 7.1. Critique of polynomial representation.- § 7.2. Definition and basic properties of Chebyshev polynomials.- § 7.3. Expansion in T-polynomials.- § 7.4. Numerical computation of the T-coefficients.- § 7.5. The use of T-expansions.- § 7.6. Best approximation in the sense of Chebyshev (T-approximation).- § 7.7. The Remez algorithm.- Notes to Chapter 7.- 8. Initial Value Problems for Ordinary Differential Equations.- §8.1. Statement of the problem.- § 8.2. The method of Euler.- § 8.3. The order of a method.- § 8.4. Methods of Runge-Kutta type.- § 8.5. Error considerations for the Runge-Kutta method when applied to linear systems of differential equations.- § 8.6. The trapezoidal rule.- § 8.7. General difference formulae.- § 8.8. The stability problem.- § 8.9. Special cases.- Notes to Chapter 8.- 9. Boundary Value Problems For Ordinary Differential Equations.- § 9.1. The shooting method.- § 9.2. Linear boundary value problems.- § 9.3. The Floquet solutions of a periodic differential equation.- § 9.4. Treatment of boundary value problems with difference methods.- § 9.5. The energy method for discretizing continuous problems.- Notes to Chapter 9.- 10. Elliptic Partial Differential Equations, Relaxation Methods.- §10.1. Discretization of the Dirichlet problem.- §10.2. The operator principle.- §10.3. The general principle of relaxation.- §10.4. The method of Gauss-Seidel, overtaxation.- §10.5. The method of conjugate gradients.- §10.6. Application to a more complicated problem.- §10.7. Remarks on norms and the condition of a matrix.- Notes to Chapter 10.- 11. Parabolic and Hyperbolic Partial Differential Equations.- §11.1. One-dimensional heat conduction problems.- §11.2. Stability of the numerical solution.- §11.3. The one-dimensional wave equation.- §11.4. Remarks on two-dimensional heat conduction problems.- Notes to Chapter 11.- 12. The Eigenvalue Problem For Symmetric Matrices.- §12.1. Introduction.- §12.2. Extremal properties of eigenvalues.- §12.3. The classical Jacobi method.- §12.4. Programming considerations.- §12.5. The cyclic Jacobi method.- §12.6. The LR transformation.- §12.7. The LR transformation with shifts.- §12.8. The Householder transformation.- §12.9. Determination of the eigenvalues of a tridiagonal matrix.- Notes to Chapter 12.- 13. The Eigenvalue Problem For Arbitrary Matrices.- §13.1. Susceptibility to errors.- §13.2. Simple vector iteration.- Notes to Chapter 13.- Appendix. An Axiomatic Theory of Numerical Computation with an Application to the Quotient-Difference Algorithm.- Editor’s Foreword.- Al. Introduction.- §A1.1. The eigenvalues of a qd-row.- §A1.2. The progressive form of the qd-algorithm.- §A1.3. The generating function of a qd-row.- §A1.4. Positive qd-rows.- §A1.5. Speed of convergence of the qd-algorithm.- §A1.6. The qd-algorithm with shifts.- §A1.7. Deflation after the determination of an eigenvaluec.- A2. Choice of Shifts.- §A2.1. Effect of the shift v on Z’.- §A2.2. Seropositive qd-rows.- § A2.4. A formal algorithm for the determination of eigenvalues.- A3. Finite Arithmetic.- §A3.1. The basic sets.- §A3.2. Properties of the arithmetic.- §A3.3. Monotonicity of the arithmetic.- §A3.4. Precision of the arithmetic.- §A3.5. Underflow and overflow control.- A4. Influence of Rounding Errors.- §A4.1. Persistent properties of the qd-algorithm.- §A4.2. Coincidence.- §A4.3. The differential form of the progressive qd-algorithm.- §A4.4. The influence of rounding errors on convergence.- A5. Stationary Form of the qd-Algorithm.- §A5.1. Development of the algorithm.- §A5.2. The differential form of the stationary qd-algorithm.- §A5.3. Properties of the stationary qd-algorithm.- §A5.4. Safe qd-steps.- Bibliography to the Appendix.- Author Index.