1nrinfo.doc

Delphi Pascal 数据挖掘领域算法包 数值算法大全

                  ABOUT NUMERICAL RECIPES IN PASCAL

This  NUMERICAL RECIPES PASCAL    SHAREWARE DISKETTE  contains  Pascal
procedures originally published as the Pascal Appendix  to the FORTRAN
book NUMERICAL RECIPES: THE ART OF SCIENTIFIC COMPUTING by William  H.
Press, Saul A. Teukolsky, Brian P. Flannery, and William T. Vetterling
(Cambridge   University  Press,  1986),  and   test   driver  programs
originally  published as  the NUMERICAL RECIPES EXAMPLE  BOOK (PASCAL)
(Cambridge  University Press,  1986).  All  procedures and programs on
this disk are   Copyright (C) 1986  by   Numerical  Recipes  Software.
Please read the file NRREADME.DOC to learn the  conditions under which
you may use these programs for free.

The   procedures on  this  diskette are    translations  from FORTRAN.
Subsequently, new versions of all the procedures have been written, in
native Pascal, and a new, all-Pascal  edition of the NUMERICAL RECIPES
book  has been  published.   These new  materials are available, at  a
modest  cost,   from  Cambridge    University   Press.   Here  follows
information on  ordering  the new  materials,   the  book's table   of
contents and list of included programs:

The book, and diskettes of the REVISED (non-shareware) programs can be
ordered by  telephone:  [phone]  [in   NY: 800-227-0247];  or  by
writing Cambridge University Press, 110 Midland  Avenue, Port Chester,
NY 10573.  Current prices at the time of writing are: Book (hardcover)
(37516-9) $44.50.  Diskette (37532-0) $29.95; Example Book (paperback)
(37675-0)  $19.95; Example   Diskette  (37533-9)  $24.95.   NOTE:  The
example book and diskette presume that you also have the main book and
diskette; they are not useful by themselves.

**********************************************************************

TABLE OF CONTENTS and LIST OF PROGRAMS for the book
NUMERICAL RECIPES IN PASCAL: THE ART OF SCIENTIFIC COMPUTING
by William H. Press, Saul A. Teukolsky, Brian P. Flannery,
and William T. Vetterling

Cambridge University Press, New York, 1989.

Copyright (C) 1986, 1989 by Cambridge University Press and
Numerical Recipes Software.

{Preface to the Pascal Edition}{xi}
{Preface}{xiii}
{List of Computer Programs}{xvii}

{1}{PRELIMINARIES}{1}
1.0 Introduction    1
1.1 Program Organization and Control Structures    4
1.2 Conventions for Scientific Computing in Pascal    14
1.3 Error, Accuracy, and Stability    23

{2}{SOLUTION OF LINEAR ALGEBRAIC EQUATIONS}{27}
2.0 Introduction    27
2.1 Gauss-Jordan Elimination    31
2.2 Gaussian Elimination with Backsubstitution    37
2.3 $LU$ Decomposition    39
2.4 Inverse of a Matrix    46
2.5 Determinant of a Matrix    47
2.6 Tridiagonal Systems of Equations    48
2.7 Iterative Improvement of a Solution to Linear Equations    49
2.8 Vandermonde Matrices and Toeplitz Matrices    52
2.9 Singular Value Decomposition    61
2.10 Sparse Linear Systems    74
2.11 Is Matrix Inversion an $N^3$ Process?    84

{3}{INTERPOLATION AND EXTRAPOLATION}{87}
3.0 Introduction    87
3.1 Polynomial Interpolation and Extrapolation    90
3.2 Rational Function Interpolation and Extrapolation    93
3.3 Cubic Spline Interpolation    97
3.4 How to Search an Ordered Table    101
3.5 Coefficients of the Interpolating Polynomial    104
3.6 Interpolation in Two or More Dimensions    107

{4}{INTEGRATION OF FUNCTIONS}{116}
4.0 Introduction    116
4.1 Classical Formulas for Equally-Spaced Abscissas    117
4.2 Elementary Algorithms    124
4.3 Romberg Integration    129
4.4 Improper Integrals    130
4.5 Gaussian Quadratures    138
4.6 Multidimensional Integrals    144

{5}{EVALUATION OF FUNCTIONS}{149}
5.0 Introduction    149
5.1 Series and Their Convergence    150
5.2 Evaluation of Continued Fractions    153
5.3 Polynomials and Rational Functions    155
5.4 Recurrence Relations and Clenshaw's Recurrence Formula    159
5.5 Quadratic and Cubic Equations    163
5.6 Chebyshev Approximation    165
5.7 Derivatives or Integrals of a Chebyshev-approximated Function   170
5.8 Polynomial Approximation from Chebyshev Coefficients    172

{6}{SPECIAL FUNCTIONS}{175}
6.0 Introduction    175
6.1 Gamma Function, Beta Function, Factorials, Binomial
    Coefficients    176
6.2 Incomplete Gamma Function, Error Function, Chi-Square
    Probability Function, Cumulative Poisson Distribution  180
6.3 Incomplete Beta Function, Student's Distribution,
    F$-Distribution, Cumulative Binomial Distribution    186
6.4 Bessel Functions of Integer Order    191
6.5 Modified Bessel Functions of Integer Order    197
6.6 Spherical Harmonics    202
6.7 Elliptic Integrals and Jacobian Elliptic Functions    205

