# Numerical Recipes Table of Contents

# Contents of Numerical Recipes

## (Second Edition in C++, C, or Fortran)

(Page numbers may vary slightly among the language versions.)
- Preface to the Second Edition xi
- Preface to the First Edition xiv
- 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 916
- Index of Programs and Dependencies 921
- General Index 935