c21-2 (779630), страница 7
Текст из файла (страница 7)
real implementation 283L’Ecuyer’s long period 280f.988linear congruential generator 276f.machine language 278Minimal Standard, Park and Miller’s 278f.nonrandomness of low-order bits 277perfect 281planes, numbers lie on 277portable 278ff.primitive polynomials modulo 2 296ff.pseudo-DES 300quasi-random sequences 309ff., 889, 896quick and dirty 283ff.quicker and dirtier 284f.in Quicksort 333random access to nth number 303random bits 296ff.recommendations 285f.rejection method 290ff.shuffling procedure 280, 281in simulated annealing method 445spectral test 284subtractive method 282system-supplied 275ff.timings 285f.transformation method 287ff.trick for trigonometric functions 289Random numbers see Monte Carlo; RandomdeviatesRandom walk 29RANDU, infamous routine 277Range 61, 63Rank (matrix) 61kernel of finite 794Rank (sorting) 329, 340f.Rank (statistics) 639ff., 699f.Kendall’s tau 642ff.Spearman correlation coefficient 640f.sum squared differences of 640Ratio variable (statistics) 628Rational Chebyshev approximation 204ff.Rational function 105, 173ff., 200ff., 204ff.approximation for Bessel functions 231f.approximation for continued fraction 170,217, 227Chebyshev approximation 204ff.evaluation of 176extrapolation in Bulirsch-Stoer method724ff., 731interpolation and extrapolation using 105,111ff., 200ff., 204ff., 724ff., 731minimax 204as power spectrum estimate 573Realizable (causal) 559, 561Rearranging see SortingReciprocal, multiple precision 919Record, in data file 338Recurrence relation 178ff.associated Legendre polynomials 253Bessel function 178, 231, 241f.binomial coefficients 215Bulirsch-Stoer 111f.characteristic polynomial of tridiagonalmatrix 475Clenshaw’s recurrence formula 181ff.and continued fraction 181continued fraction evaluation 170f.Indexconvergence 181cosine function 178, 506dominant solution 179exponential integrals 178gamma function 213generation of random bits 297f.Golden Mean 30Legendre polynomials 178minimal vs.
dominant solution 179modified Bessel function 239Neville’s 109, 188orthonormal polynomials 149Perron’s theorems 180f.Pincherle’s theorem 181polynomial interpolation 109, 189primitive polynomials modulo 2 297f.random number generator 276rational function interpolation 111f.sequence of trig functions 178f.sine function 178, 506spherical harmonics 253stability of 30f., 179ff., 182f., 231, 239,253trig functions 579weight of Gaussian quadrature 150f.Recursion, in multigrid method 874Recursive Monte Carlo integration 316ff.Recursive stratified sampling 323ff.Red-black see Odd-even orderingReduction of variance in Monte Carlo integration 308, 316ff.References (explanation) 4References (general bibliography) 926ff.Reflection formula for gamma function 213register storage class 25Regula falsi (false position) 354ff.Regularity condition 784Regularizationcompared with optimal filtering 810constrained linear inversion method 808ff.of inverse problems 805ff.linear 808ff.nonlinear 822f.objective criterion 811Phillips-Twomey method 808ff.Tikhonov-Miller 808ff.trade-off curve 808two-dimensional 812zeroth order 805ff.see also Inverse problemsRegularizing operator 807Rejection method for random number generator 290ff.Relaxation methodfor algebraically difficult sets 772automated allocation of mesh points 783f.,786computation of spheroidal harmonics 772ff.for differential equations 754f., 762ff.elliptic partial differential equations 832f.,863ff.example 772ff.Gauss-Seidel method 864, 873ff., 884internal boundary conditions 784ff.internal singular points 784ff.IndexJacobi’s method 864f., 873successive over-relaxation (SOR) 866ff.,871, 875see also Multigrid methodRemes algorithmsexchange algorithm 560for minimax rational function 205Residual 57, 62, 85in multigrid method 872Resolution function, in Backus-Gilbert method816Response function 538Restriction operator 873Reward, $1000 offered 281Richardson’s deferred approach to the limit140, 143, 188, 708, 724ff., 733f., 796,878see also Bulirsch-Stoer methodRichtmyer artificial viscosity 846Ridders’ method, for numerical derivatives188Ridders’ method, root finding 348, 356, 358Riemann shock problem 846Right eigenvalues and eigenvectors 458Rise/fall time 554f.Robust estimation 659, 699ff., 705Andrew’s sine 702average deviation 611double exponential errors 701Kalman filtering 705Lorentzian errors 701f.mean absolute deviation 611nonparametric correlation 639ff.Tukey’s biweight 702use of a priori covariances 705see also Statistical testsRomberg integration 130, 140f., 143, 188,723, 797Root finding 149f., 347ff.advanced implementations of Newton’s rule393Bairstow’s method 371, 377bisection 350, 353, 359ff., 366, 397, 476,703bracketing of roots 348, 350ff., 360, 369,371, 376Brent’s method 348, 356, 666Broyden’s method 380, 389ff., 393compared with multidimensional minimization 382complex analytic functions 371in complex plane 210convergence criteria 353, 381deflation of polynomials 369ff., 377without derivatives 361double root 348eigenvalue methods 375false position 354ff.Jenkins-Traub method 376Laguerre’s method 348, 371ff.Lehmer-Schur algorithm 376Maehly’s procedure 370, 378matrix method 375Muller’s method 371, 379multiple roots 348989Newton’s rule 149f., 185, 348, 362ff.,369, 371, 377, 379ff., 383f., 476, 749,757f., 762, 796, 882, 884, 919, 921pathological cases 350f., 362ff., 369, 380polynomials 348, 369ff., 456in relaxation method 762Ridders’ method 348, 356, 358root-polishing 365, 370f., 376ff., 378safe Newton’s rule 366secant method 354ff., 365, 371, 406in shooting method 754, 757f.singular Jacobian in Newton’s rule 393stopping criterion for polynomials 373use of minimum finding 348using derivatives 362ff.zero suppression 379see also RootsRoot polishing 365, 370, 376ff.RootsChebyshev polynomials 190cubic equations 184f.multiple 348, 371ff.nonlinear equations 347ff.polynomials 348, 369ff., 456quadratic equations 183f.reflection in unit circle 567square, multiple precision 921see also Root findingRosenbrock method 737ff.compared with semi-implicit extrapolation747stepsize control 738Roundoff error 29, 889f.bracketing a minimum 406conjugate gradient method 833eigensystems 465, 474, 476, 478, 483,485, 489extended trapezoidal rule 138general linear least squares 674, 677graceful 891hardware aspects 890Householder reduction 472IEEE standard 891interpolation 107least squares fitting 664, 674Levenberg-Marquardt method 685linear algebraic equations 32f., 36, 38, 55,64, 91linear predictive coding (LPC) 571magnification of 29, 55maximum entropy method (MEM) 574measuring 890multidimensional minimization 426, 430multiple roots 369f.numerical derivatives 186recurrence relations 179reduction to Hessenberg form 485series 170f.straight line fitting 664variance 613Row degeneracy 32Row-indexed sparse storage 78f.transpose 80f.Row operations on matrix 37, 40Row totals 630990RSS algorithm 323ff.RST properties (reflexive, symmetric, transitive) 345Runge-Kutta method 708f., 710ff., 738, 747Cash-Karp parameters 716f.embedded 715f., 738high-order 711quality control 728stepsize control 714ff.Run-length encoding 909Rybicki, G.B.
91f., 120, 151, 259, 528, 581,606S amplingimportance 316f.Latin square or hypercube 315recursive stratified 323ff.stratified 317f.uneven or irregular 576, 654Sampling theorem 501, 550for numerical approximation 606ff.Sande-Tukey FFT algorithm 509Savitzky-Golay filtersfor data smoothing 650ff.for numerical derivatives 189, 651Scallop loss 554Schrage’s algorithm 278Schrödinger equation 851ff.Schultz’s method for matrix inverse 57, 606SDLC checksum 898Searchingwith correlated values 117f.an ordered table 117f.selection 341ff.Secant method 348, 354ff., 365, 371, 406Broyden’s method 389ff.multidimensional (Broyden’s) 380, 389ff.Second Euler-Maclaurin summation formula142Second order differential equations 732f.Seed of random number generator 275Selection 329, 341ff.find m largest elements 344heap algorithm 344for median 703operation count 341f.by partition-exchange 341without rearrangement 342timings 344use to find median 614f.Semi-implicit Euler method 737, 743Semi-implicit extrapolation method 737, 743compared with Rosenbrock method 747stepsize control 744Semi-implicit midpoint rule 743Semi-invariants of a distribution 614Sentinel, in Quicksort 333, 341Separable kernel 794Separation of variables 252Serial data port 899Series 165ff.accelerating convergence of 166ff.alternating 166f.asymptotic 167Bessel function Kν 247IndexBessel function Yν 242Bessel functions 166, 230cosine integral 257divergent 167economization 198ff., 201Euler’s transformation 166ff.exponential integral 222, 224Fresnel integral 255hypergeometric 208, 271incomplete beta function 227incomplete gamma function 217Laurent 573relation to continued fractions 169f.roundoff error in 170f.sine and cosine integrals 257sine function 166Taylor 362, 414, 708, 715, 763, 767transformation of 166ff.van Wijngaarden’s algorithm 167Shaft encoder 894f.Shakespeare 8Shampine’s Rosenbrock parameters 738Shell algorithm (Shell’s sort) 330ff.Sherman-Morrison formula 73ff., 90, 389Shifting of eigenvalues 456, 477f., 486f.Shock wave 840, 846Shooting methodcomputation of spheroidal harmonics 781for differential equations 754, 757ff.,779f., 781for difficult cases 760example 779f., 781interior fitting point 760Shuffling to improve random number generator280f.Sidelobe fall-off 554Sidelobe level 554Signal, bandwidth limited 501Significance (numerical) 28Significance (statistical) 615f.one- vs.
two-sided 638peak in Lomb periodogram 577of 2-d K-S test 646f.two-tailed 619Similarity transform 459ff., 463, 483, 485,488Simplexdefined 408f.method in linear programming 396, 408f.,430, 433ff., 439ff.method of Nelder and Mead 396, 408ff.,451f., 702f.use in simulated annealing 451f.Simpson’s rule 130ff., 134, 139, 143, 590,791f., 796, 797Simpson’s three-eighths rule 132, 797, 799Simulated annealing see Annealing, method ofsimulatedSimulation see Monte CarloSine functionevaluated from tan(θ/2) 179recurrence 178series 166Sine integral 255, 257ff.continued fraction 257Indexseries 257see also Cosine integralSine transform see Fast Fourier transform(FFT); Fourier transformSingleton’s algorithm for FFT 532Singular value decomposition (SVD) 33, 34f.,59ff.approximation of matrices 66f.backsubstitution 64and bases for nullspace and range 61confidence levels from 698covariance matrix 698fewer equations than unknowns 65for inverse problems 806and least squares 62, 65f., 205, 674, 676ff.in minimization 416more equations than unknowns 65f.and rational Chebyshev approximation205of square matrix 61ff.use for ill-conditioned matrices 63f., 66,456use for orthonormal basis 66, 100Singularitiesof hypergeometric function 209, 271in integral equations 797ff.in integral equations, worked example 801in integrands 141ff., 797f.removal in numerical integration 144ff.,797f.Singularity, subtraction of the 798SIPSOL 833Skewness of distribution 612, 614Smoothing, importance in multigrid method874Smoothing of data 120, 650ff.in integral equations 790sn function 269Snyder, N.L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
