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 C 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 Some C Conventions for Scientific Computing 15

1.3 Error, Accuracy, and Stability 15

2 Solution of Linear Algebraic Equations

2.0 Introduction 32

2.1 Gauss-Jordan Elimination 36

2.2 Gaussian Elimination with Backsubstitution 41

2.3 LU Decomposition and Its Applications 43

2.4 Tridiagonal and Band Diagonal Systems of Equations 50

2.5 Iterative Improvement of a Solution to Linear Equations 55

2.6 Singular Value Decomposition 59

2.7 Sparse Linear Systems 71

2.8 Vandermonde Matrices and Toeplitz Matrices 90

2.9 Cholesky Decomposition 96

2.10 QR Decomposition 98

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

3 Interpolation and Extrapolation

3.0 Introduction 105

3.1 Polynomial Interpolation and Extrapolation 108

3.2 Rational Function Interpolation and Extrapolation 111

3.3 Cubic Spline Interpolation 113

3.4 How to Search an Ordered Table 117

3.5 Coefficients of the Interpolating Polynomial 120

3.6 Interpolation in Two or More Dimensions 123

4 Integration of Functions

4.0 Introduction 129

4.1 Classical Formulas for Equally Spaced Abscissas 130

4.2 Elementary Algorithms 136

4.3 Romberg Integration 140

4.4 Improper Integrals 141

4.5 Gaussian Quadratures and Orthogonal Polynomials 147

4.6 Multidimensional Integrals 161

5 Evaluation of Functions

5.0 Introduction 165

5.1 Series and Their Convergence 165

5.2 Evaluation of Continued Fractions 169

5.3 Polynomials and Rational Functions 173

5.4 Complex Arithmetic 176

5.5 Recurrence Relations and Clenshaw's Recurrence Formula 178

5.6 Quadratic and Cubic Equations 183

5.7 Numerical Derivatives 186

5.8 Chebyshev Approximation 190

5.9 Derivatives or Integrals of a Chebyshev-approximated Function 195

5.10 Polynomial Approximation from Chebyshev Coefficients 197

5.11 Economization of Power Series 198

5.12 Pad\'e Approximants 200

5.13 Rational Chebyshev Approximation 204

5.14 Evaluation of Functions by Path Integration 208

6 Special Functions

6.0 Introduction 212

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

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

6.3 Exponential Integrals 222

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

6.5 Bessel Functions of Integer Order 230

6.6 Modified Bessel Functions of Integer Order 236

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

6.8 Spherical Harmonics 252

6.9 Fresnel Integrals, Cosine and Sine Integrals 255

6.10 Dawson's Integral 259

6.11 Elliptic Integrals and Jacobian Elliptic Functions 261

6.12 Hypergeometric Functions 271

7 Random Numbers

7.0 Introduction 274

7.1 Uniform Deviates 275

7.2 Transformation Method: Exponential and Normal Deviates 287

7.3 Rejection Method: Gamma, Poisson, Binomial Deviates 290

7.4 Generation of Random Bits 296

7.5 Random Sequences Based on Data Encryption 300

7.6 Simple Monte Carlo Integration 304

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

7.8 Adaptive and Recursive Monte Carlo Methods 316

8 Sorting

8.0 Introduction 329

8.1 Straight Insertion and Shell's Method 330

8.2 Quicksort 332

8.3 Heapsort 336

8.4 Indexing and Ranking 338

8.5 Selecting the $M$th Largest 341

8.6 Determination of Equivalence Classes 345

9 Root Finding and Nonlinear Sets of Equations

9.0 Introduction 347

9.1 Bracketing and Bisection 350

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

9.3 Van Wijngaarden--Dekker--Brent Method 359

9.4 Newton-Raphson Method Using Derivative 362

9.5 Roots of Polynomials 369

9.6 Newton-Raphson Method for Nonlinear Systems of Equations 379

9.7 Globally Convergent Methods for Nonlinear Systems of Equations 383

10 Minimization or Maximization of Functions

10.0 Introduction 394

10.1 Golden Section Search in One Dimension 397

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

10.3 One-Dimensional Search with First Derivatives 305

10.4 Downhill Simplex Method in Multidimensions 408

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

10.6 Conjugate Gradient Methods in Multidimensions 420

10.7 Variable Metric Methods in Multidimensions 425

