Basic Concepts in Computational Physics

Benjamin A. Stickler · Ewald Schachinger

Basic

Concepts in

Computational

Physics

Second Edition

Basic Concepts in Computational Physics

Benjamin A. Stickler • Ewald Schachinger

Basic Concepts

in Computational Physics

Second Edition

123

Benjamin A. Stickler

Faculty of Physics

University of Duisburg-Essen

Duisburg

Germany

Ewald Schachinger

Institute of Theoretical and Computational

Physics

Graz University of Technology

Graz, Austria

Supplementary material and data can be found on extras.springer.com

ISBN 978-3-319-27263-4 ISBN 978-3-319-27265-8 (eBook)

DOI 10.1007/978-3-319-27265-8

Library of Congress Control Number: 2015959954

© Springer International Publishing Switzerland 2014, 2016

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of

the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microfilms or in any other physical way, and transmission or information

storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology

now known or hereafter developed.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication

does not imply, even in the absence of a specific statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this book

are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or

the editors give a warranty, express or implied, with respect to the material contained herein or for any

errors or omissions that may have been made.

Printed on acid-free paper

This Springer imprint is published by Springer Nature

The registered company is Springer International Publishing AG Switzerland

Preface

Traditionally physics is divided into two fields of activities: theoretical and experi￾mental. As a consequence of the stunning increase in computer power and of the

development of more powerful numerical techniques, a new branch of physics

was established over the last decades: Computational Physics. This new branch

was introduced as a spin-off of what nowadays is commonly called computer

simulations. They play an increasingly important role in physics and in related

sciences as well as in industrial applications and serve two purposes, namely:

• Direct simulation of physical processes such as

ı Molecular dynamics or

ı Monte Carlo simulation of physical processes

• Solution of complex mathematical problems such as

ı Differential equations

ı Minimization problems

ı High-dimensional integrals or sums

This book addresses all these scenarios on a very basic level. It is addressed

to lecturers who will have to teach a basic course/basic courses in Computational

Physics or numerical methods and to students as a companion in their first steps into

the realm of this fascinating field of modern research. Following these intentions

this book was divided into two parts. Part I deals with deterministic methods in

Computational Physics. We discuss, in particular, numerical differentiation and

integration, the treatment of ordinary differential equations, and we present some

notes on the numerics of partial differential equations. Each section within this part

of the book is complemented by numerous applications. Part II of this book provides

an introduction to stochastic methods in Computational Physics. In particular, we

will examine how to generate random numbers following a given distribution,

summarize the basics of stochastics in order to establish the necessary background

to understand techniques like MARKOV-Chain Monte Carlo. Finally, algorithms of

stochastic optimization are discussed. Again, numerous examples out of physics like

v

vi Preface

diffusion processes or the POTTS model are investigated exhaustively. Finally, this

book contains an appendix that augments the main parts of the book with a detailed

discussion of supplementary topics.

This book is not meant to be just a collection of algorithms which can

immediately be applied to various problems which may arise in Computational

Physics. On the contrary, the scope of this book is to provide the reader with a

mathematically well-founded glance behind the scene of Computational Physics.

Thus, particular emphasis is on a clear analysis of the various topics and to even

provide in some cases the necessary means to understand the very background

of these methods. Although there is a barely comprehensible amount of excellent

literature on Computational Physics, most of these books seem to concentrate either

on deterministic methods or on stochastic methods. It is not our goal to compete with

these rather specific works. On the contrary, it is the particular focus of this book to

discuss deterministic methods on par with stochastic methods and to motivate these

methods by concrete examples out of physics and/or engineering.

Nevertheless, a certain overlap with existing literature was unavoidable and we

apologize if we were not able to cite appropriately all existing works which are of

importance and which influenced this book. However, we believe that by putting the

emphasis on an exact mathematical analysis of both, deterministic and stochastic

methods, we created a stimulating presentation of the basic concepts applied in

Computational Physics.

If we assume two basic courses in Computational Physics to be part of the cur￾riculum, nicknamed here Computational Physics 101 and Computational Physics

102, then we would like to suggest to present/study the various topics of this book

according to the following syllabus:

