Computational Physics: Problem Solving with Computers PDF

Preview

Summary

Rubin H. Landau, Manuel J. Paez, and Cristian C. Bordeianu Computational Physics Problem Solving with Computers 2nd, Revised and Enlarged Edition BICENTENNIAL 1 8 O 7 ®WILEY 2 OO 7 ICINTINNIAL WILEY-VCH Verlag GmbH & Co. KGaA I VI Contents 1 Introduction 1 1.1 Computational Physics and Computati...

Description

Rubin H. Landau, Manuel J. Paez, and Cristian C. Bordeianu

Computational Physics Problem Solving with Computers 2nd, Revised and Enlarged Edition

BICENTENNIAL

1 8 O 7

®WILEY 2 OO 7 ICINTINNIAL

WILEY-VCH Verlag GmbH & Co. KGaA

I VI

Contents

1

Introduction

1.1 1.2

Computational Physics and Computational Science 2 How to Use this Book 3

1

2

Computing Software Basics

2.1 2.2 2.3 2.3.1 2.3.2 2.3.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15

Making Computers Obey 7 Computer Languages 7 Programming Warmup 9 Java-Scanner Implementation 10 C Implementation 22 Fortran Implementation 12 Shells, Editors, and Programs 22 Limited Range and Precision of Numbers 23 Number Representation 23 IEEE Floating Point Numbers 14 Over/Underflows/Exercise 20 Machine Precision 22 Determine Your Machine Precision 23 Structured Program Design 24 Summing Series 26 Numeric Summation 26 Good and Bad Pseudocode 27 Assessment 27

7

3

Errors and Uncertainties in Computations

3.1 3.2 3.3 3.4 3.5

Living with Errors 29 Types of Errors 29 Model for Disaster: Subtractive Cancellation 32 Subtractive Cancellation Exercises 32 Model for Roundoff Error Accumulation 34

29

Computationyal Physics. Problem Solving with Computers (2nd edn).

Rubin H. Landau, Manuel Jose Paez, Cristian C. Bordeianu Copyright © 2007 WILEY-VCH Verlae GmbH & Co. KGaA. Weinheim

VIM I Contents

3.6 3.7 3.8 3.9 3.10 3.11 3.12

Errors in Spherical Bessel Functions (Problem) 35 Numeric Recursion Relations (Method) 35 Implementation and Assessment: Recursion Relations 37 Experimental Error Determination 39 Errors in Algorithms 39 Minimizing the Error 41 Error Assessment 42

4

Object-Oriented Programming: Kinematics ©

4.1 4.2 4.2.1 4.3 4.4 4.5 4.5.1 4.5.2

Problem: Superposition of Motions 45 Theory: Object-Oriented Programming 45 OOP Fundamentals 46 Theory: Newton's Laws, Equation of Motion 46 OOP Method: Class Structure 47 Implementation: Uniform ID Motion, unimld.cpp 48 Uniform Motion in ID, Class UmlD 49 Implementation: Uniform Motion in 2D/Child Um2D, unimot2d.cpp 50 Class Um2D: Uniform Motion in 2D 51 Implementation: Projectile Motion, Child Accm2D, accm2d.cpp 53 Accelerated Motion in Two Directions 54 Assessment: Exploration, shms.cpp 56

4.5.3 4.5.4 4.5.5 4.6 5

Integration

5.1 5.2 5.3 5.4 5.5 5.6 5.6.1 5.6.2 5.7 5.8 5.9

Problem: Integrating a Spectrum 59 Quadrature as Box Counting (Math) 59 Algorithm: Trapezoid Rule 62 Algorithm: Simpson's Rule 63 Integration Error 65 Algorithm: Gaussian Quadrature 66 Mapping Integration Points 68 Gauss Implementation 69 Empirical Error Estimate (Assessment) 72 Experimentation 72 Higher Order Rules 72

59

6

Differentiation

6.1 6.2 6.3 6.4 6.5

Problem 1: Numerical Limits 75 Method: Numeric 75 Forward Difference 75 Central Difference 76 Extrapolated Difference 77

75

45

Contents

6.6 6.7 6.8 6.8.1

Error Analysis 78 Error Analysis (Implementation and Assessment) 79 Second Derivatives 80 Second Derivative Assessment 80

7

Trial and Error Searching

7.1 7.2 7.2.1 7.3 7.3.1 7.3.2

Quantum States in Square Well 81 Trial-and-Error Root Finding via Bisection Algorithm Bisection Algorithm Implementation 84 Newton-Raphson Algorithm 84 Newton-Raphson with Backtracking 86 Newton-Raphson Implementation 87

81

