Numerical Recipes 3rd Edition: The Art of Scientific ComputingPDF电子书下载

1 Preliminaries 1

1.0 Introduction 1

1.1 Error，Accuracy，and Stability 8

1.2 C Family Syntax 12

1.3 Objects，Classes，and Inheritance 17

1.4 Vector and Matrix Objects 24

1.5 Some Further Conventions and Capabilities 30

2 Solution of Linear Algebraic Equations 37

2.0 Introduction 37

2.1 Gauss-Jordan Elimination 41

2.2 Gaussian Elimination with Backsubstitution 46

2.3 LU Decomposition and Its Applications 48

2.4 Tridiagonal and Band-Diagonal Systems of Equations 56

2.5 Iterative Improvement of a Solution to Linear Equations 61

2.6 Singular Value Decomposition 65

2.7 Sparse Linear Systems 75

2.8 Vandermonde Matrices and Toeplitz Matrices 93

2.9 Cholesky Decomposition 100

2.10 QR Decomposition 102

2.11 Is Matrix Inversion an N3 Process？ 106

3 Interpolation and Extrapolation 110

3.0 Introduction 110

3.1 Preliminaries：Searching an Ordered Table 114

3.2 Polynomial Interpolation and Extrapolation 118

3.3 Cubic Spline Interpolation 120

3.4 Rational Function Interpolation and Extrapolation 124

3.5 Coefficients of the Interpolating Polynomial 129

3.6 Interpolation on a Grid in Multidimensions 132

3.7 Interpolation on Scattered Data in Multidimensions 139

3.8 Laplace Interpolation 150

4 Integration of Functions 155

4.0 Introduction 155

4.1 Classical Formulas for Equally Spaced Abscissas 156

4.2 Elementary Algorithms 162

4.3 Romberg Integration 166

4.4 Improper Integrals 167

4.5 Quadrature by Variable Transformation 172

4.6 Gaussian Quadratures and Orthogonal Polynomials 179

4.7 Adaptive Quadrature 194

4.8 Multidimensional Integrals 196

5 Evaluation of Functions 201

5.0 Introduction 201

5.1 Polynomials and Rational Functions 201

5.2 Evaluation of Continued Fractions 206

5.3 Series and Their Convergence 209

5.4 Recurrence Relations and Clenshaw’s Recurrence Formula 219

5.5 Complex Arithmetic 225

5.6 Quadratic and Cubic Equations 227

5.7 Numerical Derivatives 229

5.8 Chebyshev Approximation 233

5.9 Derivatives or Integrals of a Chebyshev-Approximated Function 240

5.10 Polynomial Approximation from Chebyshev Coefficients 241

5.11 Economization of Power Series 243

5.12 Pade Approximants 245

5.13 Rational Chebyshev Approximation 247

5.14 Evaluation of Functions by Path Integration 251

6 Special Functions 255

6.0 Introduction 255

6.1 Gamma Function，Beta Function，Factorials，Binomial Coefficients 256

6.2 Incomplete Gamma Function and Error Function 259

6.3 Exponential Integrals 266

6.4 Incomplete Beta Function 270

6.5 Bessel Functions of Integer Order 274

6.6 Bessel Functions of Fractional Order，Airy Functions，Spherical Bessel Functions 283

6.7 Spherical Harmonics 292

6.8 Fresnel Integrals，Cosine and Sine Integrals 297

6.9 Dawson’s Integral 302

6.10 Generalized Fermi-Dirac Integrals 304

6.11 Inverse of the Function x log（x） 307

6.12 Elliptic Integrals and Jacobian Elliptic Functions 309

6.13 Hypergeometric Functions 318

6.14 Statistical Functions 320

7 Random Numbers 340

7.0 Introduction 340

7.1 Uniform Deviates 341

7.2 Completely Hashing a Large Array 358

7.3 Deviates from Other Distributions 361

7.4 Multivariate Normal Deviates 378

