Numerical Recipes in C
The Art of Scientific Computing
SecondEdition
WilliamH.Press
Harvard-Smithsonian Center for Astrophysics
Saul A. Teukolsky
Department of Physics, Cornell University
William T. Vetterling
Polaroid Corporation
Brian P. Flannery
EXXON Research and Engineering Company
CAMBRIDGE UNIVERSITY PRESS
Cambridge New York Port Chester Melbourne Sydney
Published by the Press Syndicate of the University of Cambridge
The Pitt Building, Trumpington Street, Cambridge CB2 1RP
40 West 20th Street, New York, NY 10011-4211, USA
10 Stamford Road, Oakleigh, Melbourne 3166, Australia
Copyright
c
Cambridge University Press 1988, 1992
except for §13.10 and Appendix B, which are placed into the public domain,
and except for all other computer programs and procedures, which are
Copyright
c
Numerical Recipes Software 1987, 1988, 1992, 1997
All Rights Reserved.
Some sections of this book were originally published, in different form, in Computers
in Physics magazine, Copyright
c
American Institute of Physics, 1988–1992.
First Edition originally published 1988; Second Edition originally published 1992.
Reprinted with corrections, 1993, 1994, 1995, 1997.
This reprinting is corrected to software version 2.08
Printed in the United States of America
Typeset in T
E
X
Without an additional license to use the contained software, this book is intended as
a text and reference book, for reading purposes only. A free license for limited use of the
software by the individual owner of a copy of this book who personally types one or more
routines into a single computeris granted under terms describedon p. xvii. See the section
“License Information” (pp. xvi–xviii) for information on obtaining more general licenses
at low cost.
Machine-readablemedia containing the softwarein this book, with includedlicenses
for use on a single screen, are available from Cambridge University Press. See the
order form at the back of the book, email to “orders@cup.org” (North America) or
“trade@cup.cam.ac.uk” (rest of world), or write to Cambridge University Press, 110
Midland Avenue, Port Chester, NY 10573 (USA), for further information.
The software may also be downloaded, with immediate purchase of a license
also possible, from the Numerical Recipes Software Web Site (http://www.nr.com).
Unlicensedtransferof NumericalRecipes programsto any otherformat, or to any computer
except one that is specifically licensed, is strictly prohibited. Technical questions,
corrections, and requests for information should be addressed to Numerical Recipes
Software, P.O. Box 243, Cambridge, MA 02238 (USA), email “info@nr.com”, or fax
781 863-1739.
Library of Congress Cataloging in Publication Data
Numerical recipes in C : the art of scientific computing / William H. Press
... [et al.]. – 2nd ed.
Includes bibliographical references (p. ) and index.
ISBN 0-521-43108-5
1. Numerical analysis–Computer programs. 2. Science–Mathematics–Computerprograms.
3. C (Computer program language) I. Press, William H.
QA297.N866 1992
519.4
0
0285
0
53–dc20 92-8876
A catalog record for this book is available from the British Library.
ISBN 0 521 43108 5 Book
ISBN 0 521 43720 2 Example book in C
ISBN 0 521 43724 5 C diskette (IBM 3.5
00
, 1.44M)
ISBN 0 521 57608 3 CDROM (IBM PC/Macintosh)
ISBN 0 521 57607 5 CDROM (UNIX)
Contents
Preface to the Second Edition xi
Preface to the First Edition xiv
License Information xvi
Computer Programs by Chapter and Section xix
1 Preliminaries 1
1.0 Introduction 1
1.1 Program Organization and Control Structures 5
1.2 Some C Conventions for Scientific Computing 15
1.3 Error, Accuracy, and Stability 28
2 Solution of Linear Algebraic Equations 32
2.0 Introduction 32
2.1 Gauss-Jordan Elimination 36
2.2 Gaussian Elimination with Backsubstitution 41
2.3 LU Decomposition and Its Applications 43
2.4 Tridiagonal and Band Diagonal Systems of Equations 50
2.5 Iterative Improvement of a Solution to Linear Equations 55
2.6 Singular Value Decomposition 59
2.7 Sparse Linear Systems 71
2.8 Vandermonde Matrices and Toeplitz Matrices 90
2.9 Cholesky Decomposition 96
2.10 QR Decomposition 98
2.11 Is Matrix Inversion an N
3
Process? 102
3 Interpolation and Extrapolation 105
3.0 Introduction 105
3.1 Polynomial Interpolation and Extrapolation 108
3.2 Rational Function Interpolation and Extrapolation 111
3.3 Cubic Spline Interpolation 113
3.4 How to Search an Ordered Table 117
3.5 Coefficients of the Interpolating Polynomial 120
3.6 Interpolation in Two or More Dimensions 123
v
vi
Contents
4 Integration of Functions 129
4.0 Introduction 129
4.1 Classical Formulas for Equally Spaced Abscissas 130
4.2 Elementary Algorithms 136
4.3 Romberg Integration 140
4.4 Improper Integrals 141
4.5 Gaussian Quadratures and Orthogonal Polynomials 147
4.6 Multidimensional Integrals 161
5 Evaluation of Functions 165
5.0 Introduction 165
5.1 Series and Their Convergence 165
5.2 Evaluation of Continued Fractions 169
5.3 Polynomials and Rational Functions 173
5.4 Complex Arithmetic 176
5.5 Recurrence Relations and Clenshaw’s Recurrence Formula 178
5.6 Quadratic and Cubic Equations 183
5.7 Numerical Derivatives 186
5.8 Chebyshev Approximation 190
5.9 Derivatives or Integrals of a Chebyshev-approximated Function 195
5.10 Polynomial Approximation from Chebyshev Coefficients 197
5.11 Economization of Power Series 198
5.12 Pad
´
e Approximants 200
5.13 Rational Chebyshev Approximation 204
5.14 Evaluation of Functions by Path Integration 208
6 Special Functions 212
6.0 Introduction 212
6.1 Gamma Function, Beta Function, Factorials, Binomial Coefficients 213
6.2 Incomplete Gamma Function, Error Function, Chi-Square
Probability Function, Cumulative Poisson Function 216
6.3 Exponential Integrals 222
6.4 Incomplete Beta Function, Student’s Distribution, F-Distribution,
Cumulative Binomial Distribution 226
6.5 Bessel Functions of Integer Order 230
6.6 Modified Bessel Functions of Integer Order 236
6.7 Bessel Functions of Fractional Order, Airy Functions, Spherical
Bessel Functions 240
6.8 Spherical Harmonics 252
6.9 Fresnel Integrals, Cosine and Sine Integrals 255
6.10 Dawson’s Integral 259
6.11 Elliptic Integrals and Jacobian Elliptic Functions 261
6.12 Hypergeometric Functions 271
7 Random Numbers 274
7.0 Introduction 274
7.1 Uniform Deviates 275
Contents
vii
7.2 Transformation Method: Exponential and Normal Deviates 287
7.3 Rejection Method: Gamma, Poisson, Binomial Deviates 290
7.4 Generation of Random Bits 296
7.5 Random Sequences Based on Data Encryption 300
7.6 Simple Monte Carlo Integration 304
7.7 Quasi- (that is, Sub-) Random Sequences 309
7.8 Adaptive and Recursive Monte Carlo Methods 316
8 Sorting 329
8.0 Introduction 329
8.1 Straight Insertion and Shell’s Method 330
8.2 Quicksort 332
8.3 Heapsort 336
8.4 Indexing and Ranking 338
8.5 Selecting the M th Largest 341
8.6 Determination of Equivalence Classes 345
9 Root Finding and Nonlinear Sets of Equations 347
9.0 Introduction 347
9.1 Bracketing and Bisection 350
9.2 Secant Method, False Position Method, and Ridders’ Method 354
9.3 Van Wijngaarden–Dekker–Brent Method 359
9.4 Newton-Raphson Method Using Derivative 362
9.5 Roots of Polynomials 369
9.6 Newton-Raphson Method for Nonlinear Systems of Equations 379
9.7 Globally Convergent Methods for Nonlinear Systems of Equations 383
10 Minimization or Maximization of Functions 394
10.0 Introduction 394
10.1 Golden Section Search in One Dimension 397
10.2 Parabolic Interpolation and Brent’s Method in One Dimension 402
10.3 One-Dimensional Search with First Derivatives 405
10.4 Downhill Simplex Method in Multidimensions 408
10.5 Direction Set (Powell’s) Methods in Multidimensions 412
10.6 Conjugate Gradient Methods in Multidimensions 420
10.7 Variable Metric Methods in Multidimensions 425
10.8 Linear Programming and the Simplex Method 430
10.9 Simulated Annealing Methods 444
11 Eigensystems 456
11.0 Introduction 456
11.1 Jacobi Transformations of a Symmetric Matrix 463
11.2 Reduction of a Symmetric Matrix to Tridiagonal Form:
Givens and Householder Reductions 469
11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 475
11.4 Hermitian Matrices 481
11.5 Reduction of a General Matrix to Hessenberg Form 482
- 1
- 2
- 3
前往页