Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X)
Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 machine-
readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs
visit 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).
Numerical Recipes
in Fortran 77
The Art of Scientific Computing
Second Edition
Volume 1 of
Fortran Numerical Recipes
William H. 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
Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X)
Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 machine-
readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs
visit 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).
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 1986, 1992
except for §13.10, which is placed into the public domain,
and except for all other computer programs and procedures, which are
Copyright
c
Numerical Recipes Software 1986, 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 1986; Second Edition originally published 1992 as
Numerical Recipes in FORTRAN: The Art of Scientific Computing
Reprinted with corrections, 1993, 1994, 1995.
Reprinted with corrections, 1996, 1997, as Numerical Recipes in Fortran 77: The Art of
Scientific Computing (Vol. 1 of Fortran Numerical Recipes)
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 computer is granted under terms described on p. xxi. See the section
“License Information” (pp. xx–xxiii) for information on obtaining more general licenses at
low cost.
Machine-readablemedia containing the software in 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 Numerical Recipesprogramsto 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 Fortran 77 : the art of scientific computing / William H. Press
... [et al.]. – 2nd ed.
Includes bibliographical references (p. ) and index.
ISBN 0-521-43064-X
1. Numerical analysis–Computer programs. 2. Science–Mathematics–Computerprograms.
3. FORTRAN (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 43064 X Volume 1 (this book)
ISBN 0 521 57439 0 Volume 2
ISBN 0 521 43721 0 Example book in FORTRAN
ISBN 0 521 57440 4 FORTRAN diskette (IBM 3.5
00
)
ISBN 0 521 57608 3 CDROM (IBM PC/Macintosh)
ISBN 0 521 57607 5 CDROM (UNIX)
Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X)
Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 machine-
readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs
visit 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).
Contents
Plan of the Two-Volume Edition xiii
Preface to the Second Edition xv
Preface to the First Edition xviii
License Information xx
Computer Programs by Chapter and Section xxiv
1 Preliminaries 1
1.0 Introduction 1
1.1 Program Organization and Control Structures 5
1.2 Error, Accuracy, and Stability 18
2 Solution of Linear Algebraic Equations 22
2.0 Introduction 22
2.1 Gauss-Jordan Elimination 27
2.2 Gaussian Elimination with Backsubstitution 33
2.3 LU Decomposition and Its Applications 34
2.4 Tridiagonal and Band Diagonal Systems of Equations 42
2.5 Iterative Improvement of a Solution to Linear Equations 47
2.6 Singular Value Decomposition 51
2.7 Sparse Linear Systems 63
2.8 Vandermonde Matrices and Toeplitz Matrices 82
2.9 Cholesky Decomposition 89
2.10 QR Decomposition 91
2.11 Is Matrix Inversion an N
3
Process? 95
3 Interpolation and Extrapolation 99
3.0 Introduction 99
3.1 Polynomial Interpolation and Extrapolation 102
3.2 Rational Function Interpolation and Extrapolation 104
3.3 Cubic Spline Interpolation 107
3.4 How to Search an Ordered Table 110
3.5 Coefficients of the Interpolating Polynomial 113
3.6 Interpolation in Two or More Dimensions 116
v
vi
Contents
Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X)
Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 machine-
readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs
visit 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).
4 Integration of Functions 123
4.0 Introduction 123
4.1 Classical Formulas for Equally Spaced Abscissas 124
4.2 Elementary Algorithms 130
4.3 Romberg Integration 134
4.4 Improper Integrals 135
4.5 Gaussian Quadratures and Orthogonal Polynomials 140
4.6 Multidimensional Integrals 155
5 Evaluation of Functions 159
5.0 Introduction 159
5.1 Series and Their Convergence 159
5.2 Evaluation of Continued Fractions 163
5.3 Polynomials and Rational Functions 167
5.4 Complex Arithmetic 171
5.5 Recurrence Relations and Clenshaw’s Recurrence Formula 172
5.6 Quadratic and Cubic Equations 178
5.7 Numerical Derivatives 180
5.8 Chebyshev Approximation 184
5.9 Derivatives or Integrals of a Chebyshev-approximated Function 189
5.10 Polynomial Approximation from Chebyshev Coefficients 191
5.11 Economization of Power Series 192
5.12 Pad
´
e Approximants 194
5.13 Rational Chebyshev Approximation 197
5.14 Evaluation of Functions by Path Integration 201
6 Special Functions 205
6.0 Introduction 205
6.1 Gamma Function, Beta Function,Factorials, Binomial Coefficients 206
6.2 Incomplete Gamma Function, Error Function, Chi-Square
Probability Function, Cumulative Poisson Function 209
6.3 Exponential Integrals 215
6.4 Incomplete Beta Function, Student’s Distribution, F-Distribution,
Cumulative Binomial Distribution 219
6.5 Bessel Functions of Integer Order 223
6.6 Modified Bessel Functions of Integer Order 229
6.7 Bessel Functions of Fractional Order, Airy Functions, Spherical
Bessel Functions 234
6.8 Spherical Harmonics 246
6.9 Fresnel Integrals, Cosine and Sine Integrals 248
6.10 Dawson’s Integral 252
6.11 Elliptic Integrals and Jacobian Elliptic Functions 254
6.12 Hypergeometric Functions 263
7 Random Numbers 266
7.0 Introduction 266
7.1 Uniform Deviates 267
Contents
vii
Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X)
Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 machine-
readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs
visit 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 Deviates 277
7.3 Rejection Method: Gamma, Poisson, Binomial Deviates 281
7.4 Generation of Random Bits 287
7.5 Random Sequences Based on Data Encryption 290
7.6 Simple Monte Carlo Integration 295
7.7 Quasi- (that is, Sub-) Random Sequences 299
7.8 Adaptive and Recursive Monte Carlo Methods 306
8 Sorting 320
8.0 Introduction 320
8.1 Straight Insertion and Shell’s Method 321
8.2 Quicksort 323
8.3 Heapsort 327
8.4 Indexing and Ranking 329
8.5 Selecting the M th Largest 333
8.6 Determination of Equivalence Classes 337
9 Root Finding and Nonlinear Sets of Equations 340
9.0 Introduction 340
9.1 Bracketing and Bisection 343
9.2 Secant Method, False Position Method, and Ridders’ Method 347
9.3 Van Wijngaarden–Dekker–Brent Method 352
9.4 Newton-Raphson Method Using Derivative 355
9.5 Roots of Polynomials 362
9.6 Newton-Raphson Method for Nonlinear Systems of Equations 372
9.7 Globally Convergent Methods for Nonlinear Systems of Equations 376
10 Minimization or Maximization of Functions 387
10.0 Introduction 387
10.1 Golden Section Search in One Dimension 390
10.2 Parabolic Interpolation and Brent’s Method in One Dimension 395
10.3 One-Dimensional Search with First Derivatives 399
10.4 Downhill Simplex Method in Multidimensions 402
10.5 Direction Set (Powell’s) Methods in Multidimensions 406
10.6 Conjugate Gradient Methods in Multidimensions 413
10.7 Variable Metric Methods in Multidimensions 418
10.8 Linear Programming and the Simplex Method 423
10.9 Simulated Annealing Methods 436
11 Eigensystems 449
11.0 Introduction 449
11.1 Jacobi Transformations of a Symmetric Matrix 456
11.2 Reduction of a Symmetric Matrix to Tridiagonal Form:
Givens and Householder Reductions 462
11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 469
11.4 Hermitian Matrices 475
11.5 Reduction of a General Matrix to Hessenberg Form 476
