Numerical Methods

Boehm , Wolfgang

• Preface -- I FUNDAMENTAL CONCEPTS -- 1 Algorithms and Error Propagation -- 1.1 Algorithms -- 1.2 The Implementation of Algorithms -- 1.3 Judging an Algorithm -- 1.4 Notes and Exercises -- 2 Matrices -- 2.1 Notations -- 2.2 Products of Matrices -- 2.3 Falk’s Scheme -- 2.4 Rank and Determinant -- 2.5 Norm and Convergence -- 2.6 Notes and Exercises -- II LINEAR EQUATIONS AND INEQUALITIES -- 3 Gaussian Elimination -- 3.1 Backward Substitution -- 3.2 Gaussian Elimination -- 3.3 Pivoting -- 3.4 Notes and Exercises -- 4 The LU Factorization -- 4.1 The LU Factorization of A -- 4.2 LU Factorization with Pivoting -- 4.3 Systems of Linear Equations -- 4.4 Notes and Exercises -- 5 The Exchange Algorithm -- 5.1 Exchanging Variables -- 5.2 Scheme and Algorithm -- 5.3 Inversion -- 5.4 Linear Equations -- 5.5 Notes and Exercises -- 6 The Cholesky Factorization -- 6.1 Symmetrical Factorization -- 6.2 Existence and Uniqueness -- 6.3 Symmetric Systems of Linear Equations -- 6.4 Iterative Refinement -- 6.5 Notes and Exercises -- 7 The QU Factorization -- 7.1 The Householder Transformation -- 7.2 The Householder Algorithm -- 7.3 Systems of Linear Equations -- 7.4 Notes and Exercises -- 8 Relaxation Methods -- 8.1 Coordinate Relaxation -- 8.2 Convergence for Diagonally Dominant Matrices -- 8.3 The Minimum Problem -- 8.4 Convergence for Symmetric, Positive Definite Matrices -- 8.5 Geometric Meaning -- 8.6 Notes and Exercises -- 9 Data Fitting -- 9.1 Overdetermined Systems of Linear Equations -- 9.2 Using the QU Factorization -- 9.3 Application -- 9.4 Under determined Systems of Linear Equations -- 9.5 Application -- 9.6 Geometric Meaning and Duality -- 9.7 Notes and Exercises -- 10 Linear Optimization -- 10.1 Linear Inequalities and Linear Programming -- 10.2 Exchanging Vertices and the Simplex Method -- 10.3 Elimination -- 10.4 Data Fitting after Chebyshev -- 10.5 Notes and Exercises -- III ITERATION -- 11 Vector Iteration -- 11.1 The Eigenvalue Problem for Matrices -- 11.2 Vector Iteration after von Mises -- 11.3 Inverse Iteration -- 11.4 Improving an Approximation -- 11.5 Notes and Exercises -- 12 The LR Algorithm -- 12.1 The Algorithm of Rutishauser -- 12.2 Proving Convergence -- 12.3 Pairs of Eigenvalues with Equal Modulus -- 12.4 Notes and Exercises -- 13 One-Dimensional Iteration -- 13.1 Contractive Mappings -- 13.2 Error Bounds -- 13.3 Rate of Convergence -- 13.4 Aitken’s A2-Method -- 13.5 Geometric Acceleration -- 13.6 Roots -- 13.7 Notes and Exercises -- 14 Multi-Dimensional Iteration -- 14.1 Contractive Mappings -- 14.2 Rate of Convergence -- 14.3 Accelerating the Convergence -- 14.4 Roots of Systems -- 14.5 Notes and Exercises -- 15 Roots of Polynomials -- 15.1 The Horner Scheme -- 15.2 The Extended Horner Scheme -- 15.3 Simple Roots -- 15.4 Bairstow’s Method -- 15.5 The Extended Horner Scheme for Quadratic Factors -- 15.6 Notes and Exercises -- 16 Bernoulli’s Method -- 16.1 Linear Difference Equations -- 16.2 Matrix Notation -- 16.3 Bernoulli’s Method -- 16.4 Inverse Iteration -- 16.5 Notes and Exercises -- 17 The QD Algorithm -- 17.1 The LR Algorithm for Tridiagonal Matrices -- 17.2 The QD scheme for Polynomials -- 17.3 Pairs of Zeros with Equal Modulus -- 17.4 Notes and Exercises -- IV INTERPOLATION AND DISCRETE APPROXIMATION -- 18 Interpolation -- 18.1 Interpolation Polynomials -- 18.2 Lagrange Polynomials -- 18.3 Lagrange Form -- 18.4 Newton Form -- 18.5 Aitken’s Lemma -- 18.6 Neville’s Scheme -- 18.7 Hermite Interpolation -- 18.8 Piecewise Hermite Interpolation -- 18.9 The Cardinal Hermite Basis -- 18.10 More-Dimensional Interpolation -- 18.11 Surface Patches of Coons and Gordon -- 18.12 Notes and Exercises -- 19 Discrete Approximation -- 19.1 The Taylor Polynomials -- 19.2 The Interpolation Polynomial -- 19.3 Chebyshev Approximation -- 19.4 Chebyshev Polynomials -- 19.5 The Minimum Property -- 19.6 Expanding by Chebyshev Polynomials -- 19.7 Economization of Polynomials -- 19.8 Least Squares Method -- 19.9 The Orthogonality of Chebyshev Polynomials -- 19.10 Notes and Exercises -- 20 Polynomials in Bezier Form -- 20.1 Bernstein Polynomials -- 20.2 Polynomials in Bezier Form -- 20.3 The Construction of Position and Tangent -- 20.4 Bezier Surfaces -- 20.5 Notes and Exercises -- 21 Splines -- 21.1 Bezier Curves -- 21.2 Differentiability Conditions -- 21.3 Cubic Splines -- 21.4 The Minimum Property -- 21.5 B-Splines and Truncated Power Functions -- 21.6 Normalized B-Splines -- 21.7 De Boor’s Algorithm -- 21.8 Notes and Exercises -- V NUMERICAL DIFFERENTIATION AND INTEGRATION -- 22 Numerical Differentiation and Integration -- 22.1 Numerical Differentiation -- 22.2 Error Estimates for the Numerical Differentiation -- 22.3 Numerical Integration -- 22.4 Composite Integration Rules -- 22.5 Error Estimation for the Numerical Integration -- 22.6 Notes and Exercises -- 23 Extrapolation -- 23.1 Sequences of Approximations -- 23.2 Richardson Extrapolation -- 23.3 Iterated Richardson Extrapolation -- 23.4 Romberg Integration -- 23.5 Notes and Exercises -- 24 One-Step Methods for Differential Equations -- 24.1 Discretization -- 24.2 Discretization Error -- 24.3 Runge-Kutta Methods -- 24.4 Error Control -- 24.5 Notes and Exercises -- 25 Linear Multi-Step Methods for Differential Equations -- 25.1 Discretization -- 25.2 Convergence of Multi-Step Methods -- 25.3 Root Condition -- 25.4 Sufficient Convergence Conditions -- 25.5 Starting Values -- 25.6 Predictor-Corrector Methods -- 25.7 Step Size Control -- 25.8 Comparing One- and Multi-Step Methods -- 25.9 Notes and Exercises -- 26 The Methods by Ritz and Galerkin -- 26.1 The Principle of Minimal Energy -- 26.2 The Ritz Method -- 26.3 Galerkin’s Method -- 26.4 Relation -- 26.5 Notes and Exercises -- 27 The Finite Element Method -- 27.1 Finite Elements -- 27.2 Univariate Splines -- 27.3 Bivariate Splines -- 27.4 Numerical Examples -- 27.5 Local Coordinates -- 27.6 Notes and Exercises -- 28 Bibliography -- Index.