Preface to the Third Edition (2007) ............................ xi
Preface to the Second Edition (1992) .......................... xiv
Preface to the First Edition (1985) .......................... xvii
License and Legal Information ................................. xix
1 Preliminaries ................................................ 1
1.0 Introduction ............................................ 1
1.1 Error, Accuracy, and Stability .......................... 8
1.2 С 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 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
|