• Computational Physics 101:

– Chapter 1: Some Basic Remarks

– Chapter 2: Numerical Differentiation

– Chapter 3: Numerical Integration

– Chapter 4: The KEPLER Problem

– Chapter 5: Ordinary Differential Equations: Initial Value Problems

– Chapter 6: The Double Pendulum

– Chapter 7: Molecular Dynamics

– Chapter 8: Numerics of Ordinary Differential Equations: Boundary Value

Problems

– Chapter 9: The One-Dimensional Stationary Heat Equation

– Chapter 10: The One-Dimensional Stationary SCHRÖDINGER Equation

– Chapter 12: Pseudo-random Number Generators

• Computational Physics 102:

– Chapter 11: Partial Differential Equations

– Chapter 13: Random Sampling Methods

– Chapter 14: A Brief Introduction to Monte Carlo Methods

– Chapter 15: The ISING Model

Preface vii

– Chapter 16: Some Basics of Stochastic Processes

– Chapter 17: The Random Walk and Diffusion Theory

– Chapter 18: MARKOV-Chain Monte Carlo and the POTTS Model

– Chapter 19: Data Analysis

– Chapter 20: Stochastic Optimization

The various chapters are augmented by problems of medium complexity which

help to understand better the numerical part of the topics discussed within this book.

Although the manuscript has been carefully checked several times, we cannot

exclude that some errors escaped our scrutiny. We apologize in advance and would

highly appreciate reports of potential mistakes or typos.

Throughout the book SI-units are used except stated otherwise.

Graz, Austria Benjamin A. Stickler

July 2015 Ewald Schachinger

Acknowledgments

The authors are grateful to Profs. Dr. C. Lang and Dr. C. Gattringer (Karl-Franzens

Universität, Graz, Austria) and to Profs. Dr. W. von der Linden, Dr. H.-G. Evertz,

and Dr. H. Sormann (Graz University of Technology, Austria). They inspired this

book with their lectures on various topics of Computational Physics, computer sim￾ulation, and numerical analysis. Last but not least, the authors thank Dr. Chris Theis

(CERN) for meticulously reading the manuscript, for pointing out inconsistencies,

and for suggestions to improve the text.

ix

Contents

1 Some Basic Remarks ...................................................... 1

1.1 Motivation ............................................................ 1

1.2 Roundoff Errors...................................................... 6

1.3 Methodological Errors ............................................... 7

1.4 Stability ............................................................... 9

1.5 Concluding Remarks................................................. 12

References.................................................................... 13

Part I Deterministic Methods

2 Numerical Differentiation ................................................. 17

2.1 Introduction .......................................................... 17

2.2 Finite Differences .................................................... 18

2.3 Finite Difference Derivatives ........................................ 20

2.4 A Systematic Approach: The Operator Technique ................. 23

2.5 Concluding Discussion .............................................. 26

Summary ..................................................................... 29

Problems ..................................................................... 29

References.................................................................... 30

3 Numerical Integration ..................................................... 31

3.1 Introduction .......................................................... 31

3.2 Rectangular Rule ..................................................... 32

3.3 Trapezoidal Rule ..................................................... 35

3.4 The SIMPSON Rule .................................................. 37

3.5 General Formulation: The NEWTON-COTES Rules ................ 38

3.6 GAUSS-LEGENDRE Quadrature ..................................... 41

3.7 An Example .......................................................... 46

3.8 Concluding Discussion .............................................. 48

Summary ..................................................................... 50

Problems ..................................................................... 50

References.................................................................... 52

xi

xii Contents

4 The KEPLER Problem ..................................................... 53

4.1 Introduction .......................................................... 53

4.2 Numerical Treatment ................................................ 56

Summary ..................................................................... 60

Problems ..................................................................... 60

References.................................................................... 61

5 Ordinary Differential Equations: Initial Value Problems ............. 63

5.1 Introduction .......................................................... 63

5.2 Simple Integrators.................................................... 65

5.3 RUNGE-KUTTA Methods ............................................ 68

5.4 Hamiltonian Systems: Symplectic Integrators...................... 73

5.5 An Example: The KEPLER Problem, Revisited .................... 76