{7}{RANDOM NUMBERS}{212}
7.0 Introduction    212
7.1 Uniform Deviates    213
7.2 Transformation Method: Exponential and Normal Deviates    222
7.3 Rejection Method: Gamma, Poisson, Binomial Deviates    226
7.4 Generation of Random Bits    233
7.5 The Data Encryption Standard    239
7.6 Monte Carlo Integration    249

{8}{SORTING}{254}
8.0 Introduction    254
8.1 Straight Insertion and Shell's Method    255
8.2 Heapsort    258
8.3 Indexing and Ranking    261
8.4 Quicksort    264
8.5 Determination of Equivalence Classes    267


{9}{ROOT FINDING AND NONLINEAR SETS OF EQUATIONS}{270}
9.0 Introduction    270
9.1 Bracketing and Bisection    274
9.2 Secant Method and False Position Method    279
9.3 Van Wijngaarden--Dekker--Brent Method    283
9.4 Newton-Raphson Method Using Derivative    286
9.5 Roots of Polynomials    292
9.6 Newton-Raphson Method for Nonlinear Systems of Equations    305

{10}{MINIMIZATION OR MAXIMIZATION OF FUNCTIONS}{309}
10.0 Introduction    309
10.1 Golden Section Search in One Dimension    312
10.2 Parabolic Interpolation and Brent's Method in One Dimension
   318
10.3 One-Dimensional Search with First Derivatives    322
10.4 Downhill Simplex Method in Multidimensions    326
10.5 Direction Set (Powell's) Methods in Multidimensions    331
10.6 Conjugate Gradient Methods in Multidimensions    339
10.7 Variable Metric Methods in Multidimensions    346
10.8 Linear Programming and the Simplex Method    351
10.9 Combinatorial Minimization: Method of Simulated Annealing   366

{11}{EIGENSYSTEMS}{375}
11.0 Introduction    375
11.1 Jacobi Transformations of a Symmetric Matrix    382
11.2 Reduction of a Symmetric Matrix to Tridiagonal Form:
     Givens and Householder Reductions    389
11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix    397
11.4 Hermitian Matrices    404
11.5 Reduction of a General Matrix to Hessenberg Form    405
11.6 The $QR$ Algorithm for Real Hessenberg Matrices    410
11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse
     Iteration    418

{12}{FOURIER TRANSFORM SPECTRAL METHODS}{422}
12.0 Introduction    422
12.1 Fourier Transform of Discretely Sampled Data    427
12.2 Fast Fourier Transform (FFT)    431
12.3 FFT of Real Functions, Sine and Cosine Transforms    438
12.4 Convolution and Deconvolution Using the FFT    449
12.5 Correlation and Autocorrelation Using the FFT    457
12.6 Optimal (Wiener) Filtering with the FFT    459
12.7 Power Spectrum Estimation Using the FFT    463
12.8 Power Spectrum Estimation by the Maximum Entropy (All Poles)
     Method    473
12.9 Digital Filtering in the Time Domain    478
12.10 Linear Prediction and Linear Predictive Coding    487
12.11 FFT in Two or More Dimensions    493

{13}{STATISTICAL DESCRIPTION OF DATA}{498}
13.0 Introduction    498
13.1 Moments of a Distribution: Mean, Variance, Skewness,
    and so forth     499
13.2 Efficient Search for the Median    503
13.3 Estimation of the Mode for Continuous Data    507
13.4 Do Two Distributions Have the Same Means or Variances?    509
13.5 Are Two Distributions Different?    515
13.6 Contingency Table Analysis of Two Distributions    523
13.7 Linear Correlation    532
13.8 Nonparametric or Rank Correlation    536
13.9 Smoothing of Data    543

{14}{MODELING OF DATA}{547}
14.0 Introduction    547
14.1 Least Squares as a Maximum Likelihood Estimator    548
14.2 Fitting Data to a Straight Line    553
14.3 General Linear Least Squares    558
14.4 Nonlinear Models    572
14.5 Confidence Limits on Estimated Model Parameters    580
14.6 Robust Estimation    590

{15}{INTEGRATION OF ORDINARY DIFFERENTIAL EQUATIONS}{599}
15.0 Introduction    599
15.1 Runge-Kutta Method    602
15.2 Adaptive Stepsize Control for Runge-Kutta    607
15.3 Modified Midpoint Method    614
15.4 Richardson Extrapolation and the Bulirsch-Stoer Method    617
15.5 Predictor-Corrector Methods    624
15.6 Stiff Sets of Equations    628

{16}{TWO POINT BOUNDARY VALUE PROBLEMS}{633}
16.0 Introduction    633
16.1 The Shooting Method    637
16.2 Shooting to a Fitting Point    641
16.3 Relaxation Methods    645
16.4 A Worked Example: Spheroidal Harmonics    658
16.5 Automated Allocation of Mesh Points    666
16.6 Handling Internal Boundary Conditions or Singular Points    669

{17}{PARTIAL DIFFERENTIAL EQUATIONS}{673}
17.0 Introduction    673
17.1 Flux-Conservative Initial Value Problems    681
17.2 Diffusive Initial Value Problems    693
17.3 Initial Value Problems in Multidimensions    700
17.4 Fourier and Cyclic Reduction Methods for Boundary Value
     Problems    704
17.5 Relaxation Methods for Boundary Value Problems    710
17.6 Operator Splitting Methods and ADI    718