Numerical Recipes in Fortran 77

I. Contents......Page 3
I. Plan of the Two-Volume Edition......Page 11
I. Preface to the Second Edition......Page 13
I. Preface to the First Edition......Page 16
I. License Information......Page 18
I. Computer Programs by Chapter and Section......Page 22
1.0 Introduction......Page 30
1.1 Program Organization and Control\rStructures......Page 34
1.2 Error, Accuracy, and Stability......Page 47
2.0 Introduction......Page 51
2.1 Gauss-Jordan Elimination......Page 56
2.2 Gaussian Elimination with Backsubstitution......Page 62
2.3 LU Decomposition and Its Applications......Page 63
2.4 Tridiagonal and Band Diagonal Systems\rof Equations......Page 71
2.5 Iterative Improvement of a Solution to\rLinear Equations......Page 76
2.6 Singular Value Decomposition......Page 80
2.7 Sparse Linear Systems......Page 92
2.8 Vandermonde Matrices and Toeplitz\rMatrices......Page 111
2.9 Cholesky Decomposition......Page 118
2.10 QR Decomposition......Page 120
2.11 Is Matrix Inversion an N3 Process?......Page 124
3.0 Introduction......Page 128
3.1 Polynomial Interpolation and Extrapolation......Page 131
3.2 Rational Function Interpolation and\rExtrapolation......Page 133
3.3 Cubic Spline Interpolation......Page 136
3.4 How to Search an Ordered Table......Page 139
3.5 Coefficients of the Interpolating Polynomial......Page 142
3.6 Interpolation in Two or More Dimensions......Page 145
4.0 Introduction......Page 152
4.1 Classical Formulas for Equally Spaced\rAbscissas......Page 153
4.2 Elementary Algorithms......Page 159
4.3 Romberg Integration......Page 163
4.4 Improper Integrals......Page 164
4.5 Gaussian Quadratures and Orthogonal\rPolynomials......Page 169
4.6 Multidimensional Integrals......Page 184
5.1 Series and Their Convergence......Page 188
5.2 Evaluation of Continued Fractions......Page 192
5.3 Polynomials and Rational Functions......Page 196
5.4 Complex Arithmetic......Page 200
5.5 Recurrence Relations and Clenshaw’s\rRecurrence Formula......Page 201
5.6 Quadratic and Cubic Equations......Page 207
5.7 Numerical Derivatives......Page 209
5.8 Chebyshev Approximation......Page 213
5.9 Derivatives or Integrals of a\rChebyshev-approximated Function......Page 218
5.10 Polynomial Approximation from\rChebyshev Coefficients......Page 220
5.11 Economization of Power Series......Page 221
5.12 Padé Approximants......Page 223
5.13 Rational Chebyshev Approximation......Page 226
5.14 Evaluation of Functions by Path\rIntegration......Page 230
6.0 Introduction......Page 234
6.12 Hypergeometric Functions......Page 292
6.11 Elliptic Integrals and Jacobian Elliptic\rFunctions......Page 283
6.10 Dawson’s Integral......Page 281
6.9 Fresnel Integrals, Cosine and Sine Integrals......Page 277
6.8 Spherical Harmonics......Page 275
6.7 Bessel Functions of Fractional Order, Airy\rFunctions, Spherical Bessel Functions......Page 263
6.6 Modified Bessel Functions of Integer Order......Page 258
6.5 Bessel Functions of Integer Order......Page 252
6.4 Incomplete Beta Function, Student’s\rDistribution, F-Distribution, Cumulative\rBinomial Distribution......Page 248
6.3 Exponential Integrals......Page 244
6.2 Incomplete Gamma Function, Error\rFunction, Chi-Square Probability Function,\rCumulative Poisson Function......Page 238
6.1 Gamma Function, Beta Function, Factorials, \rBinomial Coefficients......Page 235
7.0 Introduction......Page 295
7.8 Adaptive and Recursive Monte Carlo\rMethods......Page 335
7.7 Quasi- (that is, Sub-) Random Sequences......Page 328
7.6 Simple Monte Carlo Integration......Page 324
7.5 Random Sequences Based on Data\rEncryption......Page 319
7.4 Generation of Random Bits......Page 316
7.3 Rejection Method: Gamma, Poisson,\rBinomial Deviates......Page 310
7.2 Transformation Method: Exponential and\rNormal Deviates......Page 306
7.1 Uniform Deviates......Page 296
8.0 Introduction......Page 349
8.1 Straight Insertion and Shell’s Method......Page 350
8.2 Quicksort......Page 352
8.3 Heapsort......Page 356
8.4 Indexing and Ranking......Page 358
8.5 Selecting the Mth Largest......Page 362
8.6 Determination of Equivalence Classes......Page 366
9.0 Introduction......Page 369
9.1 Bracketing and Bisection......Page 372
9.2 Secant Method, False Position Method,\rand Ridders’ Method......Page 376
9.3 Van Wijngaarden–Dekker–Brent Method......Page 381
9.4 Newton-Raphson Method Using Derivative......Page 384
9.5 Roots of Polynomials......Page 391
9.6 Newton-Raphson Method for Nonlinear\rSystems of Equations......Page 401
9.7 Globally Convergent Methods for Nonlinear\rSystems of Equations......Page 405
10.0 Introduction......Page 416
10.1 Golden Section Search in One Dimension......Page 419
10.2 Parabolic Interpolation and Brent’s\rMethod in One Dimension......Page 424
10.3 One-Dimensional Search with First\rDerivatives......Page 428
10.4 Downhill Simplex Method in\rMultidimensions......Page 431
10.5 Direction Set (Powell’s) Methods in\rMultidimensions......Page 435
10.6 Conjugate Gradient Methods in\rMultidimensions......Page 442
10.7 Variable Metric Methods in\rMultidimensions......Page 447
10.8 Linear Programming and the Simplex\rMethod......Page 452
10.9 Simulated Annealing Methods......Page 465
11.0 Introduction......Page 478
11.1 Jacobi Transformations of a Symmetric\rMatrix......Page 485
11.2 Reduction of a Symmetric Matrix\rto Tridiagonal Form: Givens and\rHouseholder Reductions......Page 491
11.3 Eigenvalues and Eigenvectors of a\rTridiagonal Matrix......Page 498
11.4 Hermitian Matrices......Page 504
11.5 Reduction of a General Matrix to\rHessenberg Form......Page 505
11.6 The QR Algorithm for Real Hessenberg\rMatrices......Page 509
11.7 Improving Eigenvalues and/or Finding\rEigenvectors by Inverse Iteration......Page 516
12.0 Introduction......Page 519
12.1 Fourier Transform of Discretely Sampled\rData......Page 523
12.2 Fast Fourier Transform (FFT)......Page 527
12.3 FFT of Real Functions, Sine and Cosine\rTransforms......Page 533
12.4 FFT in Two or More Dimensions......Page 544
12.5 Fourier Transforms of Real Data in Two\rand Three Dimensions......Page 548
12.6 External Storage or Memory-Local FFTs......Page 554
13.0 Introduction......Page 559
13.1 Convolution and Deconvolution Using\rthe FFT......Page 560
13.2 Correlation and Autocorrelation Using\rthe FFT......Page 567
13.3 Optimal (Wiener) Filtering with the FFT......Page 568
13.4 Power Spectrum Estimation Using the FFT......Page 571
13.5 Digital Filtering in the Time Domain......Page 580
13.6 Linear Prediction and Linear Predictive\rCoding......Page 586
13.7 Power Spectrum Estimation by the\rMaximum Entropy (All Poles) Method......Page 594
13.8 Spectral Analysis of Unevenly Sampled\rData......Page 598
13.9 Computing Fourier Integrals Using the FFT......Page 606
13.10 Wavelet Transforms......Page 613
13.11 Numerical Use of the Sampling Theorem......Page 629
14.0 Introduction......Page 632
14.1 Moments of a Distribution: Mean, Variance, Skewness, and So Forth......Page 633
14.2 Do Two Distributions Have the Same\rMeans or Variances?......Page 638
14.3 Are Two Distributions Different?......Page 643
14.4 Contingency Table Analysis of Two\rDistributions......Page 651
14.5 Linear Correlation......Page 659
14.6 Nonparametric or Rank Correlation......Page 662
14.7 Do Two-Dimensional Distributions Differ?......Page 669
14.8 Savitzky-Golay Smoothing Filters......Page 673
15.0 Introduction......Page 679
15.1 Least Squares as a Maximum Likelihood\rEstimator......Page 680
15.2 Fitting Data to a Straight Line......Page 684
15.3 Straight-Line Data with Errors in Both\rCoordinates......Page 689
15.4 General Linear Least Squares......Page 694
15.5 Nonlinear Models......Page 704
15.6 Confidence Limits on Estimated Model\rParameters......Page 713
15.7 Robust Estimation......Page 723
16.0 Introduction......Page 730
16.1 Runge-Kutta Method......Page 733
16.2 Adaptive Stepsize Control for Runge-Kutta......Page 737
16.3 Modified Midpoint Method......Page 745
16.4 Richardson Extrapolation and the\rBulirsch-Stoer Method......Page 747
16.5 Second-Order Conservative Equations......Page 755
16.6 Stiff Sets of Equations......Page 756
16.7 Multistep, Multivalue, and\rPredictor-Corrector Methods......Page 769
17.0 Introduction......Page 774
17.1 The Shooting Method......Page 778
17.2 Shooting to a Fitting Point......Page 780
17.3 Relaxation Methods......Page 782
17.4 AWorked Example: Spheroidal Harmonics......Page 793
17.5 Automated Allocation of Mesh Points......Page 803
17.6 Handling Internal Boundary Conditions\ror Singular Points......Page 804
18.0 Introduction......Page 808
18.1 Fredholm Equations of the Second Kind......Page 811
18.2 Volterra Equations......Page 815
18.3 Integral Equations with Singular Kernels......Page 817
18.4 Inverse Problems and the Use of A Priori\rInformation......Page 824
18.5 Linear Regularization Methods......Page 828
18.6 Backus-Gilbert Method......Page 835
18.7 Maximum Entropy Image Restoration......Page 838
19.0 Introduction......Page 847
19.1 Flux-Conservative Initial Value Problems......Page 854
19.2 Diffusive Initial Value Problems......Page 867
19.3 Initial Value Problems in Multidimensions......Page 873
19.4 Fourier and Cyclic Reduction Methods for\rBoundary Value Problems......Page 877
19.5 Relaxation Methods for Boundary Value\rProblems......Page 883
19.6 Multigrid Methods for Boundary Value\rProblems......Page 891
20.1 Diagnosing Machine Parameters......Page 910
20.2 Gray Codes......Page 915
20.3 Cyclic Redundancy and Other Checksums......Page 917
20.4 Huffman Coding and Compression of Data......Page 925
20.5 Arithmetic Coding......Page 931
20.6 Arithmetic at Arbitrary Precision......Page 935
I. References......Page 945
I. Index of Programs and Dependencies......Page 949
I. General Index to Volumes 1 and 2......Page 963
II. Contents......Page 1007
II. Preface to Volume 2......Page 1010
II. Foreword\rby Michael Metcalf......Page 1012
II. License Information......Page 1019
21.0 Introduction......Page 1023
21.1 Quick Start: Using the Fortran 90\rNumerical Recipes Routines......Page 1024
21.2 Fortran 90 Language Concepts......Page 1025
21.3 More on Arrays and Array Sections......Page 1029
21.4 Fortran 90 Intrinsic Procedures......Page 1033
21.5 Advanced Fortran 90 Topics......Page 1041
21.6 And Coming Soon: Fortran 95......Page 1047
22.0 Why Think Parallel?......Page 1050
22.1 Fortran 90 Data Parallelism: Arrays\rand Intrinsics......Page 1052
22.2 Linear Recurrence and Related\rCalculations......Page 1059
22.3 Parallel Synthetic Division and Related\rAlgorithms......Page 1065
22.4 Fast Fourier Transforms......Page 1069
22.5 Missing Language Features......Page 1071
23.0 Introduction and Summary Listing......Page 1075
23.1 Routines That Move Data......Page 1078
23.2 Routines Returning a Location......Page 1080
23.3 Argument Checking and Error Handling......Page 1082
23.4 Routines for Polynomials and Recurrences......Page 1084
23.5 Routines for Outer Operations on Vectors......Page 1088
23.6 Routines for Scatter with Combine......Page 1090
23.7 Routines for Skew Operations on Matrices......Page 1092
23.8 Other Routine(s)......Page 1095
II. Fortran 90 Code Chapters B1–B20......Page 1097
B1. Preliminaries......Page 1098
B2. Solution of\rLinear Algebraic\rEquations......Page 1102
B3. Interpolation and\rExtrapolation......Page 1131
B4. Integration of Functions......Page 1140
B5. Evaluation of Functions......Page 1158
B6. Special Functions......Page 1171
B7. Random Numbers......Page 1229
B8. Sorting......Page 1255
B9. Root Finding and\rNonlinear Sets of Equations......Page 1270
B10. Minimization or\rMaximization of Functions......Page 1289
B11. Eigensystems......Page 1313
B12. Fast Fourier Transform......Page 1323
B13. Fourier and Spectral\rApplications......Page 1341
B14. Statistical\rDescription of Data......Page 1357
B15. Modeling of Data......Page 1373
B16. Integration of Ordinary\rDifferential Equations......Page 1385
B17. Two Point Boundary\rValue Problems......Page 1402
B18. Integral Equations\rand Inverse\rTheory......Page 1413
B19. Partial Differential\rEquations......Page 1420
B20. Less-Numerical\rAlgorithms......Page 1431
II. References......Page 1447
C1. Listing of Utility Modules\r(nrtype and nrutil)......Page 1449
C2. Alphabetical Listing of\rExplicit Interfaces......Page 1472
C3. Index of Programs and\rDependencies......Page 1522
II. \rGeneral Index to Volumes 1 and 2......Page 1535