8

Matrix Computing and N-D Newton Raphson

8.1 8.1.1 8.1.2 8.2 8.2.1 8.2.2 8.2.3 8.2.4 8.2.5

Two Masses on a String 90 Statics 91 Multidimensional Newton-Raphson Searching 92 Classes of Matrix Problems 95 Practical Aspects of Matrix Computing 96 Implementation: Scientific Libraries, WWW 200 Exercises for Testing Matrix Calls 206 Matrix Solution of Problem 208 Explorations 208

9

Data Fitting

9.1 9.1.1 9.1.2 9.1.3 9.1.4 9.1.5 9.2 9.2.1 9.3 9.4 9.4.1 9.4.2 9.4.3 9.4.4 9.4.5 9-5 9.5.1 9.5.2

Fitting Experimental Spectrum 222 Lagrange Interpolation 222 Lagrange Implementation and Assessment 224 Explore Extrapolation 226 Cubic Splines 226 Spline Fit of Cross Section 228 Fitting Exponential Decay 220 Theory to Fit 220 Theory: Probability and Statistics 222 Least-Squares Fitting 224 Goodness of Fit 226 Least-Squares Fits Implementation 226 Exponential Decay Fit Assessment 228 Exercise: Fitting Heat Flow 229 Nonlinear Fit of Breit-Wigner to Cross Section 230 Appendix: Calling LAPACK from C 232 Calling LAPACK Fortran from C 234 Compiling C Programs with Fortran Calls 234

89

111

83

IX

X

Contents

10

Deterministic Randomness

10.1 10.1.1 10.1.2 10.1.3

Random Sequences 237 Random-Number Generation 238 Implementation: Random Sequence 240 Assessing Randomness and Uniformity 242

137

11

Monte Carlo Applications

11.1 11.1.1 11.1.2 11.2 11.2.1 11.2.2 11.2.3 11.3 11.4 11.5 11.5.1 11.5.2 11.6 11.6.1 11.6.2 11.6.3 11.7 11.7.1 11.7.2 11.7.3 11.7.4 11.7.5

A Random Walk 245 Simulation 145 Implementation: Random Walk 247 Radioactive Decay 248 Discrete Decay 248 Continuous Decay 250 Simulation 250 Implementation and Visualization 252 Integration by Stone Throwing 252 Integration by Rejection 253 ' Implementation 254 Integration by Mean Value 254 High-Dimensional Integration 255 Multidimensional Monte Carlo 156 Error in N-D Integration 256 Implementation: 10D Monte Carlo Integration 257 Integrating Rapidly Varying Functions 0 257 Variance Reduction © (Method) 257 Importance Sampling 0 258 Implementation: Nonuniform Randomness © 258 von Neumann Rejection 0 262 Nonuniform Assessment 0 263

145

12

Thermodynamic Simulations: Ising Model

12.1 12.2 12.2.1 12.3 12.3.1 12.3.2 12.3.3 12.3.4

Statistical Mechanics 265 An Ising Chain (Model) 266 Analytic Solutions 269 The Metropolis Algorithm 269 Implementation 273 Equilibration 273 Thermodynamic Properties 275 Beyond Nearest Neighbors and ID 277

165

Contents I XI

13

Computer Hardware Basics: Memory and CPU

13.1 13.1.1 13.2 13.2.1 13.2.2

High-Performance Computers 279 Memory Hierarchy 280 The Central Processing Unit 284 CPU Design: RISC 285 Vector Processor 286

179

14

High-Performance Computing: Profiling and Tuning

14.1 14.1.1 14.1.2 14.1.3 14.1.4 14.1.5 14.2 14.2.1 14.2.2 14.2.3

Rules for Optimization 289 Programming for Virtual Memory 290 Optimizing Programs; Java vs. Fortran/C 290 Good, Bad Virtual Memory Use 292 Experimental Effects of Hardware on Performance 293 Java versus Fortran/C 295 Programming for Data Cache 203 Exercise 1: Cache Misses 204 Exercise 2: Cache Flow 204 Exercise 3: Large Matrix Multiplication 205

15

Differential Equation Applications 207 UNIT I. Free Nonlinear Oscillations 207

15.1 15.2 15.3 15A 15.5 15.5.1 15.5.2 15.5.3 15.6 15.6.1 15.7 15.7.1 15.7.2 15.8 15.9 15.10 15.10.1 15.10.2 15.11 15.11.1

189

