Essential Numerical Methods

I H Hutchinson
Massachusetts Institute of Technology

© 2014

The book based on these lectures is A Student's Guide to Numerical Methods
published by Cambridge University Press, 2015. And available from Amazon.com.

For web reading guidance follow this link.
For corrigenda to the book consult this brief file


S.D.G.

Contents

1  Fitting Functions to Data
    1.1  Exact fitting
        1.1.1  Introduction
        1.1.2  Representing an exact fitting function linearly
        1.1.3  Solving for the coefficients
    1.2  Approximate Fitting
        1.2.1  Linear Least Squares
        1.2.2  SVD and the Moore-Penrose Pseudo-inverse
        1.2.3  Smoothing and Regularization
    1.3  Tomographic Image Reconstruction
    1.4  Efficiency and Nonlinearity
2  Ordinary Differential Equations
    2.1  Reduction to first-order
    2.2  Numerical Integration of Initial Value Problem
        2.2.1  Explicit Integration
        2.2.2  Accuracy and Runge-Kutta Schemes
        2.2.3  Stability
    2.3  Multidimensional Stiff Equations: Implicit Schemes
    2.4  Leap-Frog Schemes
3  Two-point Boundary Conditions
    3.1  Examples of Two-Point Problems
    3.2  Shooting
        3.2.1  Solving two-point problems by initial-value iteration
        3.2.2  Bisection
    3.3  Direct Solution
        3.3.1  Second-order finite differences
        3.3.2  Boundary Conditions
    3.4  Conservative Differences, Finite Volumes
4  Partial Differential Equations
    4.1  Examples of Partial Differential Equations
        4.1.1  Fluid Flow
        4.1.2  Diffusion
        4.1.3  Waves
        4.1.4  Electromagnetism
    4.2  Classification of Partial Differential Equations
    4.3  Finite Difference Partial Derivatives
5  Diffusion. Parabolic Partial Differential Equations
    5.1  Diffusion
    5.2  Time Advance Choices and Stability
        5.2.1  Forward Time, Centered Space
        5.2.2  Backward Time, Centered Space. Implicit Scheme.
        5.2.3  Partially implicit, Crank-Nicholson schemes.
    5.3  Implicit Advancing Matrix Method
    5.4  Multiple Space Dimensions
    5.5  Estimating Computational Cost
6  Elliptic Problems and Iterative Matrix Solution
    6.1  Elliptic Equations and Matrix Inversion
    6.2  Convergence Rate
    6.3  Successive Over-Relaxation
    6.4  Iteration and Nonlinear Equations
        6.4.1  Linearization
        6.4.2  Combining linear and nonlinear iteration
7  Fluid Dynamics and Hyperbolic Equations
    7.1  The fluid momentum equation
    7.2  Hyperbolic Equations
    7.3  Finite Differences and Stability
        7.3.1  FTCS is unstable
        7.3.2  Lax-Friedrichs and the CFL condition
        7.3.3  Lax-Wendroff achieves second order accuracy
    7.4  Worked Example: Three-dimensional fluids
8  Boltzmann's Equation and its solution
    8.1  The Distribution Function
    8.2  Conservation of Particles in Phase-Space
    8.3  Solving the Hyperbolic Boltzmann Equation
        8.3.1  Integration along orbits
        8.3.2  Orbits are Characteristics
    8.4  Collision Term
        8.4.1  Self-scattering
        8.4.2  No self-scattering
9  Energy-Resolved Diffusive Transport
    9.1  Collisions of Neutrons
    9.2  Reduction to multigroup diffusion equations
    9.3  Numerical Representation of Multigroup Equations
        9.3.1  Groups
        9.3.2  Steady State Eigenvalue
10  Atomistic and Particle-in-Cell Simulation
    10.1  Atomistic Simulation
        10.1.1  Atomic/Molecular Forces and Potentials
        10.1.2  Computational requirements
    10.2  Particle in Cell Codes
        10.2.1  Boltzmann Equation Pseudoparticle Representation
        10.2.2  Direct Simulation Monte Carlo treatment of gas
        10.2.3  Particle Boundary Conditions
11  Monte Carlo Techniques
    11.1  Probability and Statistics
        11.1.1  Probability and Probability Distribution
        11.1.2  Mean, Variance, Standard Deviation, and Standard Error
    11.2  Computational random selection
    11.3  Flux integration and injection choice.
12  Monte Carlo Radiation Transport
    12.1  Transport and Collisions
        12.1.1  Random walk step length
        12.1.2  Collision type and parameters
        12.1.3  Iteration and New Particles
    12.2  Tracking, Tallying and Statistical Uncertainty
    12.3  Worked Example: Density and Flux Tallies
13  Next Steps
    13.1  Finite Element Methods
    13.2  Discrete Fourier Analysis and Spectral Methods
    13.3  Sparse Matrix Iterative Krylov Solution
    13.4  Fluid Evolution Schemes
        13.4.1  Incompressible fluids and pressure correction
        13.4.2  Nonlinearities, shocks, upwind and limiter differencing
        13.4.3  Turbulence
A  Summary of Matrix Algebra
    A.1  Vector and Matrix Multiplication
    A.2  Determinants
    A.3  Inverses
    A.4  Eigenanalysis
Index

Preface

