Numerical Recipes in C: The Art of Scientific Computing

Numerical Recipes in C......Page 1
Title......Page 10
License......Page 23
Computer programs by chapter and section......Page 26
1.0.Introduction......Page 34
1.1.Program organization and control structures......Page 39
1.2.Some C conventions for scientific computing......Page 50
1.3.Error,accuracy,and stability......Page 64
2.0.Introduction......Page 68
2.1.Gauss-Jordan elimination......Page 73
2.2.Gaussian elimination with backsubstitution......Page 79
2.3.LU decomposition and its applications......Page 82
2.4.Tridiagonal and band diagonal systems of equations......Page 90
2.5.Iterative improvement of a solution to linear equations......Page 96
2.6.Singular value decomposition......Page 101
2.7.Sparce linear systems......Page 114
2.8.Vandermonde matrices and Toeplitz matrices......Page 134
2.9.Cholesky decomposition......Page 148
2.10.QR decomposition......Page 151
2.11.Is matrix inversion an N3 process ?......Page 156
3.0.Introduction......Page 159
3.1.Polynomial interpolation and extrapolation......Page 163
3.2.Rational function interpolation and extrapolation......Page 167
3.3.Cubic spline interpolation......Page 170
3.4.How to search an ordered table......Page 175
3.5.Coefficients of the interpolating polynomial......Page 179
3.6.Interpolating in two or more dimensions......Page 183
4.0.Introduction......Page 189
4.1.Classical formulas for equally spaced abscissas......Page 191
4.2.Elementary algorithms......Page 198
4.3.Romberg integration......Page 203
4.4.Improper integrals......Page 205
4.5.Gaussian quadratures and orthogonal polynomials......Page 212
4.6.Multidimensional integrals......Page 227
5.0.Introduction......Page 231
5.1.Series and their convergence......Page 232
5.2.Evaluation of continued fractions......Page 237
5.3.Polynomials and rational functions......Page 242
5.4.Complex arithmetic......Page 246
5.5.Recurrence relations and Clenshaw's recurrence formula......Page 249
5.6.Quadratic and cubic equations......Page 255
5.7.Numerical derivatives......Page 259
5.8.Chebyshev approximation......Page 264
5.9.Derivatives or integrals of a Chebyshew-approximated function......Page 270
5.10.Polynomial approximation from Chebyshev coefficients......Page 273
5.11.Economization of power series......Page 275
5.12.Pade approximants......Page 278
5.13.Rational Chebyshev approximation......Page 283
5.14.Evaluation of functions by path integration......Page 288
6.0.Introduction......Page 292
6.1.Gamma function,beta function,factorials,binomial coefficients......Page 294
6.2.Incomplete gamma function,error function,chi-square probability function,cumulative Poisson function......Page 298
6.3.Exponential integrals......Page 305
6.4.Incomplete beta function,Student's distribution,F-distribution,cumulative binomial distribution......Page 310
6.5.Bessel functions of integer order......Page 315
6.6.Modified Bessel functions of integer order......Page 322
6.7.Bessel functions of fractional order,airy functions,spherical Bessel functions......Page 327
6.8.Spherical harmonics......Page 340
6.9.Fresnel integrals,cosine and sine integrals......Page 344
6.10.Dawson's integral......Page 349
6.11.Elliptic integrals and Jacobian elliptic functions......Page 352
6.12.Hypergeometric functions......Page 363
7.0.Introduction......Page 366
7.1.Uniform deviates......Page 368
7.2.Transformation method: exponential and normal deviates......Page 381
7.3.Rejection method: gamma, Poisson, binomial deviates......Page 385
7.4.Generation of random bits......Page 392
7.5.Random sequences based on data encryption......Page 397
7.6.Simple Monte Carlo integration......Page 402
7.7.Quasi- (that is, sub-) random sequences......Page 408
7.8.Adaptive and recursive Monte Carlo methods......Page 416
8.0.Introduction......Page 429
8.1.Straight insertion and Shell's method......Page 431
8.2.Quicksort......Page 434
8.3.Heapsort......Page 439
8.4.Indexing and ranking......Page 442
8.5.Selecting the Mth largest......Page 446
8.6.Determination of equivalence classes......Page 451
9.0.Introduction......Page 453
9.1.Braketing and bisection......Page 457
9.2.Secant method, false position method,and ridder's method......Page 462
9.3.Van Wijngaarden-Dekker-Brent method......Page 468
9.4.Newton-Raphson method using derivative......Page 472
9.5.Roots of polynomials......Page 480
9.6.Newton-Raphson method for nonlinear systems of equations......Page 491
9.7.Globally convergent methods for nonlinear systems of equations......Page 496
10.0.Introduction......Page 507
10.1.Golden section search in one dimension......Page 511
10.2.Parabolic interpolation and Brent's method in one dimension......Page 517
10.3.One-dimensional search with first derivatives......Page 521
10.4.Downhill simplex method in multidimensions......Page 525
10.5.Direction set (Powell's) methods in multidimensions......Page 530
10.6.Conjurgate gradient methods in multidimensions......Page 539
10.7.Variable metric methods in multidimensions......Page 545
10.8.Linear programming and the simplex method......Page 551
10.9.Simulated annealing methods......Page 566
11.0.Introduction......Page 578
11.1.Jacobi transformations of a symmetric matrix......Page 586
11.2.Reduction of a symmetric matrix to triagonal form: givens and householder reductions......Page 593
11.3.Eigenvalues and eigenvectors of a triagonal matrix......Page 600
11.4.Hermitian matrices......Page 607
11.5.Reduction of a general matrix to Hessenberg form......Page 609
11.6.The QR algorithm for real Hessenberg matrices......Page 614
11.7.Improving eigenvalues and/or finding eigenvectors by inverse iteration......Page 622
12.0.Introduction......Page 625
12.1.Fourier transform of discretely sampled data......Page 630
12.2.Fast Fourier transform (FFT)......Page 635
12.3.FFT of real functions, sine and cosine transforms......Page 642
12.4.FFT in two or more dimensions......Page 654
12.5.Fourier transforms of real data in two and three dimensions......Page 659
12.6.External storage of memory-local FFTs......Page 667
13.0.Introduction......Page 672
13.1.Convolution and deconvolution using the FFT......Page 674
13.2.Correlation and autocorrelation using the FFT......Page 682
13.3.Optimal (Wiener) filtering with the FFT......Page 685
13.4.Power spectrum estimation using the FFT......Page 688
13.5.Digital filtering in the time domain......Page 698
13.6.Linear prediction and linear predictive coding......Page 705
13.7.Power spectrum estimation by the maximum entropy (all poles) method......Page 714
13.8.Spectral analysis of unevenly sampled data......Page 718
13.9.Computing Fourier integrals using the FFT......Page 728
13.10.Wavelet transforms......Page 736
13.11.Numerical use of the sampling theorem......Page 752
14.0.Introduction......Page 755
14.1.Moments of a distribution: mean, variance, skewness, and so forth......Page 757
14.2.Do two distributions have the same means or variances?......Page 763
14.3.Are two distributions different?......Page 769
14.4.Contingency table analysis of two distributions......Page 778
14.5.Linear correlation......Page 787
14.6.Nonparametric or rank correlation......Page 791
14.7.Do two-dimensional distributions differ?......Page 798
14.8.Savitzky-Golay smoothing filters......Page 804
15.0.Introduction......Page 810
15.1.Least squares as a maximum likehood estimator......Page 812
15.2.Fitting data to a straight line......Page 817
15.3.Straighn-line data with errors in both coordinates......Page 823
15.4.General linear least squares......Page 829
15.5.Nonlinear models......Page 840
15.6.Confidence limits on estimated model parameters......Page 849
15.7.Robust estimation......Page 860
16.0.Introduction......Page 868
16.1.Runge-Kutta method......Page 872
16.2.Adaptive stepsize control for Runge-Kutta......Page 877
16.3.Modified midpoint method......Page 886
16.4.Richardson extrapolation and the Bulirsch-Stoer method......Page 889
16.5.Second-order conservative equations......Page 898
16.6.Stiff sets of equations......Page 901
16.7.Multistep, multivalue, and predictor-corrector methods......Page 915
17.0.Introduction......Page 921
17.1.The shooting method......Page 926
17.2.Shooting to a fitting point......Page 930
17.3.Relaxation methods......Page 933
17.4.A worked exaple: spheroidal harmonics......Page 944
17.5.Automated allocation of mesh points......Page 956
17.6.Handling integral boundary conditions or singular points......Page 958
18.0.Introduction......Page 962
18.1.Fredholm equations of the second kind......Page 966
18.2.Volterra equations......Page 970
18.3.Integral equations with singular kernels......Page 974
18.4.Inverse problems and the use of a priori information......Page 982
18.5.Linear regularization methods......Page 987
18.6.Backus-Gilbert method......Page 995
18.7.Maximum entropy image restoration......Page 999
19.0.Introduction......Page 1008
19.1.Flux-conservative initial value problems......Page 1016
19.2.Diffusive initial value problems......Page 1030
19.3.Initial value problems in multidimensions......Page 1037
19.4.Fourier and cyclic reduction methods for boundary value problems......Page 1042
19.5.Relaxation methods for boundary value problems......Page 1049
19.6.Multigrid methods for boundary value problems......Page 1058
20.0.Introduction......Page 1076
20.1.Diagnosing machine parameters......Page 1077
20.2.Gray codes......Page 1083
20.3.Cyclic redundancy and other checksums......Page 1086
20.4.Huffman coding and compression of data......Page 1094
20.5.Arithmetic coding......Page 1102
20.6.Arithmetic at arbitrary precision......Page 1108
References......Page 1119
General index......Page 1158