Summary ..................................................................... 81

Problems ..................................................................... 82

References.................................................................... 82

6 The Double Pendulum ..................................................... 85

6.1 HAMILTON’s Equations ............................................. 85

6.2 Numerical Solution .................................................. 89

6.3 Numerical Analysis of Chaos ....................................... 94

Summary ..................................................................... 99

Problems ..................................................................... 100

References.................................................................... 101

7 Molecular Dynamics ....................................................... 103

7.1 Introduction .......................................................... 103

7.2 Classical Molecular Dynamics ...................................... 104

7.3 Numerical Implementation .......................................... 108

Summary ..................................................................... 113

Problems ..................................................................... 114

References.................................................................... 116

8 Numerics of Ordinary Differential Equations: Boundary

Value Problems ............................................................. 117

8.1 Introduction .......................................................... 117

8.2 Finite Difference Approach.......................................... 119

8.3 Shooting Methods.................................................... 124

Summary ..................................................................... 128

Problems ..................................................................... 129

References.................................................................... 129

9 The One-Dimensional Stationary Heat Equation ....................... 131

9.1 Introduction .......................................................... 131

9.2 Finite Differences .................................................... 132

9.3 A Second Scenario ................................................... 134

Contents xiii

Summary ..................................................................... 137

Problems ..................................................................... 137

References.................................................................... 138

10 The One-Dimensional Stationary SCHRÖDINGER

Equation .................................................................... 139

10.1 Introduction .......................................................... 139

10.2 A Simple Example: The Particle in a Box .......................... 143

10.3 Numerical Solution .................................................. 147

10.4 Another Case ......................................................... 151

Summary ..................................................................... 155

Problems ..................................................................... 155

References.................................................................... 155

11 Partial Differential Equations ............................................ 157

11.1 Introduction .......................................................... 157

11.2 The POISSON Equation .............................................. 158

11.3 The Time-Dependent Heat Equation ................................ 163

11.4 The Wave Equation .................................................. 167

11.5 The Time-Dependent SCHRÖDINGER Equation.................... 170

Summary ..................................................................... 178

Problems ..................................................................... 179

References.................................................................... 179

Part II Stochastic Methods

12 Pseudo-random Number Generators .................................... 183

12.1 Introduction .......................................................... 183

12.2 Different Methods.................................................... 186

12.3 Quality Tests ......................................................... 190

Summary ..................................................................... 194

Problems ..................................................................... 194

References.................................................................... 195

13 Random Sampling Methods .............................................. 197

13.1 Introduction .......................................................... 197

13.2 Inverse Transformation Method ..................................... 200

13.3 Rejection Method .................................................... 202

13.4 Probability Mixing ................................................... 206

Summary ..................................................................... 208

Problems ..................................................................... 208

References.................................................................... 209

14 A Brief Introduction to Monte-Carlo Methods ......................... 211

14.1 Introduction .......................................................... 211

14.2 Monte-Carlo Integration ............................................. 213

14.3 The METROPOLIS Algorithm: An Introduction .................... 219

xiv Contents

Summary ..................................................................... 222

References.................................................................... 223

15 The ISING Model ........................................................... 225

15.1 The Model ............................................................ 225

15.2 Numerics ............................................................. 236

15.3 Selected Results...................................................... 240

Summary ..................................................................... 245

Problems ..................................................................... 245

References.................................................................... 246

16 Some Basics of Stochastic Processes ..................................... 247

16.1 Introduction .......................................................... 247

16.2 Stochastic Processes ................................................. 248

16.3 MARKOV Processes.................................................. 251

16.4 MARKOV-Chains..................................................... 259

16.5 Continuous-Time MARKOV-Chains ................................ 266

Summary ..................................................................... 268

Problems ..................................................................... 269

References.................................................................... 269

17 The Random Walk and Diffusion Theory ............................... 271

17.1 Introduction .......................................................... 271

17.2 The Random Walk ................................................... 273

17.3 The WIENER Process and Brownian Motion ....................... 279

17.4 Generalized Diffusion Models ...................................... 285

Summary ..................................................................... 293

Problems ..................................................................... 294

References.................................................................... 294

