Part Ⅰ Numerical Methods 3
1 Error Analysis 3
1.1 Machine Numbers and Rounding Errors 3
1.2 Numerical Errors of Elementary Floating Point Operations 6
1.2.1 Numerical Extinction 7
1.2.2 Addition 8
1.2.3 Multiplication 9
1.3 Error Propagation 9
1.4 Stability of Iterative Algorithms 11
1.5 Example：Rotation 12
1.6 Truncation Error 13
1.7 Problems 14
2 Interpolation 15
2.1 Interpolating Functions 15
2.2 Polynomial Interpolation 16
2.2.1 Lagrange Polynomials 17
2.2.2 Barycentric Lagrange Interpolation 17
2.2.3 Newton's Divided Differences 18
2.2.4 Neville Method 20
2.2.5 Error of Polynomial Interpolation 21
2.3 Spline Interpolation 22
2.4 Rational Interpolation 25
2.4.1 PadéApproximant 25
2.4.2 Barycentric Rational Interpolation 27
2.5 Multivariate Interpolation 32
2.6 Problems 33
3 Numerical Differentiation 37
3.1 One-Sided Difference Quotient 37
3.2 Central Difference Quotient 38
3.3 Extrapolation Methods 39
3.4 Higher Derivatives 41
3.5 Partial Derivatives of Multivariate Functions 42
3.6 Problems 43
4 Numerical Integration 45
4.1 Equidistant Sample Points 46
4.1.1 Closed Newton-Cotes Formulae 46
4.1.2 Open Newton-Cotes Formulae 48
4.1.3 Composite Newton-Cotes Rules 48
4.1.4 Extrapolation Method（Romberg Integration） 49
4.2 Optimized Sample Points 50
4.2.1 Clenshaw-Curtis Expressions 50
4.2.2 Gaussian Integration 52
4.3 Problems 56
5 Systems of Inhomogeneous Linear Equations 59
5.1 Gaussian Elimination Method 60
5.1.1 Pivoting 63
5.1.2 Direct LU Decomposition 63
5.2 QR Decomposition 64
5.2.1 QR Decomposition by Orthogonalization 64
5.2.2 QR Decomposition by Householder Reflections 66
5.3 Linear Equations with Tridiagonal Matrix 69
5.4 Cyclic Tridiagonal Systems 71
5.5 Iterative Solution of Inhomogeneous Linear Equations 73
5.5.1 General Relaxation Method 73
5.5.2 Jacobi Method 73
5.5.3 Gauss-Seidel Method 74
5.5.4 Damping and Successive Over-Relaxation 75
5.6 Conjugate Gradients 76
5.7 Matrix Inversion 77
5.8 Problems 78
6 Roots and Extremal Points 83
6.1 Root Finding 83
6.1.1 Bisection 84
6.1.2 Regula Falsi（False Position）Method 85
6.1.3 Newton-Raphson Method 85
6.1.4 Secant Method 86
6.1.5 Interpolation 87
6.1.6 Inverse Interpolation 88
6.1.7 Combined Methods 91
6.1.8 Multidimensional Root Finding 97
6.1.9 Quasi-Newton Methods 98
6.2 Function Minimization 99
6.2.1 The Ternary Search Method 99
6.2.2 The Golden Section Search Method（Brent's Method） 101
6.2.3 Minimization in Multidimensions 106
6.2.4 Steepest Descent Method 106
6.2.5 Conjugate Gradient Method 107
6.2.6 Newton-Raphson Method 107
6.2.7 Quasi-Newton Methods 108
6.3 Problems 110
7 Fourier Transformation 113
7.1 Fourier Integral and Fourier Series 113
7.2 Discrete Fourier Transformation 114
7.2.1 Trigonometric Interpolation 116
7.2.2 Real Valued Functions 118
7.2.3 Approximate Continuous Fourier Transformation 119
7.3 Fourier Transform Algorithms 120
7.3.1 Goertzel's Algorithm 120
7.3.2 Fast Fourier Transformation 121
7.4 Problems 125
8 Random Numbers and Monte Carlo Methods 127
8.1 Some Basic Statistics 127
8.1.1 Probability Density and Cumulative Probability Distribution 127
8.1.2 Histogram 128
8.1.3 Expectation Values and Moments 129
8.1.4 Example：Fair Die 130
8.1.5 Normal Distribution 131
8.1.6 Multivariate Distributions 132
8.1.7 Central Limit Theorem 133
8.1.8 Example：Binomial Distribution 133
8.1.9 Average of Repeated Measurements 134
8.2 Random Numbers 135
8.2.1 Linear Congruent Mapping 135
8.2.2 Marsaglia-Zamann Method 135
8.2.3 Random Numbers with Given Distribution 136
8.2.4 Examples 136
8.3 Monte Carlo Integration 138
8.3.1 Numerical Calculation ofπ 138
8.3.2 Calculation of an Integral 139
8.3.3 More General Random Numbers 140
8.4 Monte Carlo Method for Thermodynamic Averages 141
8.4.1 Simple Sampling 141
8.4.2 Importance Sampling 142
8.4.3 Metropolis Algorithm 142
8.5 Problems 144
9 Eigenvalue Problems 147
9.1 Direct Solution 148
9.2 Jacobi Method 148
9.3 Tridiagonal Matrices 150
9.3.1 Characteristic Polynomial of a Tridiagonal Matrix 151
9.3.2 Special Tridiagonal Matrices 151
9.3.3 The QL Algorithm 156
9.4 Reduction to a Tridiagonal Matrix 157
9.5 Large Matrices 159
9.6 Problems 160
10 Data Fitting 161
10.1 Least Square Fit 162
10.1.1 Linear Least Square Fit 163
10.1.2 Linear Least Square Fit with Orthogonalization 165
10.2 Singular Value Decomposition 167
10.2.1 Full Singular Value Decomposition 168
10.2.2 Reduced Singular Value Decomposition 168
10.2.3 Low Rank Matrix Approximation 170
10.2.4 Linear Least Square Fit with Singular Value Decomposition 172
10.3 Problems 175
11 Discretization of Differential Equations 177
11.1 Classification of Differential Equations 178
11.1.1 Linear Second Order PDE 178
11.1.2 Conservation Laws 179
11.2 Finite Differences 180
11.2.1 Finite Differences in Time 181
11.2.2 Stability Analysis 182
11.2.3 Method of Lines 183
11.2.4 Eigenvector Expansion 183
11.3 Finite Volumes 185
11.3.1 Discretization of fluxes 188
11.4 Weighted Residual Based Methods 190
11.4.1 Point Collocation Method 191
11.4.2 Sub-domain Method 191
11.4.3 Least Squares Method 192
11.4.4 Galerkin Method 192
11.5 Spectral and Pseudo-spectral Methods 193
11.5.1 Fourier Pseudo-spectral Methods 193
11.5.2 Example：Polynomial Approximation 194
11.6 Finite Elements 196
11.6.1 One-Dimensional Elements 196
11.6.2 Two-and Three-Dimensional Elements 197
11.6.3 One-Dimensional Galerkin FEM 201
11.7 Boundary Element Method 204
12 Equations of Motion 207
12.1 The State Vector 208
12.2 Time Evolution of the State Vector 209
12.3 Explicit Forward Euler Method 210
12.4 Implicit Backward Euler Method 212
12.5 Improved Euler Methods 213
12.6 Taylor Series Methods 215
12.6.1 Nordsieck Predictor-Corrector Method 215
12.6.2 Gear Predictor-Corrector Methods 217
12.7 Runge-Kutta Methods 217
12.7.1 Second Order Runge-Kutta Method 218
12.7.2 Third Order Runge-Kutta Method 218
12.7.3 Fourth Order Runge-Kutta Method 219
12.8 Quality Control and Adaptive Step Size Control 220
12.9 Extrapolation Methods 221
12.10 Linear Multistep Methods 222
12.10.1 Adams-Bashforth Methods 222
12.10.2 Adams-Moulton Methods 223
12.10.3 Backward Differentiation（Gear）Methods 223
12.10.4 Predictor-Corrector Methods 224
12.11 Verlet Methods 225
12.11.1 Liouville Equation 225
12.11.2 Split-Operator Approximation 226
12.11.3 Position Verlet Method 227
12.11.4 Velocity Verlet Method 227
12.11.5 St？rmer-Verlet Method 228
12.11.6 Error Accumulation for the St？rmer-Verlet Method 229
12.11.7 Beeman's Method 230
12.11.8 The Leapfrog Method 231
12.12 Problems 232
Part Ⅱ Simulation of Classical and Quantum Systems 239
13 Rotational Motion 239
13.1 Transformation to a Body Fixed Coordinate System 239
13.2 Properties of the Rotation Matrix 240
13.3 Properties of W,Connection with the Vector of Angular Velocity 242
13.4 Transformation Properties of the Angular Velocity 244
13.5 Momentum and Angular Momentum 246
13.6 Equations of Motion of a Rigid Body 246
13.7 Moments of Inertia 247
13.8 Equations of Motion for a Rotor 248
13.9 Explicit Methods 248
13.10 Loss of Orthogonality 250
13.11 Implicit Method 251
13.12 Kinetic Energy of a Rotor 255
13.13 Parametrization by Euler Angles 255
13.14 Cayley-Klein Parameters,Quaternions,Euler Parameters 256
13.15 Solving the Equations of Motion with Quaternions 259
13.16 Problems 260
14 Molecular Mechanics 263
14.1 Atomic Coordinates 264
14.2 Force Fields 266
14.2.1 Intramolecular Forces 267
14.2.2 Intermolecular Interactions 269
14.3 Gradients 270
14.4 Normal Mode Analysis 274
14.4.1 Harmonic Approximation 274
14.5 Problems 276
15 Thermodynamic Systems 279
15.1 Simulation of a Lennard-Jones Fluid 279
15.1.1 Integration of the Equations of Motion 280
15.1.2 Boundary Conditions and Average Pressure 281
15.1.3 Initial Conditions and Average Temperature 281
15.1.4 Analysis of the Results 282
15.2 Monte Carlo Simulation 287
15.2.1 One-Dimensional Ising Model 287
15.2.2 Two-Dimensional Ising Model 289
15.3 Problems 290
16 Random Walk and Brownian Motion 293
16.1 Markovian Discrete Time Models 293
16.2 Random Walk in One Dimension 294
16.2.1 Random Walk with Constant Step Size 295
16.3 The Freely Jointed Chain 296
16.3.1 Basic Statistic Properties 297
16.3.2 Gyration Tensor 299
16.3.3 Hookean Spring Model 300
16.4 Langevin Dynamics 301
16.5 Problems 303
17 Electrostatics 305
17.1 Poisson Equation 305
17.1.1 Homogeneous Dielectric Medium 306
17.1.2 Numerical Methods for the Poisson Equation 307
17.1.3 Charged Sphere 309
17.1.4 Variable ε 311
17.1.5 Discontinuous ε 313
17.1.6 Solvation Energy of a Charged Sphere 314
17.1.7 The Shifted Grid Method 314
17.2 Poisson-Boltzmann Equation 315
17.2.1 Linearization of the Poisson-Boltzmann Equation 317
17.2.2 Discretization of the Linearized Poisson-Boltzmann Equation 318
17.3 Boundary Element Method for the Poisson Equation 318
17.3.1 Integral Equations for the Potential 318
17.3.2 Calculation of the Boundary Potential 321
17.4 Boundary Element Method for the Linearized Poisson-Boltzmann Equation 324
17.5 Electrostatic Interaction Energy（Onsager Model） 325
17.5.1 Example：Point Charge in a Spherical Cavity 326
17.6 Problems 327
18 Waves 329
18.1 Classical Waves 329
18.2 Spatial Discretization in One Dimension 332
18.3 Solution by an Eigenvector Expansion 334
18.4 Discretization of Space and Time 337
18.5 Numerical Integration with a Two-Step Method 338
18.6 Reduction to a First Order Differential Equation 340
18.7 Two-Variable Method 343
18.7.1 Leapfrog Scheme 343
18.7.2 Lax-Wendroff Scheme 345
18.7.3 Crank-Nicolson Scheme 347
18.8 Problems 349
19 Diffusion 351
19.1 Particle Flux and Concentration Changes 351
19.2 Diffusion in One Dimension 353
19.2.1 Explicit Euler（Forward Time Centered Space）Scheme 353
19.2.2 Implicit Euler（Backward Time Centered Space）Scheme 355
19.2.3 Crank-Nicolson Method 357
19.2.4 Error Order Analysis 358
19.2.5 Finite Element Discretization 360
19.3 Split-Operator Method for Multidimensions 360
19.4 Problems 362
20 Nonlinear Systems 363
20.1 Iterated Functions 364
20.1.1 Fixed Points and Stability 364
20.1.2 The Lyapunov Exponent 366
20.1.3 The Logistic Map 367
20.1.4 Fixed Points of the Logistic Map 367
20.1.5 Bifurcation Diagram 369
20.2 Population Dynamics 370
20.2.1 Equilibria and Stability 370
20.2.2 The Continuous Logistic Model 371
20.3 Lotka-Volterra Model 372
20.3.1 Stability Analysis 372
20.4 Functional Response 373
20.4.1 Holling-Tanner Model 375
20.5 Reaction-Diffusion Systems 378
20.5.1 General Properties of Reaction-Diffusion Systems 378
20.5.2 Chemical Reactions 378
20.5.3 Diffusive Population Dynamics 379
20.5.4 Stability Analysis 379
20.5.5 Lotka-Volterra Model with Diffusion 380
20.6 Problems 382
21 Simple Quantum Systems 385
21.1 Pure and Mixed Quantum States 386
21.1.1 Wavefunctions 387
21.1.2 Density Matrix for an Ensemble of Systems 387
21.1.3 Time Evolution of the Density Matrix 388
21.2 Wave Packet Morion in One Dimension 389
21.2.1 Discretization of the Kinetic Energy 390
21.2.2 Time Evolution 392
21.2.3 Example：Free Wave Packet Morion 402
21.3 Few-State Systems 403
21.3.1 Two-State System 405
21.3.2 Two-State System with Time Dependent Perturbation 408
21.3.3 Superexchange Model 410
21.3.4 Ladder Model for Exponential Decay 412
21.3.5 Landau-Zener Model 414
21.4 The Dissipative Two-State System 416
21.4.1 Equations of Morion for a Two-State System 416
21.4.2 The Vector Model 417
21.4.3 The Spin-1/2 System 418
21.4.4 Relaxation Processes—The Bloch Equations 420
21.4.5 The Driven Two-State System 421
21.4.6 Elementary Qubit Manipulation 428
21.5 Problems 430
Appendix Ⅰ Performing the Computer Experiments 433
Appendix Ⅱ Methods and Algorithms 435
References 441
Index 449