This book covers many of the traditional areas of numerical analysis as well as topics in software development and methods of Monte Carlo simulations. The book is designed to serve both as a textbook for a course in numerical methods for students in the natural sciences, and as a reference for scientists whose research involves numerical computations and simulations.
The natural sciences have come to rely heavily on computations. The most common type of computation in scientific computing is the evaluation of a mathematical expression. These computations are usually part of a larger computational program. Examples of computations for the evaluation of a mathematical expressions include solution of a system of equations, evaluation of an integral, and solution of a system of differential equations.
Another type of computation in the natural sciences is one that simulates natural phenomena. These computations are often large programs that take as input observed or assumed physical conditions, and produce output that describes or predicts behavior of physical systems.
Computer simulation has become, alongside experimentation and abstract reasoning, a third major tool of science. Simulation is itself a form of experimentation; the experimental units are entities built from computer-generated random numbers. Since Fermi, Ulam, and Pasta discovered energy solitons in metallic lattices in the 1950's using a Maniac~I computer, the use of simulation in the physical sciences has increased to form important subdisciplines. These are the ``computational sciences'', which is to be distinguished from ``computer science'', and include ``computational physics'', ``computational fluid dynamics'', ``computational biology'', and so on.
There are two main distinguishing characteristics of the computational sciences. One is the computational intensity of the methods. Datasets are often huge, but even for datasets of medium size, high performance computers are often required because the computations may be applied repetitively to different subsets of the data. The other characteristic of the computational sciences is the attitude that computation is an instrument of discovery; that is, the role of the computer is not just to store data, to perform computations, and to produce graphs and tables, but additionally to suggest to the scientist alternative models and theories. Graphical displays and visualization methods are usually integral features of the computational sciences.
The student in the computational sciences needs a background in numerical analysis, and it is one of the objectives of this text to provide that background material. Implementation of the numerical methods, as well as general principles of software development, receives attention throughout the text. Two other aspects distinguish this text from others on numerical methods: an emphasis on simulation and Monte Carlo methods and an emphasis on applying the numerical methods to the analysis of observational data.
Because the ordinary rules of arithmetic do not hold for arithmetic operations by the computer, it is important to have a basic understanding of the way data are stored in a computer, and how the computer operates on numeric data. An understanding of computer storage and manipulation of data provides the basis for development of accurate and efficient algorithms. Chapter 1 describes storage formats for numeric data and how numeric operations are performed. The discussion then focuses on algorithms. Accuracy and efficiency of algorithms are the main issues, and methods of insuring accuracy in efficient algorithms are discussed. General approaches such as divide and conquer are described, as well as methods for parallel processing. Good algorithms are useful only if they are implemented in good software, and Chapter~1 continues with considerations of software engineering for producing high-quality software.
Chapter 2 covers the areas of random number generation and Monte Carlo methods. As Monte Carlo simulation becomes more important in the scientific method, and as the simulations become ever larger, it is important to have methods of high quality for generation of random numbers. Surprisingly, many of the random number generators in common use are not very good. Systematic patterns in their output prevent accurate modeling of physical systems. As with most of the following chapters, Chapter 2 discusses relevant software that is widely available. This material on Monte Carlo simulation is presented early in the book because many exercises throughout the book require Monte Carlo studies.
Chapter 3 covers topics in numerical linear algebra. The chapter begins with definitions and properties of vectors, vector spaces, and matrices. The discussion continues with discriptions of computer representations of vectors and matrices, and computer operations with them. Matrix decompositions and solution of systems of linear equations are then discussed. The methods for linear systems form the basis for many computations in scientific applications.
Optimization, generally of nonlinear functions, occurs in many areas of science, including fitting functions to observational data and use of minimum energy principles for describing behavior of systems. Chapter~4 discusses nonlinear systems and methods of optimization of nonlinear functions. Optimization methods for both continuous and discrete systems are discussed.
Chapter 5 discusses estimating functions and smoothing data. The discussion is motivated by the need to fit observational data to scientific models.
Methods for working with multivariate data are covered in Chapter 6. The purpose of these methods is often to find structure in data. ``Structure'' in this sense may mean lower-dimensional relationships in high-dimensional data.
Numerical integration and solution of differential equations are the topics of Chapter 7. The chapter begins with basic discussions of series expansions, and then discusses methods of quadrature, including those that use standard expansions, as well as ones based on Newton-Cotes formulas. Monte Carlo methods for higher dimensional integrals are also discussed.
Chapter 7 describes numerical methods for initial value problems and boundary value problems in ODEs, and then discusses various methods for solution of partial differential equations. The chapter concludes with a discussion of applications of differential equations, including fitting differential equation models using observational data.
The material in two appendices was developed primarily for my own use. Appendix A provides some practical, but ephemeral, information on computing systems and resources. Because I use Fortran 90, S-Plus, Matlab, PV-Wave, and Maple, among other software systems, and I have trouble remembering the syntax, I made some simple examples to keep handy. Those examples were incorporated into Appendix A. Table A.1 also helps to remind me of the syntax.
I have generally used ``standard'' notation. Because of the diversity of topics, however, I found it difficult to be consistent, so I made a list of notation to use in the writing. The reader may also find the list useful. It is given in Appendix B.
The text is appropriate for readers with backgrounds in the natural sciences. It emphasizes the numerical methods, rather than the scientific applications that motivate them. The reader is expected to understand the relevant applications.
The mathematical prerequisites for this text include analysis and linear algebra at a level normally attained through an undergraduate program of study in the natural sciences. The text assumes some familiarity with programming, although if this is lacking, the reader can generally achieve the requisite level by conscientious attention to the programming exercises.
The text does not require any particular software system. It is expected that the reader can program in either Fortran or C, or that the reader will very quickly acquire this ability. Libraries in these languages are very useful, and the text frequently refers to routines in the IMSL Libraries.
The text often uses Matlab and S-Plus in examples, and describes the facilities in those packages for the methods discussed. It would be useful for the reader to have access to one or both of these packages, but other packages such as PV-Wave could serve as well. Some exercises require use of a package that performs symbolic manipulation, such as Maple or Mathematica. Some abilities for symbolic manipulation are also available in Matlab and PV-Wave, using the Maple kernel. Appendix~A provides a brief overview and reference for scientific software.
The text often refers to sources for software, much of which is readily accessible over the Internet.
The exercises comprise an important part of the text. In some cases only paper and pencil are required. In other cases computing is necessary and the solution can be presented as simple computer output. Some exercises require an exposition in a few paragraphs; other exercises require several pages of discussion. In the latter type of exercise, often a computational study must be designed and conducted.
In our graduate program in the computational sciences at George Mason University, there are three basic core areas in which all students must achieve competence. One area is computational science. The words ``science'' and ``sciences'' in the previous two sentences were chosen with some care. The singular form (and the topic of this book) refers to numerical analysis, numerical methods, and software development and usage. The plural form refers to the scientific subdisciplines mentioned above.
In addition to a foundations course in numerical methods and software, we require all students in computational sciences to take a course in scientific databases and a course in scientific and statistical visualization. Material relating to these courses and others in the computational sciences at George Mason University is available over the World Wide Web.
This book could serve as a text for a two-course sequence in scientific computing. I have used the book in a one semester graduate course that has a prerequisite of a course in numerical analysis. I generally cover slightly less than half of the material. I select the material at the ``section'' level, rather than at the ``chapter'' level; that is, I cover some material for each of the chapters. My objective in selecting material is not to duplicate meaterial in the prerequisite numerical course. Most of that material, however, is included in the present text and is reviewed as necessary.
I thank my colleagues in the Institute for Computational Sciences and Informatics for many useful ideas that are incorporated in this book. In particular, I thank John Wallin, with whom I have team-taught the foundations course, for helping to define the content of the course, and consequently, of this book. I also thank Dan Carr, with whom I have team-taught the scientific and statistical visualization course, for helping to provide a broader perspective on computational requirements. I thank the participants in our weekly seminar on computational statistics, in particular, Cliff Sutton, Charles Perry, Arndt Laemmerzahl, and Phil Sage, for enjoyable discussions on computational problems. I also thank the students in CSI 801 during the 1999 and 2000 semesters.
Some portions of this book have appeared in two books in the Springer Statistics and Computing Series, Random Number Generation and Monte Carlo Methods and Numerical Linear Algebra for Applications in Statistics. I thank Springer for permission to incorporate that material in this book.
James Gentle, jgentle@gmu.edu