Numerical Recipes

  • 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