970 Index unevenly or irregularly sampled 576, Determinant 34,49 581f,654 Deviates,random see Random deviates use of CRCs in manipulating 897 DFP algorithm see Davidon-Fletcher-Powell windowing 553ff. algorithm see also Statistical tests Diagonal dominance 51,684,789,865 Data compression 603,889 Difference equations,finite see Finite differ- arithmetic coding 910ff ence equations (FDEs) cosine transform 519 Difference operator 167 Huffman coding 903ff.,910 Differential equations 707ff. linear predictive coding (LPC)571f. accuracy vs.stability 710,736 lossless 903 Adams-Bashforth-Moulton schemes 749 Data Encryption Standard(DES)300ff. adaptive stepsize control 709.714ff..725. Data type 28 733f,738.744.749f,751 DAUB4592ff.595,598f.601 algebraically difficult sets 772 DAUB6 593 backward Euler's method 735 DAUB12 605 Bader-Deuflhard method for stiff 737, DAUB20 598f. 742f Daubechies wavelet coefficients 592ff.,596, boundary conditions 707f.,753ff.,757, 598f.,601,605 760.779f Davidon-Fletcher-Powell algorithm 397,426f. Bulirsch-Stoer method 209,272,708f., Dawson's integral 259f.,606 712,722.724f.747 approximation for 259 Bulirsch-Stoer method for conservative routine for 260 equations 733 D.C.(direct current)498 comparison of methods 708f.,747,751 Debugging 7 conservative 732f. DEC (Digital Equipment Corp.)xvii,3,894 danger of too small stepsize 720 Declarations 930ff. eigenvalue problem 756,772ff.,779f., Decomposition see Cholesky decomposition; 781 LU decomposition;QR decomposition; embedded Runge-Kutta method 715f.,738 Singular value decomposition(SVD) equivalence of multistep and multivalue Deconvolution 542,549 methods 751 see also Convolution;Fast Fourier trans- Euler's method 708.710.735 form (FFT);Fourier transform forward Euler's method 735 Defect,in multigrid method 872 free boundary problem 756,785 Deferred approach to the limit see Richard- high-order implicit methods 737ff. son's deferred approach to the limit implicit differencing 735f.,749 Deflation initial value problems 708 of matrix 478 internal boundary conditions 784ff of polynomials 369ff.,377,378 internal singular points 784ff. Degeneracy of linear algebraic equations 32, interpolation on right-hand sides 117 61,65,676 Kaps-Rentrop method for stiff 737 Degenerate kernel 794 local extrapolation 715 Degenerate minimization principle 804 modified midpoint method 722f.,726 Degrees of freedom 621f.660.695f. multistep methods 747ff. Demonstration programs 3 multivalue methods 747 Derivatives order of method 710f.,725 computation via Chebyshev approximation path integration for function evaluation 189,195 208f,271 computation via Savitzky-Golay filters predictor-corrector methods 708,737, 189,651 747 matrix of first partial see Jacobian determi- reduction to first-order sets 707,753 nant relaxation method 754f,762ff. matrix of second partial see Hessian ma- relaxation method,example of 772ff. trix r.h.s.independent of c 735 numerical computation 186ff,386,651, Rosenbrock methods for stiff 737 738.758.779 Runge-Kutta method 708f.,710ff.,714ff., of polynomial 173f. 738.747 use in optimization 395f.,406 Runge-Kutta method,high-order 711 DES see Data Encryption Standard Runge-Kutta-Fehlberg method 715f. Descending transformation,elliptic integrals scaling stepsize to required accuracy 716f. 262 second order 732f. Descent direction 383,390,427 semi-implicit differencing 737 Descriptive statistics 609ff. semi-implicit Euler method 737,743 see also Statistical tests semi-implicit extrapolation method 737, Design matrix 651,671,804,809 743
970 Index unevenly or irregularly sampled 576, 581f., 654 use of CRCs in manipulating 897 windowing 553ff. see also Statistical tests Data compression 603, 889 arithmetic coding 910ff. cosine transform 519 Huffman coding 903ff., 910 linear predictive coding (LPC) 571f. lossless 903 Data Encryption Standard (DES) 300ff. Data type 28 DAUB4 592ff., 595, 598f., 601 DAUB6 593 DAUB12 605 DAUB20 598f. Daubechies wavelet coefficients 592ff., 596, 598f., 601, 605 Davidon-Fletcher-Powell algorithm 397, 426f. Dawson’s integral 259f., 606 approximation for 259 routine for 260 D.C. (direct current) 498 Debugging 7 DEC (Digital Equipment Corp.) xvii, 3, 894 Declarations 930ff. Decomposition see Cholesky decomposition; LU decomposition; QR decomposition; Singular value decomposition (SVD) Deconvolution 542, 549 see also Convolution; Fast Fourier transform (FFT); Fourier transform Defect, in multigrid method 872 Deferred approach to the limit see Richardson’s deferred approach to the limit Deflation of matrix 478 of polynomials 369ff., 377, 378 Degeneracy of linear algebraic equations 32, 61, 65, 676 Degenerate kernel 794 Degenerate minimization principle 804 Degrees of freedom 621f., 660, 695f. Demonstration programs 3 Derivatives computation via Chebyshev approximation 189, 195 computation via Savitzky-Golay filters 189, 651 matrix of first partial see Jacobian determinant matrix of second partial see Hessian matrix numerical computation 186ff., 386, 651, 738, 758, 779 of polynomial 173f. use in optimization 395f., 406 DES see Data Encryption Standard Descending transformation, elliptic integrals 262 Descent direction 383, 390, 427 Descriptive statistics 609ff. see also Statistical tests Design matrix 651, 671, 804, 809 Determinant 34, 49 Deviates, random see Random deviates DFP algorithm see Davidon-Fletcher-Powell algorithm Diagonal dominance 51, 684, 789, 865 Difference equations, finite see Finite difference equations (FDEs) Difference operator 167 Differential equations 707ff. accuracy vs. stability 710, 736 Adams-Bashforth-Moulton schemes 749 adaptive stepsize control 709, 714ff., 725, 733f., 738, 744, 749f., 751 algebraically difficult sets 772 backward Euler’s method 735 Bader-Deuflhard method for stiff 737, 742f. boundary conditions 707f., 753ff., 757, 760, 779f. Bulirsch-Stoer method 209, 272, 708f., 712, 722, 724ff., 747 Bulirsch-Stoer method for conservative equations 733 comparison of methods 708f., 747, 751 conservative 732f. danger of too small stepsize 720 eigenvalue problem 756, 772ff., 779f., 781 embedded Runge-Kutta method 715f., 738 equivalence of multistep and multivalue methods 751 Euler’s method 708, 710, 735 forward Euler’s method 735 free boundary problem 756, 785 high-order implicit methods 737ff. implicit differencing 735f., 749 initial value problems 708 internal boundary conditions 784ff. internal singular points 784ff. interpolation on right-hand sides 117 Kaps-Rentrop method for stiff 737 local extrapolation 715 modified midpoint method 722f., 726 multistep methods 747ff. multivalue methods 747 order of method 710f., 725 path integration for function evaluation 208ff., 271 predictor-corrector methods 708, 737, 747ff. reduction to first-order sets 707, 753 relaxation method 754f., 762ff. relaxation method, example of 772ff. r.h.s. independent of x 735 Rosenbrock methods for stiff 737 Runge-Kutta method 708f., 710ff., 714ff., 738, 747 Runge-Kutta method, high-order 711 Runge-Kutta-Fehlberg method 715f. scaling stepsize to required accuracy 716f. second order 732f. semi-implicit differencing 737 semi-implicit Euler method 737, 743 semi-implicit extrapolation method 737, 743
Index 971 semi-implicit midpoint rule 743 Downhill simplex method see Simplex,method shooting method 754,757E of Nelder and Mead shooting method,example 779f.,781 Driver programs 3 similarity to Volterra integral equations Dual viewpoint,in multigrid method 883 794f Duplication theorem,elliptic integrals 262f. singular points 724f,760,784ff. dvector()utility 943 step doubling 715 DWT (discrete wavelet transform)see Wavelet stepsize control 709,714ff.,724,733f., transform 738.744.749f.751 stiff 709.734 stiff methods compared 747 Eardley,D.M.346 Stoermer's rule 732f. EBCDIC 898 see also Partial differential equations:Two- Economization of power series 198ff.,201 point boundary value problems Eigensystems 456ff. Diffusion equation 827,847ff.,864 balancing matrix 483 Crank-Nicolson method 848,853,855 bounds on eigenvalues 58 Forward Time Centered Space (FTCS) calculation of few eigenvectors or eigenval- 847E.850f.864 ues461,494 implicit differencing 848 canned routines 461 multidimensional 855f. characteristic polynomial 456,475f Digamma function 222 completeness 457 defective 457.482.494 Digital filtering see Filter deflation 478 Dihedral group Ds 902 degenerate eigenvalues 456,458 Dimensions (units)683f. elimination method 460,485 Diminishing increment sort 331 factorization method 460 Dirac delta function 293,789 fast Givens reduction 470 Direct method see Periodogram Direct methods for linear algebraic equations generalized eigenproblem 462 35 Givens reduction 469f. Hermitian matrix 481f. Direct product see Outer product of matrices Hessenberg matrix 460,477,482ff.,494 Direction of largest decrease 416f. Householder transformation 460,469ff., Direction numbers,Sobol's sequence 311 476,480,481.484f Direction-set methods for minimization 396, ill-conditioned eigenvalues 483 412ff Dirichlet boundary conditions 829,849,859, implicit shifts 478f and integral equations 788ff.,794 865.867 invariance under similarity transform 459 Disclaimer of warranty xvi inverse iteration 462,476,483,493ff. Discordant pair for Kendall's tau 643 Jacobi transformation 460,463ff.,469 Discrete convolution theorem 538ff. 481,495 Discrete Fourier transform (DFT)500ff. left eigenvalues 458 as approximate continuous transform 503 list of tasks 461 see also Fast Fourier transform (FFT) Discrete optimization 444ff. multiple eigenvalues 495 nonlinear 462 Discriminant 184.464 nonsymmetric matrix 482ff. Diskettes,how to order xvi,996f. operation count of balancing 483 Dispersion 840 operation count of Givens reduction 470 DISPO see Savitzky-Golay filters operation count of Householder reduction Dissipation.numerical 839 474 Divergent series 167 operation count of inverse iteration 494 Division operation count of Jacobi method 467 complex 177 operation count of QL method 477,480 multiple precision 919f. operation count of QR method for Hessen- of polynomials 175,369,377 berg matrices 490 dmatrix()utility 944 operation count of reduction to Hessenberg dn function 269 form 485 Do-while iteration 12 orthogonality 457 Dogleg step methods 393 polynomial roots and 375 Domain of integration 161f. QL method 476ff,481,494f. Dominant solution of recurrence relation 179 QL method with implicit shifts 478ff. Dot (denotes matrix multiplication)33 QR method60,460,463,476f. Double exponential error distribution 701 QR method for Hessenberg matrices 486ff. Double precision real,symmetric matrix 156,474,794 as refuge of scoundrels 890 reduction to Hessenberg form 484f. use in iterative improvement 56 right eigenvalues 458 Double root 348 shifting eigenvalues 456,477f.,486f
Index 971 semi-implicit midpoint rule 743 shooting method 754, 757ff. shooting method, example 779f., 781 similarity to Volterra integral equations 794f. singular points 724f., 760, 784ff. step doubling 715 stepsize control 709, 714ff., 724, 733f., 738, 744, 749f., 751 stiff 709, 734ff. stiff methods compared 747 Stoermer’s rule 732f. see also Partial differential equations; Twopoint boundary value problems Diffusion equation 827, 847ff., 864 Crank-Nicolson method 848, 853, 855 Forward Time Centered Space (FTCS) 847ff., 850f., 864 implicit differencing 848 multidimensional 855f. Digamma function 222 Digital filtering see Filter Dihedral group D5 902 Dimensions (units) 683f. Diminishing increment sort 331 Dirac delta function 293, 789 Direct method see Periodogram Direct methods for linear algebraic equations 35 Direct product see Outer product of matrices Direction of largest decrease 416f. Direction numbers, Sobol’s sequence 311 Direction-set methods for minimization 396, 412ff. Dirichlet boundary conditions 829, 849, 859, 865, 867 Disclaimer of warranty xvi Discordant pair for Kendall’s tau 643 Discrete convolution theorem 538ff. Discrete Fourier transform (DFT) 500ff. as approximate continuous transform 503 see also Fast Fourier transform (FFT) Discrete optimization 444ff. Discriminant 184, 464 Diskettes, how to order xvi, 996f. Dispersion 840 DISPO see Savitzky-Golay filters Dissipation, numerical 839 Divergent series 167 Division complex 177 multiple precision 919f. of polynomials 175, 369, 377 dmatrix() utility 944 dn function 269 Do-while iteration 12 Dogleg step methods 393 Domain of integration 161f. Dominant solution of recurrence relation 179 Dot (denotes matrix multiplication) 33 Double exponential error distribution 701 Double precision as refuge of scoundrels 890 use in iterative improvement 56 Double root 348 Downhill simplex method see Simplex, method of Nelder and Mead Driver programs 3 Dual viewpoint, in multigrid method 883 Duplication theorem, elliptic integrals 262f. dvector() utility 943 DWT (discrete wavelet transform) see Wavelet transform Eardley, D.M. 346 EBCDIC 898 Economization of power series 198ff., 201 Eigensystems 456ff. balancing matrix 483 bounds on eigenvalues 58 calculation of few eigenvectors or eigenvalues 461, 494 canned routines 461 characteristic polynomial 456, 475f. completeness 457 defective 457, 482, 494 deflation 478 degenerate eigenvalues 456, 458 elimination method 460, 485 factorization method 460 fast Givens reduction 470 generalized eigenproblem 462 Givens reduction 469f. Hermitian matrix 481f. Hessenberg matrix 460, 477, 482ff., 494 Householder transformation 460, 469ff., 476, 480, 481, 484f. ill-conditioned eigenvalues 483 implicit shifts 478ff. and integral equations 788ff., 794 invariance under similarity transform 459 inverse iteration 462, 476, 483, 493ff. Jacobi transformation 460, 463ff., 469, 481, 495 left eigenvalues 458 list of tasks 461 multiple eigenvalues 495 nonlinear 462 nonsymmetric matrix 482ff. operation count of balancing 483 operation count of Givens reduction 470 operation count of Householder reduction 474 operation count of inverse iteration 494 operation count of Jacobi method 467 operation count of QL method 477, 480 operation count of QR method for Hessenberg matrices 490 operation count of reduction to Hessenberg form 485 orthogonality 457 polynomial roots and 375 QL method 476ff., 481, 494f. QL method with implicit shifts 478ff. QR method 60, 460, 463, 476ff. QR method for Hessenberg matrices 486ff. real, symmetric matrix 156, 474, 794 reduction to Hessenberg form 484f. right eigenvalues 458 shifting eigenvalues 456, 477f., 486f
972 Index special matrices 461 nonnormal 659.695,699ff. termination criterion 489f.495 relative truncation 883 tridiagonal matrix 460,475ff.,494 roundoff 185,889f. Eigenvalue and eigenvector,defined 456 series,advantage of an even 138f.,723 Eigenvalue problem for differential equations systematic vs.statistical 659 756.772f,779,781 truncation30,186,406,715,889f Eigenvalues and polynomial root finding 375 varieties found by check digits 902 EISPACK 461,482 varieties of,in PDEs 840ff. Electromagnetic potential 525 see also Roundoff error Elimination see Gaussian elimination Error function 220f.,607 Ellipse in confidence limit estimation 693 approximation via sampling theorem 6071 Elliptic integrals 261ff.,915 Chebyshev approximation 220f. addition theorem 262 complex 259 Carlson's forms and algorithms 261ff. for Fisher's z-transformation 638 Cauchy principal value 263 relation to Dawson's integral 259 duplication theorem 262f. relation to Fresnel integrals 255 Legendre 261ff.,267ff. relation to incomplete gamma function routines for 264ff. 220 symmetric form 261f routine for 220f. Weierstrass 262 for significance of correlation 636 Elliptic partial differential equations 827 for sum squared difference of ranks 641 alternating-direction implicit method (ADI) Error handling in programs 2,940 870f.915 Estimation of parameters see Fitting;Maxi- analyze/factorize/operate package 833 mum likelihood estimate biconjugate gradient method 833 Estimation of power spectrum 549ff.,572ff. boundary conditions 828f. Euler equation (fluid flow)840 comparison of rapid methods 863 Euler-Maclaurin summation formula 138,142 conjugate gradient method 833 Euler's constant 223f..257 cyclic reduction 857f.,861f. Euler's method for differential equations 708, Fourier analysis and cyclic reduction (FACR) 710.735 857E,863 Euler's transformation 166ff. Gauss-Seidel method 864.873.874f..884 generalized form 168f. incomplete Cholesky conjugate gradient Evaluation of functions see Function method (ICCG)833 Even and odd parts,of continued fraction Jacobi's method 864f.,873 172,217,222 matrix methods 833 Even parity 896 multigrid method 833.871ff. Exception handling in programs 2,940 rapid (Fourier)method 833,857ff exit()function 2 relaxation method 832.863ff. Explicit differencing 836 strongly implicit procedure 833 Exponent in floating point format 28.890 successive over-relaxation (SOR)866ff., Exponential deviate 287f. 871,875 Exponential integral 222f Emacs.GNU xiii asymptotic expansion 224 Embedded Runge-Kutta method 715f.,738 continued fraction 222 Encapsulation,in programs 6f. recurrence relation 178 Encryption 300 related to incomplete gamma function 222 Entropy 903f. relation to cosine integral 257 of data 632ff.,820 routine for En()223f. EOM(end of message)910 routine for Ei(r）225 Equality constraints 431 series 222 Equations Exponential probability distribution 577 cubic 183ff.,367 Extended midpoint rule 130f,135,141f. normal (fitting)651,672ff.,809f. Extended Simpson's rule 134,796,799 quadratic 29,183ff. Extended Simpson's three-eighths rule 797 see also Differential equations;Partial dif- Extended trapezoidal rule 131f.,133,136ff., ferential equations;Root finding 141,795 Equivalence classes 345f. roundoff error 138 Equivalence transformation 172 extern storage class 25 Error Extirpolation (so-called)581f. checksums for preventing 899 Extrapolation 105ff. clocking 899 in Bulirsch-Stoer method 724ff.,731 double exponential distribution 701 differential equations 708 local truncation 883 by linear prediction 564ff. Lorentzian distribution 701f. local 715 in multigrid method 872 maximum entropy method as type of 574
972 Index special matrices 461 termination criterion 489f., 495 tridiagonal matrix 460, 475ff., 494 Eigenvalue and eigenvector, defined 456 Eigenvalue problem for differential equations 756, 772ff., 779, 781 Eigenvalues and polynomial root finding 375 EISPACK 461, 482 Electromagnetic potential 525 Elimination see Gaussian elimination Ellipse in confidence limit estimation 693 Elliptic integrals 261ff., 915 addition theorem 262 Carlson’s forms and algorithms 261ff. Cauchy principal value 263 duplication theorem 262f. Legendre 261ff., 267ff. routines for 264ff. symmetric form 261f. Weierstrass 262 Elliptic partial differential equations 827 alternating-direction implicit method (ADI) 870f., 915 analyze/factorize/operate package 833 biconjugate gradient method 833 boundary conditions 828f. comparison of rapid methods 863 conjugate gradient method 833 cyclic reduction 857f., 861f. Fourier analysis and cyclic reduction (FACR) 857ff., 863 Gauss-Seidel method 864, 873, 874f., 884 incomplete Cholesky conjugate gradient method (ICCG) 833 Jacobi’s method 864f., 873 matrix methods 833 multigrid method 833, 871ff. rapid (Fourier) method 833, 857ff. relaxation method 832, 863ff. strongly implicit procedure 833 successive over-relaxation (SOR) 866ff., 871, 875 Emacs, GNU xiii Embedded Runge-Kutta method 715f., 738 Encapsulation, in programs 6f. Encryption 300 Entropy 903f. of data 632ff., 820 EOM (end of message) 910 Equality constraints 431 Equations cubic 183ff., 367 normal (fitting) 651, 672ff., 809f. quadratic 29, 183ff. see also Differential equations; Partial differential equations; Root finding Equivalence classes 345f. Equivalence transformation 172 Error checksums for preventing 899 clocking 899 double exponential distribution 701 local truncation 883 Lorentzian distribution 701f. in multigrid method 872 nonnormal 659, 695, 699ff. relative truncation 883 roundoff 185, 889f. series, advantage of an even 138f., 723 systematic vs. statistical 659 truncation 30, 186, 406, 715, 889f. varieties found by check digits 902 varieties of, in PDEs 840ff. see also Roundoff error Error function 220f., 607 approximation via sampling theorem 607f. Chebyshev approximation 220f. complex 259 for Fisher’s z-transformation 638 relation to Dawson’s integral 259 relation to Fresnel integrals 255 relation to incomplete gamma function 220 routine for 220f. for significance of correlation 636 for sum squared difference of ranks 641 Error handling in programs 2, 940 Estimation of parameters see Fitting; Maximum likelihood estimate Estimation of power spectrum 549ff., 572ff. Euler equation (fluid flow) 840 Euler-Maclaurin summation formula 138, 142 Euler’s constant 223f., 257 Euler’s method for differential equations 708, 710, 735 Euler’s transformation 166ff. generalized form 168f. Evaluation of functions see Function Even and odd parts, of continued fraction 172, 217, 222 Even parity 896 Exception handling in programs 2, 940 exit() function 2 Explicit differencing 836 Exponent in floating point format 28, 890 Exponential deviate 287f. Exponential integral 222ff. asymptotic expansion 224 continued fraction 222 recurrence relation 178 related to incomplete gamma function 222 relation to cosine integral 257 routine for En(x) 223f. routine for Ei(x) 225 series 222 Exponential probability distribution 577 Extended midpoint rule 130f., 135, 141f. Extended Simpson’s rule 134, 796, 799 Extended Simpson’s three-eighths rule 797 Extended trapezoidal rule 131f., 133, 136ff., 141, 795 roundoff error 138 extern storage class 25 Extirpolation (so-called) 581f. Extrapolation 105ff. in Bulirsch-Stoer method 724ff., 731 differential equations 708 by linear prediction 564ff. local 715 maximum entropy method as type of 574
Index 973 polynomial 728,730f.,748 for multiple precision multiplication 918 rational function 724f,731 number-theoretic transforms 509f relation to interpolation 105 operation count 504 for Romberg integration 140 optimal (Wiener)filtering 547f,565f see also Interpolation order of storage in 507 Extremization see Minimization partial differential equations 833,857ff. Parzen window 554 F-distribution probability function 226,229 periodicity of 503 periodogram 550ff.,574 F-test for differences of variances 617,619 power spectrum estimation 549ff FACR see Fourier analysis and cyclic reduc- tion (FACR) for quadrature 130 of real data in 2D and 3D 525ff. Facsimile standard 909 of real functions 510ff.,525ff. Factorial double (denoted "!!"253 related algorithms 509f. evaluation of 165 Sande-Tukey algorithm 509 sine transform 514ff..859 relation to gamma function 213 routine for 214f. Singleton's algorithm 532 False position 354ff. square window 553 Family tree 345 treatment of end effects in convolution 540 FAS(full approximation storage algorithm) 882任. treatment of end effects in correlation 546 Fast Fourier transform (FFT)504ff.,889 Tukey's trick for frequency doubling 582 alternative algorithms 509f. use in smoothing data 650 applications 537f used for Lomb periodogram 581f. as approximation to continuous transform variance of power spectrum estimate 552, 503 556 Bartlett window 554 virtual memory machine 535f. bit reversal 505f.,532 Welch window 554 and Clenshaw-Curtis quadrature 196 Winograd algorithms 509 convolution 509,530,538ff.,918 see also Discrete Fourier transform (DFT); convolution of large data sets 543f Fourier transform;Spectral density Cooley-Tukey algorithm 509 Faure sequence 310 correlation 545f Fax (facsimile)Group 3 standard 909 cosine transform 196,517f,860f fcomplex (data type) 24,948 cosine transform,second form 519,861 Feasible vector 431 Danielson-Lanczos lemma 504f.532 FFT see Fast Fourier transform (FFT) data sets not a power of 2 509 Field,in data record 338 data smoothing 650 Figure-of-merit function 656 data windowing 553ff. Filon's method 590 decimation-in-frequency algorithm 509 Filter 558ff. decimation-in-time algorithm 509 acausal 559 discrete autocorrelation 546 bilinear transformation method 561 discrete convolution theorem 538ff. causal 559,650 discrete correlation theorem 545 characteristic polynomial 561 at double frequency 582 data smoothing 650 endpoint corrections 585f digital 558ff. extemal storage 532 DISPO 650 figures of merit for data windows 554 by fast Fourier transform(FFT)530, filtering 558ff. 558ff FIR filter 559f finite impulse response (FIR)538,559f. Fourier integrals 584ff. homogeneous modes of 561 Fourier integrals,infinite range 590f. infinite impulse response (IIR)559,573 Hamming window 554 Kalman 705 Hann window 554 linear 559ff. history 504 low-pass for smoothing 650 IIR filter 559 nonrecursive 559f. image processing 812,814 optimal (Wiener)542,547ff.,565f.,650 integrals using 130 quadrature mirror 592.600 inverse of cosine transform 518f. realizable 559,561 inverse of sine transform 517 recursive 559,573 large data sets 532 Remes exchange algorithm 560 leakage 551 Savitzky-Golay 189,650ff memory-local algorithm 535f stability of 561 multidimensional 521ff. in the time domain 558ff. for multiple precision arithmetic 915 Fine-to-coarse operator 873
Index 973 polynomial 728, 730f., 748 rational function 724ff., 731 relation to interpolation 105 for Romberg integration 140 see also Interpolation Extremization see Minimization F-distribution probability function 226, 229 F-test for differences of variances 617, 619 FACR see Fourier analysis and cyclic reduction (FACR) Facsimile standard 909 Factorial double (denoted “!!") 253 evaluation of 165 relation to gamma function 213 routine for 214f. False position 354ff. Family tree 345 FAS (full approximation storage algorithm) 882ff. Fast Fourier transform (FFT) 504ff., 889 alternative algorithms 509f. applications 537ff. as approximation to continuous transform 503 Bartlett window 554 bit reversal 505f., 532 and Clenshaw-Curtis quadrature 196 convolution 509, 530, 538ff., 918 convolution of large data sets 543f. Cooley-Tukey algorithm 509 correlation 545f. cosine transform 196, 517ff., 860f. cosine transform, second form 519, 861 Danielson-Lanczos lemma 504f., 532 data sets not a power of 2 509 data smoothing 650 data windowing 553ff. decimation-in-frequency algorithm 509 decimation-in-time algorithm 509 discrete autocorrelation 546 discrete convolution theorem 538ff. discrete correlation theorem 545 at double frequency 582 endpoint corrections 585f. external storage 532 figures of merit for data windows 554 filtering 558ff. FIR filter 559f. Fourier integrals 584ff. Fourier integrals, infinite range 590f. Hamming window 554 Hann window 554 history 504 IIR filter 559 image processing 812, 814 integrals using 130 inverse of cosine transform 518f. inverse of sine transform 517 large data sets 532 leakage 551 memory-local algorithm 535f. multidimensional 521ff. for multiple precision arithmetic 915 for multiple precision multiplication 918 number-theoretic transforms 509f. operation count 504 optimal (Wiener) filtering 547ff., 565f. order of storage in 507 partial differential equations 833, 857ff. Parzen window 554 periodicity of 503 periodogram 550ff., 574 power spectrum estimation 549ff. for quadrature 130 of real data in 2D and 3D 525ff. of real functions 510ff., 525ff. related algorithms 509f. Sande-Tukey algorithm 509 sine transform 514ff., 859 Singleton’s algorithm 532 square window 553 treatment of end effects in convolution 540 treatment of end effects in correlation 546 Tukey’s trick for frequency doubling 582 use in smoothing data 650 used for Lomb periodogram 581f. variance of power spectrum estimate 552, 556 virtual memory machine 535f. Welch window 554 Winograd algorithms 509 see also Discrete Fourier transform (DFT); Fourier transform; Spectral density Faure sequence 310 Fax (facsimile) Group 3 standard 909 fcomplex (data type) 24, 948 Feasible vector 431 FFT see Fast Fourier transform (FFT) Field, in data record 338 Figure-of-merit function 656 Filon’s method 590 Filter 558ff. acausal 559 bilinear transformation method 561 causal 559, 650 characteristic polynomial 561 data smoothing 650 digital 558ff. DISPO 650 by fast Fourier transform (FFT) 530, 558ff. finite impulse response (FIR) 538, 559f. homogeneous modes of 561 infinite impulse response (IIR) 559, 573 Kalman 705 linear 559ff. low-pass for smoothing 650 nonrecursive 559f. optimal (Wiener) 542, 547ff., 565f., 650 quadrature mirror 592, 600 realizable 559, 561 recursive 559, 573 Remes exchange algorithm 560 Savitzky-Golay 189, 650ff. stability of 561 in the time domain 558ff. Fine-to-coarse operator 873
974 Index Finite difference equations(FDEs)762,772, standard (probable)errors on fitted parame- 783 ters663,667E,673,677.689ǖ alternating-direction implicit method (ADI) straight line 661ff.,673f,703 856.870f. straight line,errors in both coordinates art,not science 838 666正 Cayley's form for unitary operator 853 see also Error,Least squares fitting;Max- Courant condition 838,841,845 imum likelihood estimate;Robust esti- Courant condition (multidimensional)855 mation Crank-Nicolson method 848.853.855 Five-point difference star 876 eigenmodes of 836f. Fixed point format 28 explicit vs.implicit schemes 836 Fletcher-Powell algorithm see Davidon-Fletcher- forward Euler 835f. Powell algorithm Forward Time Centered Space (FTCS) Fletcher-Reeves algorithm 396f.,421ff. 836f,847f,852,864 float to double conversion 24f. implicit scheme 848 Floating point co-processor 894 Lax method 837ff..845 Floating point format 28,890 Lax method (multidimensional)854f. care in numerical derivatives 186 mesh drifting instability 843f IEEE 285.890f. numerical derivatives 186 Flux-conservative initial value problems 834ff. partial differential equations 830ff. FMG (full multigrid method)872,877f. in relaxation methods 762ff for iteration 8,11 staggered leapfrog method 842f Formats of numbers 28,890 two-step Lax-Wendroff method 844ff FORTRAN 16.20 upwind differencing 841f..846 Numerical Recipes in xv,I see also Partial differential equations Forward deflation 370 Finite element methods,partial differential Forward difference operator 167 equations 833f. Forward Euler differencing 835f Finite impulse response (FIR)538 Forward Time Centered Space see FTCS Finkelstein,S.xii Fourier analysis and cyclic reduction (FACR) FIR (finite impulse response)filter 559f. 858,863 Fisher's z-transformation 637f. Fourier and spectral applications 537ff Fitting 656ff. Fourier integrals basis functions 671 attenuation factors 590 by Chebyshev approximation 191f. endpoint corrections 585f. chi-square 659ff. tail integration by parts 591 confidence levels related to chi-square val- use of fast Fourier transform (FFT)584ff. ues 696ff. Fourier transform 105,496ff confidence levels from singular value de aliasing 501,576 composition (SVD)698 approximation of Dawson's integral 259 confidence limits on fitted parameters 689ff. autocorrelation 498 covariance matrix not always meaningful basis functions compared 514f. 657,695 contrasted with wavelet transform 591f., degeneracy of parameters 679 601 an exponential 679 convolution 498.509.538ff.,918 freezing parameters in 674,705 correlation 498.545f. Gaussians,a sum of 687f. cosine transform 196,517E,860f general linear least squares 671ff. cosine transform,second form 519,861 Kalman filter 705 critical sampling 500,550,552 K-S test,caution regarding 627 definition 496 least squares 657ff. discrete Fourier transform (DFT)190, Legendre polynomials 680 500ff. Levenberg-Marquardt method 683ff.,825 Gaussian function 607 linear regression 661ff. image processing 812,814 maximum likelihood estimation 658, infinite range 590f. 699f inverse of discrete Fourier transform 503 Monte Carlo simulation 627,660,689ff. method for partial differential equations multidimensional 680 857E nonlinear models 681ff missing data 576 nonlinear models,advanced methods 688 missing data,fast algorithm 581f. nonlinear problems that are linear 679 Nyquist frequency 500ff,526,550,552, nonnormal errors 662,695,699ff. 576.579 polynomial90,120,197,650f,671,679f optimal(Wiener)filtering 547ff,565f. by rational Chebyshey approximation 204ff Parseval's theorem 498,504,551 robust methods 699ff. power spectral density (PSD)498f. of sharp spectral features 573 power spectrum estimation by FFT 549ff
974 Index Finite difference equations (FDEs) 762, 772, 783 alternating-direction implicit method (ADI) 856, 870f. art, not science 838 Cayley’s form for unitary operator 853 Courant condition 838, 841, 845 Courant condition (multidimensional) 855 Crank-Nicolson method 848, 853, 855 eigenmodes of 836f. explicit vs. implicit schemes 836 forward Euler 835f. Forward Time Centered Space (FTCS) 836ff., 847ff., 852, 864 implicit scheme 848 Lax method 837ff., 845 Lax method (multidimensional) 854f. mesh drifting instability 843f. numerical derivatives 186 partial differential equations 830ff. in relaxation methods 762ff. staggered leapfrog method 842f. two-step Lax-Wendroff method 844ff. upwind differencing 841f., 846 see also Partial differential equations Finite element methods, partial differential equations 833f. Finite impulse response (FIR) 538 Finkelstein, S. xii FIR (finite impulse response) filter 559f. Fisher’s z-transformation 637f. Fitting 656ff. basis functions 671 by Chebyshev approximation 191f. chi-square 659ff. confidence levels related to chi-square values 696ff. confidence levels from singular value decomposition (SVD) 698 confidence limits on fitted parameters 689ff. covariance matrix not always meaningful 657, 695 degeneracy of parameters 679 an exponential 679 freezing parameters in 674, 705 Gaussians, a sum of 687f. general linear least squares 671ff. Kalman filter 705 K–S test, caution regarding 627 least squares 657ff. Legendre polynomials 680 Levenberg-Marquardt method 683ff., 825 linear regression 661ff. maximum likelihood estimation 658, 699ff. Monte Carlo simulation 627, 660, 689ff. multidimensional 680 nonlinear models 681ff. nonlinear models, advanced methods 688 nonlinear problems that are linear 679 nonnormal errors 662, 695, 699ff. polynomial 90, 120, 197, 650f., 671, 679f. by rational Chebyshev approximation 204ff. robust methods 699ff. of sharp spectral features 573 standard (probable) errors on fitted parameters 663, 667f., 673, 677, 689ff. straight line 661ff., 673f., 703 straight line, errors in both coordinates 666ff. see also Error; Least squares fitting; Maximum likelihood estimate; Robust estimation Five-point difference star 876 Fixed point format 28 Fletcher-Powell algorithm see Davidon-FletcherPowell algorithm Fletcher-Reeves algorithm 396f., 421ff. float to double conversion 24f. Floating point co-processor 894 Floating point format 28, 890 care in numerical derivatives 186 IEEE 285, 890f. Flux-conservative initial value problems 834ff. FMG (full multigrid method) 872, 877f. for iteration 8, 11 Formats of numbers 28, 890 FORTRAN 16, 20 Numerical Recipes in xv, 1 Forward deflation 370 Forward difference operator 167 Forward Euler differencing 835f. Forward Time Centered Space see FTCS Fourier analysis and cyclic reduction (FACR) 858, 863 Fourier and spectral applications 537ff. Fourier integrals attenuation factors 590 endpoint corrections 585f. tail integration by parts 591 use of fast Fourier transform (FFT) 584ff. Fourier transform 105, 496ff. aliasing 501, 576 approximation of Dawson’s integral 259 autocorrelation 498 basis functions compared 514f. contrasted with wavelet transform 591f., 601 convolution 498, 509, 538ff., 918 correlation 498, 545f. cosine transform 196, 517ff., 860f. cosine transform, second form 519, 861 critical sampling 500, 550, 552 definition 496 discrete Fourier transform (DFT) 190, 500ff. Gaussian function 607 image processing 812, 814 infinite range 590f. inverse of discrete Fourier transform 503 method for partial differential equations 857ff. missing data 576 missing data, fast algorithm 581f. Nyquist frequency 500ff., 526, 550, 552, 576, 579 optimal (Wiener) filtering 547ff., 565f. Parseval’s theorem 498, 504, 551 power spectral density (PSD) 498f. power spectrum estimation by FFT 549ff