Nonlinear Oscillator 208 Math: Types of Differential Equations 209 Dynamical Form for ODEs 222 ODE Algorithms 223 Euler'sRule 225 Runge-Kutta Algorithm 225 Assessment: rk2 v. rk4 v. rk45 222 Solution for Nonlinear Oscillations 223 Precision Assessment: Energy Conservation 224 Extensions: Nonlinear Resonances, Beats and Friction 225 Friction: Model and Implementation 225 Resonances and Beats: Model and Implementation 226 Implementation: Inclusion of Time-Dependent Force 226 UNIT II. Balls, not Planets, Fall Out of the Sky 228 Theory: Projectile Motion with Drag 228 Simultaneous Second Order ODEs 229 Assessment 230 Exploration: Planetary Motion 232 Implementation: Planetary Motion 232

XIII Contents 16

Quantum Eigenvalues via ODE Matching

235

16.1 16.1.1 16.1.2 16.1.3 16.1.4

Theory: The Quantum Eigenvalue Problem 236 Model: Nucleon in a Box 236 Algorithm: Eigenvalues via ODE Solver + Search 238 Implementation: ODE Eigenvalues Solver 242 Explorations 243

17

Fourier Analysis of Linear and Nonlinear Signals

17.1 17.2 17.2.1 17.2.2 17.3 17.4 17.5 17.6 17.7 17.8 17.9 17.10 17.11

Harmonics of Nonlinear Oscillations 245 Fourier Analysis 246 Example 1: Sawtooth Function 248 Example 2: Half-Wave Function 249 Summation of Fourier Series(Exercise) 250 Fourier Transforms 250 Discrete Fourier Transform Algorithm (DFT) 252 Aliasing and Antialiasing© 257 DFT for Fourier Series 259 i Assessments 260 DFT of Nonperiodic Functions (Exploration) 262 Model Independent Data Analysis 0 262 Assessment 264

18

Unusual Dynamics of Nonlinear Systems

18.1 18.2 18.2.1 18.2.2 18.3 18.4 18.4.1 18.4.2 18.5 18.6 18.7

The Logistic Map 267 Properties of Nonlinear Maps 269 Fixed Points 269 Period Doubling, Attractors 270 Explicit Mapping Implementation 272 Bifurcation Diagram 272 Implementation 273 Visualization Algorithm: Binning 274 Random Numbers via Logistic Map 275 Feigenbaum Constants 276 Other Maps 276

245

267

19

Differential Chaos in Phase Space

19.1 19.2 19.2.1 19.2.2 19.2.3 19.3 19.3.1

Problem: A Pendulum Becomes Chaotic (Differential Chaos) 277 Equation of Chaotic Pendulum 278 Oscillations of a Free Pendulum 279 Pendulum's "Solution" as Elliptic Integrals 280 Implementation and Test: Free Pendulum 280 Visualization: Phase-Space Orbits 282 Chaos in Phase Space 285

277

Contents XIII

19.3.2 19 A 19.5 19.6 19.7

Assessment in Phase Space 286 Assessment: Fourier Analysis of Chaos 288 Exploration: Bifurcations in Chaotic Pendulum 290 Exploration: Another Type of Phase-Space Plot 292 Further Explorations 292

20

Fractals 293

20.1 20.2 20.2.1 20.2.2 20.3 20.3.1 20.3.2 20.3.3 20.4 20.4.1 20.5 20.5.1 20.5.2 20.5.3 20.6 20.6.1 20.6.2 20.6.3 20.6.4 20.7

Fractional Dimension 293 The Sierpiriski Gasket 294 Implementation 295 Assessing Fractal Dimension 295 Beautiful Plants 297 Self-Affine Connection 297 Barnsley's Fern (fern.c) 298 Self-Affinity in Trees (tree.c) 300 Ballistic Deposition 302 Random Deposition Algorithm (film.c) 302 Length of British Coastline 303 Coastline as Fractal 303 Box Counting Algorithm 304 Coastline Implementation 305 Problem 5: Correlated Growth, Forests, and Films 306 Correlated Ballistic Deposition Algorithm (column.c) 307 Globular Cluster 308 Diffusion-Limited Aggregation Algorithm (dla.c) 308 Fractal Analysis of DLA.Graph 320 Problem 7: Fractal* in Bifurcation Graph 322

21

Parallel Computing 313

21.1 21.1.1 21.2 21.3 21.3.1

Parallel Semantics' 324 Granularity 325 Distributed Memory Programming 326 Parallel Performance 327 Communication Overhead 329

22

Parallel Computing with MPI 321

22.1 22.1.1 22.2 22.2.1 22.2.2 22.2.3

Running on a Beowulf 322 An Alternative: BCCD = Your Cluster on a CD 326 Running MPI 326 MPI under a Queuing System 327 Your First MPI Program 329 MPIheUo.c Explained 330

