|
|
|
|
3 | (14) |
|
1.1 Machine Numbers and Rounding Errors |
|
|
3 | (4) |
|
1.2 Numerical Errors of Elementary Floating Point Operations |
|
|
7 | (3) |
|
1.2.1 Numerical Extinction |
|
|
7 | (1) |
|
|
8 | (1) |
|
|
9 | (1) |
|
|
10 | (2) |
|
1.4 Stability of Iterative Algorithms |
|
|
12 | (1) |
|
|
13 | (1) |
|
|
14 | (3) |
|
|
15 | (2) |
|
|
17 | (22) |
|
2.1 Interpolating Functions |
|
|
17 | (2) |
|
2.2 Polynomial Interpolation |
|
|
19 | (5) |
|
2.2.1 Lagrange Polynomials |
|
|
19 | (1) |
|
2.2.2 Barycentric Lagrange Interpolation |
|
|
19 | (2) |
|
2.2.3 Newton's Divided Differences |
|
|
21 | (1) |
|
|
22 | (1) |
|
2.2.5 Error of Polynomial Interpolation |
|
|
23 | (1) |
|
|
24 | (4) |
|
2.4 Rational Interpolation |
|
|
28 | (7) |
|
|
29 | (1) |
|
2.4.2 Barycentric Rational Interpolation |
|
|
30 | (5) |
|
2.5 Multivariate Interpolation |
|
|
35 | (4) |
|
|
37 | (2) |
|
3 Numerical Differentiation |
|
|
39 | (8) |
|
3.1 One-Sided Difference Quotient |
|
|
39 | (2) |
|
3.2 Central Difference Quotient |
|
|
41 | (1) |
|
3.3 Extrapolation Methods |
|
|
41 | (3) |
|
|
44 | (1) |
|
3.5 Partial Derivatives of Multivariate Functions |
|
|
45 | (2) |
|
|
46 | (1) |
|
|
47 | (16) |
|
4.1 Equidistant Sample Points |
|
|
48 | (5) |
|
4.1.1 Closed Newton--Cotes Formulae |
|
|
49 | (1) |
|
4.1.2 Open Newton--Cotes Formulae |
|
|
50 | (1) |
|
4.1.3 Composite Newton--Cotes Rules |
|
|
50 | (1) |
|
4.1.4 Extrapolation Method (Romberg Integration) |
|
|
51 | (2) |
|
4.2 Optimized Sample Points |
|
|
53 | (10) |
|
4.2.1 Clenshaw--Curtis Expressions |
|
|
53 | (3) |
|
4.2.2 Gaussian Integration |
|
|
56 | (5) |
|
|
61 | (2) |
|
5 Systems of Inhomogeneous Linear Equations |
|
|
63 | (34) |
|
5.1 Gaussian Elimination Method |
|
|
64 | (5) |
|
|
68 | (1) |
|
5.1.2 Direct LU Decomposition |
|
|
68 | (1) |
|
|
69 | (5) |
|
5.2.1 QR Decomposition by Orthogonalization |
|
|
69 | (2) |
|
5.2.2 QR Decomposition by Householder Reflections |
|
|
71 | (3) |
|
5.3 Linear Equations with Tridiagonal Matrix |
|
|
74 | (3) |
|
5.4 Cyclic Tridiagonal Systems |
|
|
77 | (1) |
|
5.5 Linear Stationary Iteration |
|
|
78 | (5) |
|
5.5.1 Richardson-Iteration |
|
|
79 | (1) |
|
5.5.2 Matrix Splitting Methods |
|
|
80 | (1) |
|
|
80 | (1) |
|
5.5.4 Gauss-Seidel Method |
|
|
81 | (1) |
|
5.5.5 Damping and Successive Over-relaxation |
|
|
81 | (2) |
|
5.6 Non Stationary Iterative Methods |
|
|
83 | (9) |
|
5.6.1 Krylov Space Methods |
|
|
83 | (1) |
|
5.6.2 Minimization Principle for Symmetric Positive Definite Systems |
|
|
84 | (1) |
|
|
85 | (1) |
|
5.6.4 Conjugate Gradients Method |
|
|
86 | (3) |
|
5.6.5 Non Symmetric Systems |
|
|
89 | (3) |
|
|
92 | (5) |
|
|
93 | (4) |
|
6 Roots and Extremal Points |
|
|
97 | (32) |
|
|
98 | (16) |
|
|
98 | (1) |
|
6.1.2 Regula Falsi (False Position) Method |
|
|
99 | (1) |
|
6.1.3 Newton--Raphson Method |
|
|
100 | (1) |
|
|
101 | (1) |
|
|
101 | (1) |
|
6.1.6 Inverse Interpolation |
|
|
102 | (3) |
|
|
105 | (6) |
|
6.1.8 Multidimensional Root Finding |
|
|
111 | (2) |
|
6.1.9 Quasi-Newton Methods |
|
|
113 | (1) |
|
6.2 Function Minimization |
|
|
114 | (15) |
|
6.2.1 The Ternary Search Method |
|
|
115 | (1) |
|
6.2.2 The Golden Section Search Method (Brent's Method) |
|
|
116 | (5) |
|
6.2.3 Minimization in Multidimensions |
|
|
121 | (1) |
|
6.2.4 Steepest Descent Method |
|
|
122 | (2) |
|
6.2.5 Conjugate Gradient Method |
|
|
124 | (1) |
|
6.2.6 Newton--Raphson Method |
|
|
124 | (1) |
|
6.2.7 Quasi-Newton Methods |
|
|
125 | (1) |
|
|
126 | (3) |
|
|
129 | (16) |
|
7.1 Fourier Integral and Fourier Series |
|
|
129 | (1) |
|
7.2 Discrete Fourier Transformation |
|
|
130 | (6) |
|
7.2.1 Trigonometric Interpolation |
|
|
132 | (2) |
|
7.2.2 Real Valued Functions |
|
|
134 | (1) |
|
7.2.3 Approximate Continuous Fourier Transformation |
|
|
135 | (1) |
|
7.3 Fourier Transform Algorithms |
|
|
136 | (9) |
|
7.3.1 Goertzel's Algorithm |
|
|
136 | (2) |
|
7.3.2 Fast Fourier Transformation |
|
|
138 | (3) |
|
|
141 | (4) |
|
8 Time-Frequency Analysis |
|
|
145 | (42) |
|
8.1 Short Time Fourier Transform (STFT) |
|
|
145 | (7) |
|
8.2 Discrete Short Time Fourier Transform |
|
|
152 | (4) |
|
|
156 | (2) |
|
|
158 | (2) |
|
|
160 | (4) |
|
8.6 Discrete Wavelet Transform and Multiresolution Analysis |
|
|
164 | (14) |
|
8.6.1 Scaling Function and Multiresolution Approximation |
|
|
164 | (7) |
|
8.6.2 Construction of an Orthonormal Wavelet Basis |
|
|
171 | (7) |
|
8.7 Discrete Data and Fast Wavelet Transform |
|
|
178 | (9) |
|
8.7.1 Recursive Wavelet Transformation |
|
|
178 | (2) |
|
8.7.2 Example: Haar Wavelet |
|
|
180 | (1) |
|
8.7.3 Signal Reconstruction |
|
|
181 | (1) |
|
8.7.4 Example: Analysis with Compactly Supported Wavelets |
|
|
182 | (2) |
|
|
184 | (3) |
|
9 Random Numbers and Monte-Carlo Methods |
|
|
187 | (26) |
|
9.1 Some Basic Statistics |
|
|
187 | (9) |
|
9.1.1 Probability Density and Cumulative Probability Distribution |
|
|
187 | (1) |
|
|
188 | (1) |
|
9.1.3 Expectation Values and Moments |
|
|
189 | (1) |
|
|
190 | (1) |
|
9.1.5 Normal Distribution |
|
|
191 | (1) |
|
9.1.6 Multivariate Distributions |
|
|
192 | (1) |
|
9.1.7 Central Limit Theorem |
|
|
193 | (1) |
|
9.1.8 Example: Binomial Distribution |
|
|
194 | (1) |
|
9.1.9 Average of Repeated Measurements |
|
|
195 | (1) |
|
|
196 | (6) |
|
9.2.1 Linear Congruent Mapping (LC) |
|
|
197 | (1) |
|
|
197 | (1) |
|
9.2.3 Multiply with Carry (MWC) |
|
|
198 | (1) |
|
9.2.4 Complementary Multiply with Carry (CMWC) |
|
|
199 | (1) |
|
9.2.5 Random Numbers with Given Distribution |
|
|
199 | (1) |
|
|
200 | (2) |
|
9.3 Monte-Carlo Integration |
|
|
202 | (11) |
|
9.3.1 Numerical Calculation of π |
|
|
202 | (1) |
|
9.3.2 Calculation of an Integral |
|
|
202 | (2) |
|
9.3.3 More General Random Numbers |
|
|
204 | (1) |
|
9.3.4 Configuration Integrals |
|
|
204 | (2) |
|
|
206 | (1) |
|
9.3.6 Importance Sampling |
|
|
207 | (1) |
|
9.3.7 Metropolis Algorithm |
|
|
207 | (3) |
|
|
210 | (3) |
|
|
213 | (22) |
|
|
214 | (1) |
|
|
214 | (3) |
|
10.3 Tridiagonal Matrices |
|
|
217 | (6) |
|
10.3.1 Characteristic Polynomial of a Tridiagonal Matrix |
|
|
217 | (1) |
|
10.3.2 Special Tridiagonal Matrices |
|
|
218 | (5) |
|
10.4 Reduction to a Tridiagonal Matrix |
|
|
223 | (2) |
|
10.5 The Power Iteration Method |
|
|
225 | (3) |
|
|
228 | (2) |
|
|
230 | (1) |
|
|
231 | (3) |
|
10.9 Non-symmetric Matrices |
|
|
234 | (1) |
|
|
234 | (1) |
|
|
235 | (20) |
|
|
236 | (6) |
|
11.1.1 Linear Least Square Fit |
|
|
237 | (2) |
|
11.1.2 Linear Least Square Fit with Orthogonalization |
|
|
239 | (3) |
|
11.2 Singular Value Decomposition |
|
|
242 | (13) |
|
11.2.1 Full Singular Value Decomposition |
|
|
243 | (1) |
|
11.2.2 Reduced Singular Value Decomposition |
|
|
243 | (2) |
|
11.2.3 Low Rank Matrix Approximation |
|
|
245 | (3) |
|
11.2.4 Linear Least Square Fit with Singular Value Decomposition |
|
|
248 | (3) |
|
11.2.5 Singular and Underdetermined Linear Systems of Equations |
|
|
251 | (2) |
|
|
253 | (2) |
|
12 Discretization of Differential Equations |
|
|
255 | (34) |
|
12.1 Classification of Differential Equations |
|
|
256 | (3) |
|
|
259 | (6) |
|
12.2.1 Finite Differences in Time |
|
|
259 | (1) |
|
12.2.2 Stability Analysis |
|
|
260 | (1) |
|
|
261 | (1) |
|
12.2.4 Eigenvector Expansion |
|
|
262 | (3) |
|
|
265 | (5) |
|
12.3.1 Discretization of fluxes |
|
|
268 | (2) |
|
12.4 Weighted Residual Based Methods |
|
|
270 | (3) |
|
12.4.1 Point Collocation Method |
|
|
271 | (1) |
|
|
271 | (1) |
|
12.4.3 Least Squares Method |
|
|
272 | (1) |
|
|
273 | (1) |
|
12.5 Spectral and Pseudo-Spectral Methods |
|
|
273 | (4) |
|
12.5.1 Fourier Pseudo-Spectral Methods |
|
|
273 | (1) |
|
12.5.2 Example: Polynomial Approximation |
|
|
274 | (3) |
|
|
277 | (9) |
|
12.6.1 One-Dimensional Elements |
|
|
277 | (1) |
|
12.6.2 Two-and Three-Dimensional Elements |
|
|
278 | (4) |
|
12.6.3 One-Dimensional Galerkin FEM |
|
|
282 | (4) |
|
12.7 Boundary Element Method |
|
|
286 | (3) |
|
|
289 | (36) |
|
|
290 | (1) |
|
13.2 Time Evolution of the State Vector |
|
|
291 | (1) |
|
13.3 Explicit Forward Euler Method |
|
|
292 | (3) |
|
13.4 Implicit Backward Euler Method |
|
|
295 | (1) |
|
13.5 Improved Euler Methods |
|
|
296 | (2) |
|
13.6 Taylor Series Methods |
|
|
298 | (3) |
|
13.6.1 Nordsieck Predictor-Corrector Method |
|
|
298 | (2) |
|
13.6.2 Gear Predictor-Corrector Methods |
|
|
300 | (1) |
|
13.7 Runge--Kutta Methods |
|
|
301 | (3) |
|
13.7.1 Second Order Runge--Kutta Method |
|
|
302 | (1) |
|
13.7.2 Third Order Runge--Kutta Method |
|
|
302 | (1) |
|
13.7.3 Fourth Order Runge--Kutta Method |
|
|
303 | (1) |
|
13.8 Quality Control and Adaptive Step Size Control |
|
|
304 | (1) |
|
13.9 Extrapolation Methods |
|
|
305 | (1) |
|
13.10 Linear Multistep Methods |
|
|
306 | (4) |
|
13.10.1 Adams--Bashforth Methods |
|
|
306 | (1) |
|
13.10.2 Adams--Moulton Methods |
|
|
307 | (1) |
|
13.10.3 Backward Differentiation (Gear) Methods |
|
|
308 | (1) |
|
13.10.4 Predictor-Corrector Methods |
|
|
309 | (1) |
|
|
310 | (15) |
|
13.11.1 Liouville Equation |
|
|
310 | (1) |
|
13.11.2 Split Operator Approximation |
|
|
311 | (1) |
|
13.11.3 Position Verlet Method |
|
|
312 | (1) |
|
13.11.4 Velocity Verlet Method |
|
|
313 | (1) |
|
13.11.5 Stoermer-Verlet Method |
|
|
313 | (2) |
|
13.11.6 Error Accumulation for the Stoermer-Verlet Method |
|
|
315 | (1) |
|
|
315 | (2) |
|
13.11.8 The Leapfrog Method |
|
|
317 | (1) |
|
|
318 | (7) |
|
Part II Simulation of Classical and Quantum Systems |
|
|
|
|
325 | (26) |
|
14.1 Transformation to a Body Fixed Coordinate System |
|
|
325 | (1) |
|
14.2 Properties of the Rotation Matrix |
|
|
326 | (2) |
|
14.3 Properties of W, Connection with the Vector of Angular Velocity |
|
|
328 | (2) |
|
14.4 Transformation Properties of the Angular Velocity |
|
|
330 | (2) |
|
14.5 Momentum and Angular Momentum |
|
|
332 | (1) |
|
14.6 Equations of Motion of a Rigid Body |
|
|
333 | (1) |
|
|
334 | (1) |
|
14.8 Equations of Motion for a Rotor |
|
|
334 | (1) |
|
|
335 | (2) |
|
14.10 Loss of Orthogonality |
|
|
337 | (1) |
|
|
338 | (3) |
|
14.12 Example: Free Symmetric Rotor |
|
|
341 | (1) |
|
14.13 Kinetic Energy of a Rotor |
|
|
342 | (1) |
|
14.14 Parametrization by Euler Angles |
|
|
342 | (1) |
|
14.15 Cayley--Klein-Parameters, Quaternions, Euler Parameters |
|
|
343 | (3) |
|
14.16 Solving the Equations of Motion with Quaternions |
|
|
346 | (5) |
|
|
347 | (4) |
|
|
351 | (18) |
|
|
352 | (3) |
|
|
355 | (3) |
|
15.2.1 Intramolecular Forces |
|
|
355 | (2) |
|
15.2.2 Intermolecular Interactions |
|
|
357 | (1) |
|
|
358 | (6) |
|
15.4 Normal Mode Analysis |
|
|
364 | (5) |
|
15.4.1 Harmonic Approximation |
|
|
364 | (3) |
|
|
367 | (2) |
|
|
369 | (16) |
|
16.1 Simulation of a Lennard--Jones Fluid |
|
|
370 | (8) |
|
16.1.1 Integration of the Equations of Motion |
|
|
370 | (1) |
|
16.1.2 Boundary Conditions and Average Pressure |
|
|
371 | (1) |
|
16.1.3 Initial Conditions and Average Temperature |
|
|
372 | (1) |
|
16.1.4 Analysis of the Results |
|
|
373 | (5) |
|
16.2 Monte-Carlo Simulation |
|
|
378 | (7) |
|
16.2.1 One-Dimensional Ising Model |
|
|
378 | (2) |
|
16.2.2 Two-Dimensional Ising Model |
|
|
380 | (1) |
|
|
381 | (4) |
|
17 Random Walk and Brownian Motion |
|
|
385 | (14) |
|
17.1 Markovian Discrete Time Models |
|
|
385 | (1) |
|
17.2 Random Walk in One Dimension |
|
|
386 | (3) |
|
17.2.1 Random Walk with Constant Step Size |
|
|
387 | (2) |
|
17.3 The Freely Jointed Chain |
|
|
389 | (6) |
|
17.3.1 Basic Statistic Properties |
|
|
389 | (3) |
|
|
392 | (1) |
|
17.3.3 Hookean Spring Model |
|
|
393 | (2) |
|
|
395 | (4) |
|
|
397 | (2) |
|
|
399 | (28) |
|
|
400 | (11) |
|
18.1.1 Homogeneous Dielectric Medium |
|
|
400 | (2) |
|
18.1.2 Numerical Methods for the Poisson Equation |
|
|
402 | (1) |
|
|
403 | (3) |
|
|
406 | (1) |
|
|
407 | (1) |
|
18.1.6 Solvation Energy of a Charged Sphere |
|
|
408 | (1) |
|
18.1.7 The Shifted Grid Method |
|
|
409 | (2) |
|
18.2 Poisson-Boltzmann Equation |
|
|
411 | (2) |
|
18.2.1 Linearization of the Poisson-Boltzmann Equation |
|
|
412 | (1) |
|
18.2.2 Discretization of the Linearized Poisson Boltzmann Equation |
|
|
413 | (1) |
|
18.3 Boundary Element Method for the Poisson Equation |
|
|
413 | (7) |
|
18.3.1 Integral Equations for the Potential |
|
|
414 | (2) |
|
18.3.2 Calculation of the Boundary Potential |
|
|
416 | (4) |
|
18.4 Boundary Element Method for the Linearized Poisson-Boltzmann Equation |
|
|
420 | (1) |
|
18.5 Electrostatic Interaction Energy (Onsager Model) |
|
|
421 | (6) |
|
18.5.1 Example: Point Charge in a Spherical Cavity |
|
|
422 | (1) |
|
|
423 | (4) |
|
|
427 | (28) |
|
19.1 The Advection Equation |
|
|
427 | (1) |
|
19.2 Advection in One Dimension |
|
|
428 | (23) |
|
19.2.1 Spatial Discretization with Finite Differences |
|
|
430 | (3) |
|
|
433 | (10) |
|
|
443 | (2) |
|
19.2.4 Finite Volume Methods |
|
|
445 | (4) |
|
19.2.5 Taylor--Galerkin Methods |
|
|
449 | (2) |
|
19.3 Advection in More Dimensions |
|
|
451 | (4) |
|
19.3.1 Lax--Wendroff Type Methods |
|
|
452 | (1) |
|
19.3.2 Finite Volume Methods |
|
|
452 | (2) |
|
19.3.3 Dimensional Splitting |
|
|
454 | (1) |
|
|
454 | (1) |
|
|
455 | (24) |
|
|
455 | (3) |
|
20.2 Spatial Discretization in One Dimension |
|
|
458 | (3) |
|
20.3 Solution by an Eigenvector Expansion |
|
|
461 | (2) |
|
20.4 Discretization of Space and Time |
|
|
463 | (1) |
|
20.5 Numerical Integration with a Two-Step Method |
|
|
464 | (3) |
|
20.6 Reduction to a First Order Differential Equation |
|
|
467 | (3) |
|
|
470 | (9) |
|
|
471 | (1) |
|
20.7.2 Lax--Wendroff Scheme |
|
|
472 | (2) |
|
20.7.3 Crank--Nicolson Scheme |
|
|
474 | (3) |
|
|
477 | (2) |
|
|
479 | (14) |
|
21.1 Particle Flux and Concentration Changes |
|
|
479 | (2) |
|
21.2 Diffusion in One Dimension |
|
|
481 | (9) |
|
21.2.1 Explicit Euler (Forward Time Centered Space) Scheme |
|
|
483 | (2) |
|
21.2.2 Implicit Euler (Backward Time Centered Space) Scheme |
|
|
485 | (1) |
|
21.2.3 Crank--Nicolson Method |
|
|
486 | (2) |
|
21.2.4 Error Order Analysis |
|
|
488 | (1) |
|
21.2.5 Finite Element Discretization |
|
|
489 | (1) |
|
21.3 Split-Operator Method for Multidimensions |
|
|
490 | (3) |
|
|
491 | (2) |
|
|
493 | (24) |
|
|
494 | (7) |
|
22.1.1 Fixed Points and Stability |
|
|
494 | (2) |
|
22.1.2 The Ljapunov-Exponent |
|
|
496 | (1) |
|
|
497 | (1) |
|
22.1.4 Fixed Points of the Logistic Map |
|
|
498 | (2) |
|
22.1.5 Bifurcation Diagram |
|
|
500 | (1) |
|
|
501 | (2) |
|
22.2.1 Equilibria and Stability |
|
|
501 | (1) |
|
22.2.2 The Continuous Logistic Model |
|
|
502 | (1) |
|
22.3 Lotka-Volterra Model |
|
|
503 | (2) |
|
22.3.1 Stability Analysis |
|
|
504 | (1) |
|
|
505 | (4) |
|
22.4.1 Holling-Tanner Model |
|
|
506 | (3) |
|
22.5 Reaction-Diffusion Systems |
|
|
509 | (8) |
|
22.5.1 General Properties of Reaction-Diffusion Systems |
|
|
509 | (1) |
|
22.5.2 Chemical Reactions |
|
|
509 | (2) |
|
22.5.3 Diffusive Population Dynamics |
|
|
511 | (1) |
|
22.5.4 Stability Analysis |
|
|
511 | (2) |
|
22.5.5 Lotka Volterra Model with Diffusion |
|
|
513 | (1) |
|
|
514 | (3) |
|
23 Simple Quantum Systems |
|
|
517 | (58) |
|
23.1 Pure and Mixed Quantum States |
|
|
518 | (4) |
|
|
519 | (1) |
|
23.1.2 Density Matrix for an Ensemble of Systems |
|
|
520 | (1) |
|
23.1.3 Time Evolution of the Density Matrix |
|
|
520 | (2) |
|
23.2 Wave Packet Motion in One Dimension |
|
|
522 | (15) |
|
23.2.1 Discretization of the Kinetic Energy |
|
|
523 | (2) |
|
|
525 | (11) |
|
23.2.3 Example: Free Wave Packet Motion |
|
|
536 | (1) |
|
|
537 | (18) |
|
|
540 | (3) |
|
23.3.2 Two-State System with Time Dependent Perturbation |
|
|
543 | (2) |
|
23.3.3 Superexchange Model |
|
|
545 | (3) |
|
23.3.4 Ladder Model for Exponential Decay |
|
|
548 | (3) |
|
23.3.5 Semiclassical Curve Crossing |
|
|
551 | (2) |
|
23.3.6 Landau-Zener Model |
|
|
553 | (2) |
|
23.4 The Dissipative Two-State System |
|
|
555 | (20) |
|
23.4.1 Equations of Motion for a Two-State System |
|
|
555 | (1) |
|
|
556 | (2) |
|
23.4.3 The Spin-1/2 System |
|
|
558 | (1) |
|
23.4.4 Relaxation Processes - The Bloch Equations |
|
|
559 | (2) |
|
23.4.5 The Driven Two-State System |
|
|
561 | (8) |
|
23.4.6 Elementary Qubit Manipulation |
|
|
569 | (3) |
|
|
572 | (3) |
|
24 Variational Methods for Quantum Systems |
|
|
575 | (30) |
|
24.1 Variational Quantum Monte Carlo Simulation of Atomic and Molecular Systems |
|
|
577 | (12) |
|
24.1.1 The Simplest Molecule: H2+ |
|
|
579 | (3) |
|
24.1.2 The Simplest Two-Electron System: The Helium Atom |
|
|
582 | (4) |
|
24.1.3 The Hydrogen Molecule H2 |
|
|
586 | (3) |
|
24.2 Exciton-Phonon Coupling in Molecular Aggregates |
|
|
589 | (16) |
|
|
592 | (6) |
|
|
598 | (3) |
|
|
601 | (4) |
Appendix A Performing the Computer Experiments |
|
605 | (4) |
Appendix B Methods and Algorithms |
|
609 | (8) |
References |
|
617 | (10) |
Index |
|
627 | |