Press, Teukolsky, Vetterling, Flannery - Numerical Recipesi in C.pdf - algorytmika 1 (JENOT15) - xyzgeo

Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)

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 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

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

Numerical Recipes Software 1987, 1988, 1992, 1997, 2002

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 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. 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 speciﬁcally 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 scientiﬁc 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

Preface to the Second Edition

Preface to the First Edition

xiv

License Information

xvi

Computer Programs by Chapter and Section

xix

1 Preliminaries

1.0 Introduction

1.1 Program Organization and Control Structures

1.2 Some C Conventions for Scientiﬁc Computing

1.3 Error, Accuracy, and Stability

2 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

2.5 Iterative Improvement of a Solution to Linear Equations

2.6 Singular Value Decomposition

2.7 Sparse Linear Systems

2.8 Vandermonde Matrices and Toeplitz Matrices

2.9 Cholesky Decomposition

2.10 QR Decomposition

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 Coefﬁcients of the Interpolating Polynomial

120

3.6 Interpolation in Two or More Dimensions

123

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 Coefﬁcients

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 Coefﬁcients

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 Modiﬁed 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

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

Press, Teukolsky, Vetterling, Flannery - Numerical Recipesi in C.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: