Nash - Scientific Computing with PCs (523165), страница 9
Текст из файла (страница 9)
However, quadrature methods have beendeveloped that are much more sophisticated either in the integration formula used or in providing anerror estimate for the difference between the true integral and the approximation made to it. Obviouslythe true integral requires an infinite number of infinitesimally small areas. Thus, there is an error madein choosing the step size(3.3.21)(xi - xi-1)as well as accumulated rounding errors in summing the quantities Ai. Furthermore, the trapezoid ruleassumes the function f(x) is linear over the interval xi to xi-1. More complicated rules exist that allowdifferently shaped interpolating formulas to be used but more evaluation may be required.As the integration formula gets more complex and if an error estimate can be calculated, the program todo all the work becomes more complicated and executes more slowly, even when the function is simpleto integrate.
For example, in many regions a function may be smooth and almost linear, while in othersit may change very rapidly, making numerical integration difficult. To handle such problems efficiently,methods have been devised for adaptive quadrature (Lyness, 1970; Kahaner, 1981). The programs involved3: COMPUTATIONAL CAPABILITIES OF PCs21are quite complicated, though Kahaner and Blue (Kahaner, 1981) showed how to do adaptive quadraturein Microsoft BASIC.For multiple integration, summations are in several dimensions. Here each problem may require a specialprogram for its solution, particularly if high precision is needed (Lyness, 1986).
However, for lowprecision integration it is possible to use a Monte-Carlo method. (See Dahlquist and Björck 1974, p. 460.)This method simply treats the integral as a volume in some multi-dimensional space. Using a randomnumber generator, points are generated in this space.
The integral is then the proportion of points "within"the volume of interest multiplied by the volume of the space considered. There are many mechanismsusing symmetry and extrapolation to improve the precision and to reduce the work in such methods. Aprincipal weakness is that reliance on the "randomness" of the points severely undermines the efficacy ofthe method.Numerical Solution of Ordinary Differential EquationsThe numerical methods that have been evolved for solving ordinary differential equations (ODEs) weretransferred successfully to early PCs (Field, 1980).
As with quadrature methods, there are packages ofmethods such as that of Gear (1971) that adapt to the problem at hand. Implementing a large system ofsoftware for ODEs may pose a difficulty that not all the system will fit simultaneously in the memory ofa PC, especially if there are addressing constraints.If we have problems of a single type, then we may be able to use much simpler software. It isstraightforward to program a method such as the Runge-Kutta-Fehlberg (RKF) which will integrate one,or a system of, well-behaved ordinary differential equations over a modest range in the integrand(Kahaner, Moler and Nash S G, 1989). Should an ill-conditioned problem be attempted, however, one mayhave to settle for imprecise results and/or have to use a very small step-size.
A small step-size will makethe integration painfully slow.A common class of "awkward" differential equation describes two or more processes for which the timescale is vastly different. Such stiff equations are the subject of special methods. These may be poorly suitedto general problems.For special cases, such as eigenvalue or boundary value problems, it may be possible to reformulate theproblem so that one solves a set of linear equations or a matrix eigenvalue problem, thereby usingwell-tried linear algebra routines.
Alternatively, various methods transform the integration of an ordinarydifferential equation into a function minimization or root-finding problem.Numerical Solution of Partial Differential EquationsPartial differential equations (PDEs) are generally difficult to solve. We note that the subject of PDEsconstitutes a large proportion of classical mathematical methods for the physical sciences (Morse andFeschbach, 1953; Margenau and Murphy, 1956; Stephenson, 1961). Traditional methods for their numericalsolution involve large computer programs and extensive arrays of working storage. After all, we musttypically try to find a function of several variables (for example x, y, z and t for the three spatialdimensions and time) over a region bounded by some oddly-shaped function.
Furthermore, we usuallyneed approximations not only to the function but also its partial derivatives with respect to one or moreof these variables.Special methods have been devised for many individual problems in order that particular features maybe used to assist in developing a solution. Indeed, one colleague who works in this area believes thedifficulties are such that one must exploit the special features of each problem. Software is developed foreach problem.Clearly, memory limitations will handicap this computational task.
Multigrid methods appear to offer apossibility of compact solution methods (McCormick, 1982). At the time of writing, there are few generalsources of software for solving PDE problems, though this situation is rapidly changing. Interested readers22Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaSCIENTIFIC COMPUTING WITH PCsCopy for:Dr. Dobb’s Journalwill need to keep in touch with developments via the literature or electronic newsletters (e.g., NA Digestfor numerical analysis; send an electronic mail message to na.help@na-net.ornl.gov for information).Integral equations and integro-differential equations are a class of problems with which few workers havemuch experience, including ourselves.
The software seems to be specialized to particular problem typesand as yet confined to research environments.Function Minimization and OptimizationBesides application problems that are naturally formulated as optimizations, many mathematical problemsreduce to such forms. When the number of constraints is very few, the problem is usually called functionminimization. A maximization problem is trivially converted to a minimization by multiplying theobjective by -1. When the number of constraints is large enough that satisfying them is the main focus ofour attention, the problem is then referred to as Mathematical Programming (MP).
This nomenclature isconfusing. It is particularized to problems that have linear, quadratic or nonlinear objective functions (LP,QP or NLP), have integer arguments (Integer Programming) or are associated with sequential decisionprocesses (Dynamic Programming).Various methods have been developed that are compact and easy to implement and use (Nash J C, 1979a,1982b, 1982c, 1982e, 1990d; Nash J C and Walker-Smith 1987).
For special cases, such as the nonlinear leastsquares problem, similar developments have been observed (Nash J C, 1977b, 1990d; Nash J C 1982b).Even when memory space is extremely limited, the Hooke and Jeeves algorithm (Nash J C, 1990d) maybe used that has been implemented on "computers" as small as programmable calculators.Mathematical programming methods have generally been much less amenable to use on personalmachines. (An exception may be made to Dynamic Programming.) The main reason is that it is traditionalto write the linear constraints in a large matrix, called the tableau. For many linear programming problemsof interest, this tableau is large and sparse. As mentioned above, methods for handling sparse matricesare often not easily transported between computers. However, we know of implementations of MINOS(Murtagh and Saunders, 1987) on Macintosh computers and are ourselves installing LANCELOT (Conn,Gould and Toint, 1991) on an MS-DOS machine.
Generally, however, math programming software forlarge-scale problems remains expensive.A related issue concerns how we enter math programming problems of interest into whatever softwarewe wish to use. The volume of data to specify the initial tableau may be a source of difficulty. Therequired data format may be uninformative to the reader. We may prefer to use a modelling languagesuch as GAMS. Once the problem has been specified, it can be important to know if special conditionsapply. There are extremely efficient algorithms for some types of math programming problems (Evans andMinieka, 1992).Root-findingClosely related to optimization, and often sharing similar algorithmic approaches, is the problem ofsolving one or more nonlinear equations, or root-finding.
Such problems are very common analyticproblems in all areas of study. They are frequently very difficult conceptually and numerically becauseof the possibility of multiple solutions and severe scale variations from one region of the variable spaceto another.3.4Component Symbolic ProblemsNot all computations need be numeric.
Computer manipulation of symbols is clearly possible — this isthe basis for all text processing and database management — to the extent of performing mathematicalmanipulations. Until quite recently, this type of computation was largely reserved for mainframes, sincethe particular operations of algebraic manipulation may require large amounts of memory. The 640K3: COMPUTATIONAL CAPABILITIES OF PCs23memory addressing limit of MS-DOS (see Section 7.1) still poses some difficulties, and some availablesoftware for symbolic mathematical manipulation will only run on MS-DOS machines with advancedarchitecture and extra memory (see, for example, a review of Mathematica in PC Magazine, March 31, 1992,vol.
11, no. 6). By contrast, David Stoutemeyer of the University of Hawaii, Honolulu, has for many yearsbeen showing the world how to do such computations on very small machines. His MuMATH andDERIVE contain a respectable spectrum of capabilities in algebra, integration, limits, differentiation andspecial functions, though we still needed to use the extended memory version for some test problems ina recent review (Nash J C, 1995).A typical symbolic problem is the development of analytic expressions for gradients and hessians fordifferential equation and minimization problems.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
