Acrobat ^® Edition

 Also available is a PostScript edition.

 Thanks to special permission from Cambridge University Press, we are able to bring you the complete Numerical Recipes in Fortran 77 book On-Line! To utilize this resource, you will need an Adobe Acrobat viewer linked as a helper program to your WWW browser. Permission is granted by the copyright owners for users of the World Wide Web to make one paper copy of these PostScript files for their own personal use. Further reproduction, or the extraction of, or copying of, machine readable files to any server computer, is strictly prohibited. This on-line resource is not intended as a substitute for purchasing the book, or for obtaining a license for the use of Numerical Recipes source code.

Want to download the Numerical Recipes routines? Jump to the Numerical Recipes On-Line Software Store. You'll get instant downloading and can use your credit card to get an immediate, low-cost, single-screen license. You can order Numerical Recipes books, too!

Front Matter, Contents, and Prefaces xi

Legal Matters xvi

Computer Programs by Chapter and Section xix

1 Preliminaries

1.0 Introduction 1

1.1 Program Organization and Control Structures 5

1.2 Error, Accuracy, and Stability 18

2 Solution of Linear Algebraic Equations

2.0 Introduction 22

2.1 Gauss-Jordan Elimination 27

2.2 Gaussian Elimination with Backsubstitution 33

2.3 LU Decomposition and Its Applications 34

2.4 Tridiagonal and Band Diagonal Systems of Equations 42

2.5 Iterative Improvement of a Solution to Linear Equations 47

2.6 Singular Value Decomposition 51

2.7 Sparse Linear Systems 63

2.8 Vandermonde Matrices and Toeplitz Matrices 82

2.9 Cholesky Decomposition 89

2.10 QR Decomposition 91

2.11 Is Matrix Inversion an $N^3$ Process? 95

3 Interpolation and Extrapolation

3.0 Introduction 99

3.1 Polynomial Interpolation and Extrapolation 102

3.2 Rational Function Interpolation and Extrapolation 104

3.3 Cubic Spline Interpolation 107

3.4 How to Search an Ordered Table 110

3.5 Coefficients of the Interpolating Polynomial 113

3.6 Interpolation in Two or More Dimensions 116

4 Integration of Functions

4.0 Introduction 123

4.1 Classical Formulas for Equally Spaced Abscissas 124

4.2 Elementary Algorithms 130

4.3 Romberg Integration 134

4.4 Improper Integrals 135

4.5 Gaussian Quadratures and Orthogonal Polynomials 140

4.6 Multidimensional Integrals 155

5 Evaluation of Functions

5.0 Introduction 159

5.1 Series and Their Convergence 159

5.2 Evaluation of Continued Fractions 163

5.3 Polynomials and Rational Functions 167

5.4 Complex Arithmetic 171

5.5 Recurrence Relations and Clenshaw's Recurrence Formula 172

5.6 Quadratic and Cubic Equations 178

5.7 Numerical Derivatives 180

5.8 Chebyshev Approximation 184

5.9 Derivatives or Integrals of a Chebyshev-approximated Function 189

5.10 Polynomial Approximation from Chebyshev Coefficients 191

5.11 Economization of Power Series 192

5.12 Pad\'e Approximants 194

5.13 Rational Chebyshev Approximation 197

5.14 Evaluation of Functions by Path Integration 201

6 Special Functions

6.0 Introduction 205

6.1 Gamma Function, Beta Function, Factorials, Binomial Coefficients 206

6.2 Incomplete Gamma Function, Error Function, Chi-Square Probability Function, Cumulative Poisson Function 209

6.3 Exponential Integrals 215

6.4 Incomplete Beta Function, Student's Distribution, F-Distribution,Cumulative Binomial Distribution 219

6.5 Bessel Functions of Integer Order 223

6.6 Modified Bessel Functions of Integer Order 229

6.7 Bessel Functions of Fractional Order, Airy Functions, SphericalBessel Functions 234

6.8 Spherical Harmonics 246

6.9 Fresnel Integrals, Cosine and Sine Integrals 248

6.10 Dawson's Integral 252

6.11 Elliptic Integrals and Jacobian Elliptic Functions 254

6.12 Hypergeometric Functions 263

7 Random Numbers

7.0 Introduction 266

7.1 Uniform Deviates 267

7.2 Transformation Method: Exponential and Normal Deviates 277

7.3 Rejection Method: Gamma, Poisson, Binomial Deviates 281

7.4 Generation of Random Bits 287

7.5 Random Sequences Based on Data Encryption 290

7.6 Simple Monte Carlo Integration 295

7.7 Quasi- (that is, Sub-) Random Sequences 299

7.8 Adaptive and Recursive Monte Carlo Methods 306

8 Sorting

8.0 Introduction 320

8.1 Straight Insertion and Shell's Method 321

8.2 Quicksort 323

8.3 Heapsort 327

8.4 Indexing and Ranking 329

8.5 Selecting the $M$th Largest 333

8.6 Determination of Equivalence Classes 337

9 Root Finding and Nonlinear Sets of Equations

9.0 Introduction 340

9.1 Bracketing and Bisection 343

9.2 Secant Method, False Position Method, and Ridders' Method 347

9.3 Van Wijngaarden--Dekker--Brent Method 352

9.4 Newton-Raphson Method Using Derivative 355

9.5 Roots of Polynomials 362

