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