c0-0 (Numerical Recipes in C), страница 2

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).7.2 Transformation Method: Exponential and Normal Deviates7.3 Rejection Method: Gamma, Poisson, Binomial Deviates7.4 Generation of Random Bits7.5 Random Sequences Based on Data Encryption7.6 Simple Monte Carlo Integration7.7 Quasi- (that is, Sub-) Random Sequences7.8 Adaptive and Recursive Monte Carlo MethodsviiviiiContents11.6 The QR Algorithm for Real Hessenberg Matrices11.7 Improving Eigenvalues and/or Finding Eigenvectors byInverse Iteration12 Fast Fourier Transform13 Fourier and Spectral Applications13.0 Introduction13.1 Convolution and Deconvolution Using the FFT13.2 Correlation and Autocorrelation Using the FFT13.3 Optimal (Wiener) Filtering with the FFT13.4 Power Spectrum Estimation Using the FFT13.5 Digital Filtering in the Time Domain13.6 Linear Prediction and Linear Predictive Coding13.7 Power Spectrum Estimation by the Maximum Entropy(All Poles) Method13.8 Spectral Analysis of Unevenly Sampled Data13.9 Computing Fourier Integrals Using the FFT13.10 Wavelet Transforms13.11 Numerical Use of the Sampling Theorem14 Statistical Description of Data14.0 Introduction14.1 Moments of a Distribution: Mean, Variance, Skewness,and So Forth14.2 Do Two Distributions Have the Same Means or Variances?14.3 Are Two Distributions Different?14.4 Contingency Table Analysis of Two Distributions14.5 Linear Correlation14.6 Nonparametric or Rank Correlation14.7 Do Two-Dimensional Distributions Differ?14.8 Savitzky-Golay Smoothing Filters15 Modeling of Data15.0 Introduction15.1 Least Squares as a Maximum Likelihood Estimator15.2 Fitting Data to a Straight Line15.3 Straight-Line Data with Errors in Both Coordinates15.4 General Linear Least Squares15.5 Nonlinear Models493496496500504510521525532537537538545547549558564572575584591606609609610615620628636639645650656656657661666671681Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).12.0 Introduction12.1 Fourier Transform of Discretely Sampled Data12.2 Fast Fourier Transform (FFT)12.3 FFT of Real Functions, Sine and Cosine Transforms12.4 FFT in Two or More Dimensions12.5 Fourier Transforms of Real Data in Two and Three Dimensions12.6 External Storage or Memory-Local FFTs486Contents15.6 Confidence Limits on Estimated Model Parameters15.7 Robust Estimation16 Integration of Ordinary Differential Equations17 Two Point Boundary Value Problems17.0 Introduction17.1 The Shooting Method17.2 Shooting to a Fitting Point17.3 Relaxation Methods17.4 A Worked Example: Spheroidal Harmonics17.5 Automated Allocation of Mesh Points17.6 Handling Internal Boundary Conditions or Singular Points18 Integral Equations and Inverse Theory18.0 Introduction18.1 Fredholm Equations of the Second Kind18.2 Volterra Equations18.3 Integral Equations with Singular Kernels18.4 Inverse Problems and the Use of A Priori Information18.5 Linear Regularization Methods18.6 Backus-Gilbert Method18.7 Maximum Entropy Image Restoration19 Partial Differential Equations19.0 Introduction19.1 Flux-Conservative Initial Value Problems19.2 Diffusive Initial Value Problems19.3 Initial Value Problems in Multidimensions19.4 Fourier and Cyclic Reduction Methods for BoundaryValue Problems19.5 Relaxation Methods for Boundary Value Problems19.6 Multigrid Methods for Boundary Value Problems20 Less-Numerical Algorithms20.0 Introduction20.1 Diagnosing Machine Parameters20.2 Gray Codes689699707707710714722724732734747753753757760762772783784788788791794797804808815818827827834847853857863871889889889894Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).16.0 Introduction16.1 Runge-Kutta Method16.2 Adaptive Stepsize Control for Runge-Kutta16.3 Modified Midpoint Method16.4 Richardson Extrapolation and the Bulirsch-Stoer Method16.5 Second-Order Conservative Equations16.6 Stiff Sets of Equations16.7 Multistep, Multivalue, and Predictor-Corrector MethodsixContentsx89690391091520.3 Cyclic Redundancy and Other Checksums20.4 Huffman Coding and Compression of Data20.5 Arithmetic Coding20.6 Arithmetic at Arbitrary Precision926Appendix A: Table of Prototype Declarations930Appendix B: Utility Routines940Appendix C: Complex Arithmetic948Index of Programs and Dependencies951General Index965Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).ReferencesPreface to the Second EditionxiSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Our aim in writing the original edition of Numerical Recipes was to provide abook that combined general discussion, analytical mathematics, algorithmics, andactual working programs. The success of the first edition puts us now in a difficult,though hardly unenviable, position.