9.6 Newton-Raphson Method for Nonlinear Systems of Equations 372

9.7 Globally Convergent Methods for Nonlinear Systems of Equations 376

10 Minimization or Maximization of Functions

10.0 Introduction 387

10.1 Golden Section Search in One Dimension 390

10.2 Parabolic Interpolation and Brent's Method in One Dimension 395

10.3 One-Dimensional Search with First Derivatives 399

10.4 Downhill Simplex Method in Multidimensions 402

10.5 Direction Set (Powell's) Methods in Multidimensions 406

10.6 Conjugate Gradient Methods in Multidimensions 413

10.7 Variable Metric Methods in Multidimensions 418

10.8 Linear Programming and the Simplex Method 423

10.9 Simulated Annealing Methods 436

11 Eigensystems

11.0 Introduction 449

11.1 Jacobi Transformations of a Symmetric Matrix 456

11.2 Reduction of a Symmetric Matrix to Tridiagonal Form: Givens and Householder Reductions 462

11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 469

11.4 Hermitian Matrices 475

11.5 Reduction of a General Matrix to Hessenberg Form 476

11.6 The QR Algorithm for Real Hessenberg Matrices 480

11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 487

12 Fast Fourier Transform

12.0 Introduction 490

12.1 Fourier Transform of Discretely Sampled Data 494

12.2 Fast Fourier Transform (FFT) 498

12.3 FFT of Real Functions, Sine and Cosine Transforms 504

12.4 FFT in Two or More Dimensions 515

12.5 Fourier Transforms of Real Data in Two and Three Dimensions 519

12.6 External Storage or Memory-Local FFTs 525

13 Fourier and Spectral Applications

13.0 Introduction 530

13.1 Convolution and Deconvolution Using the FFT 531

13.2 Correlation and Autocorrelation Using the FFT 538

13.3 Optimal (Wiener) Filtering with the FFT 539

13.4 Power Spectrum Estimation Using the FFT 542

13.5 Digital Filtering in the Time Domain 551

13.6 Linear Prediction and Linear Predictive Coding 557

13.7 Power Spectrum Estimation by the Maximum Entropy (All Poles) Method 565

13.8 Spectral Analysis of Unevenly Sampled Data 569

13.9 Computing Fourier Integrals Using the FFT 577

13.10 Wavelet Transforms 584

13.11 Numerical Use of the Sampling Theorem 600

14 Statistical Description of Data

14.0 Introduction 603

14.1 Moments of a Distribution: Mean, Variance, Skewness, and So Forth 604

14.2 Do Two Distributions Have the Same Means or Variances? 609

14.3 Are Two Distributions Different? 614

14.4 Contingency Table Analysis of Two Distributions 622

14.5 Linear Correlation 630

14.6 Nonparametric or Rank Correlation 633

14.7 Do Two-Dimensional Distributions Differ? 640

14.8 Savitzky-Golay Smoothing Filters 644

15 Modeling of Data

15.0 Introduction 650

15.1 Least Squares as a Maximum Likelihood Estimator 651

15.2 Fitting Data to a Straight Line 655

15.3 Straight-Line Data with Errors in Both Coordinates 660

15.4 General Linear Least Squares 665

15.5 Nonlinear Models 675

15.6 Confidence Limits on Estimated Model Parameters 684

15.7 Robust Estimation 694

16 Integration of Ordinary Differential Equations

16.0 Introduction 701

16.1 Runge-Kutta Method 704

16.2 Adaptive Stepsize Control for Runge-Kutta 708

16.3 Modified Midpoint Method 716

16.4 Richardson Extrapolation and the Bulirsch-Stoer Method 718

16.5 Second-Order Conservative Equations 726

16.6 Stiff Sets of Equations 727

16.7 Multistep, Multivalue, and Predictor-Corrector Methods 740

17 Two Point Boundary Value Problems

17.0 Introduction 745

17.1 The Shooting Method 749

17.2 Shooting to a Fitting Point 751

17.3 Relaxation Methods 753

17.4 A Worked Example: Spheroidal Harmonics 764

17.5 Automated Allocation of Mesh Points 774

17.6 Handling Internal Boundary Conditions or Singular Points 775

18 Integral Equations and Inverse Theory

18.0 Introduction 779

18.1 Fredholm Equations of the Second Kind 782

18.2 Volterra Equations 786

18.3 Integral Equations with Singular Kernels 788

18.4 Inverse Problems and the Use of A Priori Information 795

18.5 Linear Regularization Methods 799

18.6 Backus-Gilbert Method 806

18.7 Maximum Entropy Image Restoration 809

19 Partial Differential Equations

19.0 Introduction 818

19.1 Flux-Conservative Initial Value Problems 825

19.2 Diffusive Initial Value Problems 838

19.3 Initial Value Problems in Multidimensions 844

19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 848

19.5 Relaxation Methods for Boundary Value Problems 854

19.6 Multigrid Methods for Boundary Value Problems 862

20 Less-Numerical Algorithms

20.0 Introduction 881

20.1 Diagnosing Machine Parameters 881

20.2 Gray Codes 886

20.3 Cyclic Redundancy and Other Checksums 888

20.4 Huffman Coding and Compression of Data 896

20.5 Arithmetic Coding 902

20.6 Arithmetic at Arbitrary Precision 906

References and Program Dependencies 916

General Index 935