This book presents what every graduate-level physicist and engineer should know about solving physical problems by computer.
Hardly any research engineer or scientist, whatever their speciality, can do without at least minimal competence in computational and numerical methods. It helps the practitioner greatly to appreciate the big picture of how computational techniques are applied. A book like this that covers the breadth of the methods, with a minimum of fuss, serves the purpose of acquiring the essential knowledge. It is derived from an accelerated short course for entering graduate students in the MIT Department of Nuclear Science and Engineering. That's why some examples used to illustrate the numerical techniques are drawn from Nuclear Science and Engineering. But no specific background nuclear knowledge is required. The mathematical and computational techniques explained are applicable throughout a whole range of engineering and physical science disciplines, because the underlying numerical methods are essentially common.
For so short a course, a great deal of background must be taken for granted, and a lot of relevant topics omitted. The brevity is not a fault though; it is an intention. And while there is an enormous range of material that could be added, I see the deliberate selection as a merit. This approach, I believe, enables a student to read the text sequentially, experience rapid progress, and work to master the content. Of course the present approach contrasts strongly both with comprehensive textbooks and with handbooks. Massive teaching textbooks in addition to providing vastly more detail, cover topics such as standard matrix inversion or decomposition, and elementary quadrature. Those can mostly be taken for granted today, I believe, because of widespread use of mathematical computing systems. Large textbooks also often approach the topics by a round-about set of examples and develop the mathematics in more elementary and drawn out style. Doubtless that approach has merit, but it requires much more time to get to the heart of the matter. Students with good preparation appreciate a more accelerated approach than slogging through many hundreds of pages of textbook. That's especially so, since such textbooks often stop just when the techniques are getting useful for science and engineering, that is, with partial differential equations. This book gets to partial differential equations by the second quarter of its material, and continues into discussion of particle and Monte Carlo methods that are essential for modern computational science and engineering, but rarely treated in general numerical methods text books. There are several excellent numerical methods handbooks; and I often use them. They cover so much material, though, that the reader can and should only dip into it, and use it for reference. Benefitting from such comprehensive treatments requires an understanding of the framework of the subject. The present book aims to provide that framework in as compact a form as is reasonable.
Even having deliberately chosen to keep it short, there are some places where additional explanation or details seem really valuable. To maintain the continuity and brevity of the main text, the additional material has been placed in enrichment sections. Enrichment material can safely be omitted (and is omitted from the lectures and the expectations of the half-term course as I teach it) but its presence gives additional background and allows an interested reader to see, still briefly, where the cited results come from. The main material (excluding the footnotes, enrichment, worked examples, or exercises) of each chapter except the last is designed to be covered in a one and a half hour lecture. But most students then need to spend time reviewing the material of that lecture including the worked examples.
Although the course includes mathematical and computational exercises, which implement the algorithms that are discussed, it does not teach programming. A student who wants to master the material must tackle the exercises. To do so, the student must already have, or develop as they go, sufficient familiarity with a chosen language or computational system. The exercises have been tested with the use of Octave, which is an open source alternative with practically the same syntax and capability as Matlab. Many students will find these systems appropriate, because they have built-in graphics and matrix variable types and routines, but many other language choices are possible. Elementary familiarity with matrices and the terms of linear algebra is presumed. That knowledge is reviewed in highly abbreviated form in the appendix. A principle of the development is that routine matrix algebra and functions are just used; standard direct matrix algorithms are not explained or programmed. However, iterative matrix techniques that are specific to solving differential equations are introduced on the basis of physical intuition as part of the main development, and a brief introduction to modern iterative sparse matrix solution techniques is given in the final chapter.
Many, perhaps most, problems encountered in physical science and engineering are expressed in terms of ordinary or partial differential equations. Familiarity with vector calculus is therefore an absolute prerequisite. As much as is needed of the general theory of partial differential equations is developed within the course, but it is the merest outline. While a serious effort is made to provide self-consistent accuracy of expression and mathematics, no pretence whatever is made to mathematical rigor. There are no theorems here. The purpose is not to teach mathematical proofs; it is to equip students with the mathematical insights and tools to understand and use computational techniques. This outlook permits us to approach topics in a sequence that is intuitive, but would be ruled out by insistence on mathematical rigor.
Understanding how to solve the equations that govern common physical systems comes partly from knowing how they arise. Therefore some are derived from first principles. The majority of students will have seen some comparable derivation in their earlier education. Therefore the derivations here are terse. And while the text is mostly self-contained, the learning curve for students without any prior background in diffusion, fluid flow, collisions, or the kinetic theory of gases, will be rather steep. It may be advisable for them to supplement the treatment with wider reading.
Students that complete this book including the exercises will The idea behind these objectives is that for students who do not specialize in computational engineering or science, this might be the last course they take in numerical techniques.
Though the aim is to provide what every physicist and engineer should know about computational problem solving, it is not to provide everything they should know. Graduate students who undertake computationally based research or other professional activities in science or engineering will certainly eventually need more than is covered here. For them, however, this might be a useful first course, because it rapidly surveys a wide range of algorithms, thus quickly providing a broad perspective on computational science technique.


Acknowledgements   This book owes a great deal to students in the course Essential Numerical Methods, who by their interest, questions, corrections, and occasional puzzlement have helped me identify and explain the key conceptual challenges of learning computational physics and engineering. I am grateful to MIT for support in developing the material of this book; and always to my wife Fran, for her endless love and care, without which this work would not have happened.
HEAD NEXT