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.
Author(s): William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling
Edition: 1
Publisher: Cambridge University Press
Year: 1989
Language: English
Commentary: 4th printing 1994
Pages: XX; 759
City: Cambridge
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
