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 482Contents 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 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). 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