7.5 Linear Feedback Shift Registers 380

7.6 Hash Tables and Hash Memories 386

7.7 Simple Monte Carlo Integration 397

7.8 Quasi- （that is，Sub-） Random Sequences 403

7.9 Adaptive and Recursive Monte Carlo Methods 410

8 Sorting and Selection 419

8.0 Introduction 419

8.1 Straight Insertion and Shell’s Method 420

8.2 Quicksort 423

8.3 Heapsort 426

8.4 Indexing and Ranking 428

8.5 Selecting the Mth Largest 431

8.6 Determination of Equivalence Classes 439

9 Root Finding and Nonlinear Sets of Equations 442

9.0 Introduction 442

9.1 Bracketing and Bisection 445

9.2 Secant Method，False Position Method，and Ridders’ Method 449

9.3 Van Wijngaarden-Dekker-Brent Method 454

9.4 Newton-Raphson Method Using Derivative 456

9.5 Roots of Polynomials 463

9.6 Newton-Raphson Method for Nonlinear Systems of Equations 473

9.7 Globally Convergent Methods for Nonlinear Systems of Equations 477

10 Minimization or Maximization of Functions 487

10.0 Introduction 487

10.1 Initially Bracketing a Minimum 490

10.2 Golden Section Search in One Dimension 492

10.3 Parabolic Interpolation and Brent’s Method in One Dimension 496

10.4 One-Dimensional Search with First Derivatives 499

10.5 Downhill Simplex Method in Multidimensions 502

10.6 Line Methods in Multidimensions 507

10.7 Direction Set （Powell’s） Methods in Multidimensions 509

10.8 Conjugate Gradient Methods in Multidimensions 515

10.9 Quasi-Newton or Variable Metric Methods in Multidimensions 521

10.10 Linear Programming：The Simplex Method 526

10.11 Linear Programming：Interior-Point Methods 537

10.12 Simulated Annealing Methods 549

10.13 Dynamic Programming 555

11 Eigensystems 563

11.0 Introduction 563

11.1 Jacobi Transformations of a Symmetric Matrix 570

11.2 Real Symmetric Matrices 576

11.3 Reduction of a Symmetric Matrix to Tridiagonal Form：Givens and Householder Reductions 578

11.4 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 583

11.5 Hermitian Matrices 590

11.6 Real Nonsymmetric Matrices 590

11.7 The QR Algorithm for Real Hessenberg Matrices 596

11.8 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 597

12 Fast Fourier Transform 600

12.0 Introduction 600

12.1 Fourier Transform of Discretely Sampled Data 605

12.2 Fast Fourier Transform （FFT） 608

12.3 FFT of Real Functions 617

12.4 Fast Sine and Cosine Transforms 620

12.5 FFT in Two or More Dimensions 627

12.6 Fourier Transforms of Real Data in Two and Three Dimensions 631

12.7 External Storage or Memory-Local FFTs 637

13 Fourier and Spectral Applications 640

13.0 Introduction 640

13.1 Convolution and Deconvolution Using the FFT 641

13.2 Correlation and Autocorrelation Using the FFT 648

13.3 Optimal （Wiener） Filtering with the FFT 649

13.4 Power Spectrum Estimation Using the FFT 652

13.5 Digital Filtering in the Time Domain 667

13.6 Linear Prediction and Linear Predictive Coding 673

13.7 Power Spectrum Estimation by the Maximum Entropy （All-Poles） Method 681

13.8 Spectral Analysis of Unevenly Sampled Data 685

13.9 Computing Fourier Integrals Using the FFT 692

13.10 Wavelet Transforms 699

13.11 Numerical Use of the Sampling Theorem 717

14 Statistical Description of Data 720

14.0 Introduction 720

14.1 Moments of a Distribution：Mean，Variance，Skewness，and So Forth 721

14.2 Do Two Distributions Have the Same Means or Variances？ 726

14.3 Are Two Distributions Different？ 730

14.4 Contingency Table Analysis of Two Distributions 741

14.5 Linear Correlation 745

14.6 Nonparametric or Rank Correlation 748

14.7 Information-Theoretic Properties of Distributions 754

14.8 Do Two-Dimensional Distributions Differ？ 762

14.9 Savitzky-Golay Smoothing Filters 766

15 Modeling of Data 773

15.0 Introduction 773

15.1 Least Squares as a Maximum Likelihood Estimator 776

15.2 Fitting Data to a Straight Line 780

15.3 Straight-Line Data with Errors in Both Coordinates 785

15.4 General Linear Least Squares 788

15.5 Nonlinear Models 799

15.6 Confidence Limits on Estimated Model Parameters 807

15.7 Robust Estimation 818

15.8 Markov Chain Monte Carlo 824

15.9 Gaussian Process Regression 836

16 Classification and Inference 840

16.0 Introduction 840

16.1 Gaussian Mixture Models and k-Means Clustering 842

16.2 Viterbi Decoding 850

16.3 Markov Models and Hidden Markov Modeling 856

16.4 Hierarchical Clustering by Phylogenetic Trees 868

16.5 Support Vector Machines 883

17 Integration of Ordinary Differential Equations 899

17.0 Introduction 899

17.1 Runge-Kutta Method 907

17.2 Adaptive Stepsize Control for Runge-Kutta 910

17.3 Richardson Extrapolation and the Bulirsch-Stoer Method 921

17.4 Second-Order Conservative Equations 928

17.5 Stiff Sets of Equations 931

17.6 Multistep，Multivalue，and Predictor-Corrector Methods 942

17.7 Stochastic Simulation of Chemical Reaction Networks 946

18 Two-Point Boundary Value Problems 955

18.0 Introduction 955

18.1 The Shooting Method 959

18.2 Shooting to a Fitting Point 962

18.3 Relaxation Methods 964

18.4 A Worked Example：Spheroidal Harmonics 971

18.5 Automated Allocation of Mesh Points 981

18.6 Handling Internal Boundary Conditions or Singular Points 983

19 Integral Equations and Inverse Theory 986

19.0 Introduction 986

19.1 Fredholm Equations of the Second Kind 989

19.2 Volterra Equations 992

19.3 Integral Equations with Singular Kernels 995

19.4 Inverse Problems and the Use of A Priori Information 1001

19.5 Linear Regularization Methods 1006

19.6 Backus-Gilbert Method 1014

19.7 Maximum Entropy Image Restoration 1016

20 Partial Differential Equations 1024

20.0 Introduction 1024

20.1 Flux-Conservative Initial Value Problems 1031

20.2 Diffusive Initial Value Problems 1043

20.3 Initial Value Problems in Multidimensions 1049

20.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 1053

20.5 Relaxation Methods for Boundary Value Problems 1059

20.6 Multigrid Methods for Boundary Value Problems 1066

20.7 Spectral Methods 1083

21 Computational Geometry 1097

21.0 Introduction 1097

21.1 Points and Boxes 1099

21.2 KD Trees and Nearest-Neighbor Finding 1101

21.3 Triangles in Two and Three Dimensions 1111

21.4 Lines，Line Segments，and Polygons 1117

21.5 Spheres and Rotations 1128

21.6 Triangulation and Delaunay Triangulation 1131

21.7 Applications of Delaunay Triangulation 1141

21.8 Quadtrees and Octrees：Storing Geometrical Objects 1149

22 Less-Numerical Algorithms 1160

22.0 Introduction 1160

22.1 Plotting Simple Graphs 1160

22.2 Diagnosing Machine Parameters 1163

22.3 Gray Codes 1166

22.4 Cyclic Redundancy and Other Checksums 1168

22.5 Huffman Coding and Compression of Data 1175

22.6 Arithmetic Coding 1181

22.7 Arithmetic at Arbitrary Precision 1185

Index 1195