We wanted, then and now, to write a bookthat is informal, fearlessly editorial, unesoteric, and above all useful. There is adanger that, if we are not careful, we might produce a second edition that is weighty,balanced, scholarly, and boring.It is a mixed blessing that we know more now than we did six years ago. Then,we were making educated guesses, based on existing literature and our own research,about which numerical techniques were the most important and robust. Now, we havethe benefit of direct feedback from a large reader community.

Letters to our alter-egoenterprise, Numerical Recipes Software, are in the thousands per year. (Please, don’ttelephone us.) Our post office box has become a magnet for letters pointing outthat we have omitted some particular technique, well known to be important in aparticular field of science or engineering. We value such letters, and digest themcarefully, especially when they point us to specific references in the literature.The inevitable result of this input is that this Second Edition of NumericalRecipes is substantially larger than its predecessor, in fact about 50% larger both inwords and number of included programs (the latter now numbering well over 300).“Don’t let the book grow in size,” is the advice that we received from several wisecolleagues.

We have tried to follow the intended spirit of that advice, even as weviolate the letter of it. We have not lengthened, or increased in difficulty, the book’sprincipal discussions of mainstream topics. Many new topics are presented at thissame accessible level. Some topics, both from the earlier edition and new to thisone, are now set in smaller type that labels them as being “advanced.” The readerwho ignores such advanced sections completely will not, we think, find any lack ofcontinuity in the shorter volume that results.Here are some highlights of the new material in this Second Edition:• a new chapter on integral equations and inverse methods• a detailed treatment of multigrid methods for solving elliptic partialdifferential equations• routines for band diagonal linear systems• improved routines for linear algebra on sparse matrices• Cholesky and QR decomposition• orthogonal polynomials and Gaussian quadratures for arbitrary weightfunctions• methods for calculating numerical derivatives• Padé approximants, and rational Chebyshev approximation• Bessel functions, and modified Bessel functions, of fractional order; andseveral other new special functions• improved random number routines• quasi-random sequences• routines for adaptive and recursive Monte Carlo integration in highdimensional spaces• globally convergent methods for sets of nonlinear equationsxiiPreface to the Second Editionsimulated annealing minimization for continuous control spacesfast Fourier transform (FFT) for real data in two and three dimensionsfast Fourier transform (FFT) using external storageimproved fast cosine transform routineswavelet transformsFourier integrals with upper and lower limitsspectral analysis on unevenly sampled dataSavitzky-Golay smoothing filtersfitting straight line data with errors in both coordinatesa two-dimensional Kolmogorov-Smirnoff testthe statistical bootstrap methodembedded Runge-Kutta-Fehlberg methods for differential equationshigh-order methods for stiff differential equationsa new chapter on “less-numerical” algorithms, including Huffman andarithmetic coding, arbitrary precision arithmetic, and several other topics.Consult the Preface to the First Edition, following, or the Table of Contents, for alist of the more “basic” subjects treated.AcknowledgmentsIt is not possible for us to list by name here all the readers who have madeuseful suggestions; we are grateful for these.

In the text, we attempt to give specificattribution for ideas that appear to be original, and not known in the literature. Weapologize in advance for any omissions.Some readers and colleagues have been particularly generous in providingus with ideas, comments, suggestions, and programs for this Second Edition.We especially want to thank George Rybicki, Philip Pinto, Peter Lepage, RobertLupton, Douglas Eardley, Ramesh Narayan, David Spergel, Alan Oppenheim, SallieBaliunas, Scott Tremaine, Glennys Farrar, Steven Block, John Peacock, ThomasLoredo, Matthew Choptuik, Gregory Cook, L. Samuel Finn, P. Deuflhard, HaroldLewis, Peter Weinberger, David Syer, Richard Ferch, Steven Ebstein, BradleyKeister, and William Gould.