C++数值算法（英文版）

1 Preliminaries

1.0 Introduction

1.1 Program Organization and Control Structures

1.2 Some C++ Conventions for Scientific Computing

1.3 Imptementation of the Vector and Matrix Classes

1.4 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 N3 Process?

3 Interpolation and Extrapolation

3.0 Introduction

3.1 Polyaomial Interpolation and Extrapolation

3.2 Rational Function Interpolation and Extrapolation

3.3 Cubic Spline Interpolation

3.4 How to Search an Ordered Table

3.5 Coefficients of the Interpolating Polynomial

3.6 Interpolation in Two or More Dimensions

4 Integration of Functions

4.O Introduction

4.1 Classical Formulas for Equally Spaced Abscissas

4.2 Elementary Algorithms

4.3 Romberg Integration

4.4 Improper Integrals

4.5 Gaussian Quadratures and Orthogonal Polynomials

4.6 Multidimensional Integrals

5 Evaluation of Functions

5.0 Introduction

5.1 Series and Their Convergence

5.2 Evaluation of Continued Fractions

5.3 Polynomials and Rational Functions

5.4 Complex Arithmetic

5.5 Recurrence Relations and Clenshaw's Recurrence Formula

5.6 Quadratic and Cubic Equations

5.7 Numerical Derivatives

5.8 Chebyshev Approximation

5.9 Derivatives or Integrals of a Chebyshev-approximated Function

3.10 Polynomial Approximation from Chebyshev Coefficients

5.11 Economization of Power Series

5.12 Pade Approximants

5.13 Rational Chebyshev Appmximation

5.14 Evaluation of Functions by Path Integration

6 Speclal Functions

6.0 Introduction

6.1 Gamma Function, Beta Function, Factorials. Binomial Coefficients

6.2 Incomplete Gamma Function, Error Function. Chi-Square Probability Function, Cumulative Poisson Function

6.3 Exponential Integrals

6.4 Incomplete Beta Function, Student's Distribution, F-Distribution Cumulative Binomial Distribution

6.5 Bessel Functions of Integer Order

6.6 Modified Bessel Functions of Integer Order

6.7 Bessel Functions of Fractional Order, Airy Functions, Spherical Bessel Functions

6.8 Spherical Harmonics

6.9 Fresnel Integrals, Cosine and Sine Integrals

6.10 Dawson's Inegral

6.ll Elliptic Integrals and Jacobian Elliptic Functions

6.12 Hypergeometric Functions

7 Random Numbers

7.O Introduction

7.1 Uniform Deviates

7.2 Transformation Method: Exponential and Normal Deviates

7.3 Rejection Method: Gamma. Poisson, Binomial Deviates

7.4 Generation of Random Bits

7.5 Random Sequences Based on Data Encryption

7.6 Simple Monte Carlo Integration

7.7 Quasi- (that is, Sub-) Random Sequences

7.8 Adaptive and Recursive Monte Carlo Methods

8 Sorting

8.0 Introduction

8.1 Straight Insertion and Shell's Method

8.2 Quicksort

8.3 Heapsort

8.4 Indexing and Ranking

8.5 Selecting the Mth Largest

8.6 Determination of Equivalence Classes

9 Root Finding and Nonlinear Sets of Equations

9.0 Introduction

9.l Bracketing and Bisection

9.2 Secant Method, False Position Method, and Ridders' Method

9.3 Van Wijngaarden-Dekker-Brent Method

9.4 Newton-Raphson Metkod Using Derivative

9.5 Roots of Polynomials

9.6 Newton-Raphson Mealod for Nonlinear Systems of Equations

9.7 Globally Convergent Methods for Nonlinear Systems of Equations

10 Minimization or Maximization of Functions

10.0 Introduction

10.1 Golden Section Search in One Dimension

10.2 Parabolic lnterpolation and Brent's Method in One Dimension

10.3 One-Dimensional Search with First Derivatives

10.4 Downhill Simplex Method in Multidimensions

