Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C, страница 2

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 equationsxixiiPreface to the Second Edition••••••••••••••simulated 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. We have been helped by Nancy Lee Snyder’s masteryof a complicated TEX manuscript. We express appreciation to our editors LaurenCowles and Alan Harvey at Cambridge University Press, and to our productioneditor Russell Hahn. We remain, of course, grateful to the individuals acknowledgedin the Preface to the First Edition.Special acknowledgment is due to programming consultant Seth Finkelstein,who wrote, rewrote, or influenced many of the routines in this book, as well as inits FORTRAN-language twin and the companion Example books. Our project hasbenefited enormously from Seth’s talent for detecting, and following the trail of, evenvery slight anomalies (often compiler bugs, but occasionally our errors), and fromhis good programming sense.

To the extent that this edition of Numerical Recipesin C has a more graceful and “C-like” programming style than its predecessor, mostof the credit goes to Seth. (Of course, we accept the blame for the FORTRANishlapses that still remain.)We prepared this book for publication on DEC and Sun workstations running the UNIX operating system, and on a 486/33 PC compatible runningMS-DOS 5.0/Windows 3.0. (See §1.0 for a list of additional computers used inxiiiPreface to the Second Editionprogram tests.) We enthusiastically recommend the principal software used: GNUEmacs, TEX, Perl, Adobe Illustrator, and PostScript.

Also used were a variety of Ccompilers – too numerous (and sometimes too buggy) for individual acknowledgment. It is a sobering fact that our standard test suite (exercising all the routinesin this book) has uncovered compiler bugs in many of the compilers tried. Whenpossible, we work with developers to see that such bugs get fixed; we encourageinterested compiler developers to contact us about such arrangements.WHP and SAT acknowledge the continued support of the U.S. National ScienceFoundation for their research on computational methods. D.A.R.P.A. support isacknowledged for §13.10 on wavelets.June, 1992William H.

PressSaul A. TeukolskyWilliam T. VetterlingBrian P. FlanneryPreface to the First EditionWe call this book Numerical Recipes for several reasons. In one sense, this bookis indeed a “cookbook” on numerical computation. However there is an importantdistinction between a cookbook and a restaurant menu. The latter presents choicesamong complete dishes in each of which the individual flavors are blended anddisguised.

The former — and this book — reveals the individual ingredients andexplains how they are prepared and combined.Another purpose of the title is to connote an eclectic mixture of presentationaltechniques. This book is unique, we think, in offering, for each topic considered,a certain amount of general discussion, a certain amount of analytical mathematics,a certain amount of discussion of algorithmics, and (most important) actual implementations of these ideas in the form of working computer routines. Our task hasbeen to find the right balance among these ingredients for each topic. You willfind that for some topics we have tilted quite far to the analytic side; this where wehave felt there to be gaps in the “standard” mathematical training.

For other topics,where the mathematical prerequisites are universally held, we have tilted towardsmore in-depth discussion of the nature of the computational algorithms, or towardspractical questions of implementation.We admit, therefore, to some unevenness in the “level” of this book. About halfof it is suitable for an advanced undergraduate course on numerical computation forscience or engineering majors. The other half ranges from the level of a graduatecourse to that of a professional reference. Most cookbooks have, after all, recipes atvarying levels of complexity.