Heath - Scientific Computing, страница 3

. . . . . . . . . . .12.5 Software for FFT . . . . . . . . . . . .12.6 Historical Notes and Further Reading.................................13 Random Numbers and Simulation13.1 Stochastic Simulation . . . . . . . . . . . .13.2 Randomness and Random Numbers . . . .13.3 Random Number Generators . . .

. . . . .13.3.1 Congruential Generators . . . . . . .13.3.2 Fibonacci Generators . . . . . . . .13.3.3 Nonuniform Distributions . . . . . .13.4 Quasi-Random Sequences . . . . . . . . . .13.5 Software for Generating Random Numbers .13.6 Historical Notes and Further Reading . . .........................................................................................................................................................................................................................................................................................................338340341341342343344345349350352355356356356357................................................................................................................................................................................367367368369369372374375376377378378.........385385386386387388388389390390.......................................................................................................................................xiiCONTENTSPrefaceThis book presents a broad overview of numerical methods and software for students andprofessionals in computationally oriented disciplines who need to solve mathematical problems.

It is not a traditional numerical analysis text in that it contains relatively littledetailed analysis of the computational algorithms presented. Instead, I try to convey a general understanding of the techniques available for solving problems in each major category,including proper problem formulation and interpretation of results, but I advocate the useof professionally written mathematical software for obtaining solutions whenever possible.The book is aimed much more at potential users of mathematical software than at potentialcreators of such software.

I hope to make the reader aware of the relevant issues in selectingappropriate methods and software and using them wisely.At the University of Illinois, this book is used as the text for a comprehensive, onesemester course on numerical methods that serves three main purposes:• As a terminal course for senior undergraduates, mainly computer science, mathematics,and engineering majors• As a breadth course for graduate students in computer science who do not intend tospecialize in numerical analysis• As a training course for graduate students in science and engineering who need to usenumerical methods and software in their research.

It is a core course for the interdisciplinary graduate program in Computational Science and Engineering sponsored by theCollege of Engineering.To accommodate this diverse student clientele, the prerequisites for the course and the bookhave been kept to a minimum: basic familiarity with linear algebra, multivariate calculus,and a smattering of differential equations. No prior familiarity with numerical methodsis assumed. The book adopts a fairly sophisticated perspective, however, and the coursemoves at a rather rapid pace in order to cover all of the material, so a reasonable level ofmaturity on the part of the student (or reader) is advisable. Beyond the academic setting,I hope that the book will also be useful as a reference for practicing engineers and scientistswho may need a quick overview of a given computational problem and the methods andxiiixivPREFACEsoftware available for solving it.Although the book emphasizes the use of mathematical software, unlike some othersoftware-oriented texts it does not provide any software, nor does it concentrate on anyspecific software packages, libraries, or environments.

Instead, for each problem categorypointers are provided to specific routines available from publicly accessible repositories,other textbooks, and the major commercial libraries and packages. In many academicand industrial computing environments such software is already installed, and in any casepointers are also provided to public domain software that is freely accessible via the Internet.The computer exercises in the book are not dependent on any specific choice of software orprogramming language.The main elements in the organization of the book are as follows:Chapters: Each chapter of the book covers a major computational problem area.

Thefirst half of the book deals primarily with algebraic problems, whereas the second halftreats analytic problems involving derivatives and integrals. The first two chapters arefundamental to the remainder of the book, but the subsequent chapters can be coveredin various orders according to the instructor’s preference. More specifically, the directinterdependence of chapters is as follows:Chapter2345Depends on11, 21–31, 2, 4Chapter6789Depends on1–51, 21, 2, 5, 71, 2, 4, 5, 7, 8Chapter10111213Depends on1, 2, 4, 5, 7–91, 2, 4–101, 2, 71Thus, the main opportunities for moving material around are to cover Chapters 7 and 12earlier and Chapter 6 later than their appearance in the book. For example, Chapters 3,7, and 12 all involve some type of data fitting, so it might be desirable to cover them asa unit.

As another example, iterative methods for linear systems are covered in Chapter11 on partial differential equations because that is where the most important motivatingexamples come from, but much of this material could be covered immediately followingdirect methods for linear systems in Chapter 2.The entire book can be covered in one semester by moving at a rapid pace or by omittinga few sections. There is also sufficient material for a more leisurely two-quarter course. Aone-quarter course would likely require omitting some chapters.

Chapter 13, on randomnumbers and stochastic simulation, is only peripherally related to the remainder of the bookand is an obvious candidate for omission if time runs short (random number generators areused in a number of exercises throughout the book, however).Examples: Almost every concept and method introduced is illustrated by one or moreexamples. These examples are meant to supplement the relatively terse general discussionand should be read as an essential part of the text.

The examples have been kept as simpleas possible (sometimes at the risk of oversimplification) so that the reader can easily followthem. In my experience, a simple example that is thoroughly understood is usually morehelpful than a more realistic example that is more difficult to follow.Software: The lists of available software for each problem category are meant to bereasonably comprehensive.

I have not attempted to single out the “best” software availablefor a given problem, partly because usually no single package is superior in all respects andxvpartly to allow for the varied software availability and choice of programming language thatmay apply for different readers. All of the recommended software is at least competentlywritten, and some of it is superb.Exercises: The book contains many exercises, which are divided into three classes:• Review questions, which are short-answer questions designed to test basic conceptualunderstanding• Exercises, which require somewhat more thought, longer answers, and possibly some handcomputation• Computer problems, which require some programming and often involve the use of existingsoftware.The review questions are meant for self-testing on the part of the reader. They include somedeliberate repetition to drive home key points and to build confidence in the mastery of thematerial. The longer exercises are meant to be suitable for written homework assignments.Some of these require manual computations with simple examples, whereas others are designed to supply missing details of derivations and proofs omitted from the main text.

Thelatter should be especially useful if the book is used for a more theoretical course. The computer problems provide an opportunity for hands-on experience in using the recommendedsoftware for solving typical problems in each category. Some of these problems are generic,but others are directly related to specific applications in various scientific and engineeringdisciplines.This book provides a fairly comprehensive introduction to scientific computing, butscientific computing is only part of what has become known as computational science.Computational science is a relatively new mode of scientific investigation that includesseveral phases:1. Development of a mathematical model—often expressed as some type of equation—of aphysical phenomenon or system of interest2.

Development of an algorithm to solve the equation numerically3. Implementation of the algorithm in computer software4. Numerical simulation of the physical phenomenon using the computer software5. Representation of the computed results in some comprehensible form, often throughgraphical visualization6. Interpretation and validation of the computed results, which may lead to correction orfurther refinement of the original mathematical model and repetition of the cycle, ifnecessary.As we construe it, scientific computing is primarily concerned with phases 2–4: the development, implementation, and use of numerical algorithms and software.

Although theother phases are equally important in the overall process, their detailed study is beyondthe scope of this book. A serious study of mathematical modeling would require far moredomain-specific knowledge than we assume and far more space than we can accommodate.Fortunately, mathematical modeling is the subject of numerous excellent books, some of ageneral nature and others focusing on specific individual disciplines. Thus, although numerous concrete applications appear in the exercises, our main discussion treats each majorxviPREFACEproblem type in a very general form. Similarly, we measure the accuracy of computedresults with respect to the true solution of a given equation, whereas in practice resultsshould also be validated against the actual physical phenomenon being modeled wheneverpossible.