c21-2 (779630), страница 5
Текст из файла (страница 5)
319Leptokurtic distribution 612Levenberg-Marquardt algorithm 393, 683ff.,825advanced implementation 688Levinson’s method 92f.Lewis, H.W. 284License information xviLimbo 362Limit cycle, in Laguerre’s method 372Line minimization see Minimization, along arayLine search see Minimization, along a rayLinear algebraic equations 32ff.band diagonal 51ff.biconjugate gradient method 84f.979Cholesky decomposition 96ff., 430, 462,674complex 49f.computing A−1 · B 48conjugate gradient method 83ff., 606cyclic tridiagonal 74f.direct methods 35, 71Gauss-Jordan elimination 36ff.Gaussian elimination 41f.Hilbert matrix 90Hotelling’s method 57, 606and integral equations 788ff., 792iterative improvement 55ff., 201iterative methods 35, 83ff.large sets of 33least squares solution 62, 65f., 205, 676LU decomposition 43ff., 201, 393, 739,792, 795, 810nonsingular 33overdetermined 34f., 205, 676, 806partitioned 77f.QR decomposition 98f., 389, 393, 674row vs.
column elimination 40f.Schultz’s method 57, 606Sherman-Morrison formula 73ff., 90singular 32, 61, 66, 205, 676singular value decomposition (SVD) 59ff.,205, 676ff., 806sparse 33, 51ff., 71ff., 739, 813summary of tasks 34Toeplitz 90, 92ff., 201Vandermonde 90ff., 120wavelet solution 603ff., 791Woodbury formula 75ff., 90see also EigensystemsLinear congruential random number generator276f.choice of constants for 284f.Linear constraints 431Linear convergence 353, 400Linear correlation (statistics) 636ff.Linear dependencyconstructing orthonormal basis 66, 100of directions in N -dimensional space 415in linear algebraic equations 32f.Linear equations see Differential equations;Integral equations; Linear algebraicequationsLinear inversion method, constrained 808ff.Linear prediction 564ff.characteristic polynomial 567coefficients 564ff.compared with regularization 810contrasted to polynomial extrapolation567related to optimal filtering 565f.removal of bias in 570stability 567Linear predictive coding (LPC) 571f.Linear programming 394, 430ff.artificial variables 437auxiliary objective function 437basic variables 434composite simplex algorithm 443constraints 431980Indexconvergence criteria 439degenerate feasible vector 436dual problem 443equality constraints 431feasible basis vector 433f.feasible vector 431fundamental theorem 432f.inequality constraints 431left-hand variables 434nonbasic variables 434normal form 433objective function 431optimal feasible vector 431pivot element 435f.primal-dual algorithm 443primal problem 443reduction to normal form 436ff.restricted normal form 433ff.revised simplex method 443right-hand variables 434simplex method 408f., 430, 433ff., 439ff.slack variables 436tableau 434vertex of simplex 433Linear regression 661ff., 666ff.see also FittingLinear regularization 808ff.LINPACK 35Little-endian 302Local extrapolation 715Local extremum 394, 445Localization of roots see BracketingLogarithmic function 262Lomb periodogram method of spectral analysis576f.fast algorithm 581f.Loops 8Lorentzian probability distribution 292, 701f.Low-pass filter 558, 650LP coefficients see Linear predictionLPC (linear predictive coding) 571f.LU decomposition 43ff., 56f., 59, 63, 71,104, 381, 673, 739for A−1 · B 48band diagonal matrix 51ff., 53f.complex equations 49f.Crout’s algorithm 44ff., 53for integral equations 792, 795for inverse iteration of eigenvectors 494for inverse problems 810for matrix determinant 49for matrix inverse 48for nonlinear sets of equations 381, 393operation count 44, 48for Padé approximant 201pivoting 45f.repeated backsubstitution 48, 54solution of linear algebraic equations 48solution of normal equations 673for Toeplitz matrix 94Lucifer (encryption algorithm) 300lvector() utility 943M -estimates699ff.how to compute 702f.local 700ff.see also Maximum likelihood estimateMachine accuracy 28f., 890Macintosh, see Apple MacintoshMaehly’s procedure 370, 378Magicin MEM image restoration 823in Padé approximation 201Mantissa in floating point format 28, 890,918Marginals 630Marquardt method (least squares fitting) 683ff.,825Mass, center of 305ff.MasterCard checksum 901f.Mathematical Center (Amsterdam) 360Matrix 33ff.allocating and freeing 21f., 940ff.approximation of 66f., 605f.band diagonal 50, 51ff., 71band triangular 71banded 35, 461bidiagonal 60block diagonal 71, 762block triangular 71block tridiagonal 71bordered 71characteristic polynomial 456, 475f.Cholesky decomposition 96ff., 430, 462,674column augmented 37compatibility 940complex 49f.condition number 61, 85curvature 682cyclic banded 71cyclic tridiagonal 74f.defective 457, 482, 494of derivatives see Hessian matrix; Jacobiandeterminantdesign (fitting) 651, 671, 809determinant of 34, 49diagonalization 459ff.elementary row and column operations 37finite differencing of partial differentialequations 830ff.freeing a submatrix 23Hermitian 457, 461, 481f.Hermitian conjugate 457Hessenberg 100, 460, 477, 482, 484f., 494Hessian see Hessian matrixhierarchically band diagonal 606Hilbert 90identity 34ill-conditioned 61, 63, 120indexed storage of 78f.and integral equations 788, 792inverse 34, 36, 42, 48f., 73ff., 77f., 102ff.inverse, approximate 57inverse by Hotelling’s method 57, 606inverse by Schultz’s method 57, 606inverse multiplied by a matrix 49iteration for inverse 57, 606Jacobi transformation 460, 463ff., 469IndexJacobian 738lower triangular 43f., 96, 790multiplication denoted by dot 33norm 58normal 457, 458nullity 61nullspace 34, 61, 63, 456, 804orthogonal 98, 457, 470, 594orthogonal transformation 459, 470ff., 477orthonormal basis 66, 100outer product denoted by ⊗ 73, 427partitioning for determinant 78partitioning for inverse 77f.pattern multiply of sparse 81f.positive definite 35, 96, 674QR decomposition 98f., 389, 393, 674range 61rank 61residual 57row and column indices 33row vs.
column operations 40f.self-adjoint 457similarity transform 459ff., 463, 483, 485,488singular 61, 63, 66, 456singular value decomposition 34f., 59ff.,806sparse 33, 71ff., 78, 606, 739, 762, 813special forms 35splitting in relaxation method 865f.spread 817square root of 430, 462storage schemes in C 20f., 33f., 940ff.submatrix of 22, 945symmetric 35, 96, 457, 461, 469ff., 674,793f.threshold multiply of sparse 81ff.Toeplitz 90, 92ff., 201transpose of sparse 80f.triangular 460tridiagonal 35, 50f., 71, 115, 156, 460,461, 469ff., 475ff., 494, 848f., 862,870f.tridiagonal with fringes 831unitary 457updating 100, 389f.upper triangular 43f., 98Vandermonde 90ff., 120see also EigensystemsMatrix equations see Linear algebraic equationsmatrix() utility 943f.Matterhorn 612Maximization see MinimizationMaximum entropy method (MEM) 572ff.algorithms for image restoration 824f.Bayesian 825f.Cornwell-Evans algorithm 825demystified 823historic vs.
Bayesian 825f.image restoration 818ff.intrinsic correlation function (ICF) model826for inverse problems 818ff.operation count 574981see also Linear predictionMaximum likelihood estimate (M-estimates)695, 699ff.and Bayes’ Theorem 820chi-square test 695defined 658how to compute 702f.mean absolute deviation 701, 703relation to least squares 658Maxwell’s equations 835Mean(s)of distribution 610f., 614statistical differences between two 615ff.Mean absolute deviation of distribution 611,701related to median 703Measurement errors 656Median 329calculating 341of distribution 611, 614f.as L-estimate 699role in robust straight line fitting 703by selection 703Median-of-three, in Quicksort 333MEM see Maximum entropy method (MEM)Memory, allocating and freeing 19, 21f.,940ff.Merit function 656in general linear least squares 671for inverse problems 806nonlinear models 681for straight line fitting 662, 703for straight line fitting, errors in both coordinates 666Mesh-drift instability 843f.Mesokurtic distribution 612Method of regularization 808ff.Metropolis algorithm 445f.Microsoft xviiMidpoint method see Modified midpoint method;Semi-implicit midpoint ruleMikado, or Town of Titipu 720Miller’s algorithm 181, 234Minimal solution of recurrence relation 179Minimax polynomial 192, 204Minimax rational function 204Minimization 394ff.along a ray 84, 384f., 396, 412f., 418f.,424, 425annealing, method of simulated 394f.,444ff.bracketing of minimum 397ff., 409Brent’s method 396, 402ff., 406, 666Broyden-Fletcher-Goldfarb-Shanno algorithm 397, 426ff.chi-square 659ff., 681ff.choice of methods 395ff.combinatorial 444conjugate gradient method 396f., 420ff.,812f., 824convergence rate 400, 415f.Davidon-Fletcher-Powell algorithm 397,426f.degenerate 804direction-set methods 396, 412ff.982downhill simplex method 396, 408ff.,451f., 702f.finding best-fit parameters 656Fletcher-Reeves algorithm 396f., 421ff.functional 804global 394f., 451f., 656globally convergent multidimensional 425ff.golden section search 397ff., 403multidimensional 395f., 408ff.in nonlinear model fitting 681f.Polak-Ribiere algorithm 396f., 422f.Powell’s method 396, 408, 412ff.quasi-Newton methods 383, 397, 425ff.and root finding 382scaling of variables 428by searching smaller subspaces 824steepest descent method 421, 813termination criterion 398f., 410use in finding double roots 348use for sparse linear systems 84ff.using derivatives 396f., 405ff.variable metric methods 397, 425ff.see also Linear programmingMinimum residual method, for sparse system85MINPACK 688MIPS 894Missing data problem 576Mississippi River 446, 455Mode of distribution 611, 615Modeling of data see FittingModel-trust region 393, 688Modes, homogeneous, of recursive filters 561Modified Bessel functions see Bessel functionsModified Lentz’s method, for continued fractions 171Modified midpoint method 722f., 726Modified moments 158Modula-2 7Modular arithmetic, without overflow 278,281, 284Modularization, in programs 6f.Modulus of linear congruential generator 276Momentsof distribution 610ff.filter that preserves 650modified problem of 158problem of 90f.and quadrature formulas 799semi-invariants 614Monic polynomial 149Monotonicity constraint, in upwind differencing 846Monte Carlo 162, 275adaptive 316ff., 319ff.bootstrap method 691f.comparison of sampling methods 318f.exploration of binary tree 300importance sampling 316f.integration 130, 162, 304ff., 316ff.integration, recursive 323ff.integration, using Sobol’ sequence 313ff.integration, VEGAS algorithm 319ff.Indexand Kolmogorov-Smirnov statistic 627,646f.partial differential equations 833quasi-random sequences in 309ff.quick and dirty 691f.recursive 316ff., 323ff.significance of Lomb periodogram 578simulation of data 660, 689ff., 695stratified sampling 317f., 323Moon, calculate phases of 1f., 13f.Mother functions 591Mother Nature 689, 691Moving average (MA) model 573Moving window averaging 650Mozart 8MS xviiMS-DOS xii, 3Muller’s method 371, 379Multidimensionalconfidence levels of fitting 694data, use of binning 629Fourier transform 521ff.Fourier transform, real data 525ff.initial value problems 853ff.integrals 130, 161ff., 304ff., 316ff.interpolation 123ff.Kolmogorov-Smirnov test 645ff.least squares fitting 680minimization 408ff., 412ff., 420ff.Monte Carlo integration 304ff., 316ff.normal (Gaussian) distribution 695optimization 395f.partial differential equations 853ff.root finding 347ff., 365, 377, 379ff., 382,754, 757f., 761, 762search using quasi-random sequence 309secant method 380, 389ff.wavelet transform 602Multigrid method 833, 871ff.avoid SOR 875boundary conditions 877f.choice of operators 877coarse-to-fine operator 873coarse-grid correction 873f.cycle 874dual viewpoint 883fine-to-coarse operator 873full approximation storage (FAS) algorithm882ff.full multigrid method (FMG) 872, 877f.full weighting 876Gauss-Seidel relaxation 874f.half weighting 876importance of adjoint operator 876injection operator 873interpolation operator 873line relaxation 875local truncation error 883Newton’s rule 882, 884nonlinear equations 882ff.nonlinear Gauss-Seidel relaxation 884odd-even ordering 875, 878operation count 871prolongation operator 873recursive nature 874Indexrelative truncation error 883relaxation as smoothing operator 874restriction operator 873speeding up FMG algorithm 881f.stopping criterion 884straight injection 876symbol of operator 875f.use of Richardson extrapolation 878V-cycle 874W-cycle 874zebra relaxation 875Multiple precision arithmetic 915ff.Multiple roots 348, 369Multiplication, complex 177Multiplication, multiple precision 916, 918Multiplier of linear congruential generator276Multistep and multivalue methods (ODEs)747ff.see also Differential Equations; Predictorcorrector methodsMultivariate normal distribution 695Murphy’s Law 413Musical scores 5N AG xvii, 35, 72, 212, 461National Science Foundation (U.S.) xiii, xvNatural cubic spline 115Navier-Stokes equation 839, 840Needle, eye of (minimization) 410Negation, multiple precision 916Negentropy 820, 904Nelder-Mead minimization method 396, 408ff.Nested iteration 877Neumann boundary conditions 829, 849, 860,867Neutrino 645Neville’s algorithm 108f., 111, 140, 188Newton-Cotes formulas 131ff., 147open 132Newton-Raphson method see Newton’s ruleNewton’s rule 149f., 185, 348, 362ff., 369,371, 476with backtracking 384f.caution on use of numerical derivatives365fractal domain of convergence 367f.globally convergent multidimensional 380,383ff., 389, 757f., 761for matrix inverse 57, 606in multidimensions 377, 379ff., 757f.,761, 762in nonlinear multigrid 882, 884nonlinear Volterra equations 796for reciprocal of number 919safe 366scaling of variables 389singular Jacobian 393solving stiff ODEs 748for square root of number 921Niederreiter sequence 310NL2SOL 688Noisebursty 897effect on maximum entropy method 574983equivalent bandwidth 554fitting data which contains 653, 656model, for optimal filtering 548Nominal variable (statistics) 628Nonexpansive projection operator 814Non-interfering directions see Conjugate directionsNonlinear eigenvalue problems 462Nonlinear equationsfinding roots of 347ff.integral equations 790, 796in MEM inverse problems 822f.multigrid method for elliptic PDEs 882ff.Nonlinear instability 840Nonlinear programming 443Nonnegativity constraints 430f.Nonparametric statistics 639ff.Nonpolynomial complete (NP-complete) 445Norm, of matrix 58Normal (Gaussian) distribution 275, 658,687f., 807central limit theorem 658f.deviates from 288f., 578kurtosis of 612multivariate 695semi-invariants of 614tails compared to Poisson 659two-dimensional (binormal) 637variance of skewness of 612Normal equations (fitting) 34f., 651, 672ff.,804, 809f.often are singular 676Normalizationof Bessel functions 181of floating-point representation 28, 890of functions 149, 774of modified Bessel functions 239Notch filter 558, 562f.NP-complete problem 445nr.h prototypes for Numerical Recipes 17,930NRANSI macro 17, 930NR_END macro, for offset arrays 941nrerror() utility 2, 942f.nrutil.c utility functions 2, 19, 21f., 940,942ff.nrutil.h prototypes for utilities 17, 27,940ff.Null hypothesis 609Nullity 61Nullspace 34, 61, 63, 456, 804Number-theoretic transforms 509f.Numerical derivatives 186ff., 651Numerical integration see QuadratureNumerical Recipescompatibility with First Edition 3f.compilers tested 3Example Book 3how to get diskettes xvi, 996f.how to report bugs ivlicense information xvilist of all 951ff.machines tested 3OEM information xviino warranty on xvi984programming conventions 25ff.programs by chapter and section xixprototypes (nr.h) 17, 930table of dependencies 951ff.table of prototypes 930as trademark xviiutility functions 2, 940ff.utility prototypes (nrutil.h) 17, 27,940ff.Numerical Recipes Software xi, xviiaddress and fax number xviiNyquist frequency 500ff., 526, 550, 552, 576,578f.Nystrom method 791f., 797f.product version 797O bject extensibility 7Objective function 431Object-oriented programming 7Oblateness parameter 773Odd parity 896Odd-even orderingin Gauss-Seidel relaxation 875, 878in successive over-relaxation (SOR) 868OEM information xviiOne-sided power spectral density 498Operation countbalancing 483Bessel function evaluation 234f.bisection method 353Cholesky decomposition 97coefficients of interpolating polynomial120f.complex multiplication 104cubic spline interpolation 115evaluating polynomial 174f.fast Fourier transform (FFT) 504Gauss-Jordan elimination 42, 48Gaussian elimination 42Givens reduction 470Householder reduction 474interpolation 106inverse iteration 494iterative improvement 56Jacobi transformation 467Kendall’s tau 643f.linear congruential generator 277LU decomposition 44, 48matrix inversion 104matrix multiplication 103maximum entropy method 574multidimensional minimization 420multigrid method 871multiplication 918polynomial evaluation 104, 174f.QL method 477, 480QR decomposition 98QR method for Hessenberg matrices 490reduction to Hessenberg form 485selection by partitioning 341sorting 329ff.Toeplitz matrix 90Vandermonde matrix 90IndexOperatorassociativity, in C 25f.overloading 7precedence, in C 25f.splitting 832, 856f., 870Optimal feasible vector 431Optimal (Wiener) filtering 542, 547ff., 565f.,650compared with regularization 810Optimization see MinimizationOrdinal variable (statistics) 628Ordinary differential equations see DifferentialequationsOrthogonal see Orthonormal functions; Orthonormal polynomialsOrthogonal transformation 459, 470ff., 477,591Orthonormal basis, constructing 66, 100Orthonormal functions 149, 252Orthonormal polynomialsChebyshev 151, 190ff.construct for arbitrary weight 157ff.in Gauss-Hermite integration 153and Gaussian quadrature 149Gaussian weights from recurrence 156Hermite 151Jacobi 151Laguerre 151Legendre 151weight function log x 159Orthonormality 59f., 149, 470Outer product of matrices (denoted by ⊗) 73,427Outgoing wave boundary conditions 829Outlier 611, 659, 662, 699, 702see also Robust estimationOvercorrection 866Overflow 890how to avoid in modulo multiplication278in complex arithmetic 177Overlap-add and overlap-save methods 543f.Overrelaxation parameter 866choice of 866f.P adé approximant111, 200ff.Parabolic interpolation 403Parabolic partial differential equations 827,847ff.Parallel axis theorem 318Parameters in fitting function 657f., 689ff.Parity bit 896Park and Miller minimal standard random generator 278f.Parseval’s Theorem 498, 551discrete form 504Partial differential equations 827ff.advective equation 835alternating-direction implicit method (ADI)856, 870f.amplification factor 837, 843analyze/factorize/operate package 833artificial viscosity 840, 846biconjugate gradient method 833boundary conditions 828ff.Indexboundary value problems 828ff., 857f.Cauchy problem 827f.caution on high-order methods 853f.Cayley’s form 853characteristics 827Chebyshev acceleration 868f.classification of 827ff.comparison of rapid methods 863conjugate gradient method 833Courant condition 838, 841, 843, 845Courant condition (multidimensional) 855Crank-Nicholson method 848, 851, 853,855cyclic reduction (CR) method 857f., 861f.diffusion equation 827, 847ff., 855, 864Dirichlet boundary conditions 829, 848,859, 865, 867elliptic, defined 827error, varieties of 840ff.explicit vs.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
