This is the greatly revised and greatly expanded Second Edition of the hugely popular Numerical Recipes: The Art of Scientific Computing. The product of a unique collaboration among four leading scientists in academic research and industry Numerical Recipes is a complete text and reference book on scientific computing. In a self-contained manner it proceeds from mathematical and theoretical considerations to actual practical computer routines. With over 100 new routines bringing the total to well over 300, plus upgraded versions of the original routines, this new edition remains the most practical, comprehensive handbook of scientific computing available today. Highlights of the new material include: -A new chapter on integral equations and inverse methods -Multigrid and other methods for solving partial differential equations -Improved random number routines - Wavelet transforms -The statistical bootstrap method -A new chapter on "less-numerical" algorithms including compression coding and arbitrary precision arithmetic. The book retains the informal easy-to-read style that made the first edition so popular, while introducing some more advanced topics. It is an ideal textbook for scientists and engineers and an indispensable reference for anyone who works in scientific computing. The Second Edition is availabe in FORTRAN, the traditional language for numerical calculations and in the increasingly popular C language.
Author(s): William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling
Edition: 2
Publisher: Cambridge University Press
Year: 1992
Language: English
Pages: 933
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
Structures......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
of Equations......Page 71
2.5 Iterative Improvement of a Solution to
Linear Equations......Page 76
2.6 Singular Value Decomposition......Page 80
2.7 Sparse Linear Systems......Page 92
2.8 Vandermonde Matrices and Toeplitz
Matrices......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
Extrapolation......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
Abscissas......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
Polynomials......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
Recurrence 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
Chebyshev-approximated Function......Page 218
5.10 Polynomial Approximation from
Chebyshev 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
Integration......Page 230
6.0 Introduction......Page 234
6.12 Hypergeometric Functions......Page 292
6.11 Elliptic Integrals and Jacobian Elliptic
Functions......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
Functions, 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
Distribution, F-Distribution, Cumulative
Binomial Distribution......Page 248
6.3 Exponential Integrals......Page 244
6.2 Incomplete Gamma Function, Error
Function, Chi-Square Probability Function,
Cumulative Poisson Function......Page 238
6.1 Gamma Function, Beta Function, Factorials,
Binomial Coefficients......Page 235
7.0 Introduction......Page 295
7.8 Adaptive and Recursive Monte Carlo
Methods......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
Encryption......Page 319
7.4 Generation of Random Bits......Page 316
7.3 Rejection Method: Gamma, Poisson,
Binomial Deviates......Page 310
7.2 Transformation Method: Exponential and
Normal 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,
and 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
Systems of Equations......Page 401
9.7 Globally Convergent Methods for Nonlinear
Systems 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
Method in One Dimension......Page 424
10.3 One-Dimensional Search with First
Derivatives......Page 428
10.4 Downhill Simplex Method in
Multidimensions......Page 431
10.5 Direction Set (Powell’s) Methods in
Multidimensions......Page 435
10.6 Conjugate Gradient Methods in
Multidimensions......Page 442
10.7 Variable Metric Methods in
Multidimensions......Page 447
10.8 Linear Programming and the Simplex
Method......Page 452
10.9 Simulated Annealing Methods......Page 465
11.0 Introduction......Page 478
11.1 Jacobi Transformations of a Symmetric
Matrix......Page 485
11.2 Reduction of a Symmetric Matrix
to Tridiagonal Form: Givens and
Householder Reductions......Page 491
11.3 Eigenvalues and Eigenvectors of a
Tridiagonal Matrix......Page 498
11.4 Hermitian Matrices......Page 504
11.5 Reduction of a General Matrix to
Hessenberg Form......Page 505
11.6 The QR Algorithm for Real Hessenberg
Matrices......Page 509
11.7 Improving Eigenvalues and/or Finding
Eigenvectors by Inverse Iteration......Page 516
12.0 Introduction......Page 519
12.1 Fourier Transform of Discretely Sampled
Data......Page 523
12.2 Fast Fourier Transform (FFT)......Page 527
12.3 FFT of Real Functions, Sine and Cosine
Transforms......Page 533
12.4 FFT in Two or More Dimensions......Page 544
12.5 Fourier Transforms of Real Data in Two
and 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
the FFT......Page 560
13.2 Correlation and Autocorrelation Using
the 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
Coding......Page 586
13.7 Power Spectrum Estimation by the
Maximum Entropy (All Poles) Method......Page 594
13.8 Spectral Analysis of Unevenly Sampled
Data......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
Means or Variances?......Page 638
14.3 Are Two Distributions Different?......Page 643
14.4 Contingency Table Analysis of Two
Distributions......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
Estimator......Page 680
15.2 Fitting Data to a Straight Line......Page 684
15.3 Straight-Line Data with Errors in Both
Coordinates......Page 689
15.4 General Linear Least Squares......Page 694
15.5 Nonlinear Models......Page 704
15.6 Confidence Limits on Estimated Model
Parameters......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
Bulirsch-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
Predictor-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
or 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
Information......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
Boundary Value Problems......Page 877
19.5 Relaxation Methods for Boundary Value
Problems......Page 883
19.6 Multigrid Methods for Boundary Value
Problems......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
by Michael Metcalf......Page 1012
II. License Information......Page 1019
21.0 Introduction......Page 1023
21.1 Quick Start: Using the Fortran 90
Numerical 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
and Intrinsics......Page 1052
22.2 Linear Recurrence and Related
Calculations......Page 1059
22.3 Parallel Synthetic Division and Related
Algorithms......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
Linear Algebraic
Equations......Page 1102
B3. Interpolation and
Extrapolation......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
Nonlinear Sets of Equations......Page 1270
B10. Minimization or
Maximization of Functions......Page 1289
B11. Eigensystems......Page 1313
B12. Fast Fourier Transform......Page 1323
B13. Fourier and Spectral
Applications......Page 1341
B14. Statistical
Description of Data......Page 1357
B15. Modeling of Data......Page 1373
B16. Integration of Ordinary
Differential Equations......Page 1385
B17. Two Point Boundary
Value Problems......Page 1402
B18. Integral Equations
and Inverse
Theory......Page 1413
B19. Partial Differential
Equations......Page 1420
B20. Less-Numerical
Algorithms......Page 1431
II. References......Page 1447
C1. Listing of Utility Modules
(nrtype and nrutil)......Page 1449
C2. Alphabetical Listing of
Explicit Interfaces......Page 1472
C3. Index of Programs and
Dependencies......Page 1522
II.
General Index to Volumes 1 and 2......Page 1535