18 MARKOV-Chain Monte Carlo and the POTTS Model ................. 297

18.1 Introduction .......................................................... 297

18.2 MARKOV-Chain Monte Carlo Methods ............................ 298

18.3 The POTTS Model.................................................... 302

18.4 Advanced Algorithms for the POTTS Model ....................... 306

Summary ..................................................................... 308

Problems ..................................................................... 309

References.................................................................... 309

19 Data Analysis ............................................................... 311

19.1 Introduction .......................................................... 311

19.2 Calculation of Errors................................................. 311

19.3 Auto-Correlations .................................................... 315

19.4 The Histogram Technique ........................................... 319

Summary ..................................................................... 320

Problems ..................................................................... 321

References.................................................................... 321

Contents xv

20 Stochastic Optimization ................................................... 323

20.1 Introduction .......................................................... 323

20.2 Hill Climbing......................................................... 325

20.3 Simulated Annealing................................................. 327

20.4 Genetic Algorithms .................................................. 334

20.5 Some Further Methods............................................... 336

Summary ..................................................................... 337

Problems ..................................................................... 338

References.................................................................... 338

A The Two-Body Problem ................................................... 341

B Solving Non-linear Equations: The NEWTON Method ................ 347

C Numerical Solution of Linear Systems of Equations ................... 349

C.1 The LU Decomposition .............................................. 350

C.2 The GAUSS-SEIDEL Method ........................................ 353

D Fast Fourier Transform ................................................... 357

E Basics of Probability Theory .............................................. 363

E.1 Classical Definition .................................................. 363

E.2 Random Variables and Moments.................................... 364

E.3 Binomial Distribution and Limit Theorems ........................ 366

E.4 POISSON Distribution and Counting Experiments ................. 367

E.5 Continuous Variables ................................................ 368

E.6 BAYES’ Theorem..................................................... 369

E.7 Normal Distribution.................................................. 370

E.8 Central Limit Theorem .............................................. 370

E.9 Characteristic Function .............................................. 371

E.10 The Correlation Coefficient ......................................... 371

E.11 Stable Distributions .................................................. 373

F Phase Transitions .......................................................... 375

F.1 Some Basics.......................................................... 375

F.2 LANDAU Theory ..................................................... 376

G Fractional Integrals and Derivatives in 1D ............................. 379

H Least Squares Fit ........................................................... 381

H.1 Motivation ............................................................ 381

H.2 Linear Least Squares Fit ............................................. 383

H.3 Nonlinear Least Squares Fit ......................................... 384

xvi Contents

I Deterministic Optimization ............................................... 387

I.1 Introduction .......................................................... 387

I.2 Steepest Descent ..................................................... 388

I.3 Conjugate Gradients ................................................. 390

References.................................................................... 399

Index ............................................................................... 401

Chapter 1

Some Basic Remarks

1.1 Motivation

Computational Physics aims at solving physical problems by means of numerical

methods developed in the field of numerical analysis [1, 2]. According to I. JACQUES

and C. JUDD [3], it is defined as:

Numerical analysis is concerned with the development and analysis of methods for the

numerical solution of practical problems.

Although the term practical problems remained unspecified in this definition, it

is certainly necessary to reflect on ways to find approximate solutions to complex

problems which occur regularly in natural sciences. In fact, in most cases it is not

possible to find analytic solutions and one must rely on good approximations. Let

us give some examples.

Consider the definite integral

Z b

a

dx exp

x2 ; (1.1)

which, for instance, may occur when it is required to calculate the probability that

an event following a normal distribution takes on a value within the interval Œa; b,

where a; b 2 R. In contrast to the much simpler integral

Z b

a

dx exp .x/ D exp .b/ exp .a/ ; (1.2)

the integral (1.1) cannot be solved analytically because there is no elementary

function which differentiates to exp

x2

. Hence, we have to approximate this

integral in such a way that the approximation is accurate enough for our purpose.

This example illustrates that even mathematical expressions which appear quite

© Springer International Publishing Switzerland 2016

B.A. Stickler, E. Schachinger, Basic Concepts in Computational Physics,

DOI 10.1007/978-3-319-27265-8_1

1