10.8 Linear Programming and the Simplex Method 430

10.9 Simulated Annealing Methods 444

11 Eigensystems

11.0 Introduction 456

11.1 Jacobi Transformations of a Symmetric Matrix 463

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

11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 475

11.4 Hermitian Matrices 481

11.5 Reduction of a General Matrix to Hessenberg Form 482

11.6 The QR Algorithm for Real Hessenberg Matrices 486

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

12 Fast Fourier Transform

12.0 Introduction 496

12.1 Fourier Transform of Discretely Sampled Data 500

12.2 Fast Fourier Transform (FFT) 504

12.3 FFT of Real Functions, Sine and Cosine Transforms 510

12.4 FFT in Two or More Dimensions 521

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

12.6 External Storage or Memory-Local FFTs 532

13 Fourier and Spectral Applications

13.0 Introduction 537

13.1 Convolution and Deconvolution Using the FFT 538

13.2 Correlation and Autocorrelation Using the FFT 545

13.3 Optimal (Wiener) Filtering with the FFT 547

13.4 Power Spectrum Estimation Using the FFT 549

13.5 Digital Filtering in the Time Domain 558

13.6 Linear Prediction and Linear Predictive Coding 564

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

13.8 Spectral Analysis of Unevenly Sampled Data 575

13.9 Computing Fourier Integrals Using the FFT 584

13.10 Wavelet Transforms 591

13.11 Numerical Use of the Sampling Theorem 606

14 Statistical Description of Data

14.0 Introduction 609

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

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

14.3 Are Two Distributions Different? 620

14.4 Contingency Table Analysis of Two Distributions 628

14.5 Linear Correlation 636

14.6 Nonparametric or Rank Correlation 639

14.7 Do Two-Dimensional Distributions Differ? 645

14.8 Savitzky-Golay Smoothing Filters 650

15 Modeling of Data

15.0 Introduction 656

15.1 Least Squares as a Maximum Likelihood Estimator 657

15.2 Fitting Data to a Straight Line 661

15.3 Straight-Line Data with Errors in Both Coordinates 666

15.4 General Linear Least Squares 671

15.5 Nonlinear Models 681

15.6 Confidence Limits on Estimated Model Parameters 689

15.7 Robust Estimation 699

16 Integration of Ordinary Differential Equations

16.0 Introduction 707

16.1 Runge-Kutta Method 710

16.2 Adaptive Stepsize Control for Runge-Kutta 714

16.3 Modified Midpoint Method 722

16.4 Richardson Extrapolation and the Bulirsch-Stoer Method 724

16.5 Second-Order Conservative Equations 732

16.6 Stiff Sets of Equations 734

16.7 Multistep, Multivalue, and Predictor-Corrector Methods 747

17 Two Point Boundary Value Problems

17.0 Introduction 753

17.1 The Shooting Method 757

17.2 Shooting to a Fitting Point 760

17.3 Relaxation Methods 762

17.4 A Worked Example: Spheroidal Harmonics 772

17.5 Automated Allocation of Mesh Points 783

17.6 Handling Internal Boundary Conditions or Singular Points 784

18 Integral Equations and Inverse Theory

18.0 Introduction 788

18.1 Fredholm Equations of the Second Kind 791

18.2 Volterra Equations 794

18.3 Integral Equations with Singular Kernels 797

18.4 Inverse Problems and the Use of A Priori Information 804

18.5 Linear Regularization Methods 808

18.6 Backus-Gilbert Method 815

18.7 Maximum Entropy Image Restoration 818

19 Partial Differential Equations

19.0 Introduction 827

19.1 Flux-Conservative Initial Value Problems 834

19.2 Diffusive Initial Value Problems 847

19.3 Initial Value Problems in Multidimensions 853

19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 857

19.5 Relaxation Methods for Boundary Value Problems 863

19.6 Multigrid Methods for Boundary Value Problems 871

20 Less-Numerical Algorithms

20.0 Introduction 889

20.1 Diagnosing Machine Parameters 889

20.2 Gray Codes 894

20.3 Cyclic Redundancy and Other Checksums 896

20.4 Huffman Coding and Compression of Data 903

20.5 Arithmetic Coding 910

20.6 Arithmetic at Arbitrary Precision 915

References and Program Dependencies 926

General Index 965