Contents of Numerical Recipes

(Second Edition in C or Fortran)

(Page numbers may vary slightly between the two 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

  • 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 22

  • 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 99

  • 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 123

  • 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 159

  • 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 205

  • 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 266

  • 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 320

  • 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 340

  • 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 387

  • 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 449

  • 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 490

  • 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 530

  • 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 603

  • 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 650

  • 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 701

  • 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 745

  • 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 779

  • 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 818

  • 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 881

  • 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