Numerical Recipes in C The Art of Scientific Computing Second Edition William H.Press Harvard-Smithsonian Center for Astrophysics Saul A.Teukolsky Department of Physics,Cornell University William T.Vetterling Polaroid Corporation Brian P.Flannery http://w.nr.comorcall 1-800-872-7423(North America ony)orsend email to directcustserv@cambridge.org(outside North America). 学 NUMERICAL RECIPES IN C:THE ART OF SCIENTIFIC COMPUTING(ISBN 0-521-43108-5) EXXON Research and Engineering Company CAMBRIDGE UNIVERSITY PRESS Cambridge New York Port Chester Melbourne Sydney
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). Numerical Recipes in C The Art of Scientific Computing Second Edition 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 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 IRP 40 West 20th Street,New York,NY 10011-4211,USA 477 Williamstown Road.Port Melbourne.VIC.3207.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.2002 All Rights Reserved. Some sections of this book were originally published,in different form,in Computers http://www.nr. in Physics magazine,Copyright C American Institute of Physics,1988-1992. .com First Edition originally published 1988;Second Edition originally published 1992. Reprinted with corrections,1993,1994,1995,1997,2002 or call This reprinting is corrected to software version 2.10 Printed in the United States of America Typeset in TX 1-800-872 to any Cambridge Without an additional license to use the contained software,this book is intended as -7423 (North Am NUMERICAL RECIPES IN server computer,is to make 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 merica University Press. routines into a single computer is granted under terms described on p.xvii.See the section "License Information"(pp.xvi-xviii)for information on obtaining more general licenses at low cost. Machine-readable media containing the software in this book,with included licenses Programs C:THE ART OF 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 directcustserv@cambridge.org"(rest of world),or write to Cambridge University Press SCIENTIFIC 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) Unlicensed transfer of Numerical Recipes programs to any other format,or to any computer except one that is specifically licensed,is strictly prohibited.Technical question corrections,and requests for information should be addressed to Numerical Recipe Software,P.O.Box 380243,Cambridge,MA 02238-0243 (USA),email "info@nr.com" or fax781863-1739. ridge. To order Numerical Recipes books or sonal use.Further 1988-1992 by Numerical Recipes S5。-80134-126。-0/材B(C Library of Congress Cataloging in Publication Data Numerical recipes in C:the art of scientific computing William H.Press ..fet al.].-2nd ed. Includes bibliographical references(p. and index. ISBN0-521-43108-5 Software. 1.Numerical analysis-Computer programs.2.Science-Mathematics-Computer programs. 3.C(Computer program language) I.Press,William H. QA297.N8661992 519.4'028553-dc20 92-8876 North America) A catalog record for this book is available from the British Library. ISBN0521431085 Book ISBN 0 521 43720 2 Example book in C ISBN 0 521 75037 7 C/C++CDROM (Windows/Macintosh) ISBN 0 521 75035 0 Complete CDROM (Windows/Macintosh) ISBN 0 521 75036 9 Complete CDROM (UNIX/Linux)
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (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 477 Williamstown Road, Port Melbourne, VIC, 3207, 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, 2002 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, 2002. This reprinting is corrected to software version 2.10 Printed in the United States of America Typeset in TEX 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. xvii. See the section “License Information” (pp. xvi–xviii) for information on obtaining more general licenses at low cost. Machine-readable media containing the software in this book, with included licenses 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 “directcustserv@cambridge.org” (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). Unlicensed transfer of Numerical Recipes programs to any other format, 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 380243, Cambridge, MA 02238-0243 (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–Computer programs. 3. C (Computer program language) I. Press, William H. QA297.N866 1992 519.4 0285 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 75037 7 C/C++ CDROM (Windows/Macintosh) ISBN 0 521 75035 0 Complete CDROM (Windows/Macintosh) ISBN 0 521 75036 9 Complete CDROM (UNIX/Linux)
Contents http://www.nr.com Preface to the Second Edition xi or call Preface to the First Edition xiv -800-872- License Information XVi (North Am Cambridge NUMERICAL RECIPES IN Computer Programs by Chapter and Section xix to make University 1 Preliminaries one pap Press. 1.0 Introduction 1.1 Program Organization and Control Structures 1.2 Some C Conventions for Scientific Computing 55 088 Programs 1.3 Error,Accuracy,and Stability 28 2 32 email Solution of Linear Algebraic Equations 2.0 Introduction 2.1 Gauss-Jordan Elimination 2.2 Gaussian Elimination with Backsubstitution 2.3 LU Decomposition and Its Applications 2.4 Tridiagonal and Band Diagonal Systems of Equations 2649005 C:THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) 2.5 Iterative Improvement of a Solution to Linear Equations 2.6 Singular Value Decomposition 59 sonal use.Further reproduction, 2.7 Sparse Linear Systems 2.8 Vandermonde Matrices and Toeplitz Matrices 0% to directcustserv@cambridge.org(outside North America). 2.9 Cholesky Decomposition 2.10 QR Decomposition 2.11 Is Matrix Inversion an N3 Process? 102 Interpolation and Extrapolation 105 ing of machine visit website 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 3.5 Coefficients of the Interpolating Polynomial 3.6 Interpolation in Two or More Dimensions 108
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 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 19881992 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 from NUMERICAL RECIPES IN C: 5.6 Quadratic and Cubic Equations 183 5.7 Numerical Derivatives 186 5.8 Chebyshev Approximation 190 America THE 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 9 5.12 Pade Approximants 200 Programs 5.13 Rational Chebyshev Approximation 204 5.14 Evaluation of Functions by Path Integration 208 eraCn 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. 1988-1992 by Numerical Recipes ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) Cumulative Binomial Distribution 226 6.5 Bessel Functions of Integer Order 230 6.6 Modified Bessel Functions of Integer Order 236 (outside 膜 6.7 Bessel Functions of Fractional Order,Airy Functions,Spherical Software. Bessel Functions 240 North 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
vi Contents Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 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 Pade 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 1.200 8.5 Selecting the Mth Largest 341 8.6 Determination of Equivalence Classes 345 NUMERICAL RECIPES IN C: 9 Root Finding and Nonlinear Sets of Equations 347 (North 9.0 Introduction 347 州bMe se 9.1 Bracketing and Bisection 350 America users to make one paper e University Press. THE 9.2 Secant Method.False Position Method.and Ridders'Method 354 ART 9.3 Van Wijngaarden-Dekker-Brent Method 359 9.4 Newton-Raphson Method Using Derivative 362 9 Programs 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 1988-1992 by Numerical Recipes OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) 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 (outside 10.8 Linear Programming and the Simplex Method 430 North Software. 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
Contents vii Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 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 Mth 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
vini Contents 11.6 The OR Algorithm for Real Hessenberg Matrices 486 11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 493 12 Fast Fourier Transform 496 12.0 Introduction 496 12.1 Fourier Transform of Discretely Sampled Data 500 12.2 Fast Fourier Transform(FFT) 504 12.3 FFT of Real Functions.Sine and Cosine Transforms 510 12.4 FFT in Two or More Dimensions 521 12.5 Fourier Transforms of Real Data in Two and Three Dimensions 525 12.6 External Storage or Memory-Local FFTs 532 13 Fourier and Spectral Applications 537 13.0 Introduction 537 13.1 Convolution and Deconvolution Using the FFT 538 13.2 Correlation and Autocorrelation Using the FFT 545 547 (North America from NUMERICAL RECIPES IN C:THE 19881992 13.3 Optimal (Wiener)Filtering with the FFT 13.4 Power Spectrum Estimation Using the FFT 549 13.5 Digital Filtering in the Time Domain 558 tusers to make one paper 13.6 Linear Prediction and Linear Predictive Coding 564 13.7 Power Spectrum Estimation by the Maximum Entropy 9 (All Poles)Method 572 Programs 13.8 Spectral Analysis of Unevenly Sampled Data 575 13.9 Computing Fourier Integrals Using the FFT 584 13.10 Wavelet Transforms 591 13.11 Numerical Use of the Sampling Theorem 606 14 Statistical Description of Data 609 14.0 Introduction 609 14.1 Moments of a Distribution:Mean.Variance.Skewness 610 ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) and So Forth 14.2 Do Two Distributions Have the Same Means or Variances? 615 1988-1992 by Numerical Recipes 14.3 Are Two Distributions Different? 620 14.4 Contingency Table Analysis of Two Distributions 628 14.5 Linear Correlation 636 (outside 14.6 Nonparametric or Rank Correlation 639 Software. 14.7 Do Two-Dimensional Distributions Differ? 645 North 14.8 Savitzky-Golay Smoothing Filters 650 15 Modeling of Data 656 15.0 Introduction 656 15.1 Least Squares as a Maximum Likelihood Estimator 657 15.2 Fitting Data to a Straight Line 661 15.3 Straight-Line Data with Errors in Both Coordinates 666 15.4 General Linear Least Squares 671 15.5 Nonlinear Models 681
viii Contents Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 11.6 The QR Algorithm for Real Hessenberg Matrices 486 11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration 493 12 Fast Fourier Transform 496 12.0 Introduction 496 12.1 Fourier Transform of Discretely Sampled Data 500 12.2 Fast Fourier Transform (FFT) 504 12.3 FFT of Real Functions, Sine and Cosine Transforms 510 12.4 FFT in Two or More Dimensions 521 12.5 Fourier Transforms of Real Data in Two and Three Dimensions 525 12.6 External Storage or Memory-Local FFTs 532 13 Fourier and Spectral Applications 537 13.0 Introduction 537 13.1 Convolution and Deconvolution Using the FFT 538 13.2 Correlation and Autocorrelation Using the FFT 545 13.3 Optimal (Wiener) Filtering with the FFT 547 13.4 Power Spectrum Estimation Using the FFT 549 13.5 Digital Filtering in the Time Domain 558 13.6 Linear Prediction and Linear Predictive Coding 564 13.7 Power Spectrum Estimation by the Maximum Entropy (All Poles) Method 572 13.8 Spectral Analysis of Unevenly Sampled Data 575 13.9 Computing Fourier Integrals Using the FFT 584 13.10 Wavelet Transforms 591 13.11 Numerical Use of the Sampling Theorem 606 14 Statistical Description of Data 609 14.0 Introduction 609 14.1 Moments of a Distribution: Mean, Variance, Skewness, and So Forth 610 14.2 Do Two Distributions Have the Same Means or Variances? 615 14.3 Are Two Distributions Different? 620 14.4 Contingency Table Analysis of Two Distributions 628 14.5 Linear Correlation 636 14.6 Nonparametric or Rank Correlation 639 14.7 Do Two-Dimensional Distributions Differ? 645 14.8 Savitzky-Golay Smoothing Filters 650 15 Modeling of Data 656 15.0 Introduction 656 15.1 Least Squares as a Maximum Likelihood Estimator 657 15.2 Fitting Data to a Straight Line 661 15.3 Straight-Line Data with Errors in Both Coordinates 666 15.4 General Linear Least Squares 671 15.5 Nonlinear Models 681
Contents ix 15.6 Confidence Limits on Estimated Model Parameters 689 15.7 Robust Estimation 699 16 Integration of Ordinary Differential Equations 707 16.0 Introduction 707 16.1 Runge-Kutta Method 710 16.2 Adaptive Stepsize Control for Runge-Kutta 714 16.3 Modified Midpoint Method 722 16.4 Richardson Extrapolation and the Bulirsch-Stoer Method 724 16.5 Second-Order Conservative Equations 732 16.6 Stiff Sets of Equations 734 16.7 Multistep,Multivalue,and Predictor-Corrector Methods 747 虽 from NUMERICAL RECIPES IN C: 19881992 17 Two Point Boundary Value Problems 753 17.0 Introduction 753 17.1 The Shooting Method 757 17.2 Shooting to a Fitting Point 760 17.3 Relaxation Methods 762 17.4 A Worked Example:Spheroidal Harmonics 772 (North America 州bMe se users to make one paper THE 17.5 Automated Allocation of Mesh Points 783 17.6 Handling Internal Boundary Conditions or Singular Points 784 9 Programs 18 Integral Equations and Inverse Theory 788 strictly proh 18.0 Introduction 788 18.1 Fredholm Equations of the Second Kind 791 18.2 Volterra Equations 794 18.3 Integral Equations with Singular Kernels 797 18.4 Inverse Problems and the Use of A Priori Information 804 18.5 Linear Regularization Methods 808 18.6 Backus-Gilbert Method 815 18.7 Maximum Entropy Image Restoration 818 1988-1992 by Numerical Recipes ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) 19 Partial Differential Equations 827 19.0 Introduction 827 19.1 Flux-Conservative Initial Value Problems 834 (outside 19.2 Diffusive Initial Value Problems 847 19.3 Initial Value Problems in Multidimensions 853 North Software. 19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 857 19.5 Relaxation Methods for Boundary Value Problems 863 19.6 Multigrid Methods for Boundary Value Problems 871 20 Less-Numerical Algorithms 889 20.0 Introduction 889 20.1 Diagnosing Machine Parameters 889 20.2 Gray Codes 894
Contents ix Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 15.6 Confidence Limits on Estimated Model Parameters 689 15.7 Robust Estimation 699 16 Integration of Ordinary Differential Equations 707 16.0 Introduction 707 16.1 Runge-Kutta Method 710 16.2 Adaptive Stepsize Control for Runge-Kutta 714 16.3 Modified Midpoint Method 722 16.4 Richardson Extrapolation and the Bulirsch-Stoer Method 724 16.5 Second-Order Conservative Equations 732 16.6 Stiff Sets of Equations 734 16.7 Multistep, Multivalue, and Predictor-Corrector Methods 747 17 Two Point Boundary Value Problems 753 17.0 Introduction 753 17.1 The Shooting Method 757 17.2 Shooting to a Fitting Point 760 17.3 Relaxation Methods 762 17.4 A Worked Example: Spheroidal Harmonics 772 17.5 Automated Allocation of Mesh Points 783 17.6 Handling Internal Boundary Conditions or Singular Points 784 18 Integral Equations and Inverse Theory 788 18.0 Introduction 788 18.1 Fredholm Equations of the Second Kind 791 18.2 Volterra Equations 794 18.3 Integral Equations with Singular Kernels 797 18.4 Inverse Problems and the Use of A Priori Information 804 18.5 Linear Regularization Methods 808 18.6 Backus-Gilbert Method 815 18.7 Maximum Entropy Image Restoration 818 19 Partial Differential Equations 827 19.0 Introduction 827 19.1 Flux-Conservative Initial Value Problems 834 19.2 Diffusive Initial Value Problems 847 19.3 Initial Value Problems in Multidimensions 853 19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems 857 19.5 Relaxation Methods for Boundary Value Problems 863 19.6 Multigrid Methods for Boundary Value Problems 871 20 Less-Numerical Algorithms 889 20.0 Introduction 889 20.1 Diagnosing Machine Parameters 889 20.2 Gray Codes 894
Contents 20.3 Cyclic Redundancy and Other Checksums 896 20.4 Huffman Coding and Compression of Data 903 20.5 Arithmetic Coding 910 20.6 Arithmetic at Arbitrary Precision 915 References 926 Appendix A:Table of Prototype Declarations 930 http://www.nr. Permission is readable files Appendix B:Utility Routines 940 Appendix C:Complex Arithmetic 948 .com or call 1-800-872- (including this one) Index of Programs and Dependencies 951 General Index 965 -7423 (North America only),orsend email to directcustserv@cambridge.org (outside North America). granted for internet users to make one paper copy for their own Copyright(C)1988-1992 by Cambridge University Press.Programs Copyright(C)1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C:THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)
x Contents Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 20.3 Cyclic Redundancy and Other Checksums 896 20.4 Huffman Coding and Compression of Data 903 20.5 Arithmetic Coding 910 20.6 Arithmetic at Arbitrary Precision 915 References 926 Appendix A: Table of Prototype Declarations 930 Appendix B: Utility Routines 940 Appendix C: Complex Arithmetic 948 Index of Programs and Dependencies 951 General Index 965
Preface to the Second Edition Our aim in writing the original edition of Numerical Recipes was to provide a book that combined general discussion,analytical mathematics,algorithmics,and actual 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 book that is informal.fearlessly editorial.unesoteric.and above all useful.There is a danger 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 have the benefit of direct feedback from a large reader community.Letters to our alter-ego enterprise,Numerical Recipes Software,are in the thousands per year.(Please,don't telephone us.Our post office box has become a magnet for letters pointing out that we have omitted some particular technique,well known to be important in a particular field of science or engineering.We value such letters,and digest them carefully,especially when they point us to specific references in the literature. 三多 The inevitable result of this input is that this Second Edition of Numerical Recipes is substantially larger than its predecessor,in fact about 50%larger both in 9苏 words 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 wise colleagues.We have tried to follow the intended spirit of that advice,even as we g violate the letter of it.We have not lengthened,or increased in difficulty,the book's principal discussions of mainstream topics.Many new topics are presented at this same accessible level.Some topics,both from the earlier edition and new to this one,are now set in smaller type that labels them as being"advanced."The reader 6 who ignores such advanced sections completely will not,we think.find any lack of continuity in the shorter volume that results. 92y 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 partial differential equations routines for band diagonal linear systems ecipes .improved routines for linear algebra on sparse matrices .Cholesky and OR decomposition (outside orthogonal polynomials and Gaussian quadratures for arbitrary weight North Software. functions methods for calculating numerical derivatives Pade approximants,and rational Chebyshev approximation America). Bessel functions,and modified Bessel functions,of fractional order;and several other new special functions improved random number routines quasi-random sequences routines for adaptive and recursive Monte Carlo integration in high- dimensional spaces globally convergent methods for sets of nonlinear equations Xi
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). Preface to the Second Edition Our aim in writing the original edition of Numerical Recipes was to provide a book that combined general discussion, analytical mathematics, algorithmics, and actual 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 book that is informal, fearlessly editorial, unesoteric, and above all useful. There is a danger 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 have the benefit of direct feedback from a large reader community. Letters to our alter-ego enterprise, Numerical Recipes Software, are in the thousands per year. (Please, don’t telephone us.) Our post office box has become a magnet for letters pointing out that we have omitted some particular technique, well known to be important in a particular field of science or engineering. We value such letters, and digest them carefully, especially when they point us to specific references in the literature. The inevitable result of this input is that this Second Edition of Numerical Recipes is substantially larger than its predecessor, in fact about 50% larger both in words 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 wise colleagues. We have tried to follow the intended spirit of that advice, even as we violate the letter of it. We have not lengthened, or increased in difficulty, the book’s principal discussions of mainstream topics. Many new topics are presented at this same accessible level. Some topics, both from the earlier edition and new to this one, are now set in smaller type that labels them as being “advanced.” The reader who ignores such advanced sections completely will not, we think, find any lack of continuity 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 partial differential 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 weight functions • methods for calculating numerical derivatives • Pade approximants, and rational Chebyshev approximation ´ • Bessel functions, and modified Bessel functions, of fractional order; and several 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 equations xi
xii Preface to the Second Edition simulated annealing minimization for continuous control spaces fast Fourier transform(FFT)for real data in two and three dimensions fast Fourier transform (FFT)using external storage improved fast cosine transform routines wavelet transforms Fourier integrals with upper and lower limits spectral analysis on unevenly sampled data .Savitzky-Golay smoothing filters fitting straight line data with errors in both coordinates a two-dimensional Kolmogorov-Smirnoff test the statistical bootstrap method 8 embedded Runge-Kutta-Fehlberg methods for differential equations 虽 nted for high-order methods for stiff differential equations a new chapter on "less-numerical"algorithms,including Huffman and arithmetic coding,arbitrary precision arithmetic,and several other topics. Consult the Preface to the First Edition,following,or the Table of Contents,for a list of the more "basic"subjects treated. Acknowledgments It is not possible for us to list by name here all the readers who have made useful suggestions;we are grateful for these.In the text,we attempt to give specific attribution for ideas that appear to be original,and not known in the literature.We apologize in advance for any omissions. 三笪∽的 Some readers and colleagues have been particularly generous in providing OF SCIENTIFIC us with ideas,comments,suggestions,and programs for this Second Edition. We especially want to thank George Rybicki,Philip Pinto,Peter Lepage,Robert 6 Lupton,Douglas Eardley,Ramesh Narayan,David Spergel,Alan Oppenheim,Sallie Baliunas,Scott Tremaine,Glennys Farrar,Steven Block,John Peacock,Thomas Loredo,Matthew Choptuik,Gregory Cook,L.Samuel Finn,P.Deuflhard,Harold Lewis,Peter Weinberger,David Syer,Richard Ferch,Steven Ebstein,Bradley Keister,and William Gould.We have been helped by Nancy Lee Snyder's mastery 70入。公 Recipes Numerica 10621 of a complicated TEX manuscript.We express appreciation to our editors Lauren Cowles and Alan Harvey at Cambridge University Press,and to our production editor Russell Hahn.We remain,of course,grateful to the individuals acknowledged in 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 in its FORTRAN-language twin and the companion Example books.Our project has benefited enormously from Seth's talent for detecting,and following the trail of,even very slight anomalies (often compiler bugs,but occasionally our errors),and from his good programming sense.To the extent that this edition of Numerical Recipes in C has a more graceful and "C-like"programming style than its predecessor,most of the credit goes to Seth.(Of course,we accept the blame for the FORTRANish lapses that still remain.) We prepared this book for publication on DEC and Sun workstations run- ning the UNIX operating system,and on a 486/33 PC compatible running MS-DOS 5.0/Windows 3.0.(See $1.0 for a list of additional computers used in
xii Preface to the Second Edition Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). • simulated annealing minimization for continuous control spaces • fast Fourier transform (FFT) for real data in two and three dimensions • fast Fourier transform (FFT) using external storage • improved fast cosine transform routines • wavelet transforms • Fourier integrals with upper and lower limits • spectral analysis on unevenly sampled data • Savitzky-Golay smoothing filters • fitting straight line data with errors in both coordinates • a two-dimensional Kolmogorov-Smirnoff test • the statistical bootstrap method • embedded Runge-Kutta-Fehlberg methods for differential equations • high-order methods for stiff differential equations • a new chapter on “less-numerical” algorithms, including Huffman and arithmetic coding, arbitrary precision arithmetic, and several other topics. Consult the Preface to the First Edition, following, or the Table of Contents, for a list of the more “basic” subjects treated. Acknowledgments It is not possible for us to list by name here all the readers who have made useful suggestions; we are grateful for these. In the text, we attempt to give specific attribution for ideas that appear to be original, and not known in the literature. We apologize in advance for any omissions. Some readers and colleagues have been particularly generous in providing us with ideas, comments, suggestions, and programs for this Second Edition. We especially want to thank George Rybicki, Philip Pinto, Peter Lepage, Robert Lupton, Douglas Eardley, Ramesh Narayan, David Spergel, Alan Oppenheim, Sallie Baliunas, Scott Tremaine, Glennys Farrar, Steven Block, John Peacock, Thomas Loredo, Matthew Choptuik, Gregory Cook, L. Samuel Finn, P. Deuflhard, Harold Lewis, Peter Weinberger, David Syer, Richard Ferch, Steven Ebstein, Bradley Keister, and William Gould. We have been helped by Nancy Lee Snyder’s mastery of a complicated TEX manuscript. We express appreciation to our editors Lauren Cowles and Alan Harvey at Cambridge University Press, and to our production editor Russell Hahn. We remain, of course, grateful to the individuals acknowledged in 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 in its FORTRAN-language twin and the companion Example books. Our project has benefited enormously from Seth’s talent for detecting, and following the trail of, even very slight anomalies (often compiler bugs, but occasionally our errors), and from his good programming sense. To the extent that this edition of Numerical Recipes in C has a more graceful and “C-like” programming style than its predecessor, most of the credit goes to Seth. (Of course, we accept the blame for the FORTRANish lapses 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 running MS-DOS 5.0/Windows 3.0. (See §1.0 for a list of additional computers used in