Numerical Algorithms with Fortran

1 Computer Numbers, Error Analysis, Conditioning, Stability of Algorithms and Operations Count.- 1.1 Definition of Errors.- 1.2 Decimal Representation of Numbers.- 1.3 Sources of Errors.- 1.3.1 Input Errors.- 1.3.2 Procedural Errors.- 1.3.3 Error Propagation and the Condition of a Problem.- 1.3.4 The Computational Error and Numerical Stability of an Algorithm.- 1.4 Operations Count, et cetera.- 2 Nonlinear Equations in One Variable.- 2.1 Introduction.- 2.2 Definitions and Theorems on Roots.- 2.3 General Iteration Procedures.- 2.3.1 How to Construct an Iterative Process.- 2.3.2 Existence and Uniqueness of Solutions.- 2.3.3 Convergence and Error Estimates of Iterative Procedures.- 2.3.4 Practical Implementation.- 2.4 Order of Convergence of an Iterative Procedure.- 2.4.1 Definitions and Theorems.- 2.4.2 Determining the Order of Convergence Experimentally.- 2.5 Newton's Method.- 2.5.1 Finding Simple Roots.- 2.5.2 A Damped Version of Newton's Method.- 2.5.3 Newton's Method for Multiple Zeros; a Modified Newton's Method.- 2.6 Regula Falsi.- 2.6.1 Regula Falsi for Simple Roots.- 2.6.2 Modified Regula Falsi for Multiple Zeros.- 2.6.3 Simplest Version of the Regula Falsi.- 2.7 Steffensen Method.- 2.7.1 Steffensen Method for Simple Zeros.- 2.7.2 Modified Steffensen Method for Multiple Zeros.- 2.8 Inclusion Methods.- 2.8.1 Bisection Method.- 2.8.2 Pegasus Method.- 2.8.3 Anderson-Bjorck Method.- 2.8.4 The King and the Anderson-Bjorck-King Methods, the Illinois Method.- 2.8.5 Zeroin Method.- 2.9 Efficiency of the Methods and Aids for Decision Making.- 3 Roots of Polynomials.- 3.1 Preliminary Remarks.- 3.2 The Horner Scheme.- 3.2.1 First Level Horner Scheme for Real Arguments.- 3.2.2 First Level Horner Scheme for Complex Arguments.- 3.2.3 Complete Horner Scheme for Real Arguments.- 3.2.4 Applications.- 3.3 Methods for Finding all Solutions of Algebraic Equations.- 3.3.1 Preliminaries.- 3.3.2 Muller's Method.- 3.3.3 Bauhuber's Method.- 3.3.4 The Jenkins-Traub Method.- 3.3.5 The Laguerre Method.- 3.4 Hints for Choosing a Method.- 4 Direct Methods for Solving Systems of Linear Equations..- 4.1 The Problem.- 4.2 Definitions and Theoretical Background.- 4.3 Solvability Conditions for Systems of Linear Equations.- 4.4 The Factorization Principle.- 4.5 Gaufi Algorithm.- 4.5.1 Gaufi Algorithm with Column Pivot Search.- 4.5.2 Pivot Strategies.- 4.5.3 Computer Implementation of Gaufi Algorithm.- 4.5.4 Gaufi Algorithm for Systems with Several Right Hand Sides.- 4.6 Matrix Inversion via Gaufi Algorithm.- 4.7 Linear Equations with Symmetric Strongly Nonsingular System Matrices.- 4.7.1 The Cholesky Decomposition.- 4.7.2 The Conjugate Gradient Method.- 4.8 The Gaufi - Jordan Method.- 4.9 The Matrix Inverse via Exchange Steps.- 4.10 Linear Systems with Tridiagonal Matrices.- 4.10.1 Systems with Tridiagonal Matrices.- 4.10.2 Systems with Tridiagonal Symmetric Strongly Nonsingular Matrices.- 4.11 Linear Systems with Cyclically Tridiagonal Matrices.- 4.11.1 Systems with a Cyclically Tridiagonal Matrix.- 4.11.2 Systems with Symmetric Cyclically Tridiagonal Strongly Nonsingular Matrices.- 4.12 Linear Systems with Five-Diagonal Matrices.- 4.12.1 Systems with Five-Diagonal Matrices.- 4.12.2 Systems with Five-Diagonal Symmetric Matrices.- 4.13 Linear Systems with Band Matrices.- 4.14 Solving Linear Systems via Householder Transformations.- 4.15 Errors, Conditioning and Iterative Refinement.- 4.15.1 Errors and the Condition Number.- 4.15.2 Condition Estimates.- 4.15.3 Improving the Condition Number.- 4.15.4 Iterative Refinement.- 4.16 Systems of Equations with Block Matrices.- 4.16.1 Preliminary Remarks.- 4.16.2 Gaufi Algorithm for Block Matrices.- 4.16.3 Gaufi Algorithm for Block Tridiagonal Systems.- 4.16.4 Other Block Methods.- 4.17 The Algorithm of Cuthill-McKee for Sparse Symmetric Matrices.- 4.18 Recommendations for Selecting a Method.- 5 Iterative Methods for Linear Systems.- 5.1 Preliminary Remarks.- 5.2 Vector and Matrix Norms.- 5.3 The Jacobi Method.- 5.4 The Gaufi-Seidel Iteration.- 5.5 A Relaxation Method using the Jacobi Method.- 5.6 A Relaxation Method using the Gaufi-Seidel Method.- 5.6.1 Iteration Rule.- 5.6.2 Estimate for the Optimal Relaxation Coefficient, an Adaptive SOR Method.- 6 Systems of Nonlinear Equations.- 6.1 General Iterative Methods.- 6.2 Special Iterative Methods.- 6.2.1 Newton Methods for Nonlinear Systems.- 6.2.1.1 The Basic Newton Method.- 6.2.1.2 Damped Newton Method for Systems.- 6.2.2 Regula Falsi for Nonlinear Systems.- 6.2.3 Method of Steepest Descent for Nonlinear Systems.- 6.2.4 Brown's Method for Nonlinear Systems.- 6.3 Choosing a Method.- 7 Eigenvalues and Eigenvectors of Matrices.- 7.1 Basic Concepts.- 7.2 Diagonalizable Matrices and the Conditioning of the Eigenvalue Problem.- 7.3 Vector Iteration.- 7.3.1 The Dominant Eigenvalue and the Associated Eigenvector of a Matrix.- 7.3.2 Determination of the Eigenvalue Closest to Zero.- 7.3.3 Eigenvalues in Between.- 7.4 The Rayleigh Quotient for Hermitian Matrices.- 7.5 The Krylov Method.- 7.5.1 Determining the Eigenvalues.- 7.5.2 Determining the Eigenvectors.- 7.6 Eigenvalues of Positive Definite Tridiagonal Matrices, the QD Algorithm.- 7.7 Transformation to Hessenberg Form, the LR and QR Algorithms.- 7.7.1 Transformation of a Matrix to Upper Hessenberg Form.- 7.7.2 The LR Algorithm.- 7.7.3 The Basic QR Algorithm.- 7.8 Eigenvalues and Eigenvectors of a Matrix via the QR Algorithm.- 7.9 Decision Strategy.- 8 Linear and Nonlinear Approximation.- 8.1 Linear Approximation.- 8.1.1 Statement of the Problem and Best Approximation.- 8.1.2 Linear Continuous Root-Mean-Square Approximation.- 8.1.3 Discrete Linear Root-Mean-Square Approximation.- 8.1.3.1 Normal Equations for Discrete Linear Least Squares.- 8.1.3.2 Discrete Least Squares via Algebraic Polynomials and Orthogonal Polynomials.- 8.1.3.3 Linear Regression, the Least Squares Solution Using Linear Algebraic Polynomials.- 8.1.3.4 Solving Linear Least Squares Problems using Householder Transformations.- 8.1.4 Approximation of Polynomials by Chebyshev Polynomials.- 8.1.4.1 Best Uniform Approximation.- 8.1.4.2 Approximation by Chebyshev Polynomials.- 8.1.5 Approximation of Periodic Functions and the FFT.- 8.1.5.1 Root-Mean-Square Approximation of Periodic Functions.- 8.1.5.2 Trigonometric Interpolation.- 8.1.5.3 Complex Discrete Fourier Transformation (FFT).- 8.1.6 Error Estimates for Linear Approximation.- 8.1.6.1 Estimates for the Error in Best Approximation.- 8.1.6.2 Error Estimates for Simultaneous Approximation of a Function and its Derivatives.- 8.1.6.3 Approximation Error Estimates using Linear Projection Operators.- 8.2 Nonlinear Approximation.- 8.2.1 Transformation Method for Nonlinear Least Squares.- 8.2.2 Nonlinear Root-Mean-Square Fitting.- 8.3 Decision Strategy.- 9 Polynomial and Rational Interpolation.- 9.1 The Problem.- 9.2 Lagrange Interpolation Formula.- 9.2.1 Lagrange Formula for Arbitrary Nodes.- 9.2.2 Lagrange Formula for Equidistant Nodes.- 9.3 The Aitken Interpolation Scheme for Arbitrary Nodes.- 9.4 Inverse Interpolation According to Aitken.- 9.5 Newton Interpolation Formula.- 9.5.1 Newton Formula for Arbitrary Nodes.- 9.5.2 Newton Formula for Equidistant Nodes.- 9.6 Remainder of an Interpolation and Estimates of the Interpolation Error.- 9.7 Rational Interpolation.- 9.8 Interpolation for Functions in Several Variables.- 9.8.1 Lagrange Interpolation Formula for Two Variables.- 9.8.2 Shepard Interpolation.- 9.9 Hints for Selecting an Appropriate Interpolation Method.- 10 Interpolating Polynomial Splines for Constructing Smooth Curves.- 10.1 Cubic Polynomial Splines.- 10.1.1 Definition of Interpolating Cubic Spline Functions.- 10.1.2 Computation of Non-Parametric Cubic Splines.- 10.1.3 Computing Parametric Cubic Splines.- 10.1.4 Joined Interpolating Polynomial Splines.- 10.1.5 Convergence and Error Estimates for Interpolating Cubic Splines.- 10.2 Hermite Splines of Fifth Degree.- 10.2.1 Definition of Hermite Splines.- 10.2.2 Computation of Non-Parametric Hermite Splines.- 10.2.3 Computation of Parametric Hermite Splines.- 10.3 Hints for Selecting Appropriate Interpolating or Approximating Splines.- 11 Cubic Fitting Splines for Constructing Smooth Curves.- 11.1 The Problem.- 11.2 Definition of Fitting Spline Functions.- 11.3 Non-Parametric Cubic Fitting Splines.- 11.4 Parametrie Cubie Fitting Splines.- 11.5 Deeision Strategy.- 12 Two-Dimensional Splines, Surface Splines, Bézier Splines, B-Splines.- 12.1 Interpolating Two-Dimensional Cubie Splines for Construeting Smooth Surfaees.- 12.2 Two-Dimensional Interpolating Surfaee Splines.- 12.3 Bézier Splines.- 12.3.1 Bézier Spline Curves.- 12.3.2 Bézier Spline Surfaees.- 12.3.3 Modified Interpolating Cubie Bezier Splines.- 12.4 B-Splines.- 12.4.1 B-Spline-Curves.- 12.4.2 B-Spline-Surfaees.- 12.5 Hints.- 13 Akima and Renner Subsplines.- 13.1 Akima Subsplines.- 13.2 Renner Subsplines.- 13.3 Rounding of Corners with Akima and Renner Splines.- 13.4 Approximate Computation of Are Length.- 13.5 Seleetion Hints.- 14 Numerical Differentiation.- 14.1 The Task.- 14.2 Differentiation Using Interpolating Polynomials.- 14.3 Differentiation via Interpolating Cubie Splines.- 14.4 Differentiation by the Romberg Method.- 14.5 Deeision Hints.- 15 Numerical Integration.- 15.1 Preliminary Remarks.- 15.2 Interpolating Quadrature Formulas.- 15.3 Newton-Cotes Formulas.- 15.3.1 The Trapezoidal Rule.- 15.3.2 Simpson's Rule.- 15.3.3 The 3/8 Formula.- 15.3.4 Other Newton-Cotes Formulas.- 15.3.5 The Error Order of Newton-Cotes Formulas.- 15.4 Maclaurin Quadrature Formulas.- 15.4.1 The Tangent Trapezoidal Formula.- 15.4.2 Other Maclaurin Formulas.- 15.5 Euler-Maclaurin Formulas.- 15.6 Chebyshev Quadrature Formulas.- 15.7 Gauß Quadrature Formulas.- 15.8 Calculation of Weights and Nodes of Generalized Gaussian Quadrature Formulas.- 15.9 Clenshaw-Curtis Quadrature Formulas.- 15.10 Romberg Integration.- 15.11 Error Estimates and Computational Errors.- 15.12 Adaptive Quadrature Methods.- 15.13 Convergence of Quadrature Formulas.- 15.14 Hints for Choosing an Appropriate Method.- 16 Numerical Cubature.- 16.1 The Problem.- 16.2 Interpolating Cubature Formulas.- 16.3 Newton-Cotes Cubature Formulas for Rectangular Regions.- 16.4 Newton-Cotes Cubature Formulas for Triangles.- 16.5 Romberg Cubature for Rectangular Regions.- 16.6 Gauß Cubature Formulas for Rectangles.- 16.7 Gauß Cubature Formulas for Triangles.- 16.7.1 Right Triangles with Legs Parallel to the Axis.- 16.7.2 General Triangles.- 16.8 Riemann Double Integrals using Bicubic Splines.- 16.9 Decision Strategy.- 17 Initial Value Problems for Ordinary Differential Equations.- 17.1 The Problem.- 17.2 Principles of the Numerical Methods.- 17.3 One-Step Methods.- 17.3.1 The Euler-Cauchy Polygonal Method.- 17.3.2 The Improved Euler-Cauchy Method.- 17.3.3 The Predictor-Corrector Method of Heun.- 17.3.4 Explicit Runge-Kutta Methods.- 17.3.4.1 Construction of Runge-Kutta Methods.- 17.3.4.2 The Classical Runge-Kutta Method.- 17.3.4.3 A List of Explicit Runge-Kutta Formulas.- 17.3.4.4 Embedding Formulas.- 17.3.5 Implicit Runge-Kutta Methods of Gaussian Type.- 17.3.6 Consistence and Convergence of One-Step Methods.- 17.3.7 Error Estimation and Step Size Control.- 17.3.7.1 Error Estimation.- 17.3.7.2 Automatic Step Size Control, Adaptive Methods for Initial Value Problems.- 17.4 Multi-Step Methods.- 17.4.1 The Principle of Multi-Step Methods.- 17.4.2 The Adams-Bashforth Method.- 17.4.3 The Predictor-Corrector Method of Adams-Moulton.- 17.4.4 The Adams-Stormer Method.- 17.4.5 Error Estimates for Multi-Step Methods.- 17.4.6 Computational Error of One-Step and Multi-Step Methods.- 17.5 Bulirsch-Stoer-Gragg Extrapolation.- 17.6 Stability.- 17.6.1 Preliminary Remarks.- 17.6.2 Stability of Differential Equations.- 17.6.3 Stability of the Numerical Method.- 17.7 Stiff Systems of Differential Equations.- 17.7.1 The Problem.- 17.7.2 Criteria for the Stiffness of a System.- 17.7.3 Gear's Method for Integrating Stiff Systems.- 17.8 Suggestions for Choosing among the Methods.- 18 Boundary Value Problems for Ordinary Differential Equations.- 18.1 Statement of the Problem.- 18.2 Reduction of Boundary Value Problems to Initial Value Problems.- 18.2.1 Boundary Value Problems for Nonlinear Differential Equations of Second Order.- 18.2.2 Boundary Value Problems for Systems of Differential Equations of First Order.- 18.2.3 The Multiple Shooting Method.- 18.3 Difference Methods.- 18.3.1 The Ordinary Difference Method.- 18.3.2 Higher Order Difference Methods.- 18.3.3 Iterative Solution of Linear Systems for Special Boundary Value Problems.- 18.3.4 Linear Eigenvalue Problems.- A Appendix: Standard FORTRAN 77 Subroutines.- A.1 Preface of the Appendix.- A.2 Information on Campus and Site Licenses, as well as on Other Software Packages.- A.3 Contents of the Enclosed CD.- of the Appendix.- A.4 FORTRAN 77 Subroutines.- B Bibliography.- Literature for Other Topics.- - Numerical Treatment of Partial Differential Equations.- - Finite Element Method.- C Index.