Numerical recipes in C : the art of scientific computing
Press, William H.
Numerical recipes in C : the art of scientific computing - Cambridge Cambridge Uni. Press 1988 - 735p.
CONTENS
Preface to the C Edition XI
Preface XIll
List of Computer Programs xvii
1 PRELIMINARIES
0 Introduction 1
1 Program Organization and Control Structures 4
2 Some C Conventions for Scientific Computing 14
3 Error, Accuracy, and Stability 24
2 SOLUTION OF LINEAR ALGEBRAIC EQUATIONS 28
0 Introduction 28
1 Gauss-Jordan Elimination 32
2 Gaussian Elimination with Backsubstitution 37
3 LU Decomposition 39
4 Inverse of a Matrix 45
5 Determinant of a Matrix 46
6 Tridiagonal Systems of Equations 47
7 Iterative Improvement of a Solution to Linear Equations 49
8 Vanderrnonde Matrices and Toeplitz Matrices 51
9 Singula)- Value Decomposition 60
10 Sparse Linear Systems 72
11 Is Matrix Inversion an TV3 Process? 81
3 INTERPOLATION AND EXTRAPOLATION 85
0 Introduction 85
1 Polynomial Interpolation and Extrapolation 88
2 Rational Function Interpolation and Extrapolation 91
3 Cubic Spline Interpolation 94
4 How to Search an Ordered Table 98
5 Coefficients of the Interpolating Polynomial 101
6 Interpolation in Two or More Dimensions 104
INTEGRATION OF FUNCTIONS 1ll
0 Introduction 111
1 Classical Formulas for Equally-Spaced Abscissas 112
2 Elementary Algorithms 119
3 Romberg Integration 123
4 Improper Integrals 125
5 Gaussian Quadratures 131
6 Multidimensional Integrals 137
5 EVALUATION OF FUNCTIONS 142
0 Introduction 142
1 Series and Their Convergence 143
2 Evaluation of Continued Fractions 146
3 Polynomials and Rational Functions 148
4 Recurrence Relations and Clenshaw's Recurrence Formula 15
5 Quadratic and Cubic Equations 156
6 Chebyshev Approximation 158
7 Derivatives or Integrals of a Chebyshev-approximated Function (
8 Polynomial Approximation from Chebyshev Coefficients 164
6 SPECIAL FUNCTIONS 166
0 Introduction 166
1 Gamma Function, Beta Function, Factorials, and Binomial 1 Coefficients 167
2 Incomplete Gamma Function, Error Function, Chi-Square Probability Function, Cumulative Poisson Distribution 171
3 Incomplete Beta Function, Student's Distribution, ! F-Distribution, Cumulative Binomial Distribution 178
4 Bessel Functions of Integer Order 182 I
5 Modified Bessel Functions of Integer Order 189
6 Spherical Harmonics 194
7 Elliptic Integrals and Jacobian Elliptic Functions 197
7 RANDOM NUMBERS 204
0 Introduction 204
1 Uniform Deviates 205
2 Transformation Method: Exponential and Normal Deviates 214
3 Rejection Method: Gamma, Poisson, Binomial Deviates 218
4 Generation of Random Bits 224
5 The Data Encryption Standard 228
6 Monte Carlo Integration 237
8 SORTING 242
0 Introduction 242
1 Straight Insertion and Shell's Method 243
2 Heapsort 245
3 Indexing and Ranking 248
4 Quicksort 251
5 Determination of Equivalence Classes 252
9 ROOT FINDING AND NONLINEAR SETS OF
EQUATIONS 255
0 Introduction 255
1 Bracketing and Bisection 258
2 Secant Method and False Position Method 263
3 Van Wijngaarden- Dekker-Brent Method 267
4 Newton-Raphson Method Using Derivative 269
5 Roots of Polynomials 275
6 Newton-Raphson Method for Nonlinear Systems of Equations 286
10 MINIMIZATION OR MAXIMIZATION OF
FUNCTIONS 290
0 Introduction 290
1 Golden Section Search in One Dimension 293
2 Parabolic Interpolation and Brent's Method in One Dimension 299
3 One-Dimensional Search with First Derivatives 302
4 Downhill Simplex Method in Multidimensions 305
5 Direction Set (Powell's) Methods in Multidimensions 309
6 Conjugate Gradient Methods in Multidimensions 317
7 Variable Metric Methods in Multidimensions 324
8 Linear Programming and the Simplex Method 329
9 Combinatorial Minimization: Method of Simulated Annealing 343
11 EIGENSYSTEMS 353
0 Introduction 353
1 Jacobi Transformations of a Symmetric Matrix 360
2 Reduction of a Symmetric Matrix to Tridiagonal Form: Givens and Householder Reductions 367
3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 374
4 Hermitian Matrices 381
5 Reduction of a General Matrix to Hessenberg Form 382
6 The QR Algorithm for Real Hessenberg Matrices 387
7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 394
12 FOURIER TRANSFORM SPECTRAL METHODS 398
0 Introduction 398
1 Fourier Transform of Discretely Sampled Data 403
2 Fast Fourier Transform (FFT) 407
3 FFT of Real Functions, Sine and Cosine Transforms 414
4 Convolution and Deconvolution Using the FFT 425
5 Correlation and Autocorrelation Using the FFT 432
6 Optimal (Wiener) Filtering with the FFT 434
7 Power Spectrum Estimation Using the FFT 437
8 Power Spectrum Estimation by the Maximum Entropy (All Poles) Method 447
9 Digital Filtering in the Time Domain 452
10 Linear Prediction and Linear Predictive Coding 461
FFT in Two or More Dimensions 467
13 STATISTICAL DESCRIPTION OF DATA 471
10 Introduction 471
11 of a Distribution: Mean, Variance, Skewness, and so forth 472
12 Efficient Search for the Median 476
13 Estimation of the Mode for Continuous Data 479
14 Do Two Distributions Have the Same Means or Variances?
15 Are Two Distributions Different? 487
16 Contingency Table Analysis of Two Distributions 494
17 Linear Correlation 503
18 Nonparametric or Rank Correlation 507
19 Smoothing of Data 514
14 MODELING OF DATA 517
0 Introduction 517
1 Least Squares as a Maximum Likelihood Estimator 518
2 Fitting Data to a Straight Line 523
3 General Linear Least Squares 528
4 Nonlinear Models 540
5 Confidence Limits on Estimated Model Parameters 548
6 Robust Estimation 558
15 INTEGRATION OF ORDINARY DIFFERENTIAL
EQUATIONS 566
0 Introduction 566
1 Runge-Kutta Method 569
2 Adaptive Stepsize Control for Runge-Kutta 574
3 Modified Midpoint Method 580
4 Richardson Extrapolation and the Bulirsch-Stoer Method
5 Predictor-Corrector Methods 589
6 Stiff Sets of Equations 592
16 TWO POINT BOUNDARY VALUE PROBLEMS 598
0 Introduction 598
1 The Shooting Method 602
2 Shooting to a Fitting Point 606
3 Relaxation Methods 609
4 A Worked Example: Spheroidal Harmonics 621
5 Automated Allocation of Mesh Points 630
6 Handling Internal Boundary Conditions or Singular Points
17 PARTIAL DIFFERENTIAL EQUATIONS 636
0 Introduction 636
1 Flux-Conservative Initial Value Problems 644
2 Diffusive Initial Value Problems 656
Initial Value Problems in Multidimenviii 663
4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 667
5 Relaxation Methods for Boundary Value Problems 673
6 Operator Splitting; Methods and ADI 681
APPENDIX A: References 689
APPENDIX B: Table of Program Dependencies 694
APPENDIX C: Table of Prototype Declarations 699
APPENDIX D: Utility Routines (nrutil.c) 705
APPENDIX E: Complex Arithmetic (complex.c) 710
Index 713
052135465X
005.133 / PRE
Numerical recipes in C : the art of scientific computing - Cambridge Cambridge Uni. Press 1988 - 735p.
CONTENS
Preface to the C Edition XI
Preface XIll
List of Computer Programs xvii
1 PRELIMINARIES
0 Introduction 1
1 Program Organization and Control Structures 4
2 Some C Conventions for Scientific Computing 14
3 Error, Accuracy, and Stability 24
2 SOLUTION OF LINEAR ALGEBRAIC EQUATIONS 28
0 Introduction 28
1 Gauss-Jordan Elimination 32
2 Gaussian Elimination with Backsubstitution 37
3 LU Decomposition 39
4 Inverse of a Matrix 45
5 Determinant of a Matrix 46
6 Tridiagonal Systems of Equations 47
7 Iterative Improvement of a Solution to Linear Equations 49
8 Vanderrnonde Matrices and Toeplitz Matrices 51
9 Singula)- Value Decomposition 60
10 Sparse Linear Systems 72
11 Is Matrix Inversion an TV3 Process? 81
3 INTERPOLATION AND EXTRAPOLATION 85
0 Introduction 85
1 Polynomial Interpolation and Extrapolation 88
2 Rational Function Interpolation and Extrapolation 91
3 Cubic Spline Interpolation 94
4 How to Search an Ordered Table 98
5 Coefficients of the Interpolating Polynomial 101
6 Interpolation in Two or More Dimensions 104
INTEGRATION OF FUNCTIONS 1ll
0 Introduction 111
1 Classical Formulas for Equally-Spaced Abscissas 112
2 Elementary Algorithms 119
3 Romberg Integration 123
4 Improper Integrals 125
5 Gaussian Quadratures 131
6 Multidimensional Integrals 137
5 EVALUATION OF FUNCTIONS 142
0 Introduction 142
1 Series and Their Convergence 143
2 Evaluation of Continued Fractions 146
3 Polynomials and Rational Functions 148
4 Recurrence Relations and Clenshaw's Recurrence Formula 15
5 Quadratic and Cubic Equations 156
6 Chebyshev Approximation 158
7 Derivatives or Integrals of a Chebyshev-approximated Function (
8 Polynomial Approximation from Chebyshev Coefficients 164
6 SPECIAL FUNCTIONS 166
0 Introduction 166
1 Gamma Function, Beta Function, Factorials, and Binomial 1 Coefficients 167
2 Incomplete Gamma Function, Error Function, Chi-Square Probability Function, Cumulative Poisson Distribution 171
3 Incomplete Beta Function, Student's Distribution, ! F-Distribution, Cumulative Binomial Distribution 178
4 Bessel Functions of Integer Order 182 I
5 Modified Bessel Functions of Integer Order 189
6 Spherical Harmonics 194
7 Elliptic Integrals and Jacobian Elliptic Functions 197
7 RANDOM NUMBERS 204
0 Introduction 204
1 Uniform Deviates 205
2 Transformation Method: Exponential and Normal Deviates 214
3 Rejection Method: Gamma, Poisson, Binomial Deviates 218
4 Generation of Random Bits 224
5 The Data Encryption Standard 228
6 Monte Carlo Integration 237
8 SORTING 242
0 Introduction 242
1 Straight Insertion and Shell's Method 243
2 Heapsort 245
3 Indexing and Ranking 248
4 Quicksort 251
5 Determination of Equivalence Classes 252
9 ROOT FINDING AND NONLINEAR SETS OF
EQUATIONS 255
0 Introduction 255
1 Bracketing and Bisection 258
2 Secant Method and False Position Method 263
3 Van Wijngaarden- Dekker-Brent Method 267
4 Newton-Raphson Method Using Derivative 269
5 Roots of Polynomials 275
6 Newton-Raphson Method for Nonlinear Systems of Equations 286
10 MINIMIZATION OR MAXIMIZATION OF
FUNCTIONS 290
0 Introduction 290
1 Golden Section Search in One Dimension 293
2 Parabolic Interpolation and Brent's Method in One Dimension 299
3 One-Dimensional Search with First Derivatives 302
4 Downhill Simplex Method in Multidimensions 305
5 Direction Set (Powell's) Methods in Multidimensions 309
6 Conjugate Gradient Methods in Multidimensions 317
7 Variable Metric Methods in Multidimensions 324
8 Linear Programming and the Simplex Method 329
9 Combinatorial Minimization: Method of Simulated Annealing 343
11 EIGENSYSTEMS 353
0 Introduction 353
1 Jacobi Transformations of a Symmetric Matrix 360
2 Reduction of a Symmetric Matrix to Tridiagonal Form: Givens and Householder Reductions 367
3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 374
4 Hermitian Matrices 381
5 Reduction of a General Matrix to Hessenberg Form 382
6 The QR Algorithm for Real Hessenberg Matrices 387
7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 394
12 FOURIER TRANSFORM SPECTRAL METHODS 398
0 Introduction 398
1 Fourier Transform of Discretely Sampled Data 403
2 Fast Fourier Transform (FFT) 407
3 FFT of Real Functions, Sine and Cosine Transforms 414
4 Convolution and Deconvolution Using the FFT 425
5 Correlation and Autocorrelation Using the FFT 432
6 Optimal (Wiener) Filtering with the FFT 434
7 Power Spectrum Estimation Using the FFT 437
8 Power Spectrum Estimation by the Maximum Entropy (All Poles) Method 447
9 Digital Filtering in the Time Domain 452
10 Linear Prediction and Linear Predictive Coding 461
FFT in Two or More Dimensions 467
13 STATISTICAL DESCRIPTION OF DATA 471
10 Introduction 471
11 of a Distribution: Mean, Variance, Skewness, and so forth 472
12 Efficient Search for the Median 476
13 Estimation of the Mode for Continuous Data 479
14 Do Two Distributions Have the Same Means or Variances?
15 Are Two Distributions Different? 487
16 Contingency Table Analysis of Two Distributions 494
17 Linear Correlation 503
18 Nonparametric or Rank Correlation 507
19 Smoothing of Data 514
14 MODELING OF DATA 517
0 Introduction 517
1 Least Squares as a Maximum Likelihood Estimator 518
2 Fitting Data to a Straight Line 523
3 General Linear Least Squares 528
4 Nonlinear Models 540
5 Confidence Limits on Estimated Model Parameters 548
6 Robust Estimation 558
15 INTEGRATION OF ORDINARY DIFFERENTIAL
EQUATIONS 566
0 Introduction 566
1 Runge-Kutta Method 569
2 Adaptive Stepsize Control for Runge-Kutta 574
3 Modified Midpoint Method 580
4 Richardson Extrapolation and the Bulirsch-Stoer Method
5 Predictor-Corrector Methods 589
6 Stiff Sets of Equations 592
16 TWO POINT BOUNDARY VALUE PROBLEMS 598
0 Introduction 598
1 The Shooting Method 602
2 Shooting to a Fitting Point 606
3 Relaxation Methods 609
4 A Worked Example: Spheroidal Harmonics 621
5 Automated Allocation of Mesh Points 630
6 Handling Internal Boundary Conditions or Singular Points
17 PARTIAL DIFFERENTIAL EQUATIONS 636
0 Introduction 636
1 Flux-Conservative Initial Value Problems 644
2 Diffusive Initial Value Problems 656
Initial Value Problems in Multidimenviii 663
4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 667
5 Relaxation Methods for Boundary Value Problems 673
6 Operator Splitting; Methods and ADI 681
APPENDIX A: References 689
APPENDIX B: Table of Program Dependencies 694
APPENDIX C: Table of Prototype Declarations 699
APPENDIX D: Utility Routines (nrutil.c) 705
APPENDIX E: Complex Arithmetic (complex.c) 710
Index 713
052135465X
005.133 / PRE