XIVI Contents

22.2.4 22.2.5 22.2.6 22.2.7 22.3 22.4 22A.I 22.5 22.5.1 22.5.2 22.6 22.7

Send/Receive Messages 332 Receive More Messages 333 Broadcast Messages: MPIpi.c 334 Exercise 336 Parallel Tuning: TuneMPI.c 340 A String Vibrating in Parallel 342 MPIstring.c Exercise 345 Deadlock 346 Nonblocking Communication 347 Collective Communication 347 Supplementary Exercises 348 List of MPI Commands 349

23

Electrostatics Potentials via Finite Differences (PDEs)

23.1 23.2 23.2.1 23.3 23.3.1 23.4 23A.I 23.4.2 23.5 23.6 23.7 23.8

PDE Generalities 352 Electrostatic Potentials 353 Laplace's Elliptic PDE 353 , Fourier Series Solution of PDE 354 Shortcomings of Polynomial Expansions 356 Solution: Finite Difference Method 357 Relaxation and Over-Relaxation 359 Lattice PDE Implementation 362 Assessment via Surface Plot 362 Three Alternate Capacitor Problems 363 Implementation and Assessment 365 Other Geometries and Boundary Conditions 368

24

Heat Flow

24.1 24.2 24.3 24.4 24.4.1 24.5

The Parabolic Heat Equation 369 Solution: Analytic Expansion 370 Solution: Finite Time Stepping (Leap Frog) 372 von Neumann Stability Assessment 373 Implementation 374 Assessment and Visualization 376

369

25

PDE Waves on Strings and Membranes

25.1 25.1.1 25.1.2 25.1.3 25.1.4 25.1.5

The Hyperbolic Wave Equation 379 Solution via Normal Mode Expansion 382 Algorithm: Time Stepping (Leapfrog) 382 Implementation 386 Assessment and Exploration 386 Including Friction (Extension) 388

379

351

Contents

25.1.6 25.2 25.3 25.4 25.5

Variable Tension and Density 390 Realistic ID Wave Exercises 392 Vibrating Membrane (2D Waves) 392 Analytical Solution 394 Numerical Solution for 2D Waves 396

26

Solitons; KdeV and Sine-Gordon

26.1 26.2 26.2.1 26.3 26 A 26.5 26.6 26.7 26.8 26.8.1 26.8.2 26.8.3 26.8.4 26.8.5

Chain of Coupled Pendulums (Theory) 399 Wave Dispersion 400 Continuum Limit, the SGE 402 Analytic SGE Solution 403 Numeric Solution: 2D SGE Solitons 403 2D Soliton Implementation 406 Visualization 408 Shallow Water (KdeV) Solitons 0 409 Theory: The Korteweg-de Vries Equation 420 Analytic Solution: KdeV Solitons 422 Algorithm: KdeV Soliton Solution 422 Implementation: KdeV Solitons 423 Exploration: Two KdeV Solitons Crossing 425 Phase-Space Behavior 425

27

Quantum Wave Packets 0

27.1 27.1.1 27.1.2 27.1.3 27.2 27.2.1

Time-Dependent Schrodinger Equation (Theory) 427 Finite Difference Solution 429 Implementation 429 Visualization and Animation 422 Wave Packets Confined to Other Wells (Exploration) 422 Algorithm for 2D Schrodinger Equation 423

399

417

28

Quantum Paths for Functional Integration

28.1 28.1.1 28.1.2 28.1.3 28.1.4

Feynman's Space-Time Propagation 427 Bound-State Wave Function 432 Lattice Path Integration (Algorithm) 432 Implementation 439 Assessment and Exploration 442

427

29

Quantum Bound States via Integral Equations

29.1 29.1.1 29.1.2 29.1.3

Momentum-Space Schrodinger Equation 444 Integral to Linear Equations 445 Delta-Shell Potential (Model) 447 Implementation 448

443

XV

XVII Contents

29.1 A

Wave Function 449

30

Quantum Scattering via Integral Equations 451

30.1 30.1.1 30.1.2 30.1.3 30.1.4 30.1.5 30.1.6 30.1.7

Lippmann-Schwinger Equation 452 Singular Integrals 452 Numerical Principal Values 453 Reducing Integral to Matrix Equations 454 Solution via Inversion, Elimination 455 Solving ie Integral Equations © 456 Delta-Shell Potential Implementation 456 Scattering Wave Function 458

A

PtPlot: 2D Graphs within Java 461

B

Glossary 467

C

Fortran 95 Codes 479

D

Fortran 77 Codes 513

E

C Language Codes 547

i

References 583 Index 587...