Numerical Algorithms with Fortran

by Gisela Engeln-Mïllges, M. Schon (Translator), Frank Uhlig, F. Uhlig (Translator)

Overview

This is a completely up-to-date compendium of Fortran algorithms for numerical mathematics, including many sophisticated algorithms which are not available elsewhere. All have been extensively field-tested and cover methods for solving nonlinear equations, the method of Laguerre for solving algebraic equations, conjugating gradients for solving linear systems of equations, and the McKee algorithm for solving special systems of symmetric equations. The real, practical algorithms provided make the book indispensable for applied scientists working in all areas of research. The CD contains Fortran programs for the algorithms given in the text.

Product Details

ISBN-13:	9783642800450
Publisher:	Springer Berlin Heidelberg
Publication date:	08/02/2013
Edition description:	Softcover reprint of the original 1st ed. 1996
Pages:	602
Product dimensions:	6.10(w) x 9.25(h) x 0.05(d)

Table of Contents

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.