Heath - Scientific Computing (523150), страница 4
Текст из файла (страница 4)
Learning about scientific computing is an important component in the trainingof computational scientists and engineers, but there is more to computational science thanjust numerical methods and software. Accordingly, this book is intended as only a portionof a well-rounded curriculum in computational science, which should also include additionalcomputer skills—e.g., software design principles, data structures, non-numerical algorithms,performance evaluation and tuning, graphics/visualization, and the software tools associated with all of these—as well as much deeper treatment of specific applications in scienceand engineering.The presentation of largely familiar material is inevitably influenced by other treatmentsone has seen.
My initial experience in presenting some of the material in this book wasas a graduate teaching assistant at Stanford University using a prepublication draft ofthe book by Forsythe, Malcolm, and Moler [82]. “FMM” was one of the first softwareoriented textbooks on numerical methods, and its spirit is very much reflected in the currentbook. I later used FMM very successfully in teaching in-house courses for practical-mindedscientists and engineers at Oak Ridge National Laboratory, and more recently I have used itssuccessor, by Kahaner, Moler and Nash [142], in teaching a similar course at the Universityof Illinois.
Readers familiar with those two books will recognize the origin of some aspects ofthe treatment given here. As far as they go, those two books would be difficult to improveupon; in the present book I have incorporated a significant amount of new material whiletrying to preserve the spirit of the originals. In addition to these two obvious sources, Ihave doubtless borrowed many examples and exercises from many other sources over theyears, for which I am grateful.I would like to acknowledge the influence of the mentors who first introduced me to theunexpected charms of numerical computation, Alston Householder and Gene Golub.
I amgrateful for the feedback I have received from students and instructors who have used thelecture notes from which this book evolved and from numerous reviewers, some anonymous,who read and commented on the manuscript before publication. Specifically, I would like toacknowledge the helpful input of Eric Grosse, Jason Hibbeler, Paul Hovland, Linda Kaufman, Thomas Kerkhoven, Cleve Moler, Padma Raghavan, David Richards, Faisal Saied,Paul Saylor, Robert Skeel, and the following reviewers: Alan George, University of Waterloo; Dianne O’Leary, University of Maryland; James M.
Ortega, University of Virginia;John Strikwerda, University of Wisconsin; and Lloyd N. Trefethen, Cornell University. Finally, I deeply appreciate the patience and understanding of my wife, Mona, during thecountless hours spent in writing the original lecture notes and then transforming them intothis book. With great pleasure and gratitude I dedicate the book to her.Michael T. HeathNotationThe notation used in this book is fairly standard and should require little explanation. Wefreely use vector and matrix notation, generally using uppercase bold type for matrices,lowercase bold type for vectors, regular (nonbold) type for scalars, and calligraphic typefor sets.
Iteration and component indices are denoted by subscripts, usually i through n.For example, a vector x and matrix A have entries xi and aij , respectively. On the fewoccasions when both an iteration index and a component index are needed, the iteration(k)is indicated by a parenthesized superscript, as in xi to indicate the ith component of thekth vector in a sequence. Otherwise, xi denotes the ith component of a vector x, whereasxi denotes the ith vector in a sequence.For simplicity, we will deal primarily with real vectors and matrices, although most ofthe theory and algorithms we discuss carry over with little or no change to the complexfield.
The set of real numbers is denoted by R, n-dimensional real Euclidean space by Rn ,and the set of real m × n matrices by Rm×n .The transpose of a vector or matrix is indicated by a superscript T , and the conjugatetranspose by superscript H (for Hermitian). Unless otherwise indicated, all vectors areregarded as column vectors; a row vector is indicated by explicitly transposing a columnvector. For typesetting convenience, the components of a column vector are sometimesindicated by transposing the corresponding row vector, as in x = [ x1 x2 ]T . The innerproduct (also known as dot product or scalar product) of two n-vectors x and y is simplya special case of matrix multiplication and thus is denoted by xT y (or xH y in the complexcase).
Similarly, their outer product, which is an n × n matrix, is denoted by xy T . Theidentity matrix of order n is denoted by In (or just I if the dimension n is clear fromcontext), and its ith column is denoted by ei . A zero matrix is denoted by O, a zerovector by o, and a zero scalar by 0. A diagonal matrix with diagonal entries d1 , . .
. , dn isdenoted by diag(d1 , . . . , dn ). Inequalities between vectors or matrices are to be understoodelementwise.The ordinary derivative of a function f (t) of one variable is denoted by df /dt or by f 0 (t).Partial derivatives of a function of several variables, such as u(x, y), are denoted by ∂u/∂x,for example, or in some contexts by a subscript, as in ux . Notation for gradient vectors andxviixviiiNOTATIONJacobian and Hessian matrices will be introduced as needed. All logarithms are naturallogarithms (base e ≈ 2.718) unless another base is explicitly indicated.The computational cost, or complexity, of numerical algorithms is usually measuredby the number of arithmetic operations required. Traditionally, numerical analysts havecounted only multiplications (and possibly divisions and square roots), because multiplications were usually significantly more expensive than additions or subtractions and becausein most algorithms multiplications tend to be paired with a similar number of additions(for example, in computing the inner product of two vectors).
More recently, the differencein cost between additions and multiplications has largely disappeared.1 Computer vendorsand users like to advertise the highest possible performance, so it is increasingly commonfor every arithmetic operation to be counted. Because certain operation counts are so wellknown using the traditional practice, however, in this book only multiplications are usuallycounted. To clarify the meaning, the phrase “and a similar number of additions” will beadded, or else it will be explicitly stated when both are being counted.In quantifying operation counts and the accuracy of approximations, we will often use“big-oh” notation to indicate the order of magnitude, or dominant term, of a function.
Foran operation count, we are interested in the behavior as the size of the problem, say n,becomes large. We say thatf (n) = O(g(n))(read “f is big-oh of g” or “f is of order g”) if there is a positive constant C such that|f (n)| ≤ C|g(n)|for n sufficiently large. For example,2n3 + 3n2 + n = O(n3 )because as n becomes large, the terms of order lower than n3 become relatively insignificant.For an accuracy estimate, we are interested in the behavior as some quantity h, such as astepsize or mesh spacing, becomes small. We say thatf (h) = O(g(h))if there is a positive constant C such that|f (h)| ≤ C|g(h)|for h sufficiently small.
For example,1= 1 + h + h2 + h3 + · · · = 1 + h + O(h2 )1−hbecause as h becomes small, the omitted terms beyond h2 become relatively insignificant.Note that the two definitions are equivalent if h = 1/n.1Many modern microprocessors can perform a coupled multiplication and addition with a singlemultiply-add instruction.Chapter 1Scientific Computing1.1IntroductionThe subject of this book is traditionally called numerical analysis. Numerical analysis isconcerned with the design and analysis of algorithms for solving mathematical problems thatarise in computational science and engineering.
For this reason, numerical analysis has morerecently become known as scientific computing. Numerical analysis is distinguished frommost other parts of computer science in that it deals with quantities that are continuous,as opposed to discrete. It is concerned with functions and equations whose underlyingvariables—time, distance, velocity, temperature, density, pressure, stress, and the like—arecontinuous in nature.Most of the problems of continuous mathematics (for example, almost any probleminvolving derivatives, integrals, or nonlinearities) cannot be solved, even in principle, in afinite number of steps and thus must be solved by a (theoretically infinite) iterative processthat ultimately converges to a solution. In practice, of course, one does not iterate forever,but only until the answer is approximately correct, “close enough” to the desired resultfor practical purposes.
Thus, one of the most important aspects of scientific computing isfinding rapidly convergent iterative algorithms and assessing the accuracy of the resultingapproximation. If convergence is sufficiently rapid, even some of the problems that can besolved by finite algorithms, such as systems of linear algebraic equations, may in some casesbe better solved by iterative methods, as we will see.Consequently, a second factor that distinguishes numerical analysis is its concern withapproximations and their effects. Many solution techniques involve a whole series of approximations of various types.
Even the arithmetic used is only approximate, for digitalcomputers cannot represent all real numbers exactly. In addition to having the usual properties of good algorithms, such as efficiency, numerical algorithms should also be as reliableand accurate as possible despite the various approximations made along the way.121.1.1CHAPTER 1. SCIENTIFIC COMPUTINGGeneral StrategyIn seeking a solution to a given computational problem, a basic general strategy, whichoccurs throughout this book, is to replace a difficult problem with an easier one that hasthe same solution, or at least a closely related solution.
Examples of this approach include• Replacing infinite processes with finite processes, such as replacing integrals or infiniteseries with finite sums, or derivatives with finite difference quotients• Replacing general matrices with matrices having a simpler form• Replacing complicated functions with simple functions, such as polynomials• Replacing nonlinear problems with linear problems• Replacing differential equations with algebraic equations• Replacing high-order systems with low-order systems• Replacing infinite-dimensional spaces with finite-dimensional spacesFor example, to solve a system of nonlinear differential equations, we might first replace itwith a system of nonlinear algebraic equations, then replace the nonlinear algebraic systemwith a linear algebraic system, then replace the matrix of the linear system with one of aspecial form for which the solution is easy to compute.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
