Numerical Recipes in PASCAL - The Art of Scientific Computing

Description

This book is supposed to teach you methods of numerical computing which are practical, efficient, and (insofar as possible) elegant. We presume throughout this book that you, the reader, have particular tasks that you want to get done. We view our job as educating you on how to proceed. Occasionally we may try to reroute you briefly onto a particularly beautiful side road; but by and large, we will travel with you along main highways that lead to practical destinations. Throughout this book, you will find us fearlessly editorializing, telling you what you should and shouldn't do. This prescriptive tone results from a conscious decision on our part, and we hope that you will not find it irritating. We do not claim that our advice is infallible! Rather, we are reacting against a tendency, in the textbook literature of computation, to discuss every possible method that has ever been invented, without ever offering a practical judgment on relative merit. We do, therefore, offer you our practical judgments whenever we can. As you gain experience, you will form your own opinion of how reliable our advice is. We presume that you are able to read computer programs in Pascal. In this edition of Numerical Recipes that is the language in which all the "recipes" are implemented. If you are more comfortable with FORTRAN or C, you will find other editions of the book in those languages. The various editions are quite similar with respect to mathematical and algorithmic content. Moreover, we have chosen our programming conventions to accentuate the similarities between languages. If you are multilingual, any single edition should suffice. Title Page Contents Preface to the Pascal Edition Preface Acknowledgements List of Computer Programs 1 PRELIMINARIES 1.0 Introduction 1.1 Program Organization and Control Structures 1.2 Conventions for Scientific Computing in Pascal 1.3 Error, Accuracy, and Stability 2 SOLUTION OF LINEAR ALGEBRAIC EQUATIONS 2.0 Introduction 2.1 Gauss-Jordan Elimination 2.2 Gaussian Elimination with Backsubstitution 2.3 LU Decomposition 2.4 Inverse of a Matrix 2.5 Determinant of a Matrix 2.6 Tridiagonal Systems of Equations 2.7 Iterative Improvement of a Solution to Linear Equations 2.8 Vandermonde Matrices and Toeplitz Matrices 2.9 Singular Value Decomposition 2.10 Sparse Linear Systems 2.11 Is Matrix Inversion an N^3 Process? 3 INTERPOLATION AND EXTRAPOLATION 3.0 Introduction 3.1 Polynomial Interpolation and Extrapolation 3.2 Rational Function Interpolation and Extrapol 3.3 Cubic Spline Interpolation 3.4 How to Search an Ordered Table 3.5 Coefficients of the Interpolating Polynomial 3.6 Interpolation in Two or More Dimensions 4 INTEGRATION OF FUNCTIONS 4.0 Introduction 4.1 Classical Formulas for Equally-Spaced Abscissas 4.2 Elementary Algorithms 4.3 Romberg Integration 4.4 Improper Integrals 4.5 Gaussian Quadratures 4.6 Multidimensional Integrals 5 EVALUATION OF FUNCTIONS 5.0 Introduction 5.1 Series and Their Convergence 5.2 Evaluation of Continued Fractions 5.3 Polynomials and Rational Functions 5.4 Recurrence Relations and Clenshaw's Recurrence Formula 5.5 Quadratic and Cubic Equations 5.6 Chebyshev Approximation 5.7 Derivatives or Integrals of a Chebyshev-approximated Function 5.8 Polynomial Approximation from Chebyshev Coefficients 6 SPECIAL FUNCTIONS 6.0 Introduction 6.1 Gamma Function, Beta Function, Factorials, Binomial Coefficients 6.2 Incomplete Gamma Function, Error Function, Chi-Square Probability Function, Cumulative Poisson Distribution 6.3 Incomplete Beta Function, Student's Distribution, F-Distribution, Cumulative Binomial Distribution 6.4 Bessel Functions of Integer Order 6.5 Modified Bessel Functions of Integer Order 6.6 Spherical Harmonics 6.7 Elliptic Integrals and Jacobian Elliptic Functions 7 RANDOM NUMBERS 7.0 Introduction 7.1 Uniform Deviates 7.2 Transformation Method: Exponential and Normal Deviates 7.3 Rejection Method: Gamma, Poisson, Binomial Deviates 7.4 Generation of Random Bits 7.5 The Data Encryption Standard 7.6 Monte Carlo Integration 8 SORTING 8.0 Introduction 8.1 Straight Insertion and Shell's Method 8.2 Heapsort 8.3 Indexing and Ranking 8.4 Quicksort 8.5 Determination of Equivalence Classes 9 ROOT FINDING AND NONLINEAR SETS OFEQUATIONS 9.0 Introduction 9.1 Bracketing and Bisection 9.2 Secant Method and False Position Method 9.3 Van Wijngaarden-Dekker-Brent Method 9.4 Newton-Raphson Method Using Derivative 9.5 Roots of Polynomials 9.6 Newton-Raphson Method for Nonlinear Systems of Equations 10 MINIMIZATION OR MAXIMIZATION OF FUNCTIONS 10.0 Introduction 10.1 Golden Section Search in One Dimension 10.2 Parabolic Interpolation and Brent's Method in One Dimension 10.3 One-Dimensional Search with First Derivatives 10.4 Downhill Simplex Method in Multidimensions 10.5 Direction Set (Powell's) Methods in Multidimensions 10.6 Conjugate Gradient Methods in Multidimensions 10.7 Variable Metric Methods in Multidimensions 10.8 Linear Programming and the Simplex Method 10.9 Combinatorial Minimization: Method of Simulated Annealing 11 EIGENSYSTEMS 11.0 Introduction 11.1 Jacobi Transformations of a Symmetric Matrix 11.2 Reduction of a Symmetric Matrix to Tridiagonal Form: Givens and Householder Reductions 11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 11.4 Hermitian Matrices 11.5 Reduction of a General Matrix to Hessenberg Form 11.6 The QR Algorithm for Real Hessenberg Matrices 11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 12 FOURIER TRANSFORM SPECTRAL METHODS 12.0 Introduction 12.1 Fourier Transform of Discretely Sampled Data 12.2 Fast Fourier Transform (FFT) 12.3 FFT of Real Functions, Sine and Cosine Transforms 12.4 Convolution and Deconvolution Using the FFT 12.5 Correlation and Autocorrelation Using the FFT 12.6 Optimal (Wiener) Filtering with the FFT 12.7 Power Spectrum Estimation Using the FFT 12.8 Power Spectrum Estimation by the Maximum Entropy (All Poles)Method 12.9 Digital Filtering in the Time Domain 12.10 Linear Prediction and Linear Predictive Coding 12.11 FFT in Two or More Dimensions 13 STATISTICAL DESCRIPTION OF DATA 13.0 Introduction 13.1 Moments of a Distribution: Mean, Variance, Skewness, and so forth 13.2 Efficient Search for the Median 13.3 Estimation of the Mode for Continuous Data 13.4 Do Two Distributions Have the Same Means or Variances? 13.5 Are Two Distributions Different? 13.6 Contingency Table Analysis of Two Distributions 13.7 Linear Correlation 13.8 Nonparametric or Rank Correlation 13.9 Smoothing of Data 14 MODELING OF DATA 14.0 Introduction 14.1 Least Squares as a Maximum Likelihood Estimator 14.2 Fitting Data to a Straight Line 14.3 General Linear Least Squares 14.4 Nonlinear Models 14.5 Confidence Limits on Estimated Model Parameters 14.6 Robust Estimation 15 INTEGRATION OF ORDINARY DIFFERENTIAL EQUATIONS 15.0 Introduction 15.1 Runge-Kutta Method 15.2 Adaptive Stepsize Control for Runge-Kutta 15.3 Modified Midpoint Method 15.4 Richardson Extrapolation and the Bulirsch-Stoer Method 15.5 Predictor-Corrector Methods 15.6 Stiff Sets of Equations 16 TWO POINT BOUNDARY VALUE PROBLEMS 16.0 Introduction 16.1 The Shooting Method 16.2 Shooting to a Fitting Point 16.3 Relaxation Methods 16.4 A Worked Example: Spheroidal Harmonics 16.5 Automated Allocation of Mesh Points 16.6 Handling Internal Boundary Conditions or Singular Points 17 PARTIAL DIFFERENTIAL EQUATIONS 17.0 Introduction 17.1 Flux-Conservative Initial Value Problems 17.2 Diffusive Initial Value Problems 17.3 Initial Value Problems in Multidimensions 17.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 17.5 Relaxation Methods for Boundary Value Problems 17.6 Operator Splitting Methods and ADI APPENDIX A: References APPENDIX B: Table of Program Dependencies Index