10.5 Direction Set (Powell's) Methods in Multidimensions

10.6 Conjugate Gadient Methods in Multidimensions

10.7 Variable Metric Methods in Multidimensions

10.8 Linear Pro

10.9 Simulated Annealing Meathods

11 Eigensystems

11.0 Introduction

11.1 Jacobi Transformations of a Symmetric Matrix

11.2 Reduction of a Symmetric Matrix to Tridiagonal Form

Givens and Householder Reductions

11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix

11.4 Hermitian Matrices

11.5 Reduction of a General Matrix to Hessenberg Form

11.6 The QR Algorithm for Real Hessenbery Matrices

11.7 Improving Eigenvalues and/or Finding Eigenvectors by

Inverse Iteration

12 Fast Fourier Transform

12.0 Introduction

12.1 Fourier Transform of Discretely Sampled Data

12.2 Fast Fourier Transform (FFT)

12.3 FFT of Real Functions, Sine and Cosine Transforms

12.4 FFT in Two or More Dimensions

12.5 Fourier Transforms of Real Data in Two and Three Dimensions

12.6 External Storage or Memory-Local FFTs

13 Fourier and Spectral Applications

13.0 Introduction

13.1 Convolution and Deconvolution Using the FFT

13.2 Correlation and Autocorrelation Using the FFT

13.3 Optimal (Wiener) Filterin with the FFT

13.4 Power Spectrum Estimation Using the FFT

13.5 Digital Filtering in ahe Time Domain

13.6 Linear Prediction and Linear Predictive Coding

13.7 Power Spectrum Estimation by the Maximum Entropy

(All Poles) Method

13.8 Spectral Analysis of Unevenly Sampled Data

13.9 Computing Fourier Integrals Using Ule FFT

13.10 Wavelet Transforms

13.11 Numerical Use of the Sampling Theorem

14 Statistical Deseription of Data

14.O Introduction

14.1 Moments of a Distribution: Mean, Variance, Skewness,

and So Forth

14.2 Do Two Distributions Have the Same Means or Variances?

14.3 Are Two Distributions Different?

14.4 Contingency Table Analysis of Two Distributions

14.5 Linear Correlation

14.6 Nonparametric or Rank Correlation

14.7 Do Two-Dimensional Distributions Differ?

14.8 Savitzky-Golay Smoothing Filters

15 Modeling of Data

15.0 Introduction

15.1 Least Squares as a Maximum Likelihood Estimator

15.2 Fitting Data to a Straight Line

15.3 Straight-Line Data with Errors in Both Coordinates

15.4 General Linear Least Squares

15.5 Nonlinear Models

15.6 Confidence Limits on Estimated Model Parameters

15.7 Robust Estimation

16 Integration of Ordinary Differential Equations

l6.0 Introduction

16.1 Runge-Kutta Method

16.2 Adaptive Stepsize Control for Runge-Kutta

16.3 Modified Midpoint Mealod

16.4 Richardson Extrapolation and the Bulirsch-Stoer Method

16.5 Second-Order Conservative Equations

16.6 Stiff Sets of Equations

l6.7 Multistep, Multivalue, and Predictor-Corrector Methods

17 Two Point Boundary Value Problems

17.O Introdnction

17.1 The Shooting Method

17.2 Shooting to a Fitting Point

17.3 Relaxation Methods

17.4 A Worked Example: Spheroidal Harmonics

17.5 Automated Allocation of Mesh Points

17.6 Handling Internal Boundary Conditions or Singular Points

18 Integral Equations and Inverse Theory

18.0 Introduction

18.1 Fredholm Equations of the Second Kind

18.2 Volterra Equations

18.3 Integral Equations with Singular Kernels

18.4 Inverse Problems and the Use of A Priori Information

18.5 Linear Regularization Methods

18.6 Backus-Gilbert Method

18.7 Maximum Entropy Image Restoration

19 Partial Differential Equations

19.0 Introduction

19.1 Flux-Conservative Initial Value Problems

19.2 Diffusive Initial Value Problems

19.3 Initial Value Problems in Multidimensions

19.4 Fourier and Cyclic Reduction Methods for Boundary

Value Problems

19.5 Relaxation Methods for Boundary Value Problems

19.6 Multigrid Methods for Boundary Value Problems

20 Less-Numerical Algorithms

20.0 Introduction

20.1 Diagnosing Machine Parameters

20.2 Gray Codes

20.3 Cyclic Redundancy and Other Checksums

20.4 Huffman Coding and Compression of Data

20.5 Arithmetic Coding

20.6 Arithmetic at Arbitrary Precision

References

Appendix A: Table of Funetion Declarations

Appendix B: Utility Routines and Classes

Appendix C: Convetring to Single Precision

Index of Programs and Dependencies

General Index