, Sample 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 machine-
readable 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 (outside North America).
Numerical Recipes in C
The Art of Scientific Computing
Cambridge New York Port Chester Melbourne Sydney
CAMBRIDGE UNIVERSITY PRESS
EXXON Research and Engineering Company
Harvard-Smithsonian Center for Astrophysics
Department of Physics, Cornell University
William T. Vetterling
Saul A. Teukolsky
Brian P. Flannery
Second Edition
William H. Press
Polaroid Corporation
,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
http://www.nr.com or call 1-800-872-7423 (North America only), or send email to (outside North America).
readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-
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)
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 “” (North America) or
“” (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 “”,
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 or call 1-800-872-7423 (North America only), or send email to (outside North America).
readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-
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)
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
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 machine-
readable 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 (outside North America).
Numerical Recipes in C
The Art of Scientific Computing
Cambridge New York Port Chester Melbourne Sydney
CAMBRIDGE UNIVERSITY PRESS
EXXON Research and Engineering Company
Harvard-Smithsonian Center for Astrophysics
Department of Physics, Cornell University
William T. Vetterling
Saul A. Teukolsky
Brian P. Flannery
Second Edition
William H. Press
Polaroid Corporation
,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
http://www.nr.com or call 1-800-872-7423 (North America only), or send email to (outside North America).
readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-
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)
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 “” (North America) or
“” (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 “”,
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 or call 1-800-872-7423 (North America only), or send email to (outside North America).
readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-
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)
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
